如何找出數(shù)據(jù)集的基礎(chǔ)結(jié)構(gòu)？如何聚類和建立最有效的分組？

如何找出數(shù)據(jù)集的基礎(chǔ)結(jié)構(gòu)？如何聚類和建立最有效的分組？如何在壓縮格式后有效地表達(dá)數(shù)據(jù)？這些都是無監(jiān)督學(xué)習(xí)的目標(biāo)。它是“無監(jiān)督”的——因?yàn)槟闶菑奈唇?jīng)標(biāo)記的數(shù)據(jù)開始的（沒有Y）。

在這篇文章中，我們要探討的無監(jiān)督學(xué)習(xí)任務(wù)主要有兩個(gè)，一是通過相似性把數(shù)據(jù)聚類成組，二是以降低維度的方式壓縮數(shù)據(jù)，同時(shí)保持其結(jié)構(gòu)和可用性。

無監(jiān)督學(xué)習(xí)可能涉及的場(chǎng)景：

某廣告平臺(tái)把美國(guó)消費(fèi)者細(xì)分為有類似購(gòu)物習(xí)慣的較小群體，以便更精準(zhǔn)地向他們投放廣告；

Airbnb將根據(jù)社區(qū)對(duì)住房列表進(jìn)行分組，以便用戶能更簡(jiǎn)便地進(jìn)行查詢；

數(shù)據(jù)科學(xué)研究團(tuán)隊(duì)降低大型數(shù)據(jù)集的維度，以簡(jiǎn)化模型和控制文件大小。

與監(jiān)督學(xué)習(xí)相比，我們無法提前預(yù)測(cè)無監(jiān)督學(xué)習(xí)算法的具體效果，它的“表現(xiàn)”往往是主觀的，只面向特定領(lǐng)域。

聚類

在現(xiàn)實(shí)世界中，聚類的一個(gè)典型案例是市場(chǎng)數(shù)據(jù)提供商Acxiom的系統(tǒng)Personicx，它把美國(guó)家庭分為21個(gè)生活水平群體，又在其下細(xì)分出79類不同群組。也許這看起來并沒有多大用處，但對(duì)于廣告商來說，這些數(shù)據(jù)成了他們?cè)贔acebook上確定廣告投放地區(qū)、時(shí)間段的重要依據(jù)。

Personicx人口聚類

在白皮書中，Acxiom稱系統(tǒng)使用的聚類方法是質(zhì)心聚類和主成分分析，之后我們會(huì)對(duì)它們做簡(jiǎn)要介紹。

你可以想象，這些數(shù)據(jù)精準(zhǔn)地切合了廣告商的需求。對(duì)于迫切希望通過推送廣告來達(dá)到立竿見影效果的廣告商而言，他們重視的內(nèi)容有兩個(gè)：一是了解目標(biāo)消費(fèi)者的群體大?。欢峭ㄟ^針對(duì)消費(fèi)者的人口統(tǒng)計(jì)特征，如興趣愛好和生活方式，挖掘潛在的新客戶。

Acxiom有一個(gè)名為“我的聚類是什么”的小工具，只需回答幾個(gè)簡(jiǎn)單問題，你就能知道算法對(duì)你的分類

讓我們先從聚類算法開始，慢慢了解他們是怎么做的。

k-means聚類

聚類是一種涉及數(shù)據(jù)點(diǎn)分組的機(jī)器學(xué)習(xí)技術(shù)。給定一組數(shù)據(jù)點(diǎn)，我們可以用聚類算法將每個(gè)數(shù)據(jù)點(diǎn)到分類到圖像中的特定組中。理論上，同一組中的數(shù)據(jù)點(diǎn)應(yīng)具有相似的屬性和特征，而不同組中的數(shù)據(jù)點(diǎn)的屬性和特征則應(yīng)高度不同。

通過k-means算法，我們能把目標(biāo)數(shù)據(jù)點(diǎn)聚類為k個(gè)簇。k值越大，簇越少，每一簇包含的數(shù)據(jù)點(diǎn)就越多；k值越小，簇越多，每一簇包含的數(shù)據(jù)點(diǎn)就越少。

