1.無監(jiān)督學(xué)習(xí)：簡介

聚類算法：第一個無監(jiān)督學(xué)習(xí)算法（無標(biāo)簽的數(shù)據(jù)）

什么是無監(jiān)督學(xué)習(xí)呢？
對比：監(jiān)督學(xué)習(xí)問題指的是，我們有一系列標(biāo)簽，然后用假設(shè)函數(shù)去擬合它，作為對比，在無監(jiān)督學(xué)習(xí)中，我們的數(shù)據(jù)并沒有任何標(biāo)簽，無監(jiān)督學(xué)習(xí)要做的就是將這系列沒有標(biāo)簽的數(shù)據(jù)輸入到算法中，然后我們要讓算法找到隱含在數(shù)據(jù)中的結(jié)構(gòu)。例如聚類算法，當(dāng)然還有一些其他的無監(jiān)督學(xué)習(xí)算法，而不單單是簇。

在這里我們有一系列點，卻沒有標(biāo)簽。因此，我們的訓(xùn)練集可以寫成只有x^(1)， x^(2)….. 一直到x^(m)。我們沒有任何標(biāo)簽y。因此，圖上畫的這些點沒有標(biāo)簽信息。也就是說，在非監(jiān)督學(xué)習(xí)中，我們需要將一系列無標(biāo)簽的訓(xùn)練數(shù)據(jù)，輸入到一個算法中，然后我們告訴這個算法，快去為我們找找這個數(shù)據(jù)的內(nèi)在結(jié)構(gòu)給定數(shù)據(jù)。我們可能需要某種算法幫助我們尋找一種結(jié)構(gòu)。圖上的數(shù)據(jù)看起來可以分成兩個分開的點集（稱為簇），一個能夠找到我圈出的這些點集的算法，就被稱為聚類算法。

這將是我們介紹的第一個非監(jiān)督學(xué)習(xí)算法。當(dāng)然，此后我們還將提到其他類型的非監(jiān)督學(xué)習(xí)算法，它們可以為我們找到其他類型的結(jié)構(gòu)或者其他的一些模式，而不只是簇。

我們將先介紹聚類算法。此后，我們將陸續(xù)介紹其他算法。那么聚類算法一般用來做什么呢？

在這門課程的早些時候，我曾經(jīng)列舉過一些應(yīng)用：比如市場分割。也許你在數(shù)據(jù)庫中存儲了許多客戶的信息，而你希望將他們分成不同的客戶群，這樣你可以對不同類型的客戶分別銷售產(chǎn)品或者分別提供更適合的服務(wù)。社交網(wǎng)絡(luò)分析：事實上有許多研究人員正在研究這樣一些內(nèi)容，他們關(guān)注一群人，關(guān)注社交網(wǎng)絡(luò)，例如Facebook，Google+，或者是其他的一些信息，比如說：你經(jīng)常跟哪些人聯(lián)系，而這些人又經(jīng)常給哪些人發(fā)郵件，由此找到關(guān)系密切的人群。因此，這可能需要另一個聚類算法，你希望用它發(fā)現(xiàn)社交網(wǎng)絡(luò)中關(guān)系密切的朋友。我有一個朋友正在研究這個問題，他希望使用聚類算法來更好的組織計算機集群，或者更好的管理數(shù)據(jù)中心。因為如果你知道數(shù)據(jù)中心中，那些計算機經(jīng)常協(xié)作工作。那么，你可以重新分配資源，重新布局網(wǎng)絡(luò)。由此優(yōu)化數(shù)據(jù)中心，優(yōu)化數(shù)據(jù)通信。

2.K-均值算法

K-均值是最普及的聚類算法，算法接受一個未標(biāo)記的數(shù)據(jù)集，然后將數(shù)據(jù)聚類成不同的組。

K-均值是一個迭代算法，假設(shè)我們想要將數(shù)據(jù)聚類成n個組，其方法為:

