【正文】 算法的目的就是要過濾低密度區(qū)域，找到稠密樣本點。該算法涉及一些新的概念： （ 1） ? 鄰域：給定對象半徑為 ? 內(nèi)的區(qū)域稱為該對象的 ? 領(lǐng)域； （ 2）核對象：如果一個對象 ? 領(lǐng)域內(nèi)的樣本點數(shù)大于等于事先給定的最小樣本點數(shù) MinPts，則稱該對象為核對象。 （ 4）密度可達(dá)：對于樣本集合 D，給定一串樣本點 1 2 1, , , nnp p p p p q p?? ，假如對象 ip 從 1ip? 出發(fā)直接密度可達(dá)，那么對象 q 從對象 p 密度可達(dá)。 DBSCAN 的中心思想是找到密度相連的最大集合。 表 24 DBSCAN 算法 ? 初始化：半徑 ? ；給定對象成為核心對象的 ? 領(lǐng)域內(nèi)最少點數(shù) MinPts； 集合 D ? 循環(huán)，直到所有輸入點都判斷完畢 判斷輸入點是否為核心對象。算法提出者是 Alessandro Laio 和 Alex Rodriguez，之所以在這里提到他們的名字是因為本文作者覺得他們提出的算法非常的浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 11 漂亮。 本文認(rèn)為 FDP 算法的核心思想有兩點，一是對聚類中心的刻畫，作者認(rèn)為聚類中心同時滿足兩點， (1)本身密度大，它被密度均不超過它的鄰居包圍； (2)與其他密度更大的數(shù)據(jù)點之間的“距離”更大。 表 25 FDP 算法 ? 初始化：設(shè)定 cd （使得每個數(shù)據(jù)點的鄰居數(shù)為所有數(shù)據(jù)點 的 12%）。 ? 循環(huán)，直到所有數(shù)據(jù)點都計算完畢 計算每個點的 rho 和 delta，記錄每個點中距離其最近的密度比其大的點的標(biāo)號。根據(jù)rho 的順序依次將非中心點劃分給比它密度大的最近的點。 根據(jù)作者提供的 matlab 程序 [11]和網(wǎng)絡(luò)上相關(guān)材料，嘗試描述算法，在這之前先介紹幾個概念。對于 S 中的每個數(shù)據(jù)點可以為其定義局部密度 rho 和與聚類中心的距離 delta。 (2) 每個點與聚類中心的距離 delta。 粒子群 聚類 算法 粒子群聚類算法是近年來應(yīng)用方興未艾的一類基于優(yōu)化的聚類算法 [12]。另一種是將優(yōu)化算法應(yīng)用到已有其它聚類算法的聚類過程之中。 粒子群算法，將優(yōu)化問題的解看做搜索空間中的一只鳥，即“粒子”。每個粒子都將在解空間中運動，并由運動速度決定其飛行方向和距離。粒子群算法核心是以下兩個公式。 ( ) .1 * ( ) ( ( ) . ( ) . )2 * ( ) ( . ( ) . )P a r tic le i v e lo c ity w P a r tic le i v e lo c ityh r a n d p i lo c a tio n P a r tic le i lo c a tio nh r a n d g lo c a tio n P a r tic le i lo c a tio n??? (210) ( ) . ( ) . ( ) . 39。 用粒子群算法直接求解聚類問題也有兩種思路，一種是以聚類結(jié)果為解，一種是以聚類中心的集合為解。適應(yīng)度由下面公式表示 11 / 1 / ( , )ijkijj x cfi tn e s s J d x x???? ?? (212) 詳細(xì)算法見表 26 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 13 表 26 粒子群聚類算法 ? 初始化：設(shè)置聚類數(shù)目和粒子數(shù)目，對每個粒子，將每個數(shù)據(jù)點指派為某一類，并計算各類聚 類中心，作為粒子的位置編碼。 ? 循環(huán)，直到達(dá)到設(shè)定迭代次數(shù) 根據(jù)公式更新所有粒子的速度和位置。 計算新的聚類中心，更新粒子適應(yīng)度，個體最佳位置 p(i)和種群最佳位置 p。 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 14 第 3 章 多種 聚類算法演示平臺 實現(xiàn) 需求 分析 隨著硬件產(chǎn)能的提升，傳感器、存儲器的大量應(yīng)用，積累了大量的可用于數(shù)據(jù)分析的數(shù)據(jù)。一方面，這些算法都只能解決某一類問題，針對一個具體的聚類問題，人們面臨大量的可選擇的聚類算法，這往往令人無所適從，由此帶來很大的工作量。開發(fā)一個可擴(kuò)展其它算法，帶有針對典型數(shù)據(jù)集的演示功能的聚類算法演示平臺可以很好的解決 這兩個問題，勢必給聚類問題的解決，聚類算法的研發(fā)帶來很大 的幫助。其中算法、數(shù)據(jù)集應(yīng)該要可擴(kuò)展。利用 shiny 包制作基于網(wǎng)頁的互動應(yīng)用。 用 C++引用 RInside 和 Qt 制作界面。調(diào)研四種方法后，發(fā)現(xiàn) shiny 最容易上手，決定基于 shiny 包實現(xiàn)該演示平臺。 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 15 詳細(xì)設(shè)計 shiny 包簡介 Shiny 是 Rstudio 公司開發(fā)的一個 用于 R 語言的 開源軟件包（也有專業(yè)收費版本）。它最終可以生成一個網(wǎng)頁，能實現(xiàn) HTML 語言的大部分功能和 其它 HTML 語言無法實現(xiàn)的功能。 、 是 shiny 軟件的框架， 負(fù)責(zé)生成網(wǎng)頁的交互式界面，包括布局、文字、控件等。用戶觸發(fā)的影響，都 會經(jīng)過 命名的 input 類數(shù)據(jù)傳遞給 繼而影響 中相應(yīng)代碼的執(zhí)行。 Shiny 軟件可用的控件和 提供的控件類似，有下拉菜單、單選框、多選框、按鈕等。使用的源文件可直接放置在 或者通過相對路徑可訪問的文件夾下 ，代碼中可經(jīng)過相對路徑訪問 。通過 Rstudio 上傳自己的軟件，可以通過 賬號在Rstuido 提供的后臺管理自己所有的 shiny 網(wǎng)站。本文嘗試選擇了一些有代表性的數(shù)據(jù)，如表 31。 圖 31 Spiral/Jain/Flame/Aggregation 數(shù)據(jù)集（從左至右，從上到下依次為Spiral/Jain/Flame/Aggregation 數(shù)據(jù)集） 之所以并沒有選用混合屬性的數(shù)據(jù)或者其他非數(shù)值屬性的數(shù)據(jù)，一方面是因為處理混合屬性的數(shù)據(jù)，需要重新定義 數(shù)據(jù)點之間 相似度 ，且相似度的定義方法又各有技巧。 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 17 當(dāng)選擇完以上數(shù)據(jù)集之后，從互聯(lián)網(wǎng)上下載這些數(shù)據(jù)集， 使得最后一列為類別屬性。 然后通過用戶選擇 執(zhí)行代碼 讀入這些數(shù)據(jù)集 以供 使用。 11 1 111fpi if ipn nf npx x xx x xx x x???????? (31) 聚類結(jié)果評價 及實現(xiàn) 對聚類效果進(jìn)行評價的研究稱為聚類有效性分析（ Clusetr Validity）。通常，在聚類有效性分析研究中評價聚類算法得到的聚類結(jié)果 C 的方法主要有三類。 (2) 內(nèi)部標(biāo)準(zhǔn) (Internal Criteria)：用參與聚類的樣本 (n 個數(shù)據(jù)對象 )來評價 C，比如采用 C 中各個簇的誤差平方和，即 kmean、本文 pso 聚類的目標(biāo)函數(shù)。 一般來說，聚類結(jié)果是用外部準(zhǔn)則來評價的 [20]。為了引出常見的幾種外部準(zhǔn)則，引入一個預(yù)期的結(jié)果簇結(jié)構(gòu)。 (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 的聚類效果越好。 在信息檢索中常見的指標(biāo) 還有 有 purity 和 Fmeasure 值，因為 Fmeasure 值使用更加廣泛，區(qū)分能力也更強(qiáng)，所以在這里具體介紹一下 [14]。聚類可能產(chǎn)生兩類錯誤， FP 錯誤將不相似的文檔劃分到同一個簇中， FN 錯誤將相似的文檔劃分到不同的簇中。 R 表示召回率， R 的通俗解釋是檢索出的相關(guān)文檔數(shù) 和文檔庫中所有相關(guān) 文檔數(shù) 的比率，衡量的是查全率 。因為在實際應(yīng)用中，F(xiàn)N 這種錯誤往往 比 FP 錯誤更加嚴(yán)重。 R 語言中對聚類結(jié)果的評價可以通過 clv、 clusterCrit 兩個包實現(xiàn)，這兩個包的作者提供了包括本文使用的除 F 值以外 5 個外部指標(biāo)在內(nèi)的 各類 評價方法的 R 語言實現(xiàn)。并設(shè)計當(dāng)用戶觸發(fā)選擇時，顯示當(dāng)前指標(biāo)的值。 結(jié)果向量的第 i 個位置表示第 i 個數(shù)據(jù)點，第 i 個位置的值表示第 i 個數(shù)據(jù)點所屬的類標(biāo)號 。 本文在深入學(xué)習(xí)第二章列舉的 6 個算法之后，結(jié)合相關(guān)資料用 R 語言自主編寫了AP 算法、 FDP 算法和粒子群聚類算法，代碼見附錄，用 R 語言軟件包實現(xiàn)了 dbscan、kmeans 和 AGNES 算法。 kmeans 是 R 語言軟件自帶的算法，針對 Spiral 數(shù)據(jù)集只需輸入 kmeans(Spiral, 3)，即可返回一個 kmeans 類，它是一個列表，其中包含一個屬性 cluster，可用 kmean(Spiral, 3)$cluster 提取 。 DBSAN 算法的 Minpts 參數(shù)默認(rèn)設(shè)置為 5，也就是 核心對象 ? 領(lǐng)域中的點數(shù) 至少為 5 個 ， ? 領(lǐng)域的長度用戶通過參數(shù)進(jìn)行設(shè)置。 AGNES 算法 R 語言也沒有自帶，但是 cluster 包提供了這一算法 ， AGNES 算法可以在沒有參數(shù)輸入的情況下生成一顆聚類樹。因此只需用 cutree(agnes(Spiral), 3)就可以得到 Spiral 的聚類結(jié)果向量。其中 s 是數(shù)據(jù)矩陣， p 代表參考度相對相似度的分位數(shù)（每個數(shù)據(jù)點參考度相同）。 對于 FDP 算法，根據(jù)作 者提供的 matlab 程序 [11]和網(wǎng)絡(luò)上相關(guān)材料結(jié)合 R 語言特點，編寫 FDP 算法 fdpcluster function(datam, noc, percent, method=euclidean, p=2)，其中參數(shù) datam 表示輸入的數(shù)據(jù)矩陣， noc 表示簇的數(shù)目， percent 用于確定 cd ， method=euclidean表示默認(rèn)采用歐幾里德距離， p=2 用于計算計算明氏距離，具體參見附錄 2。 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 20 對于 PSO 聚類，根據(jù)文獻(xiàn) [16]和網(wǎng)絡(luò)上相關(guān)材料結(jié)合 R 語言特點，編寫粒子群聚類算法 psocluster function(datam, centerNum, iterNum=20)，詳見附錄 3，其中 datam 表示數(shù)據(jù)矩陣， centerNum 表示簇的數(shù)目， iterNum 表示迭代次數(shù)，函數(shù)中粒子數(shù)量選擇 20 個。同樣對 Spiral 數(shù)據(jù)應(yīng)用 pso算法，可以通過 psocluster(Spiral, 3)idx 得到結(jié)果向量。 圖 32 演示平臺界面 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 21 網(wǎng)頁 發(fā)布在 由四部分組成， 用黑框框出， 第一部分是算法和數(shù)據(jù)集選擇窗口，算法包括上文提到的6 中算法，數(shù)據(jù)集包括上文提到的 7 種數(shù)據(jù)集，均可通過下拉菜單選擇 ，通過 input 傳入 ；第二部分是圖形演示窗口，從上到下，依次是當(dāng)前算法的計算結(jié)果 圖 和數(shù)據(jù)集的實際分布 圖，圖形下方分別是結(jié)果向量和數(shù)據(jù)自然結(jié)果向量，均通過 output 輸出，可供用戶實時查看當(dāng)前算法對每個數(shù)據(jù)對象的聚類情況 ；第三部分是參數(shù)選擇部分， 通過輸入框輸入，通過 input 傳入， 每次參數(shù)的改變都會 引起算法 重新計算并繪圖；第四部分是上文提到的 6 個聚類算法外部指標(biāo) R、 J、 FM、 P、 R、 F5 以及誤差平方和準(zhǔn)則 J 值 ，它們隨著算法和數(shù)據(jù)集的改變而改變 ，通過 output 函數(shù)打印到界面上 。 表 32 實驗前算法分析 算法名稱 穩(wěn)定性 屬性種類 輸入?yún)?shù) kmeans 不穩(wěn)定 只能處理數(shù)值屬性數(shù)據(jù) 參數(shù) k AP 算法 穩(wěn)定 可處理任意屬性 參數(shù) p DBSCAN 算法 穩(wěn)定 可處理任意屬性 參數(shù) ? fdp 算法 穩(wěn)定 可處理任意屬性 k (可不用 )、 percent 本文使用的粒子群聚類算法 不穩(wěn)定 只能處理數(shù)值屬性數(shù)據(jù) 參數(shù) k AGNES 算法 穩(wěn)定 可處理任意屬性 參數(shù) k 在有數(shù)據(jù)集情況下 ，本文設(shè)計兩類實驗。 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 22 （ a） kmeans 算法 （ b） AP算法 （ c） DBSCAN 算法 （ d） FDP算法 （ a）粒子群聚類算法 （ b） AGNES算法 圖 33 6 種算法在 Spiral 上的運用效果 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 23 對 Spiral 分別應(yīng)用 6 中算法的結(jié)果如圖 33。 fdp 算法帶有一些基于密度的思想，可見基于密度的算法可以發(fā)現(xiàn)環(huán)形簇。 對 Jain 分別應(yīng)用 6 中算法的結(jié)果如圖 3