【導讀】專業(yè)____自動化____班級____1104____學生姓名/學號徐天宇/202003120423__. 試數據集，完成聚類并利用圖和表等形式演示聚類效果。2020年12月至2020年2月：完成文獻調研、綜述撰寫和2篇外文文獻翻譯；2020年3. 演示聚類算法的效率評價；2020年5月：完成實驗總結并撰寫畢業(yè)論文，準備答辯。按照某種指導思想劃分成一些簇的過程。由于聚類問題的重要性，近50年提出了各種。為了新算法的開發(fā)需要，以及為了解決特定聚類問題的需要，開發(fā)一個。利用Rstudio公司開發(fā)的shiny包實現(xiàn)交互式演示平臺，實現(xiàn)良好用戶交互性，動員類型分類和球隊球員結構分類的應用，驗證了所實現(xiàn)聚類算法的有效性。

　　

【正文】 。 浙江工業(yè)大學本科畢業(yè)設計論文 17 當選擇完以上數據集之后，從互聯(lián)網上下載這些數據集， 使得最后一列為類別屬性。分別將其 存儲為 （由于R 自帶 Iris 這里就不需要存儲了）放入和 及 同一個目錄下的 clusterdatas文件夾中。 然后通過用戶選擇 執(zhí)行代碼 讀入這些數據集 以供 使用。 數據集在 txt 文件和程序中都以矩陣形式存儲，公式 31 是用 p 個變量（特征）表示 n 個數據元素 的例子。 11 1 111fpi if ipn nf npx x xx x xx x x???????? (31) 聚類結果評價 及實現(xiàn) 對聚類效果進行評價的研究稱為聚類有效性分析（ Clusetr Validity）。聚類有效性分析本身也是很復雜的，最好是根據不同的問題和不同的聚類算法做具體的分析。通常，在聚類有效性分析研究中評價聚類算法得到的聚類結果 C 的方法主要有三類。 (1) 外部標準 (External Criteria)：用事先判定的聚類結構來評價 C。 (2) 內部標準 (Internal Criteria)：用參與聚類的樣本 (n 個數據對象 )來評價 C，比如采用 C 中各個簇的誤差平方和，即 kmean、本文 pso 聚類的目標函數。 (3) 相對標準 (Relative Criteria)：用同一算法的不同結果 (不同參數得到 )來評價 C，通過與其他聚類算法的比較來判斷 C 的好壞。 一般來說，聚類結果是用外部準則來評價的 [20]。因為往往人們判定結果的好壞是和自己預想結果去對比的。為了引出常見的幾種外部準則，引入一個預期的結果簇結構。 12{ , , , }sP P P P? (32) 考慮 X 中任意兩個互異的數據對象 ( , )ijxx ，按照 ix 和 jx 在 C 結構 (由聚類算法得到的 )和 P 結構中是否屬于同一個簇，有以下四種 關系： 1. SS(TP)： ix 和 jx 在 C 結構和 P 結構屬于同一個簇 2. SD(FP)： ix 和 jx 在 C 結構中屬于同一個簇，而在 P 結構中屬于不同的簇 3. DS(FN)： ix 和 jx 在 C 結構中屬于不同的簇，而在 P 結構中屬于相同的簇 4. DD(TN)： ix 和 jx 在 C 結構和 P 結構屬于不同的簇 浙江工業(yè)大學本科畢業(yè)設計論文 18 若記 , , ,abcd 分別表示 SS， SD， DS， DD 的關系數目，則根據 , , ,abcd 的值，可以定義出不同的評價指標，常見的有 [13]。 (1) Rand Statistic adRa b c d?? ? ? ? (33) (2) Jaccard coefficient aJabc? ?? (34) (3) Fowlkes and Mallows index aaFMa b a c???? (35) 上述 ,R J FM 三個統(tǒng)計量越大，表面 C 和 P 的吻合程度越高， C 的聚類效果越好。本文聚類算法演示平臺使用了這三個統(tǒng)計量。 在信息檢索中常見的指標 還有 有 purity 和 Fmeasure 值，因為 Fmeasure 值使用更加廣泛，區(qū)分能力也更強，所以在這里具體介紹一下 [14]。和上文的 SS， SD， DS， DD相對應，信息檢索中將 TP 定義為將相似的文檔劃分到同一個簇中， TN 定義為將不相似的文檔劃分到不同的簇中。聚類可能產生兩類錯誤， FP 錯誤將不相似的文檔劃分到同一個簇中， FN 錯誤將相似的文檔劃分到不同的簇中。那么 Fmeasure 值定義如下： 22T P T P ( 1 )T P + F P T P + F N PRP R F PR? ?? ?? ? ? ? (36) 其中 P 表示準確率， P 的通俗解釋是檢索出的相關文檔數和檢索出的文檔 總數 的比率衡量查準率。 R 表示召回率， R 的通俗解釋是檢索出的相關文檔數 和文檔庫中所有相關 文檔數 的比率，衡量的是查全率 。 相對 Rand Statistic 給兩類錯誤同樣的權值，這里通過 ? 給兩類錯誤不同的權值，通常取 1?? 從而給召回率更多的權值。因為在實際應用中，F(xiàn)N 這種錯誤往往 比 FP 錯誤更加嚴重。 本文的多種聚類演示平臺取 5?? 。 R 語言中對聚類結果的評價可以通過 clv、 clusterCrit 兩個包實現(xiàn)，這兩個包的作者提供了包括本文使用的除 F 值以外 5 個外部指標在內的 各類 評價方法的 R 語言實現(xiàn)。本文利用這兩個包實現(xiàn)了上述 6 個指標。并設計當用戶觸發(fā)選擇時，顯示當前指標的值。 浙江工業(yè)大學本科畢業(yè)設計論文 19 多種 聚類算法 R 語言實現(xiàn) 結合演示平臺的需要我們希望每個聚類算法的輸入是數據集和相關參數，輸出是聚類的結果向量。 結果向量的第 i 個位置表示第 i 個數據點，第 i 個位置的值表示第 i 個數據點所屬的類標號 。這樣的封裝有利于繪圖和結果呈現(xiàn)。 本文在深入學習第二章列舉的 6 個算法之后，結合相關資料用 R 語言自主編寫了AP 算法、 FDP 算法和粒子群聚類算法，代碼見附錄，用 R 語言軟件包實現(xiàn)了 dbscan、kmeans 和 AGNES 算法。這里簡要介紹各算法實現(xiàn)方式。 kmeans 是 R 語言軟件自帶的算法，針對 Spiral 數據集只需輸入 kmeans(Spiral, 3)，即可返回一個 kmeans 類，它是一個列表，其中包含一個屬性 cluster，可用 kmean(Spiral, 3)$cluster 提取 。 DBSCAN 算法 R 語言并沒有自帶，但是通過網絡搜索和查閱 R 語言的 CRAN 可以發(fā)現(xiàn)， fpc 包提供了 DBSCAN 算法。 DBSAN 算法的 Minpts 參數默認設置為 5，也就是 核心對象 ? 領域中的點數 至少為 5 個 ， ? 領域的長度用戶通過參數進行設置。 用dbscan(Spiral,? )$cluster 可以提取對 Spiral 數據聚類的結果向量。 AGNES 算法 R 語言也沒有自帶，但是 cluster 包提供了這一算法 ， AGNES 算法可以在沒有參數輸入的情況下生成一顆聚類樹。因此要得到結果向量還要對它進行剪枝，R 語言基礎包 stats 提供了剪枝算法 cutree(tree, number)， number 確定最后結果中簇的數目，且 cutree 的返回值恰好是結果向量類型。因此只需用 cutree(agnes(Spiral), 3)就可以得到 Spiral 的聚類結果向量。 對于 AP 算法，根據作者提供的支持材料 [15]中的 matlab 程序，寫出 它的 R 語言版本 iapcluster（ s, p=）函數，詳見附錄 1。其中 s 是數據矩陣， p 代表參考度相對相似度的分位數（每個數據點參考度相同）。同樣對 Spiral 數據應用 AP 算法，可以通過 iapcluster(Spiral)@idx 得到結果向量。 對于 FDP 算法，根據作 者提供的 matlab 程序 [11]和網絡上相關材料結合 R 語言特點，編寫 FDP 算法 fdpcluster function(datam, noc, percent, method=euclidean, p=2)，其中參數 datam 表示輸入的數據矩陣， noc 表示簇的數目， percent 用于確定 cd ， method=euclidean表示默認采用歐幾里德距離， p=2 用于計算計算明氏距離，具體參見附錄 2。同樣對 Spiral 數據應用 fdp 算法，可以通過 fdpcluster(Spiral, 3, 2)@idx 得到結果向量。 浙江工業(yè)大學本科畢業(yè)設計論文 20 對于 PSO 聚類，根據文獻 [16]和網絡上相關材料結合 R 語言特點，編寫粒子群聚類算法 psocluster function(datam, centerNum, iterNum=20)，詳見附錄 3，其中 datam 表示數據矩陣， centerNum 表示簇的數目， iterNum 表示迭代次數，函數中粒子數量選擇 20 個。且涉及 psocluster 函數的返回值即為結果向量。同樣對 Spiral 數據應用 pso算法，可以通過 psocluster(Spiral, 3)@idx 得到結果向量。 演示平臺實現(xiàn) 結果 通過文獻 [17] 上的例子和教程，結合聚類算法演示的需要開發(fā)了 clustering algorithms demonstration 網頁，基本界面如圖 32。 圖 32 演示平臺界面 浙江工業(yè)大學本科畢業(yè)設計論文 21 網頁 發(fā)布在 由四部分組成， 用黑框框出， 第一部分是算法和數據集選擇窗口，算法包括上文提到的6 中算法，數據集包括上文提到的 7 種數據集，均可通過下拉菜單選擇 ，通過 input 傳入 ；第二部分是圖形演示窗口，從上到下，依次是當前算法的計算結果 圖 和數據集的實際分布 圖，圖形下方分別是結果向量和數據自然結果向量，均通過 output 輸出，可供用戶實時查看當前算法對每個數據對象的聚類情況 ；第三部分是參數選擇部分， 通過輸入框輸入，通過 input 傳入， 每次參數的改變都會 引起算法 重新計算并繪圖；第四部分是上文提到的 6 個聚類算法外部指標 R、 J、 FM、 P、 R、 F5 以及誤差平方和準則 J 值 ，它們隨著算法和數據集的改變而改變 ，通過 output 函數打印到界面上 。 結合演示平臺對多種聚類算法的比較 在沒有在數據集上運行之前，首先對各個聚類算法在 穩(wěn)定性（是否多次運行結果一樣） 、輸入參數、處理不同數據類型數據能力 這三個對于本文用到的聚類算法可以分析的方面 進行比較 ，總結在表 32。 表 32 實驗前算法分析 算法名稱 穩(wěn)定性 屬性種類 輸入參數 kmeans 不穩(wěn)定 只能處理數值屬性數據 參數 k AP 算法 穩(wěn)定 可處理任意屬性 參數 p DBSCAN 算法 穩(wěn)定 可處理任意屬性 參數 ? fdp 算法 穩(wěn)定 可處理任意屬性 k (可不用 )、 percent 本文使用的粒子群聚類算法 不穩(wěn)定 只能處理數值屬性數據 參數 k AGNES 算法 穩(wěn)定 可處理任意屬性 參數 k 在有數據集情況下 ，本文設計兩類實驗。一類主要針對幾種特殊形狀的二維數據集，可以通過肉眼直觀判斷聚類結果的好壞，另一類涉及高維數據集和無法用肉眼判斷的經典數據集 iris，通過 外部指標和簇內平方和準則評價聚類質量 。 浙江工業(yè)大學本科畢業(yè)設計論文 22 （ a） kmeans 算法 （ b） AP算法 （ c） DBSCAN 算法 （ d） FDP算法 （ a）粒子群聚類算法 （ b） AGNES算法 圖 33 6 種算法在 Spiral 上的運用效果 浙江工業(yè)大學本科畢業(yè)設計論文 23 對 Spiral 分別應用 6 中算法的結果如圖 33。 從上圖可以看出只有 DBSCAN 算法和fdp 算法三者準確的得出了聚類結果，而其余 4 個算法似乎犯了同一個錯誤，就是在找到 認為的中心后，將其余的點劃分給離開它們最近的聚類中心。 fdp 算法帶有一些基于密度的思想，可見基于密度的算法可以發(fā)現(xiàn)環(huán)形簇。本文還發(fā)現(xiàn)一個問題， kmeans 算法和粒子群算法均以誤差平方和準則函數作為目標函數進行優(yōu)化，但是 Spiral 數據集的天然劃分的誤差平方和為 遠遠大于 kmeans 和粒子群算法得到的聚類結果，可見誤差平方和準則函數在這里作為評價聚類算法的指標并不合適。 對 Jain 分別應用 6 中算法的結果如圖 34。 （ a） kmeans算法 （ b） AP算法 （ c） DBSCAN算法 （ d） FDP算法 浙江工業(yè)大學本科畢業(yè)設計論文 24 （ a）粒子群聚類算法 （ b） AGNES算法 圖 34 6 種算法在 Jain 上的運用效果 從上圖可以看出， fdp 算法和 agnes 算法得到的結果還算滿意， 而其它算法卻無法取得滿意的結果，這是由于原數據點的分布造成的，在上一個環(huán)中數據之間的間隔大于了兩個環(huán)之間的距離，從而使得 DBSCAN 束手無策， kmeans、粒子群聚類則