【正文】 r t i c l e i v e l o c i t y?? (211) 其中 ()pi 、 g 分別代表 每個(gè)粒子到達(dá)過(guò)的最佳位置和整個(gè)種群到達(dá)過(guò)的最佳位置， hh2 是兩個(gè) 對(duì)優(yōu)化結(jié)果有很大影響的 參數(shù)。粒子運(yùn)動(dòng)速度通過(guò)跟蹤粒子本身找到的最優(yōu)解和整個(gè)種群目前找到的最優(yōu)解來(lái)更新。粒子群算法是一種有效的全局尋優(yōu)算法，最早由美國(guó)的 Kennedy 和 Eberhart 于 1995 年受到鳥(niǎo)群遷徙行為提出，通過(guò)群體中粒子間的合作和競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)尋優(yōu)。 設(shè) 1{}Niiq? 表示 1{}Niirho ? 的一個(gè)降序排列下標(biāo)序，即它滿足 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)論文 12 12 Nq q qrho rho rho? ? ? (28) 那么定義 ,2m i n { } , 2m a x { } , 1ijjjiijqqqqqjdide lta rho i?????? ? ??? (29) 在以上基礎(chǔ)上可以得到 FDP 算法如表 25。考慮待聚類數(shù)據(jù)集 1{ } , {1, 2 , , }Ni i sS x I N???為相應(yīng)指標(biāo)集， ,ijd 表示數(shù)據(jù)點(diǎn) ix 和 jx 之間的（某種）距離。 ? 根據(jù)聚類數(shù)目選擇 rho 和 delta 乘積最大的 k 個(gè)數(shù)據(jù)點(diǎn)作為聚類中心。二是和 kmeans、 AP 算法不同，它并不是在找到聚類中心之后將其它數(shù)據(jù)點(diǎn)劃分到鄰近的聚類中心，而是將其它數(shù)據(jù)點(diǎn)從密度大的開(kāi)始，依次劃分到與它相鄰的密度比它更大的聚類中心。 找出核心對(duì)象的 ? 鄰域中所有直接密度可達(dá)點(diǎn) ? 循環(huán)，直到所有核心對(duì)象的 ? 領(lǐng)域都遍歷完畢 針對(duì)所有核心對(duì)象的 ? 領(lǐng)域所有直接密度可達(dá)點(diǎn)找到最大密度相連對(duì)象集合，中間設(shè)計(jì)一些密度可達(dá)對(duì)象的合并 ? 輸出：簇 ? ?1,kCC ,簇?cái)?shù)目 k FDP 算法 FDP 算法是本文對(duì)文獻(xiàn) [10]中的算法的稱呼。 （ 5）密度相連：對(duì)于樣本集合 D 中任意一點(diǎn) o，如果存在對(duì)象 p 到對(duì)象 o 密度可達(dá)，對(duì)象 q 到對(duì)象 o 密度可達(dá)，那么對(duì)象 q 和對(duì)象 p 密度相連。它將簇定義為高密度相連點(diǎn)的最大集合?；诿芏鹊木垲愃惴ㄓ胁灰粯拥木垲愃悸泛拖嗨贫群饬糠绞?，這樣的相似度度量方式有利于發(fā)現(xiàn)各種形狀的簇，其主要思想是以空間中的一個(gè)樣本為中心，單位體積內(nèi)的樣本個(gè)數(shù)稱為該點(diǎn)的密度，從直觀上看，簇內(nèi)樣本的密度較大，簇間樣本的密度較小。q i j q i jC C C n n n k k? ? ? ? ? 根據(jù)單連接方式更新距離矩陣 D ? 輸出：剪枝后得到 ，簇 ? ?1,kCC。 （ 1）單連接 兩個(gè)簇之間的距離由兩個(gè)簇所有連接中最短的那個(gè)決定： ? ? ? ? , , m a x ,ijij x C y Cd C C d x y??? (24) （ 2）全連接 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)論文 9 兩個(gè)簇之間的距離由兩個(gè)簇所有連接中最長(zhǎng)的那個(gè)決定： ? ? ? ? , , m in ,ijij x C y Cd C C d x y??? (25) （ 3）平均連接 兩個(gè)簇之間的距離由兩個(gè)簇的所有連接的平均長(zhǎng)度決定： ? ? ? ? , 1, , ijij x C y Cijd C C d x ynn ??? ? (26) 在以上連接方式的基礎(chǔ)上，給出 AGNES 算法如表 23?；趯哟蔚乃惴▽?shù)據(jù)對(duì)象組成一顆聚類的樹(shù)，根據(jù)層次分解是自底向上生成還是自頂向下生成，層次的聚類方法可以分為凝聚的和分裂的。 s .t. 39。,39。 , 39。 ,ikr 和 ,ika 越強(qiáng)，則 k 點(diǎn)作為聚類中心的可能性越大， AP 算法通過(guò)迭代而不斷地更新每個(gè)點(diǎn)的吸引度和歸屬度，直到產(chǎn)生 m 個(gè)高質(zhì)量的 exemplar，同時(shí)將其余的數(shù)據(jù)點(diǎn)分配到相應(yīng) 的簇中。參考度是 AP 算法用到的唯一一個(gè)人為參數(shù)，在沒(méi)有先驗(yàn)知識(shí)的前提下，通常每個(gè)數(shù)據(jù)點(diǎn)的參考度相同，且根據(jù)相似度的分布取值，該參數(shù)的大小很大程度上影響了最終簇?cái)?shù)目的多少， preference 越大，簇?cái)?shù)目越多。這些相似度組成 N N 的相似度矩陣 S（其中 N 為 N 個(gè)數(shù)據(jù)點(diǎn)）。 假設(shè) n 個(gè)樣本 ? ?1, 2, ,Nix R i n?? L 分為 k 類，對(duì) 1,2 ,jk? L 和 1,2,in? L ，定義： 1 , 0 , ij ij? ?? ?? 如 果 第 個(gè) 樣 本 屬 于 類否 則 (21) 則矩陣 ? ?= ?ijμ 具有如下性質(zhì)： ? ? ? ?10 , 1 = 1 1 , 2 ,kij ijj in?? ????且 設(shè) jn 表示第 j 類中所包含的樣本個(gè)數(shù)，則 ? ?1 1, 2 ,nj ijin j k????? 設(shè) NjmR? 表示第 j 類的中心，則 ? ?1111 1 , 2 ,ni j i nij i j iniijixm x j kn??????? ? ?? ?? (22) 所以第 j 類的類內(nèi)差異為 21()njij i jiJ x m?????μ 那么，整體類內(nèi)差異 (誤差平方和準(zhǔn)則 )為 ? ? 21 1 1() k k njW ij i jj j iJ J x m?? ? ?? ? ?? ? ?μ μ (23) kmeans 算法的具體步驟如表 21 浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)論文 7 表 21 kmeans 算法 ? 初始化：隨機(jī)選擇 k 個(gè)數(shù)據(jù)元素作為 k 個(gè)簇的均值 1, 2 ,Njm R j k?? ? 循環(huán)，直到 k 個(gè)均值都不再變化為止： ? ?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 提出的一種聚類算法，提出以來(lái)，一直受到研究領(lǐng)域的廣泛關(guān)注。 通過(guò)學(xué)習(xí)這些算法的相關(guān)文獻(xiàn)，將它們總結(jié)如下。它包括支持直接運(yùn)浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)論文 5 行代碼的控制臺(tái)和語(yǔ)法高亮編輯器，以及用于畫(huà)圖、查看歷史記錄、調(diào)試和工作空間管理的工具。 聚類算法研究工具 —— R 語(yǔ)言和 Rstudio R 語(yǔ)言是一個(gè)有著強(qiáng)大統(tǒng)計(jì)分析及作圖功能的軟件系統(tǒng)，在 GNU 下免費(fèi)發(fā)行，最先由 Ross Ihaka 和 Robert Gentleman 共同創(chuàng)立，現(xiàn)在由 R 開(kāi)發(fā)核心小組（ R Development Core Team）維護(hù)，他們的開(kāi)發(fā)完 全出于自愿、工作努力負(fù)責(zé)，將全球優(yōu)秀的統(tǒng)計(jì)應(yīng)用軟件打包提供給我 們共享。第二章主要介紹多種 聚類算法演示平臺(tái)用到的聚類算法，包括基于劃分的 kmeans、 AP 算法、基于密度的 DBSCAN、和基于層次的 AGENS、基于粒子群的聚類算法以及發(fā)表在 14 年 science雜志上的 FDP 算法。另一方面，開(kāi)發(fā)一個(gè)新的聚類算法往往需要和已有的典型聚類算法進(jìn)行比較。所有算浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)論文 4 法在可伸縮性、算法效率、處理不同類型屬性的能力、發(fā)現(xiàn)任意形狀的簇、輸入?yún)?shù)數(shù)量最小化、初始敏感性、高維性、處理噪聲能力、可解釋性等方面存在或多或少的問(wèn)題[67]。 聚類算法的國(guó)內(nèi)外發(fā)展現(xiàn)狀 聚類分析的主要研究對(duì)象是聚類算法，也是本 文研究的主要對(duì)象。面對(duì)復(fù)雜的數(shù)據(jù)和問(wèn)題，在聚類的結(jié)果上運(yùn)用其它的數(shù)據(jù)挖掘技術(shù)，不僅可以提高其它挖掘方法的效率，而且可以提高其挖掘的可靠性。對(duì)于某些 2 維數(shù)據(jù)人類自己可以通過(guò)觀察對(duì)其進(jìn)行分類，但對(duì)于更高維數(shù)據(jù)人類就束手無(wú)策了。 聚類分析的作用 聚類分析旨在無(wú)類別標(biāo)簽的訓(xùn)練樣本條件下，根據(jù)數(shù)據(jù)本身的特征分布提煉出數(shù)據(jù)的內(nèi)在的模式或結(jié)構(gòu)。常見(jiàn)的相似性度量主要是“距離”度量、角度度量和相關(guān)系數(shù)。 特 征 提 取 與 選 擇 相 似 性 度 量特 征 描 述 聚 類 算 法 聚 類 結(jié) 果輸 入 數(shù) 據(jù) 集聚 類 有 效 性 檢 驗(yàn) 圖 11 聚類分析的過(guò)程 特征提取與選擇是聚類分析的基礎(chǔ)，這又和具體用 于解決的問(wèn)題息息相關(guān)。當(dāng)然這里不考慮模糊聚類，對(duì)于模糊聚類，一個(gè)數(shù)據(jù)元素可以屬于多個(gè)簇，以隸屬度加以區(qū)分?！? 聚類的公式化描述：數(shù)據(jù)集 ? ?1,nD x x? L 中包含 k 個(gè)簇，簇?cái)?shù)目 k 可能是先驗(yàn)已知的，也可能需要在聚類過(guò)程中確定， k 個(gè)簇 1,kCCL 需要滿足如下條件： a) , 1, , 。第一種只涉及有標(biāo)簽的數(shù)據(jù)，而第二種只涉及無(wú)標(biāo)簽的數(shù)據(jù) [1]。數(shù)據(jù)分析方法可以概括為主要的兩類： (i)探索性的或描述性的，指研究者沒(méi)有事先明確的模型或假設(shè)但是想理解數(shù)據(jù)的大體特征和結(jié)構(gòu)。 （ 3）基于實(shí)現(xiàn)的聚類算法和演示平臺(tái)，本文實(shí)現(xiàn)了基于聚類分析的 NBA 籃球運(yùn)動(dòng)員類型分類和球隊(duì)球員結(jié)構(gòu)分類的應(yīng)用，驗(yàn)證了所實(shí)現(xiàn)聚類算法的有效性。 五、主要參考文獻(xiàn)： [1]Zhu Qun, Zhang YuHong, Hu XueGang, Li PeiPei. A doublewindowbased classification algorithm for concept drifting data streams [J]. Acta Automatica Sinica, 2020, 37(9):10771084 [2]Hassani M, Spaus P, Gaber M M, Seidl T. Densitybased projected clustering of data streams [J]. In: Proceeding of the 2020 Scalable Uncertainty management, Berlin Heidelberg, Springer, 2020 311324. [3] Huang D C, Shen X Q, Lu Y H. Double knearest Neighbors of Heterogeneous Data Stream Clustering Algorithm [J]. Journal of Computer Science and Technology, 2020, 40(10):226230. [4] Yang C Y, Zhou J. A heterogeneous data stream clustering algorithm [J]. Chinese J of Computers, 2020, 30(8):13641371. [5] Aggarwal C C, Yu P S. A framework for clustering massive text and categorical data streams [J]. In: Proceeding of the 6th SIAM International Conference on Data Mining. Bethesda, 2020: 477481. 任務(wù)書(shū)下發(fā)日期 2020 年 12 月 26 日 設(shè)計(jì)（論文、創(chuàng)作）工作自 2020 年 12 月 26 日 至 2020 年 6 月 8 日 設(shè)計(jì)（論文、創(chuàng)作）指導(dǎo)教師 學(xué)科（方向）負(fù)責(zé)人 主管院長(zhǎng) I 基于 R 語(yǔ)言的多種聚類算法演示平臺(tái) 開(kāi)發(fā) 摘 要 聚類分析是模式識(shí)別、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)中的很重要的 一類方法，它是將數(shù)據(jù)集按照某種指導(dǎo)思想劃分成一些簇的過(guò)程。 本科畢業(yè)設(shè)計(jì)論文 題目 ： 基于 R 語(yǔ)言的多種聚類算法演示平臺(tái)開(kāi)發(fā) 作者姓名 徐天宇 指導(dǎo)教師