【文章內容簡介】 敗。聚類的有效性檢驗可 以說是一種反饋機制，根據(jù)有效性檢驗結果，需要對聚類的其它三個環(huán)節(jié)進行調整，從而獲得滿足問題要求的聚類結果。 聚類分析的作用 聚類分析旨在無類別標簽的訓練樣本條件下，根據(jù)數(shù)據(jù)本身的特征分布提煉出數(shù)據(jù)的內在的模式或結構?？偟膩碚f它主要有三個作用 [13]。 1) 聚類本身是人類學習的一種重要方式。在沒有人指導的情況下，人類可以根據(jù)自己的實踐經(jīng)驗總結，對不同的事物進行分門別類。對于某些 2 維數(shù)據(jù)人類自己可以通過觀察對其進行分類，但對于更高維數(shù)據(jù)人類就束手無策了。借助聚類分析可以通過計浙江工業(yè)大學本科畢業(yè)設計論文 3 算機運行一定算法對更高維 數(shù)據(jù)進行分門別類，從而拓展人類對數(shù)據(jù)的認知。 2) 有時獲得數(shù)據(jù)的類別信息還不是人類的最終目的。數(shù)據(jù)中的一些更深入的模式信息還需要進一步挖掘。面對復雜的數(shù)據(jù)和問題，在聚類的結果上運用其它的數(shù)據(jù)挖掘技術，不僅可以提高其它挖掘方法的效率，而且可以提高其挖掘的可靠性。 3) 聚類分析還可以用于孤立點的檢測。有時進行聚類分析不是為了將相似的對象聚集在一起，而是為了將某個異常的對象從數(shù)據(jù)集中分離出來。比如可用于檢測工業(yè)控制中由多個變量引起的異常 [4]。 聚類算法的國內外發(fā)展現(xiàn)狀 聚類分析的主要研究對象是聚類算法，也是本 文研究的主要對象。在過去的 50 多年，人們持續(xù)不斷的研究聚類算法，提出和發(fā)表了大量的聚類算法，它大致的 分類 如圖1 所示 [5]。 圖 12 聚類算法 分類 [5] 由于聚類問題是一個病態(tài)問題，目前為止提出的包括以上算法在內的算法都只能解決一部分的聚類問題。問題對象的改變，很多算法就不再適用 ，或者性能很差 。所有算浙江工業(yè)大學本科畢業(yè)設計論文 4 法在可伸縮性、算法效率、處理不同類型屬性的能力、發(fā)現(xiàn)任意形狀的簇、輸入?yún)?shù)數(shù)量最小化、初始敏感性、高維性、處理噪聲能力、可解釋性等方面存在或多或少的問題[67]。 聚類算法演示平臺 研究目的 和意義 隨著硬件產(chǎn)能的提升，傳感器、存儲器的大量應用，積累了大量的可用于數(shù)據(jù)分析的數(shù)據(jù)。人們提出了各種各樣的聚類問題，針對這些聚類問題，又相應的提出了各種各樣的聚類算法。一方面，這些算法都只能解決某一類問題，針對一個具體的聚類問題，人們面臨大量的可選擇的聚類算法，這往往令人無所適從，由此帶來很大的工作量。另一方面，開發(fā)一個新的聚類算法往往需要和已有的典型聚類算法進行比較。開發(fā)一個可擴展其它算法，帶有針對典型數(shù)據(jù)集的演示功能的聚類算法演示平臺可以很好的解決這兩個問題，勢必給聚類問題的解決，聚類算法的研發(fā)帶來很 大的幫助。本論文的主要工作就是基于 R 語言開發(fā)這樣一個具有實用價值的多種聚類算法演示平臺。 論文框架 論文第一章介 紹聚類問題的背景與意義以及論文的目的和框架。第二章主要介紹多種 聚類算法演示平臺用到的聚類算法，包括基于劃分的 kmeans、 AP 算法、基于密度的 DBSCAN、和基于層次的 AGENS、基于粒子群的聚類算法以及發(fā)表在 14 年 science雜志上的 FDP 算法。第三章主要介紹利用 Rstudio 公司開發(fā)的 shiny 包實現(xiàn)交互式演示平臺以及利用該平臺對第二章提到的算法進行比較分析。第四章介紹基于聚類分 析的NBA 籃球運動員位置分類。第 五 章對本文的研究情況進行總結并展望。 聚類算法研究工具 —— R 語言和 Rstudio R 語言是一個有著強大統(tǒng)計分析及作圖功能的軟件系統(tǒng)，在 GNU 下免費發(fā)行，最先由 Ross Ihaka 和 Robert Gentleman 共同創(chuàng)立，現(xiàn)在由 R 開發(fā)核心小組（ R Development Core Team）維護，他們的開發(fā)完 全出于自愿、工作努力負責，將全球優(yōu)秀的統(tǒng)計應用軟件打包提供給我 們共享。 2020 年 用戶成為成長最快的語言之一， 已經(jīng)在數(shù)據(jù)挖掘的各個領域得到成功應用。 R 的開源免費和 統(tǒng)計背景使得 R 和其它語言相比在處理數(shù)據(jù)、學習聚類方面有很大優(yōu)勢。 Rstudio 是由 Rstudio 公司開發(fā)的 R 語言集成開發(fā)環(huán)境（ IDE）。它包括支持直接運浙江工業(yè)大學本科畢業(yè)設計論文 5 行代碼的控制臺和語法高亮編輯器，以及用于畫圖、查看歷史記錄、調試和工作空間管理的工具。它有商業(yè)版本和開源版本兩個。實測表明是一個用于 R 語言開發(fā)的極棒開發(fā)環(huán)境。 浙江工業(yè)大學本科畢業(yè)設計論文 6 第 2 章 多種聚類算法 研究 本章介紹本文開發(fā)的多種聚類算法演示平臺用到的 六種 聚類算法 ， 包括基于劃分的kmeans 算法、基于密度的 DBSCAN 算法、基于層次的 AGNES 算法、基于優(yōu)化的粒子群聚 類算法和 分別在 07 年和 14 年發(fā)表在 science 雜志上的 AP算法和 FDP 算法。 通過學習這些算法的相關文獻，將它們總結如下。 kmeans 算法 kmeans 算法是典型的基于劃分的聚類算法?；趧澐值姆椒ㄔ诮o定的含有 n 個數(shù)據(jù)對象的數(shù)據(jù)集上，構建 k 個劃分，往往是首先創(chuàng)建一個初始劃分，然后采用一種迭代重定位技術，嘗試通過對象在劃分間移動來不斷改進劃分。在這個迭代過程中， kmeans優(yōu)化以下誤差平方和準則函數(shù)作為改進目標。 假設 n 個樣本 ? ?1, 2, ,Nix R i n?? L 分為 k 類，對 1,2 ,jk? L 和 1,2,in? L ，定義： 1 , 0 , ij ij? ?? ?? 如 果 第 個 樣 本 屬 于 類否 則 (21) 則矩陣 ? ?= ?ijμ 具有如下性質： ? ? ? ?10 , 1 = 1 1 , 2 ,kij ijj in?? ????且 設 jn 表示第 j 類中所包含的樣本個數(shù)，則 ? ?1 1, 2 ,nj ijin j k????? 設 NjmR? 表示第 j 類的中心，則 ? ?1111 1 , 2 ,ni j i nij i j iniijixm x j kn??????? ? ?? ?? (22) 所以第 j 類的類內差異為 21()njij i jiJ x m?????μ 那么，整體類內差異 (誤差平方和準則 )為 ? ? 21 1 1() k k njW ij i jj j iJ J x m?? ? ?? ? ?? ? ?μ μ (23) kmeans 算法的具體步驟如表 21 浙江工業(yè)大學本科畢業(yè)設計論文 7 表 21 kmeans 算法 ? 初始化：隨機選擇 k 個數(shù)據(jù)元素作為 k 個簇的均值 1, 2 ,Njm R j k?? ? 循環(huán)，直到 k 個均值都不再變化為止： ? ?1111 1 a r g m in , 1 1 1 , 2 ,i j iljknij i nij ij iniijifo r i to nl x m ue n d fo rxm x j kn??????????? ? ?? ? ????μ 0 ? 輸出 ?μ AP 算法 Affinity Propagation (AP)聚類算法 [89]是 Frey 等人 2020 提出的一種聚類算法，提出以來，一直受到研究領域的廣泛關注。 從類型上看，它也是一種基于劃分的算法。 AP算法本質上是 一種基于因子圖的信念傳播和最大化算法。它根據(jù) N 個數(shù)據(jù)點之間的相似度進行聚類，這些相似度可以是對稱 的，即兩個數(shù)據(jù)點互相 之間 相似度一樣（如歐式距離）；也可以是不對稱的，即兩個數(shù)據(jù)點互相之間的相似度不等。這些相似度組成 N N 的相似度矩陣 S（其中 N 為 N 個數(shù)據(jù)點）。 可見 AP 算法對數(shù)據(jù)點之間相似度的度量非常的寬泛，不像 kmeans 一樣僅使用 歐式距離作為相似度度量。 但是本文聚類算法演示平臺用到的 AP 算法仍然以歐式距離作為相似度度量方式。 AP 算法事先不需要指定聚類數(shù)目，而是將所有數(shù)據(jù)點都作為潛在的聚類中心，稱之為 exemplar，并以 S 的對角線上的 N 個值 ,iiS 作為每 個數(shù)據(jù)點能否成為聚類中心的評價標準，并稱之為參考度（ preference），數(shù)據(jù)點 i 參考度越大，成為聚類中心可能性越大。參考度是 AP 算法用到的唯一一個人為參數(shù)，在沒有先驗知識的前提下，通常每個數(shù)據(jù)點的參考度相同，且根據(jù)相似度的分布取值，該參數(shù)的大小很大程度上影響了最終簇數(shù)目的多少， preference 越大，簇數(shù)目越多。 AP 算法中傳遞兩種類型的消息：從點 i 發(fā)送到候選聚類中心 k 的數(shù)值消息 ,ikr 和從候選聚類中心 k 發(fā)送到 i 的數(shù)值消息 ,ika 。這里 ,ikr 反映 k 點作為 i 點的聚類中心是否合浙江工業(yè)大學本科畢業(yè)設計論文 8 適，而 ,ika 反映 i 點選擇 k 作為其聚類中心的意愿程度。兩者分別被稱為吸引度和歸屬度。 ,ikr 和 ,ika 越強，則 k 點作為聚類中心的可能性越大， AP 算法通過迭代而不斷地更新每個點的吸引度和歸屬度，直到產(chǎn)生 m 個高質量的 exemplar，同時將其余的數(shù)據(jù)點分配到相應 的簇中。根據(jù)作者提供的 matlab 代碼， AP 算法的具體步驟如表 22。 表 22 AP 算法 ? 初始化：先計算 N 個點之間的相似度值，構成矩陣 S，選取 preference(一般取 S 的均值 ) ；設置一個最大迭代次數(shù)， 令 , 0ika ? 。 ? 循環(huán)，直到達到最大迭代次數(shù)或者聚類結果多次迭代不變： , , , 39。 , 39。39。 s .t . 39。m a x { }i k i k i k i kk k kr S a S?? ? ? , , 39。,39。 s . t . 39。 { , }m in 0 , m a x { 0 , }i k k k i ki i i ka r r?????????? , 39。,39。 s .t. 39。 m a x {0 , }k k i ki i kar?? ? ? 輸出 ,0i i i ira?? 的位置，把這些 i 作為聚類中心。然后將其它點依次賦值給最近的聚類中心。 AGNES 算法 AGNES(Agglomerative Nesting)算法是凝聚層次聚類算法?；趯哟蔚乃惴▽?shù)據(jù)對象組成一顆聚類的樹，根據(jù)層次分解是自底向上生成還是自頂向下生成，層次的聚類方法可以分為凝聚的和分裂的。由于分裂的層次聚類算法，復雜度高，可伸縮性差，本文選擇更常用的凝聚聚類算法 AGNES 加入算法演示平臺。 AGNES 算法中心思想：首先將每個樣本看成一個簇，然后根據(jù)一定連接方式（是一種簇間相似度的衡量方式）將最相似的簇合成一個簇，這個過程迭代進行直到滿足一定終止條件。在這里首先介紹不同的連接方式下簇間相似度的度量方式。 （ 1）單連接 兩個簇之間的距離由兩個簇所有連接中最短的那個決定： ? ? ? ? , , m a x ,ijij x C y Cd C C d x y??? (24) （ 2）全連接 浙江工業(yè)大學本科畢業(yè)設計論文 9 兩個簇之間的距離由兩個簇所有連接中最長的那個決定： ? ? ? ? , , m in ,ijij x C y Cd C C d x y??? (25) （ 3）平均連接 兩個簇之間的距離由兩個簇的所有連接的平均長度決定： ? ? ? ? , 1, , ijij x C y Cijd C C d x ynn ??? ? (26) 在以上連接方式的基礎上，給出 AGNES 算法如表 23。 表 23 AGNES 算法 ? 初始化：每個樣本作為一個單獨的簇， ? ?, 1, , 。iiC x i n?? 每個簇的樣本數(shù)1in? 計 算任意兩個樣本之間的距離，構成相異度矩陣 ? ?? ?,ij i j nnD d x x ???D，簇數(shù)目 kn? 。 ? 循環(huán)，直到聚類終止條件為止： 尋找距離矩陣 D 中上三角矩陣元素的最小值 ijD 刪除簇 iC 和 jC 增加新的簇 , , 1 。q i j q i jC C C n n n k k? ? ? ? ? 根據(jù)單連接方式更新距離矩陣 D ? 輸出：剪枝后得到 ，簇 ? ?1,kCC。 上述的終止條件可以是預定簇數(shù)目、距離閾值（因為越往后簇間的距離越大）、最優(yōu)聚類（某種準則）。 本文的多種算法演示平臺，以預定簇數(shù)目為終止條件。 DBSCAN 算法 DBSCAN 算法是典型的基于密度的聚類算法?；诿芏鹊木垲愃惴ㄓ胁灰粯拥木垲愃悸泛拖?