【正文】 ? ? ? ? , , m a x ,ijij x C y Cd C C d x y??? (24) （ 2）全連接 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 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) 在以上連接方式的基礎(chǔ)上，給出 AGNES 算法如表 23。基于密度的聚類算法有不一樣的聚類思路和相似度衡量方式，這樣的相似度度量方式有利于發(fā)現(xiàn)各種形狀的簇，其主要思想是以空間中的一個樣本為中心，單位體積內(nèi)的樣本個數(shù)稱為該點(diǎn)的密度，從直觀上看，簇內(nèi)樣本的密度較大，簇間樣本的密度較小。 （ 5）密度相連：對于樣本集合 D 中任意一點(diǎn) o，如果存在對象 p 到對象 o 密度可達(dá)，對象 q 到對象 o 密度可達(dá)，那么對象 q 和對象 p 密度相連。二是和 kmeans、 AP 算法不同，它并不是在找到聚類中心之后將其它數(shù)據(jù)點(diǎn)劃分到鄰近的聚類中心，而是將其它數(shù)據(jù)點(diǎn)從密度大的開始，依次劃分到與它相鄰的密度比它更大的聚類中心?？紤]待聚類數(shù)據(jù)集 1{ } , {1, 2 , , }Ni i sS x I N???為相應(yīng)指標(biāo)集， ,ijd 表示數(shù)據(jù)點(diǎn) ix 和 jx 之間的（某種）距離。粒子群算法是一種有效的全局尋優(yōu)算法，最早由美國的 Kennedy 和 Eberhart 于 1995 年受到鳥群遷徙行為提出，通過群體中粒子間的合作和競爭產(chǎn)生的群體智能指導(dǎo)尋優(yōu)。P a r t i c l e i l o c a t i o n P a r t i c l e i l o c a t i o n P a r t i c l e i v e l o c i t y?? (211) 其中 ()pi 、 g 分別代表 每個粒子到達(dá)過的最佳位置和整個種群到達(dá)過的最佳位置， hh2 是兩個 對優(yōu)化結(jié)果有很大影響的 參數(shù)。 ? 循環(huán)，直到達(dá)到設(shè)定迭代次數(shù) ? 根據(jù)種群最佳位置，按最近鄰法則，輸出 簇 ? ?1,kCC。 概要設(shè)計 要基于 R 語言實現(xiàn)這樣一個交互式演示平臺， 通過求助網(wǎng)友發(fā)現(xiàn)至少有四種方法。Rstudio 公司的愿景 是希望通過 Shiny 提供一個為 R 語言服務(wù)的網(wǎng)頁應(yīng)用程序框架，這個框架可以使得用戶方便的通過使用 shiny 交互式的展示數(shù)據(jù)分析成果。軟件用到的圖片必須放在命名為 的文件夾中，以供 Shiny 調(diào)用。另一方面本文選用的聚類方法，是否能夠用于處理混合屬性或者非數(shù)值屬性，從算法本身就可以 大體 判斷。 (1) 外部標(biāo)準(zhǔn) (External Criteria)：用事先判定的聚類結(jié)構(gòu)來評價 C。本文聚類算法演示平臺使用了這三個統(tǒng)計量。 本文的多種聚類演示平臺取 5?? 。這里簡要介紹各算法實現(xiàn)方式。 對于 AP 算法，根據(jù)作者提供的支持材料 [15]中的 matlab 程序，寫出 它的 R 語言版本 iapcluster（ s, p=）函數(shù)，詳見附錄 1。 演示平臺實現(xiàn) 結(jié)果 通過文獻(xiàn) [17] 上的例子和教程，結(jié)合聚類算法演示的需要開發(fā)了 clustering algorithms demonstration 網(wǎng)頁，基本界面如圖 32。本文還發(fā)現(xiàn)一個問題， kmeans 算法和粒子群算法均以誤差平方和準(zhǔn)則函數(shù)作為目標(biāo)函數(shù)進(jìn)行優(yōu)化，但是 Spiral 數(shù)據(jù)集的天然劃分的誤差平方和為 遠(yuǎn)遠(yuǎn)大于 kmeans 和粒子群算法得到的聚類結(jié)果，可見誤差平方和準(zhǔn)則函數(shù)在這里作為評價聚類算法的指標(biāo)并不合適。 從上圖可以看出只有 DBSCAN 算法和fdp 算法三者準(zhǔn)確的得出了聚類結(jié)果，而其余 4 個算法似乎犯了同一個錯誤，就是在找到 認(rèn)為的中心后，將其余的點(diǎn)劃分給離開它們最近的聚類中心。且涉及 psocluster 函數(shù)的返回值即為結(jié)果向量。因此要得到結(jié)果向量還要對它進(jìn)行剪枝，R 語言基礎(chǔ)包 stats 提供了剪枝算法 cutree(tree, number)， number 確定最后結(jié)果中簇的數(shù)目，且 cutree 的返回值恰好是結(jié)果向量類型。這樣的封裝有利于繪圖和結(jié)果呈現(xiàn)。 相對 Rand Statistic 給兩類錯誤同樣的權(quán)值，這里通過 ? 給兩類錯誤不同的權(quán)值，通常取 1?? 從而給召回率更多的權(quán)值。 12{ , , , }sP P P P? (32) 考慮 X 中任意兩個互異的數(shù)據(jù)對象 ( , )ijxx ，按照 ix 和 jx 在 C 結(jié)構(gòu) (由聚類算法得到的 )和 P 結(jié)構(gòu)中是否屬于同一個簇，有以下四種 關(guān)系： 1. SS(TP)： ix 和 jx 在 C 結(jié)構(gòu)和 P 結(jié)構(gòu)屬于同一個簇 2. SD(FP)： ix 和 jx 在 C 結(jié)構(gòu)中屬于同一個簇，而在 P 結(jié)構(gòu)中屬于不同的簇 3. DS(FN)： ix 和 jx 在 C 結(jié)構(gòu)中屬于不同的簇，而在 P 結(jié)構(gòu)中屬于相同的簇 4. DD(TN)： ix 和 jx 在 C 結(jié)構(gòu)和 P 結(jié)構(gòu)屬于不同的簇 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 18 若記 , , ,abcd 分別表示 SS， SD， DS， DD 的關(guān)系數(shù)目，則根據(jù) , , ,abcd 的值，可以定義出不同的評價指標(biāo)，常見的有 [13]。聚類有效性分析本身也是很復(fù)雜的，最好是根據(jù)不同的問題和不同的聚類算法做具體的分析。 表 31 數(shù)據(jù)集 [21] 數(shù)據(jù)集名稱 維數(shù) 數(shù)值型 維 數(shù) 分類型 維數(shù) 類屬性數(shù) 數(shù)據(jù)量 Aggregation 2 2 0 7 788 Spiral 2 2 0 3 312 Jain 2 2 0 2 373 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 16 Flame 2 2 0 2 240 Iris 4 4 0 4 150 Dim032 32 32 0 16 1024 Dim128 128 128 0 16 1024 其中選擇了四個二維屬性的數(shù)據(jù)，可用于 像圖 31 一樣 作圖， 作圖程序見附錄， 從而形象化的演示聚類算法的有效性。 中代碼執(zhí)行的結(jié)果經(jīng)過 ouput 類數(shù)據(jù)傳遞給用戶界面，影響界面顯示。 最終確定用 shiny 的選擇框控件提供用戶選擇的算法類型和數(shù)據(jù)集類型，輸入框控件實現(xiàn)用戶的算法參數(shù)輸入，利用文本顯示用戶選擇的算法在數(shù)據(jù)集上應(yīng)用后的指標(biāo)顯示，利用圖形 (僅適用于二維數(shù)據(jù)集 )、文字分別顯示數(shù)據(jù)集的自然分布以及利用聚類算法后的結(jié)果分布。 結(jié)合上述目的，在演示平臺中，至少要包含三個部分，第一部分要提供用戶多個可選數(shù)據(jù)集；第二部分要提供用戶多種可選聚類算法；第三部分要針對用戶選擇的算法在用戶選擇的數(shù)據(jù)集上運(yùn)行并用相關(guān)指標(biāo)給出算法運(yùn)行的效果。 按照粒子聚類中心編碼，按照最近鄰法則，對每個數(shù)據(jù)點(diǎn)進(jìn)行聚類劃分。 ( ) . 39?；趦?yōu)化的算法主要有兩種應(yīng)用方式，一種是直接以聚類準(zhǔn)則或指標(biāo)，如 kmeans 算法用到的誤差平方和準(zhǔn)則函數(shù)，作為優(yōu)化算法的目標(biāo)函數(shù)， 因為 kmeans 有時不能找到全局最優(yōu)解。 ? 輸出：簇 ? ?1,kCC 。它是一種基于密度算 法和基于劃分算法的結(jié)合。 （ 3）直接密度可達(dá)：給定一個對象集合 D，核對象 p 的 ? 領(lǐng)域內(nèi)的樣本點(diǎn) q，稱對象 q 是從核對象 p 出發(fā)直接密度可達(dá)的。 本文的多種算法演示平臺，以預(yù)定簇數(shù)目為終止條件。 AGNES 算法中心思想：首先將每個樣本看成一個簇，然后根據(jù)一定連接方式（是一種簇間相似度的衡量方式）將最相似的簇合成一個簇，這個過程迭代進(jìn)行直到滿足一定終止條件。 { , }m in 0 , m a x { 0 , }i k k k i ki i i ka r r?????????? , 39。 表 22 AP 算法 ? 初始化：先計算 N 個點(diǎn)之間的相似度值，構(gòu)成矩陣 S，選取 preference(一般取 S 的均值 ) ；設(shè)置一個最大迭代次數(shù)， 令 , 0ika ? 。 但是本文聚類算法演示平臺用到的 AP 算法仍然以歐式距離作為相似度度量方式?；趧澐值姆椒ㄔ诮o定的含有 n 個數(shù)據(jù)對象的數(shù)據(jù)集上，構(gòu)建 k 個劃分，往往是首先創(chuàng)建一個初始劃分，然后采用一種迭代重定位技術(shù)，嘗試通過對象在劃分間移動來不斷改進(jìn)劃分。 R 的開源免費(fèi)和 統(tǒng)計背景使得 R 和其它語言相比在處理數(shù)據(jù)、學(xué)習(xí)聚類方面有很大優(yōu)勢。本論文的主要工作就是基于 R 語言開發(fā)這樣一個具有實用價值的多種聚類算法演示平臺。 圖 12 聚類算法 分類 [5] 由于聚類問題是一個病態(tài)問題，目前為止提出的包括以上算法在內(nèi)的算法都只能解決一部分的聚類問題。 2) 有時獲得數(shù)據(jù)的類別信息還不是人類的最終目的。聚類算法的性能、聚類算法和問題的匹配程度某種程度上決定了整個聚類分析過程的成敗。其中聚類有效性檢驗貫穿在整個聚類分析過程之中 [2]。 聚類分析的定義 數(shù)據(jù)聚類或者說聚類分析的目標(biāo)是發(fā)現(xiàn)一系列模式、點(diǎn)或者對象的天然的分組情況。同時，不僅是可利用的數(shù)據(jù)的量大量增長，類型也增多了（文本、圖像、視頻），包括 Email、博客、交易數(shù)據(jù)以及數(shù)以億計的網(wǎng)頁每天產(chǎn)生數(shù) TB 的新數(shù)據(jù)，而且這類數(shù)據(jù)都是松散的。 基本 要求 ： （ 1） 分析 現(xiàn) 有 聚類算法 及其優(yōu)缺點(diǎn) ；（ 2） 自主 設(shè)計 基于 R 語言 的 各種 聚類算法實現(xiàn)和調(diào)試 ；（ 3） 編寫 程序 實現(xiàn) 交互式 演示平臺，完成各種聚 類算法的性能比較和演示 ； （ 4） 仿真 實驗 利用UCI 數(shù)據(jù) 集驗證 平臺對各個聚類算法的演示和效率評價 。由于聚類問題的重要性，近 50 年提出了各種各樣的算法，又因為聚類問題屬于一個病態(tài)問題，聚類算法的效果和實際數(shù)據(jù)對象有很大的相關(guān)性，目前還沒有一個算法可以很好的解決所有的聚類問題，不同的算法有各自不同的優(yōu)缺點(diǎn)。 (ii)驗證性的或推理性的，指 研究者想要驗證適用于可用數(shù)據(jù)的假設(shè) /模型。iC i k? ? ? L b) 1 。對于同樣一組對象采用不同的特征聚類，結(jié)果可能是完全不同的，只有選擇和提取合適的特征，聚類過程才能得到所需要的結(jié)果?？偟膩碚f它主要有三個作用 [13]。 3) 聚類分析還可以用于孤立點(diǎn)的檢測。 聚類算法演示平臺 研究目的 和意義 隨著硬件產(chǎn)能的提升，傳感器、存儲器的大量應(yīng)用，積累了大量的可用于數(shù)據(jù)分析的數(shù)據(jù)。第三章主要介紹利用 Rstudio 公司開發(fā)的 shiny 包實現(xiàn)交互式演示平臺以及利用該平臺對第二章提到的算法進(jìn)行比較分析。它有商業(yè)版本和開源版本兩個。 從類型上看，它也是一種基于劃分的算法。 AP 算法中傳遞兩種類型的消息：從點(diǎn) i 發(fā)送到候選聚類中心 k 的數(shù)值消息 ,ikr 和從候選聚類中心 k 發(fā)送到 i 的數(shù)值消息 ,ika 。39。 m a x {0 , }k k i ki i kar?? ? ? 輸出 ,0i i i ira?? 的位置，把這些 i 作為聚類中心。 表 23 AGNES 算法 ? 初始化：每個樣本作為一個單獨(dú)的簇， ? ?, 1, , 。該算法根據(jù) 空間密度的差異，將簇看做是樣本空間中被低密度區(qū)域分隔開的高密度樣本區(qū)域。 DBSCAN 的中心思想是找到密度相連的最大集合。 表 25 FDP 算法 ? 初始化：設(shè)定 cd （使得每個數(shù)據(jù)點(diǎn)的鄰居數(shù)為所有數(shù)據(jù)點(diǎn) 的 12%）。對于 S 中的每個數(shù)據(jù)點(diǎn)可以為其定義局部密度 rho 和與聚類中心的距離 delta。 粒子群算法，將優(yōu)化問題的解看做搜索空間中的一只鳥，即“粒子”。 用粒子群算法直接求解聚類問題也有兩種思路，一種是以聚類結(jié)果為解，一種是以聚類中心的集合為解。 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 14 第 3 章 多種 聚類算法演示平臺 實現(xiàn) 需求 分析 隨著硬件產(chǎn)能的提升，傳感器、存儲器的大量應(yīng)用，積累了大量的可用于數(shù)據(jù)分析的數(shù)據(jù)。利用 shiny 包制作基于網(wǎng)頁的互動應(yīng)用。它最終可以生成一個網(wǎng)頁，能實現(xiàn) HTML 語言的大部分功能和 其它 HTML 語言無法實現(xiàn)的功能。使用的源文件可直接放置在 或者通過相對路徑可訪問的文件夾下 ，代碼中可經(jīng)過相對路徑訪問 。 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計論文 17 當(dāng)選擇完以上數(shù)據(jù)集之后，從互聯(lián)網(wǎng)上下載這些數(shù)據(jù)集， 使得最后一列為類別屬性。 (2) 內(nèi)部標(biāo)準(zhǔn) (Internal Criteria)：用參與聚類的樣本 (n 個數(shù)據(jù)對象 )來評價 C，比如采用 C 中各個簇的誤差平方和，即 kmean、本文 pso 聚類的目標(biāo)函數(shù)。 在信息檢索中常見的指標(biāo) 還有 有 purity 和 Fmeasure 值，因為 Fmeasure 值使用更加廣泛，區(qū)分能力也更強(qiáng)，所以在這里具體介紹一下 [14]。 R 語言中對聚類結(jié)果的評價可以通過