A. 數據挖掘干貨總結（四）--聚類演算法
本文共計2680字，預計閱讀時長七分鍾
聚類演算法
一 、 本質
將數據劃分到不同的類里，使相似的數據在同一類里，不相似的數據在不同類里
二 、 分類演算法用來解決什麼問題
文本聚類、圖像聚類和商品聚類，便於發現規律，以解決數據稀疏問題
三 、 聚類演算法基礎知識
1. 層次聚類 vs 非層次聚類
– 不同類之間有無包含關系
2. 硬聚類 vs 軟聚類
– 硬聚類：每個對象只屬於一個類
– 軟聚類：每個對象以某個概率屬於每個類
3. 用向量表示對象
– 每個對象用一個向量表示，可以視為高維空間的一個點
– 所有對象形成數據空間（矩陣）
– 相似度計算：Cosine、點積、質心距離
4. 用矩陣列出對象之間的距離、相似度
5. 用字典保存上述矩陣（節省空間）
D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}
6. 評價方法
– 內部評價法（Internal Evalution）：
• 沒有外部標准，非監督式
• 同類是否相似，跨類是否相異
DB值越小聚類效果越好，反之，越不好
– 外部評價法（External Evalution）：
• 准確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)
• 精度（Precision）: C11 / (C11 + C21 )
• 召回（Recall）: C11 / (C11 + C12 )
• F值（F-measure）：
β表示對精度P的重視程度，越大越重視，默認設置為1，即變成了F值，F較高時則能說明聚類效果較好。
四 、 有哪些聚類演算法
主要分為 層次化聚類演算法 ， 劃分式聚類演算法 ， 基於密度的聚類演算法 ， 基於網格的聚類演算法 ， 基於模型的聚類演算法等 。
4.1 層次化聚類演算法
又稱樹聚類演算法，透過一種層次架構方式，反復將數據進行分裂或聚合。典型的有BIRCH演算法，CURE演算法，CHAMELEON演算法，Sequence data rough clustering演算法,Between groups average演算法,Furthest neighbor演算法,Neares neighbor演算法等。
凝聚型層次聚類 ：
先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。
演算法流程：
1. 將每個對象看作一類，計算兩兩之間的最小距離；
2. 將距離最小的兩個類合並成一個新類；
3. 重新計算新類與所有類之間的距離；
4. 重復2、3，直到所有類最後合並成一類。
特點：
1. 演算法簡單
2. 層次用於概念聚類（生成概念、文檔層次樹）
3. 聚類對象的兩種表示法都適用
4. 處理大小不同的簇
5. 簇選取步驟在樹狀圖生成之後
4.2 劃分式聚類演算法
預先指定聚類數目或聚類中心，反復迭代逐步降低目標函數誤差值直至收斂，得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，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網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特徵。
演算法流程：
1. 網路初始化，對輸出層每個節點權重賦初值；
2. 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；
3. 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；
4. 提供新樣本、進行訓練；
5. 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。
4.4 基於密度聚類演算法
只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類，擅於解決不規則形狀的聚類問題，廣泛應用於空間信息處理,SGC,GCHL，DBSCAN演算法、OPTICS演算法、DENCLUE演算法。
DBSCAN：
對於集中區域效果較好，為了發現任意形狀的簇，這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域；一種基於高密度連通區域的基於密度的聚類方法，該演算法將具有足夠高密度的區域劃分為簇，並在具有雜訊的空間數據中發現任意形狀的簇。
4.5 基於網格的聚類演算法
基於網格的方法把對象空間量化為有限數目的單元，形成一個網格結構。所有的聚類操作都在這個網格結構（即量化空間）上進行。這種方法的主要優點是它的處理 速度很快，其處理速度獨立於數據對象的數目，只與量化空間中每一維的單元數目有關。但這種演算法效率的提高是以聚類結果的精確性為代價的。經常與基於密度的演算法結合使用。代表演算法有STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法等。
B. 用於數據挖掘的聚類演算法有哪些，各有何優勢
聚類方法的分類，主要分為層次化聚類演算法，劃分式聚類演算法，基於密度的聚類演算法，基於網格的聚類演算法，基於模型的聚類演算法等。
而衡量聚類演算法優劣的標准主要是這幾個方面：處理大的數據集的能力；處理任意形狀，包括有間隙的嵌套的數據的能力；演算法處理的結果與數據輸入的順序是否相關，也就是說演算法是否獨立於數據輸入順序；處理數據雜訊的能力；是否需要預先知道聚類個數，是否需要用戶給出領域知識；演算法處理有很多屬性數據的能力，也就是對數據維數是否敏感。
.聚類演算法主要有兩種演算法，一種是自下而上法（bottom-up），一種是自上而下法（top-down）。這兩種路徑本質上各有優勢，主要看實際應用的時候要根據數據適用於哪一種，Hierarchical methods中比較新的演算法有BIRCH主要是在數據體量很大的時候使用；ROCK優勢在於異常數據抗干擾性強……
關於數據挖掘的相關學習，推薦CDA數據師的相關課程，課程以項目調動學員數據挖掘實用能力的場景式教學為主，在講師設計的業務場景下由講師不斷提出業務問題，再由學員循序漸進思考並操作解決問題的過程中，幫助學員掌握真正過硬的解決業務問題的數據挖掘能力。這種教學方式能夠引發學員的獨立思考及主觀能動性，學員掌握的技能知識可以快速轉化為自身能夠靈活應用的技能，在面對不同場景時能夠自由發揮。點擊預約免費試聽課。
C. 層次聚類分析案例（三）
之前的筆記：
聚類介紹： 點這里
層次聚類分析案例（一）
層次聚類分析案例（二）
獲取全基因組表達數據的能力是一項計算復雜度非常高的任務。由於人腦的局限性，是無法解決這個問題。但是，通過將基因分類進數量較少的類別後再進行分析，就能將基因數據加工到更易理解的水平。
聚類的目標是將一組基因進行劃分，使相似的基因落入同一個簇，同時不相似的基因落入不同的簇。這里需要考慮的關鍵問題是如何定義相似性，以及處理已分類基因。這里我們使用兩種基因類型的感光性來探索基因聚類問題。
准備工作
為了進行層次聚類，我們使用從實驗鼠身上採集的數據集。
第1步：收集和描述數據
該任務使用名為GSE4051_data和GSE4051_design的數據集。該數據集以標准格式存儲在名為GSE4051_data.csv和GSE4051_design.csv的CSV格式的文件中。數據獲取路徑： 在這里
GSE4051_data數據集包含29949行數據和39個變數。數值型變數如下：
GSE4051_design數據集包含39行數據和4個變數。數值型變數是：sidNum
非數值型變數是：sidChar；devStage；gType；
具體實施步驟以下為實現細節。
第2步：探索數據
RColorBrewer包是一個R包，可從 http://colorbrewer2.org 獲取，它提供地圖和其他圖形的彩色模板。
pvclust包用來實現非確定性的層次聚類分析。在層次聚類中，每個簇通過多尺度有放回抽樣計算p值。一個簇的p值在0～1之間。p值有兩種類型：近似無偏（approximately unbiased，AU）和有放回概率（bootstrap probability，BP）值。AU p值通過多尺度有放回採樣方法計算，經典的有放回採樣方法用來計算BP p值。AU p值相比BP p值存在優效性偏見。
xtable包可以生成LaTeX格式的表格。使用xtable可以將特定的R對象轉換成xtables。這些xtables能夠以LaTeX或HTML的格式輸出。
plyr包被用來進行分置合並（split-apply-combine，SAC）過程。它將一個大的問題切分成易處理的小塊，在每個小塊上進行操作，然後將所有小塊合並起來。
載入以下包：
讓我們探索並理解變數間的關系。從導入名為GSE4051_data.csv的CSV文件開始。我們將該文件數據存儲到GSE4051_data數據框中：
接下來，輸出GSE4051_data數據框的信息。str（）函數返回GSE4051_data的結構信息。它簡略顯示了GSE4051_data數據框的內部結構。max.level指明了為了顯示網狀結構的最大等級。
結果如下：
下面，我們導入名為GSE4051_design.csv的CSV文件，將其數據保存到GSE4051_design數據框中：
輸出GSE4051_design數據框的內部結構。
結果如下：
第3步：轉換數據
為了便於後續的可視化階段，需要對每一行數據進行拉伸操作。這是由於在目前的要求下，不同基因表達之間存在絕對值的差距，因此需要對每一行數據進行拉伸。
中心化變數和創建z值是兩個常見的數據分析方法。scale函數中心化並拉伸數值型矩陣的列。
變換矩陣。傳入GSE4051_data數據框用t（）函數進行數據框變換。
接下來，我們輸出GSE4051_data數據框的信息。通過設置give.attr=FALSE，次級結構的屬性不會被顯示。
結果如下：
round（）函數用於舍入到最接近的整數。語法形式只有1種：Y = round(X)，這里的X可以是數，向量，矩陣，輸出對應。
head（）函數返回一個向量、矩陣、表、數據框或函數的頭部。GSE4051_data和trans_GSE4051_data數據框被當作對象傳入。rowMeans（）函數計算每列的平均值。data.frame（）函數創建數據框耦合變數集合，並且共享許多指標的性質：
結果如下：
第4步：訓練模型
接下來是訓練模型。第一步是計算距離矩陣。dist（）函數用來計算並返回距離矩陣，可以使用特定的距離度量方法來計算數據矩陣中各行間的距離。這里可使用的距離度量方法有歐式距離、最大距離、曼哈頓距離、堪培拉距離、二進制距離，或閔可夫斯基距離。這里使用歐式距離。歐式距離計算兩個向量間的距離公式為sqrt（sum（（x_i-y_i）^2））。轉換後的trans_GSE4051_data數據框被用來計算距離。結果存儲在pair_dist_GSE4051_data數據框中。
接下來，使用interaction（）函數計算並返回gType、devStage變數間相互作用的無序因子。無序因子的結果連同GSE4051_design數據框一同被傳入with（）函數。該函數計算產生一個新的因子代表gType、devStage變數的相互作用：
summary（）函數用來生成GSE4051_design$group數據框的結果總結：
結果如下：
下面，使用多種不同的聯合類型計算層次聚類。
使用hclust（）函數對n個不同對象進行聚類分析。第一個階段，每個對象被指派給自己的簇。演算法在每個階段迭代聚合兩個最相似的簇。持續該過程直到只剩一個單獨的簇。hclust（）函數要求我們以距離矩陣的形式提供數據。pair_dist_GSE4051_data數據框被傳入。
在第一個例子中使用single聚類方法：
結果如下：
在第二個例子中使用complete聚集方法。
調用pr.hc.complete的結果是顯示所使用的聚集方法、距離計算方法和對象數量：
結果如下：
在第三個例子中使用average聚類方法：
調用pr.hc.complete的結果是顯示所使用的聚集方法、距離計算方法和對象數量：
結果如下：
在第四個例子中使用ward聚類方法：
pr.hc.ward的調用結果是顯示所使用的聚集方法、距離計算方法和對象數量：
結果如下：
plot（）函數是繪制R對象的通用函數。
第一次調用plot（）函數，傳遞pr.hc.single數據框作為輸入對象：
結果如下：
第二次調用plot（）函數，傳入pr.hc.complete數據框作為輸入對象：
結果如下：
第三次調用plot（）函數，傳入pr.hc.average數據框作為輸入對象：
結果如下：
第四次調用plot（）函數，傳入pr.hc.ward數據框作為輸入對象：
結果如下：
第5步：繪制模型
plot（）函數是繪制R對象的通用函數。這里，plot（）函數用來繪制系統樹圖。
rect.hclust（）函數強調不同的簇，並在系統樹圖的枝幹上繪制長方形。系統樹圖首先在某個等級上被剪切，之後在選定的枝幹上繪制長方形。
RColorBrewer使用從 http://colorbrewer2.org 獲得的包來選擇繪制R圖像的顏色模板。
顏色分為三組：
最重要的一個RColorBrewer函數是brewer.pal（）。通過向該函數傳入顏色的數量和配色的名字，可以從display.brewer.all（）函數中選擇一個配色方案。
在第一個例子中，pr.hc.single作為一個對象傳入plot（）函數：
結果如下：
下面創建熱度圖，使用single聚集方法。heatmap（）函數默認使用euclidean聚集方法：
結果如下：
在第二例子中，pr.hc.complete作為對象傳入plot（）函數：
結果如下：
下面使用complete聚集方法創建熱度圖：
結果如下：
在第三個例子中，pr.hc.average作為對象傳入plot（）函數：
結果如下：
下面創建average聚集方法的熱度圖：
結果如下：
在第四個例子中，pr.hc.ward作為對象傳入plot（）函數：
結果如下：
下面繪制ward聚集方法的熱度圖：
結果如下：