該算法的輸出是一堆打好了“標(biāo)簽”的數(shù)據(jù)點(diǎn)，每個(gè)標(biāo)簽指向數(shù)據(jù)點(diǎn)所屬的k簇。進(jìn)行聚類時(shí)，算法會(huì)根據(jù)k值為數(shù)據(jù)定義k個(gè)聚類質(zhì)心點(diǎn)，這些質(zhì)心就像是每個(gè)簇的核心，它們不斷“捕捉”最接近自己的點(diǎn)并把它們添加進(jìn)聚類中。

如果這還不夠形象，那你也可以把它們想成派對(duì)舞會(huì)上出現(xiàn)的那些充滿魅力的人，他們瞬間就能引起身邊人的關(guān)注。如果這樣的人只有一個(gè)，那全場(chǎng)人都會(huì)聚集在他身邊；如果有很多個(gè)，那舞會(huì)上就會(huì)形成許多較小的活動(dòng)團(tuán)體。

以下是k-means聚類的簡(jiǎn)要步驟：

1. 定義k個(gè)質(zhì)心。隨機(jī)初始化k個(gè)質(zhì)心；

2. 為質(zhì)心找到最接近它的數(shù)據(jù)點(diǎn)并構(gòu)建簇。將每個(gè)數(shù)據(jù)點(diǎn)分配給k個(gè)質(zhì)心中的一個(gè)，分配依據(jù)是數(shù)據(jù)點(diǎn)和質(zhì)心的接近程度，也就是歐氏距離平方和最小。

3. 更新質(zhì)心位置，將它移到更新后簇的中心。計(jì)算簇中所有點(diǎn)的平均位置，這個(gè)得出的新向量就是質(zhì)心的新位置。

k-means聚類的一個(gè)實(shí)際應(yīng)用是對(duì)手寫數(shù)字進(jìn)行分類。假設(shè)我們有一些黑白的數(shù)字圖像，圖像的像素為64 × 64，每個(gè)像素代表一個(gè)維度，那么這些圖像就有64 × 64 = 4,096個(gè)維度。在這個(gè)4,096維的空間中，k-means算法能把所有聚集緊密的像素點(diǎn)聚類成一個(gè)簇，假設(shè)它們同屬于一個(gè)數(shù)字。實(shí)踐證明，這種做法在數(shù)字識(shí)別上取得了非常好的結(jié)果。

層次聚類

層次聚類和常規(guī)的聚類算法大體相似，它的不同之處在于它聚類的簇具有層次結(jié)構(gòu)。這對(duì)于一些有不同靈活性需求的任務(wù)來說很有用，如想象一下Amazon的網(wǎng)上商城，它的主頁(yè)上有很多分組的商品，通過導(dǎo)航欄，我們能找到目標(biāo)商品所屬的大類，之后再是更細(xì)分的、更具體的小類。對(duì)于一些項(xiàng)目集群，像這樣逐層提高數(shù)據(jù)顆粒密度是有價(jià)值的。

就算法的輸出而言，除了聚類成各個(gè)子集，層次聚類的一個(gè)優(yōu)點(diǎn)是可以呈現(xiàn)一整棵樹，并由你自行選擇要聚類成什么效果，比如簇的數(shù)量。

以下是參差聚類的簡(jiǎn)要步驟：

1. 定義N個(gè)簇，每個(gè)簇包含1個(gè)數(shù)據(jù)點(diǎn)；

2. 合并彼此最接近的兩個(gè)簇，現(xiàn)在我們就有N-1個(gè)簇；

3. 重新計(jì)算各簇之間的距離。對(duì)于計(jì)算距離，我們有多種方法，其中一種是將兩個(gè)簇之間的距離視為他們各自數(shù)據(jù)點(diǎn)之間的平均距離。

4. 重復(fù)步驟2和3，直到最后獲得一個(gè)包含所有數(shù)據(jù)點(diǎn)的簇。這時(shí)我們得到了一棵樹，如下圖所示。

5. 選取多個(gè)簇并在樹狀圖上繪制一條水平線。例：如果我們想要k = 2個(gè)簇，那就應(yīng)該在distance = 20000的位置畫一條線，這時(shí)我們就能得到一個(gè)包含數(shù)據(jù)點(diǎn)8、9、11、16的簇以及另一個(gè)簇。簇的數(shù)量等于水平線和樹狀圖的交點(diǎn)數(shù)。

降維