第一步是隨機生成兩點（聚類中心（兩類））
K均值算法是一個迭代算法，它會做兩件事，第一件是簇分配，第二個是移動聚類中心。算法內(nèi)部每次內(nèi)循環(huán)的第一步是要進行簇分配，即我要遍歷圖中的每個綠點，然后根據(jù)每個點是與紅色聚類中心更近，還是藍色聚類中心更近，來將每個數(shù)據(jù)點分配給兩個聚類中心之一。

具體來說
1.遍歷你的數(shù)據(jù)集
然后將每個點染成紅色或藍色，這取決于點是更接近藍色聚類中心還是紅色聚類中心。

2.移動聚類中心
將兩個聚類中心，也就是紅色和藍色的叉，將其移動到同色的點的均值處，所以接下來要做的是找到所有紅色的點，求出所有紅色點的平均位置，然后把紅色的聚類中心移動到這里，藍色聚類中心同理。

3.簇分配步驟：
再次檢查所有的無標(biāo)簽數(shù)據(jù)，然后根據(jù)這些點與紅色還是藍色聚類中心更近，將其涂成藍色或者紅色，再重新分配給紅色或者藍色聚類中心。再計算出所有同色點的平均位置，移動紅色/藍色聚類中心。

4.重復(fù)2,3，直到你繼續(xù)進行K均值算法的迭代，聚類中心也不會再改變了，并且點的顏色也不會再改變了。此時，K均值已經(jīng)聚合了。

更規(guī)范的格式寫出K均值算法：

接受兩個輸出：
1.K，表示你想從數(shù)據(jù)中聚類處的簇的個數(shù)
2.一系列無標(biāo)簽的只用x表示的數(shù)據(jù)集（無監(jiān)督學(xué)習(xí)，不需要y值）

同時非監(jiān)督學(xué)習(xí)的K均值算法中，約定x^(i)是一個n維實數(shù)向量。

K均值聚類算法要做的事：

第一步是初始化K個聚類中心，記作u1,u2...uK。
簇分配步驟：(1)迭代，用c(i)表示第1到第K個最接近x^(i)的聚類中心（看看它離哪個聚類中心更近一些），將其染成對應(yīng)的顏色。

(2)移動聚類中心
如果存在一個沒有點的聚類中心會怎么樣？
這時最常見的做法是直接移除那個聚類中心，并最終得到K-1個簇，而不是K個簇。

K均值算法另一個常見應(yīng)用，它可以用來解決分離不佳的簇的問題。

3.優(yōu)化目標(biāo)

之前學(xué)習(xí)的算法都有一個優(yōu)化目標(biāo)函數(shù)或者說代價函數(shù)，K均值算法也有一個優(yōu)化目標(biāo)函數(shù)，或者一個用于最小化的代價函數(shù)。

求解這個優(yōu)化目標(biāo)函數(shù)，一方面是因為這將幫助我們對學(xué)習(xí)算法進行調(diào)試，確保K均值算法運行正確。第二點也是最重要的一點，我們也要運用它幫助K均值算法找到更好的簇，并且避免局部最優(yōu)解。

K均值算法要做的事情就是它要找打c^(i)和ui，也就是能最小化代價函數(shù)J的c和u。這個代價函數(shù)有時也叫失真代價函數(shù)或者K均值算法的失真。

K均值算法實際做的就是，它把兩個系列的變量，把它們分成兩半，第一組是變量c，然后是變量u。首先它會最小化J關(guān)于變量c，接著最小化J關(guān)于變量u，然后保持迭代。

我們可以用這個是真函數(shù)來調(diào)試K均值算法，并幫助我證明K均值是收斂的，并且能夠正常運行。

如何用這個方法幫助K均值找到更好的簇？以及幫助K均值避免局部最優(yōu)解？

4.隨機初始化

如何初始化K均值聚類算法？如何使算法避開局部最優(yōu)解？

我通常用來初始化K均值聚類的方法是隨機挑選K個訓(xùn)練樣本 ，然后設(shè)定u1到uk，讓它們等于這K個樣本。

