聚類分析

聚類分析，這樣讓在同一個子集中的成員物件都有相似的一些屬性，常見的包括在座標系中更加短的空間距離等。一般把資料聚類歸納為一種非監督式學習。定義.“聚類(clustering)”的概念不能精確定義，這也是為什麼聚類演算法眾多的原因之一。 聚類問題的共同點就是有一組資料物件。 然而，不同的研究人員採用不同的聚類模型，並且對於這些聚類模型中的每一個，可以再給出不同的演算法。 而且不同演算法發現的“類”在其屬性上往往會有很大差異。 理解這些“聚類模型”是理解各種演算法之間差異的關鍵。 典型的聚類模型包括以下幾種：“聚類”的本質上是找到一組類, 這些類通常包含資料集中的所有物件。 此外，它可以指定各個類彼此之間的關係，例如，類相互嵌入的層次結構。 聚類可以大致區分為：也可能有更細微的區別，例如：嚴格分割槽聚類：每個物件恰好屬於一個類演算法.沒有客觀上“正確”的聚類演算法，但正如人們所指出的，“聚類在觀察者的眼中”。除非你有喜歡一個聚類模型而不是另一個的數學原因，通常需要透過實驗選擇最適合特定問題的聚類演算法。為一種模型設計的演算法通常會在包含完全不同型別模型的資料集上失敗。 例如，k-means 無法找到非凸簇。連通性聚類.基於連通性的聚類，也稱為層次聚類，其核心思想是物件與附近物件的相關性高於與較遠物件的相關性。 這些演算法根據它們的距離將“物件”連線起來形成“簇”。 叢集可以主要透過連線叢集各部分所需的最大距離來描述。 在不同的距離，會形成不同的聚類，這可以用樹狀圖表示，這解釋了通用名稱“層次聚類”的這些演算法不提供資料集的單一分割槽，而是提供廣泛的層次結構 在一定距離處相互合併的簇。 在樹狀圖中，y 軸標記叢集合併的距離，而物件沿 x 軸放置，這樣叢集就不會混合。基於連通性的聚類是一整套方法，它們因計算距離的方式不同而不同。 除了通常選擇的距離函式外，使用者還需要決定要使用的連線標準。這些方法不會產生資料集的唯一分割槽，而是產生一個層次結構，使用者仍然需要從中選擇合適的叢集。 它們對異常值不是很穩健，異常值要麼顯示為額外的叢集，要麼甚至導致其他叢集合併。 在一般情況下，複雜度是 O("n")"3") 對於凝聚聚類和 O("2""n-1") 用於分裂聚類，[7] 這使得它們對於大型資料集來說太慢了。 對於某些特殊情況，已知最優有效方法（複雜度 O("n")"2") ：SLINK 用於單鏈接和 CLINK 用於完全連結聚類。質心聚類.在基於質心的聚類演算法中，每個聚類由一箇中心向量表示，它不一定是資料集的成員。 當簇數固定為 k 時，k-means 聚類給出了最佳化問題的形式化定義：找到 k 個簇中心並將物件分配到最近的簇中心，使得與簇的平方距離最小。已知最佳化問題本身是 NP問題，不太隨機地選擇初始中心（ k-means++) 或允許模糊聚類分配 (fuzzy c-means)。大多數 k-means 型別的演算法都需要預先指定聚類的數量 - k，這被認為是這些演算法的最大缺點之一。 此外，演算法更喜歡大小大致相似的簇，因為它們總是會將物件分配給最近的質心。 這通常會導致錯誤地切割叢集邊界。K-means 有許多有趣的理論特性。 首先，它將資料空間劃分為一種稱為 Voronoi 圖的結構。 其次，它在概念上接近最近鄰分類，因此在機器學習中很受歡迎。 第三，它可以看作是基於模型的聚類的變體，Lloyd 演算法可以看作是下面討論的該模型的期望最大化演算法的變體。基於質心的聚類問題中，任務是找到最佳倉庫位置以最佳地服務一組給定的消費者。 人們可以將“倉庫”視為聚類質心，將“消費者位置”視為要聚類的資料。 這使得將設施位置完善的演算法解決方案應用於目前考慮的基於質心的聚類問題成為可能。分佈模型聚類.與統計學關係最密切的聚類模型是基於分佈模型的。 然後可以很容易地將聚類定義為最有可能屬於同一分佈的物件。 這種方法的一個方便的特性是它非常類似於生成人工資料集的方式：透過從分佈中抽取隨機物件。儘管這些方法的理論基礎非常出色，但它們都存在一個稱為過度擬合的關鍵問題，除非對模型的複雜性施加約束。 更復雜的模型通常能夠更好地解釋資料，這使得選擇合適的模型複雜性本身就很困難。一種著名的方法被稱為高斯混合模型的高斯分佈建模，這些高斯分佈隨機初始化並且其引數經過迭代最佳化以更好地擬合數據集。 這將收斂到區域性最優，因此多次執行可能會產生不同的結果。 為了獲得硬聚類，通常會將物件分配給它們最有可能屬於的高斯分佈； 對於軟聚類，這不是必需的。基於分佈的聚類為聚類生成複雜模型，可以捕獲屬性之間的相關性和依賴性。 然而，這些演算法給使用者帶來了額外的負擔：對於許多真實資料集，可能沒有簡明定義的數學模型。密度聚類.在基於密度的聚類中，聚類被定義為密度高於資料集其餘部分的區域。 稀疏區域中的物件——需要分離叢集——通常被認為是噪聲和邊界點。最流行的基於密度的聚類方法是 DBSCAN,。與許多較新的方法相比，它具有一個定義明確的叢集模型，稱為“密度可達性”。 類似於基於連結的聚類，它基於一定距離閾值內的連線點。 然而，它只連線滿足密度標準的點，在原始變體中定義為該半徑內其他物件的最小數量。 簇由所有密度連線的物件 在每次執行中，因此無需多次執行。 OPTICS是 DBSCAN 的推廣，無需為範圍引數 ε 引數，並透過使用 R 樹索引提供了優於 OPTICS 的效能改進。DBSCAN 和 OPTICS 的主要缺點是它們期望某種密度下降來檢測簇邊界。 例如，在具有重疊高斯分佈的資料集上，這些演算法生成的聚類邊界通常看起來很隨意，因為聚類密度不斷降低。 在由高斯混合組成的資料集上，這些演算法幾乎總是優於能夠精確建模此類資料的 EM 聚類等方法。均值漂移(mean-shift)是一種聚類方法，其中基於核密度估計將每個物件移動到其附近最密集的區域。 最終，物件會聚到密度的區域性最大值。 與 k-means 聚類類似，這些“密度吸引子”可以作為資料集的代表，但 mean-shift 可以檢測類似於 DBSCAN 的任意形狀的聚類。 由於昂貴的迭代過程和密度估計，均值漂移通常比 DBSCAN 或 k-Means 慢。 除此之外，均值漂移演算法對多維資料的適用性受到核密度估計的不平滑行為的阻礙，這會導致聚類尾部過度碎片化。網格聚類.基於網格的技術用於多維資料集。 在此技術中，我們建立一個網格結構，並在網格上執行比較。 基於網格的技術速度快，計算複雜度低。 有兩種型別的基於網格的聚類方法：STING 和 CLIQUE。聚類型別.資料聚類演算法可以分為結構性或者分散性。結構性演算法利用以前成功使用過的聚類器進行分類，而分散型演算法則是一次確定所有分類。結構性演算法可以從上至下或者從下至上雙向進行計算。從下至上演算法從每個物件作為單獨分類開始，不斷融合其中相近的物件。而從上至下演算法則是把所有物件作為一個整體分類，然後逐漸分小。分散式聚類演算法，是一次性確定要產生的類別，這種演算法也已應用於從下至上聚類演算法。基於密度的聚類演算法，是為了挖掘有任意形狀特性的類別而發明的。此演算法把一個類別視為資料集中大於某閾值的一個區域。DBSCAN和OPTICS是兩個典型的演算法。許多聚類演算法在執行之前，需要指定從輸入資料集中產生的分類個數。除非事先準備好一個合適的值，否則必須決定一個大概值，關於這個問題已經有一些現成的技術。距離測量.資料物件間的相似度度量一般是透過資料之間的相互關係來確定。在結構性聚類中，關鍵性的一步就是要選擇測量的距離。一個簡單的測量就是使用曼哈頓距離，它相當於每個變數的絕對差值之和。該名字的由來起源於在紐約市區測量街道之間的距離就是由人步行的步數來確定的。一個更為常見的測量方法是利用歐氏空間距離，可以認為資料分佈一個多維空間中，並且計算每個空間中每個點到原點的距離，然後對所有距離進行換算。常用的幾個距離計算方法：結構性聚類.在已經得到距離值之後，元素間可以被聯絡起來。透過分離和融合可以構建一個結構。傳統上，表示的方法是樹形資料結構，然後對該結構進行修剪。樹的根節點表示一個包含所有專案的類別，樹葉表示與個別的專案相關的類別。層次聚類演算法，要麼是自底向上聚集型的，即從葉子節點開始，最終匯聚到根節點；要麼是自頂向下分裂型的，即從根節點開始，遞迴的向下分裂。任意非負值的函式都可以用於衡量一對觀測值之間的相似度。決定一個類別是否分裂或者合併的是一個連動的標準，它是兩兩觀測值之間距離的函式。在一個指定高度上切割此樹，可以得到一個相應精度的分類。聚集型層次聚類.它的層次聚類樹如下圖分散性聚類.K-均值法及衍生演算法.K-均值法聚類.K-均值演算法表示以空間中k個點為中心進行聚類，對最靠近他們的物件歸類。"例如："資料集合為三維，聚類以兩點："X" =("x"1, "x"2, "x"3),"Y" =("y"1, "y"2, "y"3)。中心點"Z"變為"Z" =("z"1, "z"2, "z"3)，其中"z"1 = ("x"1 + "y"1)/2，"z"2 = ("x"2 + "y"2)/2，"z"3 = ("x"3 + "y"3)/2。演算法歸納為：該演算法的最大優勢在於簡潔和快速。劣勢在於對於一些結果並不能夠滿足需要，因為結果往往需要隨機點的選擇非常巧合。譜聚類.在多元變數統計中，譜聚類，在對資料進行降維後，以較少的維度進行聚類。相似矩陣作為輸入，提供了對資料集中每一對點相對相似性的定量評估。在影象分割中，譜聚類被稱為基於分割的物體分類。評估和驗證.聚類結果的評估與聚類本身一樣困難 。 流行的方法包括“內部”評估，其中聚類被總結為一個單一的質量分數，“外部”評估，其中聚類與現有的“基準真相(ground truth)”分類進行比較，由人類專家進行“手動”評估，以及“間接”透過評估聚類在其預期應用中的效用來進行評估。內部評估措施存在一個問題，即它們代表的功能本身可以被視為聚類目標。 例如，可以透過 Silhouette 係數對資料集進行聚類； 除了沒有已知的有效演算法之外。 透過使用這種內部衡量指標進行評估，人們更願意比較最佳化問題的相似性, 而不一定是聚類的有用程度 。外部評估也有類似的問題：如果我們有這樣的“ground truth”標籤，那麼我們就不需要聚類了； 而在實際應用中我們通常沒有這樣的標籤。 另一方面，標籤僅反映了資料集的一種可能分割槽，這並不意味著不存在不同的甚至更好的聚類。因此，這兩種方法都不能最終判斷聚類的實際質量，但這需要人工評估， 這是非常主觀的。 儘管如此，這樣的統計資料在識別不良聚類方面可能非常有用， 但不應忽視主觀的人為評估。應用.其他應用.For spectral clustering :For estimating number of clusters:For discussion of the elbow criterion: