無監督學習中有哪些算法屬于聚類與降維？

可以說機器學習已經成為了改變時代的大事，一時間似乎人人都應該懂一點機器學習。但機器學習涉及到的數學知識和編程能力往往讓沒有相關經驗的人望而卻步。

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

我們將在這里探索的兩種無監督學習任務是：1）將數據按相似度聚類（clustering）成不同的分組；2）降維（reducing dimensionality），以便在保留數據結構和有用性的同時對數據進行壓縮。

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

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

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

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

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

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

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

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

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

實際上，你只需要在 Acxiom 的「我屬于哪個聚類？」工具中回答幾個簡單問題，你就能知道你個人屬于哪個聚類，體驗地址：https://isapps.acxiom.com/personicx/personicx.aspx

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

K 均值聚類

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

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

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

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

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

K 均值聚類的步驟如下：

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

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

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

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

這就是 K 均值聚類工作方式的精簡版！該算法的可視化演示可在這里查看：https://www.naftaliharris.com/blog/visualizing-k-means-clustering/，你可以像讀漫畫一樣理解。平面上的每個數據點都根據離自己最近的重心加了顏色。你可以看到這些重心（更大一點的藍點、紅點和綠點）一開始是隨機的，然后很快進行了調整，得到了它們各自的聚類。

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

分層聚類

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

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

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

分層聚類的步驟如下：

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

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

3. 重新計算這些聚類之間的距離。有很多可以辦到這件事的方法（參見這個教程了解更多細節：https://home.deib.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html）。其中一種方法（平均連接聚類，average-linkage clustering）是將兩個聚類之間的距離看作是它們各自元素之間所有距離的平均。

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

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

更多有關分層聚類的詳細信息，可參閱這個視頻：https://www.youtube.com/watch?v=OcoE7JlbXvY

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

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

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

主成分分析（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

奇異值分解（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；之后，這些數據可被用于深度神經網絡或其它監督式學習算法。