降維聽起來和壓縮差不多。它是為了盡量減少數(shù)據(jù)的復(fù)雜性，同時(shí)保持盡可能多的相關(guān)結(jié)構(gòu)。如果我們有一張128 × 128 × 3的圖像（長(zhǎng)×寬×RGB），它的數(shù)據(jù)維度就是49,152。這時(shí)，如果我們能在不破壞圖象原有內(nèi)容的前提下降低圖像所在空間的維度，這對(duì)于后續(xù)計(jì)算是十分有幫助的。

讓我們先通過實(shí)踐看看兩種用于降維的主要方法：主成分分析和奇異值分解。

主成分分析（PCA）

在開始講解前，我們先來做一個(gè)線性代數(shù)小復(fù)習(xí)——向量空間和基。

在一個(gè)普通的平面坐標(biāo)中，原點(diǎn)O是(0, 0)，基向量i為(1, 0)，j為(0, 1)。但事實(shí)證明，我們可以選擇一個(gè)完全不同的基，比如把i'=(2, 1)和j'=(1, 2)作為基向量，這就成了另一個(gè)坐標(biāo)系。如果你有耐心，你可以計(jì)算出原來iOj坐標(biāo)系上的(2, 2)到i'Oj'上會(huì)變成(6, 6)。

這樣做的意義在于我們能改變向量空間的基，想象更高維的空間，比如5萬(wàn)維。選擇一個(gè)基，挑選出其中最重要的200個(gè)基向量，我們把這些向量稱之為“主成分”。這之后，你挑出的向量子集就能構(gòu)成一個(gè)新的向量空間，它的維度比原來的更低，但保留了大部分?jǐn)?shù)據(jù)復(fù)雜性。

選擇最重要的主成分，考察它保留了多少差異性，然后按照這個(gè)指標(biāo)進(jìn)行排序。

PCA的另一個(gè)用處在于降低數(shù)據(jù)文件大小。經(jīng)過重新映射后，原本的數(shù)據(jù)空間會(huì)被壓縮至低維，更有利于之后的計(jì)算。

擴(kuò)展閱讀：Diffusion Mapping and PCA on the WikiLeaks Cable Database

地址：http://mou3amalet.com/cargocollective/675_xuesabri-final.pdf

奇異值分解（SVD）

讓我們將數(shù)據(jù)表示為一個(gè)較大的A = m × n的矩陣。SVD是一種計(jì)算，它允許我們將該大矩陣分解為3個(gè)較小矩陣（U = m × r，對(duì)角矩陣Σ= r × r，以及V = r × n，其中r是一個(gè)小數(shù)）的乘積。

以下是一個(gè)直觀的例子。

r*r對(duì)角矩陣Σ中的值被稱為奇異值。它們的神奇之處在于可以用來壓縮原始矩陣。如果我們?cè)谠季仃嘦和V中刪除最小的20%奇異值的相關(guān)列，矩陣會(huì)縮小很多，但仍能很好地表示底層矩陣。為了更準(zhǔn)確地展示它的效果，我們可以來看看這條狗：

首先，如果我們按照量級(jí)對(duì)奇異值（矩陣Σ的值）進(jìn)行排序，則前50個(gè)奇異值包含整個(gè)矩陣Σ85％的量值。

因此我們可以把矩陣Σ中剩下的250個(gè)值舍去，也就是設(shè)置為0，獲得一個(gè)“rank 50”的版本。在下圖中，我們分別列舉了200、100、50、30、20、10和3的狗，可以看出，隨著圖片空間逐漸變小，它的清晰度也不斷下降，但就肉眼的觀察情況看，“rank 30”的圖像還是表現(xiàn)出了很多接近原圖的特征。我們可以計(jì)算這一過程中算法壓縮了多少空間：原始圖像矩陣有305 × 275 = 83,875個(gè)值；“rank 30”的狗則只有305 × 30 + 30 + 30 × 275 = 17,430個(gè)值（要算上矩陣U和V乘以0的量）——幾乎是原圖的五分之一。

實(shí)戰(zhàn)演練和進(jìn)階閱讀

k-means聚類

嘗試可視化聚類過程，以建立對(duì)算法工作原理更直觀的理解。你也可以參考用k-means聚類手寫數(shù)字的開源項(xiàng)目，并學(xué)習(xí)坐著列出的各類在線教程。