超級乾貨：一文詳解聚類和降維

本文長度為3500字，建議閱讀6分鐘

本文對無監督學習的聚類和降維演算法進行介紹，其中包括 K 均值聚類、層次聚類、主成分分析（PCA）和奇異值分解（SVD）。

我們可以怎樣發現一個數據集的底層結構？我們可以怎樣最有用地對其進行歸納和分組？我們可以怎樣以一種壓縮格式有效地表徵數據？這都是無監督學習的目標，之所以稱之為「無監督」，是因為這是從無標籤的數據開始學習的。

我們將在這裡探索的兩種無監督學習任務是：

將數據按相似度聚類（clustering）成不同的分組；

降維（reducing dimensionality），以便在保留數據結構和有用性的同時對數據進行壓縮。

無監督學習方法可能有用的案例：

一家廣告平台需要根據相似的人口學特徵和購買習慣將美國人口分成不同的小組，以便廣告客戶可以通過有關聯的廣告接觸到他們的目標客戶。

Airbnb 需要將自己的房屋清單分組成不同的社區，以便用戶能更輕鬆地查閱這些清單。

一個數據科學團隊需要降低一個大型數據集的維度的數量，以便簡化建模和降低文件大小。

和監督學習不同，要找到評價無監督學習演算法優劣的指標可並不輕鬆。「表現水平」往往是主觀的，而且因領域不同而各不相同。

聚類

聚類的一個有趣的真實應用案例是營銷數據提供商 Acxiom 的人生階段聚類系統 Personicx。這項服務將美國家庭分成了 70 個不同的聚類，它們分屬於 21 個人生階段分組，可以被廣告主用於投放定向 Facebook 廣告、陳列式廣告和直郵廣告等。

Personix 人口學特徵聚類的一部分

他們的白皮書表明他們使用了重心聚類（centroid clustering）和主成分分析，這兩種技術在這一節都有覆蓋。

你可以想像，如果廣告主想（1）理解他們已有的客戶群，（2）通過相關的人口學特徵、興趣和生活習慣向潛在新客戶投放定向廣告以便高效利用廣告開支，那麼這些聚類將對他們非常有用。

實際上，你只需要在 Acxiom 的「我屬於哪個聚類？」工具中回答幾個簡單問題，你就能知道你個人屬於哪個聚類，體驗地址：

https://isapps.acxiom.com/personicx/personicx.aspx

讓我們了解幾種聚類方法，看看這樣的任務是如何完成的。

1. K 均值聚類

「重心之賽有 k 個魔戒，在那之上，是希望的力量。」

聚類的目標是為數據點分組，使得不同聚類中的數據點是不相似的，同一聚類中的數據點則是類似的。

使用 K 均值聚類，我們希望將我們的數據點聚類為 K 組。K 更大時，創造的分組就更小，就有更多粒度；K 更小時，則分組就更大，粒度更少。

該演算法的輸出是一組「標籤」，這些標籤將每個數據點都分配到了 K 組中的一組。在 K 均值聚類中，這些組的定義方式是為每個組創造一個重心（centroid）。這些重心就像是聚類的心臟，它們可以「捕獲」離自己最近的點並將其加入到自己的聚類中。

你可以把這些重心看作是派對上成為關注焦點的人，他們就像是有磁性一樣。如果只有一個這樣的人，每個人都會圍繞在他周圍；如果有很多這樣的人，就會形成很多更小一點的活動中心。

K 均值聚類的步驟如下：

定義 K 個重心。一開始這些重心是隨機的（也有一些更加有效的用於初始化重心的演算法）

尋找最近的重心並且更新聚類分配。將每個數據點都分配給這 K 個聚類中的一個。每個數據點都被分配給離它們最近的重心的聚類。這裡的「接近程度」的度量是一個超參數——通常是歐幾里得距離（Euclidean distance）。

