聚類算法
？
壹.本質
將數據劃分到不同的類中，使相似的數據在同壹類中，不相似的數據在不同的類中。
？
二、分類算法是用來解決什麽問題的？
文本聚類、圖像聚類、商品聚類容易發現規律，解決數據稀疏問題。
三、聚類算法的基礎知識
1.層次聚類？vs？非層次聚類
–不同類別之間是否存在包含關系？
2.硬聚類？vs？軟聚類
–硬聚類:每個對象只屬於壹個類。
–軟聚類:每個對象以壹定的概率屬於每個類。
3.用向量表示物體
每個物體用壹個向量表示，可以看作高維空間中的壹個點。
–所有對象形成壹個數據空間(矩陣)
–相似性計算:余弦、點積和質心距離。
4.用矩陣列出物體之間的距離和相似度。
5.用字典保存上面的矩陣(節省空間)
D={(1，1):0，(1，2):2，(1，3):6...(5,5):0}
6.評估方法
–內部評估方法:
？沒有外部標準，沒有監督
？同類是否相似，跨類是否不同。
DB值越小，聚類效果越好，否則越差。
–外部評估方法:
？精度:(c 11+c22)/(c 11+c 12+c 21+c22)
？精度:c 11/(c 11+c 21)
？召回:c 11/(c 11+c 12)
？F值(F值):
β表示對精度p的重視程度，值越大越重要。默認設置是1，也就是說它變成了f的值，f越高說明聚類效果越好。
4.有哪些聚類算法？
主要分為層次聚類算法、劃分聚類算法、基於密度的聚類算法、基於網格的聚類算法、基於模型的聚類算法等。
4.1層次聚類算法
也稱為樹聚類算法，它通過分層結構重復拆分或聚合數據。典型的算法有BIRCH算法、CURE算法、CHAMELEON算法、序列數據粗糙聚類算法、組間平均算法、最遠鄰居算法、最近鄰居算法等。
內聚層次聚類:
先把每個對象當作壹個簇，然後把這些原子簇合並成越來越大的簇，直到所有對象都在壹個簇中或者滿足某個終止條件。
算法流程:
1.將每個對象視為壹個類，計算兩兩之間的最小距離；
2.將距離最小的兩個類合並成壹個新類；
3.重新計算新類別與所有類別之間的距離；
4.重復2和3，直到所有類最終合並為壹個類。
特點:
1.簡單算法
2.層次用於概念聚類(生成概念和文檔層次樹)。
3.聚類對象的兩種表示都是適用的。
4.處理不同大小的集群
5.聚類選擇步驟是在生成樹形圖之後。
4.2分區聚類算法
預先指定聚類數或聚類中心，通過叠代逐步減小目標函數的誤差值直至收斂，得到最終結果。K-means、k-modes-Huang、k-means-CP、cluster、特征加權模糊聚類、CLARANS等。
經典K-means:
算法流程:
1.隨機選擇k個對象，每個對象最初代表壹個簇的中心；
2.對於每個剩余的對象，根據其到每個簇中心的距離將其分配到最近的簇中；
3.重新計算每個聚類的平均值，並更新到新的聚類中心；
4.重復2和3，直到標準函數收斂。
特點:
選擇1。K
2.中心點的選擇
–隨機
–多輪隨機化:選擇最小的WCSS。
3.優勢
–算法簡單有效。
–時間復雜度:O(nkt)
4.不足之處
–不適合處理球形數據。
-不同密度和大小的集群受K的限制，很難找到自然的集群。
4.3基於模型的聚類算法
為每個聚類假設壹個模型，以找到數據與給定模型的最佳擬合。同壹個“類”的數據屬於同壹個概率分布，即假設數據是按照潛在概率分布產生的。主要有基於統計模型和神經網絡模型的方法，尤其是基於概率模型的方法。基於模型的算法可以通過構造反映數據點的空間分布的密度函數來定位聚類。基於模型的聚類試圖優化給定數據和某些數據模型之間的適應性。
SOM神經網絡算法；
該算法假設輸入對象中存在某種拓撲結構或序列，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射。該映射具有保持拓撲特征的性質，並且與實際的大腦處理具有很強的理論聯系。
SOM網絡包括輸入層和輸出層。輸入層對應於壹個高維輸入向量，輸出層由壹系列在二維網格上組織的有序節點組成。輸入節點和輸出節點通過權重向量連接。在學習過程中，找到距離最短的輸出層單元，即獲勝單元，並進行更新。同時，更新相鄰區域的權值以保持輸入向量的拓撲特征。
算法流程:
1.網絡初始化，為輸出層中每個節點的權重分配壹個初始值；
2.從輸入樣本中隨機選擇輸入向量，以找到與輸入向量距離最小的權重向量；
3.定義獲勝單元，調整獲勝單元附近的權重，使其接近輸入向量；
4.提供新樣品並進行培訓；
5.縮小鄰域半徑，降低學習率，重復直到小於允許值，輸出聚類結果。
4.4基於密度的聚類算法
只要相鄰區域的密度(對象或數據點的數量)超過壹定閾值，就會繼續聚類，擅長解決不規則形狀的聚類問題，廣泛應用於空間信息處理、SGC、GCHL、DBSCAN算法、OPTICS算法和DENCLUE算法。
數據庫掃描:
它對集中區域很有效。為了找到具有任意形狀的簇，該方法將簇視為數據空間中由低密度區域分隔的密集對象區域。壹種基於高密度連通區域的基於密度的聚類方法，將足夠高密度的區域劃分成簇，在有噪聲的空間數據中尋找任意形狀的簇。
4.5基於網格的聚類算法
基於網格的方法將對象空間量化為有限數量的單元以形成網格結構。所有的聚類操作都是在這個網格結構(即量化空間)上進行的。這種方法的主要優點是它的處理？它的速度非常快，其處理速度與數據對象的數量無關，只與量化空間中每壹維的單位數有關。但是這種算法的效率提高是以犧牲聚類結果的準確性為代價的。通常與基於密度的算法結合使用。代表性的算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。？