上圖才是真正的K均值算法初始化的方法，在你實現(xiàn)K均值聚類時，最好使用這種方法。即使隨機狀態(tài)可能會讓你的算法最終可能會收斂得到不同的結(jié)果，這取決于聚類的初始化狀態(tài)，隨機初始化的狀態(tài)不同，K均值最后可能會得到不同的結(jié)果。

具體而言，K均值算法可能會落到局部最優(yōu)，就不能很好的最小化畸變函數(shù)J。如果你擔(dān)心K均值算法落在局部最優(yōu)，如果你想讓K均值算法找到最有可能的聚類，我們可以嘗試多次隨機初始化，并運行K均值算法很多次，以此來保證我們最終能得到一個足夠好的結(jié)果，一個盡可能好的局部或全局最優(yōu)值。

選取運行100次的畸變函數(shù)值中最小的那一個！事實證明，如果你運行K均值算法時，所用的聚類數(shù)相當(dāng)小，那么多次隨機初始化，通常能夠保證你能找到較好的局部最優(yōu)解。保證你能找到更好的聚類。如果K值很大，那么多次使用K均值算法就不會有太大改善。

5.選取聚類數(shù)量

K均值聚類中如何選擇聚類數(shù)量？如何選擇參數(shù)K的值？
比較好的方法仍然是通過觀察可視化的圖，或者通過觀察聚類算法的輸出等，即比較好的方法是手動選擇聚類的數(shù)目。

在無監(jiān)督學(xué)習(xí)中，數(shù)據(jù)沒有標(biāo)簽，因此并不總是有一個明確的答案。因此，用一個自動化的算法來選擇聚類數(shù)量很困難。

肘部法則：
我們所要做的是改變K，也就是聚類總數(shù)，我們先用一個類來聚類，所有的數(shù)據(jù)都會分到一個類中，然后計算代價函數(shù)，即畸變函數(shù)J，把它畫出來，然后我們再用兩個類來跑K均值算法，可能多次隨機初始化，也可能只初始化一次，但是在兩類的情況下，一般畸變值會小一些，然后再畫在這里。再用三個類來跑K均值聚類，很可能得到一個更小的畸變值，再畫回到圖里，再用四類五類去跑均值算法，最終會得到一條曲線顯示隨著聚類數(shù)量的增多，畸變值下降的曲線。
肘部法則就是觀察這個圖，可以看到這條曲線有一條肘部，類比于人的肘部。

這將是一種用來選擇聚類個數(shù)的合理方法。

但也許沒有清晰的拐點！所以它是一種值得嘗試的方法，但是你不能期望它能解決任何問題。

另外一種，如果下游目標(biāo)能給你一個評估標(biāo)準(zhǔn)，那么決定聚類數(shù)量更好的方式是看哪個聚類數(shù)量能更好地應(yīng)用于后續(xù)目的。

這就給了我們另一種方法去選擇聚類數(shù)量，你可以從下游的角度去思考多少個分類能滿足下游要求。

大部分時候聚類數(shù)量K仍然是通過手動、人工輸入或者我們的經(jīng)驗來決定，一種可以嘗試的方法是使用“肘部法則”，但是不能期望每次都有好的效果。選擇聚類數(shù)量，更好的思路是問自己，運行K均值聚類的目的是什么？

聚類參考資料：

降維(Dimensionality Reduction)

6.動機一：數(shù)據(jù)壓縮

第二種無監(jiān)督學(xué)習(xí)問題：降維
你想要使用降維的目的？
一是數(shù)據(jù)壓縮。數(shù)據(jù)壓縮不僅能讓我們對數(shù)據(jù)進行壓縮，使數(shù)據(jù)占用更少的內(nèi)存或硬盤空間，它還能讓我們對學(xué)習(xí)算法進行加速。

什么是降維？
cm和英寸作為兩個特征值，描述的都是物體的長度，存在一定的數(shù)據(jù)冗余。如果我們能把數(shù)據(jù)從二維減少到一維，就能減少這種冗余。

那么我們把數(shù)據(jù)從二維降到一維，究竟意味著什么？

總結(jié)一下：如果允許我們通過投影這條綠線上所有的原始樣本來近似原始的數(shù)據(jù)集，那么我只需要一個數(shù)就能指定點在直線上的位置，即只用一個數(shù)字就可以指定每個訓(xùn)練樣本的位置。
這樣就能把內(nèi)存（數(shù)據(jù)空間）的需求減半。這將允許我們讓學(xué)習(xí)算法運行的更快，同時這也是數(shù)據(jù)壓縮中更有趣的一種應(yīng)用。

從三維降到二維：

這樣的處理過程可以被用于把任何維度的數(shù)據(jù)降到任何想要的維度，例如將1000維的特征降至100維。

正如我們所看到的，最后，這將使我們能夠使我們的一些學(xué)習(xí)算法運行也較晚，但我們會在以后的視頻提到它。

7.動機二：數(shù)據(jù)可視化

降維的第一個應(yīng)用時壓縮數(shù)據(jù)
第二個應(yīng)用就是可視化數(shù)據(jù)

它能很好的幫助我們對學(xué)習(xí)算法進行優(yōu)化，讓我們能更好的了解我們的數(shù)據(jù)，幫助我們更好的對數(shù)據(jù)進行可視化。

如何可視化這些數(shù)據(jù)？
如果你有50維的特征，你很難繪制50維的數(shù)據(jù)。怎么樣才能很好的檢查這些數(shù)據(jù)呢？

只用一個數(shù)字來概述這50個數(shù)字！

但是當(dāng)你觀察降維算法的輸出時，你會發(fā)現(xiàn)z通常不是你所期望的具有物理意義的特征，我們需要去弄清楚這些特征是什么意思？

通過z1和z2能讓你快速捕捉在不同的國家之間兩個維度的變化。

記下來PCA（主成分分析），可以進行降維操作，也可以用來實現(xiàn)我們之前提到的壓縮數(shù)據(jù)。

8.主成分分析問題

降維問題最常用的算法叫做主成分分析（PSA）算法，我們先討論PCA的公式描述（試著用公式準(zhǔn)確的表述PCA的用途）

點到投影點的距離比較?。∷訮CA所做的是：它會找一個低維平面，然后將數(shù)據(jù)投影到上面，使藍色線段的平方最短，這些藍色線段的長度被稱為投影誤差。即它會試圖尋找一個投影平面對數(shù)據(jù)進行投影，使得最小化這個距離。

應(yīng)用PCA之前，通常需要先進行均值歸一化和特征規(guī)范化，使得特征x1,x2，其均值為0并且其數(shù)值在可比較的范圍之內(nèi)。

這也是為什么，主成分分析會選擇紅色的直線而不是洋紅色的直線。

PCA做的就是如果想將數(shù)據(jù)從二維降到一維，我們要試著找一個向量，假設(shè)為u^(i)，使得數(shù)據(jù)投影后，能夠最小化投影誤差的方向。該向量不分正負(fù)，因為它定義的是同一條直線。

對于N維降到K維，這時不只是想找單個向量，來對數(shù)據(jù)進行投影，而是想尋找K個方向，來對數(shù)據(jù)進行投影，來最小化投影誤差。對于三維向量，即想把所有的數(shù)據(jù)點投影到這k個向量展開的線性子空間上。

更正式的，我們想要找出能夠最小化投影距離的方式，來對數(shù)據(jù)進行投影，也就是數(shù)據(jù)點和投影后的點之間的距離。投影誤差就是該點與二維平面上對應(yīng)的投影點之間的距離，最小化平方投影。

有點類似于線性回歸，但PCA不是線性回歸，盡管有一點相似，但是是兩種不相同的算法。線性歸回做的是用所有的x值來預(yù)測y。在PCA中特征值都是一樣的，計算的是同等的特征值x1,x2...xn。

總計一下PCA所做的事：它試圖找到一個低維平面，來對數(shù)據(jù)進行投影，以便最小化投影誤差的平方，以及最小化每個點與投影后的對應(yīng)點之間的距離的平方值。

怎么找到對數(shù)據(jù)投影的這個低維平面？