將重心移動到它們的聚類的中心。每個聚類的重心的新位置是通過計算該聚類中所有數據點的平均位置得到的。

重複第 2 和 3 步，直到每次迭代時重心的位置不再顯著變化（即直到該演算法收斂）。

這就是 K 均值聚類工作方式的精簡版！該演算法的可視化演示可在這裡查看：

https://www.naftaliharris.com/blog/visualizing-k-means-clustering/

你可以像讀漫畫一樣理解。平面上的每個數據點都根據離自己最近的重心加了顏色。你可以看到這些重心（更大一點的藍點、紅點和綠點）一開始是隨機的，然後很快進行了調整，得到了它們各自的聚類。

K 均值聚類的另一個真實應用是分類手寫數字。假設我們有用像素亮度的長向量表示的數字的圖像。假設這些圖像是黑白兩色的，大小為 64×64 像素。每個像素代表一個維度。那麼這些圖像就生活在一個有 64×64=4096 個維度的世界裡。在這個 4096 維的世界裡，K 均值聚類讓我們可以按接近程度對這些圖像分組，並且假設這些靠得很近的圖像都是同一個數字。這種演算法可以在數字識別上得到相當好的結果，參閱：

//ieeexplore.ieee.org/document/6755106/?reload=true

2. 層次聚類

「讓我們把 100 萬個選項變成 7 個選項。或者 5 個。或者 20 個？呃，我們可以過會兒決定。」

層次聚類類似於常規的聚類，只是你的目標是構建一個聚類的層次。如果你最終的聚類數量不確定，那這種方法會非常有用。比如說，假設要給 Etsy 或亞馬遜等網路市場上的項目分組。在主頁上，你只需要少量大組方便導航，但隨著你的分類越來越特定，你需要的粒度水平也越來越大，即區別更加明顯的項聚類。

在演算法的輸出方面，除了聚類分配，你也需要構建一個很好的樹結構，以幫助你了解這些聚類之間的層次結構。然後你可以從這個樹中選擇你希望得到的聚類數量。

層次聚類的步驟如下：

首先從 N 個聚類開始，每個數據點一個聚類。

將彼此靠得最近的兩個聚類融合為一個。現在你有 N-1 個聚類。

重新計算這些聚類之間的距離。有很多可以辦到這件事的方法（參見這個教程了解更多細節：

https://home.deib.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html）。

其中一種方法（平均連接聚類，average-linkage clustering）是將兩個聚類之間的距離看作是它們各自元素之間所有距離的平均。

重複第 2 和 3 步，直到你得到包含 N 個數據點的一個聚類。你就會得到如下圖所示的樹（也被稱為樹狀圖））。

選擇一個聚類數量，然後在這個樹狀圖中劃一條水平線。比如說，如果你想要 K=2 個聚類，你應該在距離大約為 20000 的位置畫一條水平線，你會得到一個包含數據點 8、9、11、16 的聚類和包含其它數據點的另一個聚類。一般而言，你得到的聚類的數量就是水平線與樹狀圖中的豎直線的交叉點的數量。

更多有關層次聚類的詳細信息，可參閱這個視頻：

https://www.youtube.com/watch?v=OcoE7JlbXvY

降維

「對於那些該砍去的非精髓部分的態度，並不是每天增加吸收，而是每日盡量排減。」——李小龍

降維看上去很像壓縮。這是為了在儘可能保存相關的結構的同時降低數據的複雜度。如果你有一張簡單的 128×128×3 像素的圖像（長×寬×RGB 值），那麼數據就有 49152 維。如果你可以給這個圖像空間降維，同時又不毀掉圖像中太多有意義的內容，那麼你就很好地執行了降維。

我們將了解兩種實際中很常用的降維技術：主成分分析和奇異值分解。

1. 主成分分析（PCA）

首先，了解一點線性代數知識——看看空間（space）和基（base）。

