本文共計2680字，預(yù)計閱讀時長七分鐘
聚類算法
?
一、本質(zhì)
將數(shù)據(jù)劃分到不同的類里，使相似的數(shù)據(jù)在同一類里，不相似的數(shù)據(jù)在不同類里
?
二、分類算法用來解決什么問題
文本聚類、圖像聚類和商品聚類，便于發(fā)現(xiàn)規(guī)律，以解決數(shù)據(jù)稀疏問題
三、聚類算法基礎(chǔ)知識
1. 層次聚類?vs?非層次聚類
– 不同類之間有無包含關(guān)系
2. 硬聚類?vs?軟聚類
– 硬聚類：每個對象只屬于一個類
– 軟聚類：每個對象以某個概率屬于每個類
3. 用向量表示對象
– 每個對象用一個向量表示，可以視為高維空間的一個點
– 所有對象形成數(shù)據(jù)空間（矩陣）
– 相似度計算：Cosine、點積、質(zhì)心距離
4. 用矩陣列出對象之間的距離、相似度
5. 用字典保存上述矩陣（節(jié)省空間）
????D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}
6. 評價方法
– 內(nèi)部評價法（Internal Evalution）：
? 沒有外部標(biāo)準(zhǔn)，非監(jiān)督式
? 同類是否相似，跨類是否相異
DB值越小聚類效果越好，反之，越不好
– 外部評價法（External Evalution）：
??準(zhǔn)確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)
??精度（Precision）: C11 / (C11 + C21 )
??召回（Recall）: C11 / (C11 + C12 )
??F值（F-measure）：
β表示對精度P的重視程度，越大越重視，默認(rèn)設(shè)置為1，即變成了F值，F(xiàn)較高時則能說明聚類效果較好。
四、有哪些聚類算法
參考來源：清華大學(xué)數(shù)據(jù)科學(xué)研究院
鏈接：https://www.zhihu.com/question/34554321/answer/233489816
主要分為層次化聚類算法，劃分式聚類算法，基于密度的聚類算法，基于網(wǎng)格的聚類算法，基于模型的聚類算法等。
4.1 層次化聚類算法
又稱樹聚類算法，透過一種層次架構(gòu)方式，反復(fù)將數(shù)據(jù)進(jìn)行分裂或聚合。典型的有BIRCH算法，CURE算法，CHAMELEON算法，Sequence data rough clustering算法,Between groups average算法,Furthest neighbor算法,Neares neighbor算法等。
凝聚型層次聚類：
先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結(jié)條件被滿足。
算法流程：
1. 將每個對象看作一類，計算兩兩之間的最小距離；
2. 將距離最小的兩個類合并成一個新類；
3. 重新計算新類與所有類之間的距離；
4. 重復(fù)2、3，直到所有類最后合并成一類。
特點：
1. 算法簡單
2. 層次用于概念聚類（生成概念、文檔層次樹）
3. 聚類對象的兩種表示法都適用
4. 處理大小不同的簇
5. 簇選取步驟在樹狀圖生成之后
4.2 劃分式聚類算法
預(yù)先指定聚類數(shù)目或聚類中心，反復(fù)迭代逐步降低目標(biāo)函數(shù)誤差值直至收斂，得到最終結(jié)果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等
經(jīng)典K-means：
算法流程：
1. 隨機(jī)地選擇k個對象，每個對象初始地代表了一個簇的中心；
2. 對剩余的每個對象，根據(jù)其與各簇中心的距離，將它賦給最近的簇；
3. 重新計算每個簇的平均值，更新為新的簇中心；
4. 不斷重復(fù)2、3，直到準(zhǔn)則函數(shù)收斂。
特點：
1.K的選擇
2.中心點的選擇
– 隨機(jī)
– 多輪隨機(jī)：選擇最小的WCSS
3.優(yōu)點
– 算法簡單、有效
– 時間復(fù)雜度：O(nkt)
4.缺點
– 不適于處理球面數(shù)據(jù)
– 密度、大小不同的聚類，受K的限制，難于發(fā)現(xiàn)自然的聚類
4.3 基于模型的聚類算法
為每簇假定了一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合，同一”類“的數(shù)據(jù)屬于同一種概率分布，即假設(shè)數(shù)據(jù)是根據(jù)潛在的概率分布生成的。主要有基于統(tǒng)計學(xué)模型的方法和基于神經(jīng)網(wǎng)絡(luò)模型的方法，尤其以基于概率模型的方法居多。一個基于模型的算法可能通過構(gòu)建反應(yīng)數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類。基于模型的聚類試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)據(jù)模型之間的適應(yīng)性。
SOM神經(jīng)網(wǎng)絡(luò)算法：
該算法假設(shè)在輸入對象中存在一些拓?fù)浣Y(jié)構(gòu)或順序，可以實現(xiàn)從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓?fù)涮卣鞅３中再|(zhì),與實際的大腦處理有很強的理論聯(lián)系。
SOM網(wǎng)絡(luò)包含輸入層和輸出層。輸入層對應(yīng)一個高維的輸入向量，輸出層由一系列組織在2維網(wǎng)格上的有序節(jié)點構(gòu)成，輸入節(jié)點與輸出節(jié)點通過權(quán)重向量連接。學(xué)習(xí)過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區(qū)域的權(quán)值更新，使輸出節(jié)點保持輸入向量的拓?fù)涮卣鳌?/p>
算法流程：
1. 網(wǎng)絡(luò)初始化，對輸出層每個節(jié)點權(quán)重賦初值；
2. 將輸入樣本中隨機(jī)選取輸入向量，找到與輸入向量距離最小的權(quán)重向量；
3. 定義獲勝單元，在獲勝單元的鄰近區(qū)域調(diào)整權(quán)重使其向輸入向量靠攏；
4. 提供新樣本、進(jìn)行訓(xùn)練；
5. 收縮鄰域半徑、減小學(xué)習(xí)率、重復(fù)，直到小于允許值，輸出聚類結(jié)果。
4.4 基于密度聚類算法
只要鄰近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個閾值，就繼續(xù)聚類，擅于解決不規(guī)則形狀的聚類問題，廣泛應(yīng)用于空間信息處理,SGC,GCHL，DBSCAN算法、OPTICS算法、DENCLUE算法。
DBSCAN：
對于集中區(qū)域效果較好，為了發(fā)現(xiàn)任意形狀的簇，這類方法將簇看做是數(shù)據(jù)空間中被低密度區(qū)域分割開的稠密對象區(qū)域；一種基于高密度連通區(qū)域的基于密度的聚類方法，該算法將具有足夠高密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇。
4.5 基于網(wǎng)格的聚類算法
????基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)（即量化空間）上進(jìn)行。這種方法的主要優(yōu)點是它的處理?速度很快，其處理速度獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。但這種算法效率的提高是以聚類結(jié)果的精確性為代價的。經(jīng)常與基于密度的算法結(jié)合使用。代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。?