9.主成分分析算法

自主使用主成分分析算法，并且能夠用PCA對自己的數(shù)據(jù)進行降維。

在使用PCA之前，首先要做的是進行數(shù)據(jù)預(yù)處理，執(zhí)行均值標(biāo)準(zhǔn)化，對數(shù)據(jù)進行特征縮放（分母sj是特征j的一些測量值（最大值減去最小值），或者是一個特征j的標(biāo)準(zhǔn)偏差）

做完P(guān)CA的數(shù)據(jù)預(yù)處理以后，我們要去尋找最小化投影距離的向量了（我們需要想出一個方法計算兩個東西，一個是計算這些向量例如u(1),u(2)，如何來計算這些數(shù)據(jù)？）：

數(shù)學(xué)上的證明很復(fù)雜。
下面是求解過程，我們想要把n維向量降到k維，我們首先要做的是計算協(xié)方差，協(xié)方差用∑表示，不用于數(shù)學(xué)求和公式，它表示的是一個矩陣，如何求解矩陣sigma的特征向量？

Octave要使用命令svd()，svd代表奇異值分解，這是一個更高級的分解算法，高級的線性代數(shù)應(yīng)用。eig()函數(shù)也可以用來做相同的事，但是svd()函數(shù)更穩(wěn)定。協(xié)方差矩陣總是滿足在數(shù)學(xué)上的一個性質(zhì)叫做正定矩陣。其他編程語言中也會有類似的線性代數(shù)庫求解奇異值矩陣，它得到的是一個nn矩陣。而你真正需要的是U矩陣，這個U矩陣也將是一個nn矩陣，這個矩陣的列就是u^(1), u^(2), u^(3)...等。

所以我們想要減少數(shù)據(jù)的維數(shù)從n維降到k維，我們需要做的就是提取前k個向量，即我們想投影到數(shù)據(jù)的方向。

接下來從svd線性代數(shù)的數(shù)值過程中得到了矩陣U S D，我們將用U矩陣的前k個列獲取u(1)-u(k)的向量，一個n*k的矩陣，把它成為Ureduce，這是一類U矩陣被降維的版本，將使用它來對數(shù)據(jù)進行降維。

接下來計算z！z是k為向量，x將是我們數(shù)據(jù)集中的例子。

計算矩陣的正確向量化公式：

沒有數(shù)學(xué)證明，但是因為代碼量比較少，按照這個步驟進行操作，你的降維算法是可以運行的很好的。

PCA算法是嘗試找到一個線或者一個面把數(shù)據(jù)投影到這個面或者線上以便于最小化平方投影誤差。

10.選擇主成分的數(shù)量

怎么選擇PCA算法中的k？

我們希望在平均均方誤差與訓(xùn)練集方差的比例盡可能小的情況下選擇盡可能小的k值。

如果我們希望這個比例小于1%，就意味著原本數(shù)據(jù)的偏差有99%都保留下來了，如果我們選擇保留95%的偏差，便能非常顯著地降低模型中特征的維度了。

我們可以先令k=1，然后進行主要成分分析，獲得Ureduce和z，然后計算比例是否小于1%。如果不是的話再令k=2，如此類推，直到找到可以使得比例小于1%的最小k 值（原因是各個特征之間通常情況存在某種相關(guān)性）。

還有一些更好的方式來選擇k，當(dāng)我們在Octave中調(diào)用“svd”函數(shù)的時候，我們獲得三個參數(shù)：[U, S, V] = svd(sigma)。

其中的S是一個n×n的矩陣，只有對角線上有值，而其它單元都是0，我們可以使用這個矩陣來計算平均均方誤差與訓(xùn)練集方差的比例。

在壓縮過數(shù)據(jù)后，我們可以采用如下方法來近似地獲得原有的特征：

11.重建的壓縮表示

之前把1000維降維到100維的特征向量，如果這是一個壓縮方法，那么對應(yīng)應(yīng)該有一種近似表示，可以把壓縮的數(shù)據(jù)回到原來的表示：

即原始數(shù)據(jù)的重構(gòu)：

12.主成分分析法的應(yīng)用建議

如何選擇K，如何選擇低維表示z的維度？

降低維數(shù)可以提高算法的運算效率，如何具體去做PCA的一些具體建議？

在計算機視覺中，你有100*100個像素點，如果x^(i)特征向量包含10000個像素強度值，這就是10000維的特征向量。對于這種高維的特征向量，運行學(xué)習(xí)算法將變得非常緩慢。如果你要使用10000維的特征向量進行l(wèi)ogistic回歸，或者輸入神經(jīng)網(wǎng)絡(luò)，或支持向量機，或其他你想要的操作，因為數(shù)據(jù)太大，包含10000個數(shù)字，將會是你的算法運行的非常慢，幸運的是，用PCA算法，可以減少數(shù)據(jù)的維度，從而使算法運行的更加高效。首先檢查已經(jīng)被標(biāo)記的訓(xùn)練集，并抽取輸入，抽取出這些x，把y先臨時放到一邊，就得到了一個無標(biāo)簽的訓(xùn)練集。10000維的樣本，僅僅抽取了輸入的向量，接著用PCA得到原始數(shù)據(jù)的低維表示，變成了1000維。這就給了我們一個新的訓(xùn)練集，一個新的訓(xùn)練樣本，可以把這個低維的訓(xùn)練樣本輸入可能是神經(jīng)網(wǎng)絡(luò)或者是回歸算法。對于一個新樣本，也是通過PCA算法進行轉(zhuǎn)換后輸入到學(xué)習(xí)算法中。
最后注意一點：PCA所做的是定義一個從x到z的映射，這個映射只能通過在訓(xùn)練集上運行PCA來定義，具體而言，PCA學(xué)習(xí)的這個映射所做的就是計算一系列參數(shù)，進行特征縮放和均值歸一化，它還計算Ureduce。
但我們應(yīng)該只在訓(xùn)練集上擬合這些參數(shù)，而不是交叉驗證集或者是測試集上。在訓(xùn)練集上找到這些參數(shù)后，你可以把這個映射用在交叉驗證集或者測試集上的其他樣本上。

總結(jié)一下：當(dāng)運行PCA時，僅僅在訓(xùn)練集上的數(shù)據(jù)上運行，不能用在交叉訓(xùn)練集和測試集數(shù)據(jù)上，定義了x到z的映射后，可以將這個映射用在交叉驗證集或者測試集上的其他樣本上。

總而言之，我們討論了PCA算法的以下應(yīng)用：
壓縮數(shù)據(jù)
加速學(xué)習(xí)算法
選擇k：需要保留99%的方差
可視化應(yīng)用

此外，有一種常見的對PCA算法的誤用。（嘗試使用PCA去防止過擬合）
通過減少數(shù)據(jù)維度來解決過擬合不是一種很好的方式，相比于正則化。
它會扔掉一部分特征，轉(zhuǎn)換為無標(biāo)簽數(shù)據(jù)，所以即使99%方差信息被保留，它也有可能扔掉了一些有用信息。

使用PCA的比較好的方式是使用它來提高算法的運算速度，但是使用PCA防止過擬合不是一個好應(yīng)用，應(yīng)該使用正則化來防止過擬合。

濫用問題：

有些人在設(shè)計機器學(xué)習(xí)系統(tǒng)的時候，可能會寫下這樣一個計劃：
建議：應(yīng)該首先考慮使用最原始的數(shù)據(jù)x(i)，只有這么做不能達到目的的情況下，才考慮使用PCA和z(i)，因此使用PCA之間，與其考慮減少數(shù)據(jù)維度，不如考慮放棄PCA這一步，在原始數(shù)據(jù)上直接訓(xùn)練算法往往是更好的。只有當(dāng)你的算法運行速度很慢，或內(nèi)存不足，或硬盤空間太大，因此你需要去壓縮數(shù)據(jù)表示，即有強有力的證據(jù)證明x(i)不能有效的工作再用PCA。