你應該知道由原點 O(0,0) 和基向量 i(1,0) 與 j(0,1) 定義的坐標平面。事實上，你也可以選擇一個完全不同的基礎，其中的數學仍然有效。比如說，你可以保持原點仍然為 O，但選擇 i =(2,1) 和 j =(1,2) 作為基向量。如果你有耐心計算一下，你會發現在 i , j 坐標系統中標記為 (2,2) 的點在 i, j 系統標記為 (6, 6)。

使用 Mathisfun 的「互動式笛卡爾坐標」繪製：

https://www.mathsisfun.com/data/cartesian-coordinates-interactive.html

這意味著我們可以修改空間的基礎。現在想像有更高維度的空間，比如有 5 萬維。你可以為這個空間選擇一個基礎，然後根據這個基礎僅選擇 200 個最重要的向量。這些基向量被稱為主成分，而且你可以選擇其中一個子集構成一個新空間，它的維度比原來的空間少，但又保留了儘可能多的數據複雜度。

要選擇出最重要的主成分，我們需要檢查這些數據的方差，並按這個指標給它們排序。

理解 PCA 的另一個思路是 PCA 將我們數據中存在的空間重映射成了一個更加緊湊的空間。這種變換後的維度比原來的維度更小。

僅需使用重映射空間的前幾個維度，我們就可以開始理解這個數據集的組織結構。這就是降維的目的：減少複雜度（即這裡的維度），同時保留結構（方差）。這裡有篇 Samer 寫的論文，介紹了使用 PCA（以及擴散映射等技術）試圖理解維基解密披露的電報：

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

2. 奇異值分解（SVD）

假設我們將我們的數據表示成一個 A=m×n 的大型矩陣。SVD 讓我們可以將這個大型矩陣分解成 3 個較小的矩陣的乘積；這 3 個矩陣分別是 U=m x r、對角矩陣 Σ=r x r、V=r x n，其中 r 是一個很小的值。

在這個 r×r 的對角矩陣 Σ 中的值被稱為奇異值。這些值的奇妙之處是可以被用於壓縮原來的矩陣，如果你丟棄奇異值中最小的 20% 以及矩陣 U 和 V 中相關的列，你就可以節省大量空間，同時仍然能很好地表徵原來的矩陣。

為了更準確地了解其中的含義，我們來看看一張小狗的圖片：

我們將使用Andrew Gibiansky寫的關於SVD的文章中代碼：

http://andrew.gibiansky.com/blog/mathematics/cool-linear-algebra-singular-value-decomposition/。

首先，我們發現如果我們根據大小排序這些奇異值（矩陣 Σ 的值），那麼前 50 個奇異值將包含整個矩陣 Σ 的大小的 85％。

根據這個事實，我們可以丟棄後面的250個值（即將它們設為0），僅保留這張小狗圖像的「rank（秩）50」版本。這裡，我們創建了秩為200、100、50、30、20、10 和3的小狗照片。顯然，照片變小了。但假設我們認為秩為30的小狗仍然很好，現在讓我們看看我們實現了多少壓縮。原先的圖像矩陣有305*275=83,875個值，秩為30的圖像則有305*30+30+30*275=17,430個值。值的數量差不多少了5倍，但質量卻下降很少。上述計算的原因是當我們執行UΣ V運算時，U和V矩陣中的一部分因為乘0也被丟棄（其中Σ 是Σ的修改後版本，其中僅包含了前面的30個值）。

無監督學習常常被用於數據預處理。一般而言，這意味著以某種平均-保留的方式壓縮數據，比如 PCA 或 SVD；之後，這些數據可被用於深度神經網路或其它監督式學習演算法。

原文地址：

END

推薦：

優秀人才不缺工作機會，只缺適合自己的好機會。但是他們往往沒有精力從海量機會中找到最適合的那個。100offer會對平台上的人才和企業進行嚴格篩選，讓「最好的人才」和「最好的公司」相遇。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！