【正文】 感謝我的家人，感謝他們?nèi)Φ闹С治业膶W(xué)業(yè) 。 向 葉 老師表達(dá)我深深地謝意 。 他們總是給我們開闊眼界的機(jī)會(huì)，他們不但教會(huì)了 我們知識還教會(huì)了我們許多待人接物與為人處世的道理 。 由于此項(xiàng)技術(shù)應(yīng)用越來越廣泛， Kmeans 算法的優(yōu)化也將越來越重要 ， 本系統(tǒng)通過對 Kmeans 算法的實(shí)現(xiàn)和使用更能對 Kmeans 算法的優(yōu)缺點(diǎn)有更深體會(huì) ， 對優(yōu)化此算法會(huì)有一定幫助 。 其次，通過對現(xiàn)有的 Kmeans 聚類算法進(jìn)行了詳細(xì)的分析研究。 實(shí)例測試 對于上述測試實(shí)例，系統(tǒng)最終生成的結(jié)果 如表 、表 。 圖 數(shù)據(jù)輸出界面 結(jié)果輸出界面 如圖 。i++) pDCEllipse((X[i]+5)*20,460(Y[i]+1)*20,(X[i]++5)*20,460(Y[i]++1)*20)。 } pOldPen=pDCSelectObject(amp。 pDCMoveTo((X[N+i]+5)*20,460(Y[N+i]+1)*20)。i++){ pDCMoveTo((X[N+i]+5)*20,460(Y[N+i]+1)*20)。 } 繪圖模塊 本模塊的入口在結(jié)果輸出模塊中，當(dāng)用戶點(diǎn)選繪圖后，主系統(tǒng)將數(shù)據(jù)傳遞給該模塊，該模塊根據(jù)數(shù)據(jù)二維平面坐標(biāo)中繪出各個(gè)樣本點(diǎn) 以及中心點(diǎn)，并將同一個(gè)所屬的樣本點(diǎn)與中心點(diǎn)通過直線連接起來，以使結(jié)果更加直觀 。 (%.2f,Y[i])。i++){ (第 %d 樣本點(diǎn) ,i+1)。 (%.2f,Y[N+i])。i++){ (第 %d 中心點(diǎn) ,i+1)。 } } 結(jié)果輸出 模塊 在計(jì)算模塊計(jì)算結(jié)束后，自動(dòng)進(jìn)入結(jié)果輸出模塊，主系統(tǒng)將計(jì)算模塊返回的數(shù)據(jù)結(jié)果傳遞給輸出模塊，本模塊根據(jù)數(shù)據(jù)通過列表輸出最后的中心點(diǎn)信息以及每個(gè)沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 20 樣本的數(shù)據(jù)和所屬中心點(diǎn) 。jN。 } } } for(i=0。p++) { if(d[i][j]d[p][j]) { break。iM。j++) { d[i][j]=sqrt((X[N+i]X[j])*(X[N+i]X[j])+(Y[N+i]Y[j])*(Y[N+i]Y[j]))。 for(i=0。 該模塊流程完全按照Kmeans 算法的主要計(jì)算流程設(shè)計(jì)， 主要功能代碼如下。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 19 (m_edybdz1, 2, y)。 Y[m_edybdz1]=m_edybdY。 輸 入 樣 本 點(diǎn)數(shù) 量輸 入 中 心 點(diǎn)數(shù) 量輸 入 樣 本 點(diǎn)坐 標(biāo)輸 入 模 塊 結(jié)束判 斷 輸 入 是否 合 理判 斷 數(shù) 量 是否 符 合是是否否 圖 輸入模塊流程圖 UpdateData(TRUE)。 繪圖模塊：本模塊的入口在結(jié)果輸出模塊中，當(dāng)用戶點(diǎn)選繪圖后，主系統(tǒng)將數(shù)據(jù)傳遞給該模塊，該模塊根據(jù)數(shù)據(jù)二維平面坐標(biāo)中繪出各個(gè)樣本點(diǎn)以及中心點(diǎn)，并將同一個(gè)所屬的樣本點(diǎn)與中心點(diǎn)通過直線連接起來，以使結(jié)果更 加直觀。 主 程 序數(shù) 據(jù) 輸 入模 塊k m e a n s 算法 計(jì) 算 模塊結(jié) 果 輸 出模 塊繪 圖 模 塊 圖 系統(tǒng)模塊圖 數(shù)據(jù)輸入模塊：本模塊 主要做為用戶輸入數(shù)據(jù)接口，根據(jù)提示輸入中心點(diǎn)個(gè)數(shù)、樣本點(diǎn)個(gè)數(shù)及具體樣本點(diǎn)數(shù)據(jù)。 同時(shí)數(shù)學(xué)公式的算法清晰明了 。 設(shè)計(jì)原則 系統(tǒng)主要實(shí)現(xiàn)內(nèi)容為： 通過輸入中心點(diǎn)以及樣本點(diǎn)后，系統(tǒng)將結(jié)果直觀返回給用戶，并且能夠根據(jù)結(jié)果繪圖形象反映計(jì)算結(jié)果 。 圖 為本系統(tǒng)流程圖。 Visual Studio 2021 包括各種增強(qiáng)功能，例如可視化設(shè)計(jì)器（使用 .NET Framework 加速開發(fā)）、對 Web 開發(fā)工具的大量改進(jìn)，以及能夠加速開發(fā)和處理所有類型數(shù)據(jù)的語言增強(qiáng)功能。 MFC 編制軟件時(shí)的大量內(nèi)節(jié)，如應(yīng)用程序?qū)崿F(xiàn)消息的處理，設(shè)備環(huán)境繪圖，這種結(jié)合是以方便為目的的，必定要付出一定代價(jià)，因此就造成了 MFC 對類封裝中的一定程度的的冗余和迂回，但這是可以接受的。目前最新版本為 （截止 2021 年 3 月），并且發(fā)布了中文版。 相關(guān) 技術(shù)介紹 C++語言發(fā)展大概可以分為三個(gè)階段： 第一階段從 80 年代到 1995 年。 方法如下： (1)從整個(gè)樣本 n中，任意選擇 k個(gè)對象作為初始的簇的中心 mi(i=1,2,? k)； (2)利用公 式 ，計(jì)算數(shù)據(jù)集中的每個(gè) p 到 k 個(gè)簇中心的距離 d ( p , mi )； (3)找到每個(gè)對象 p 的最小的 d(p, mi)，將 p 歸入到與 mi相同的簇中 ； (4)遍歷完所有對象之后，利用公式 重新計(jì)算 mi的值，作為新的簇中心 ； (5)重新將整個(gè)數(shù)據(jù)集中的對象賦給最類似的簇。 Kmeans 算法 Kmeans 算法是劃分聚類算法的典型代表，實(shí)質(zhì)上該算法基于簇中對象的平均值。 公式 所示聚類標(biāo)準(zhǔn)旨在使所獲得的 k 個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊， 而各聚類間盡可能的分開。 首先從 n個(gè)數(shù)據(jù)對象中任意選擇 k 個(gè)對象作為初始聚類中心；而對于所剩下的其它對象，則根據(jù)他們與這些聚類中心的相似度 （ 距離 ） ，分別將他們分配給與其最相似的 （ 聚類中心所代表的 ） 聚類。 (2)分別計(jì)算每個(gè)對象到各個(gè)聚類中心的距離，把對象分配到距離最近的聚類中。 在 1967 年提出的 Kmeans 算法，是一種被廣泛應(yīng)用于科學(xué)研究和工業(yè)應(yīng)用中的經(jīng)典聚類算法。 經(jīng)濟(jì)效益分析 本系統(tǒng)旨在 通過對 Kmeans 算法的深入理解和使用后，在親身體驗(yàn) Kmeans 算法的應(yīng)用過程中深切體會(huì) Kmeans 算法的優(yōu)點(diǎn)和缺點(diǎn)，為以后不斷完善此算法做好準(zhǔn)備。 常用的層次聚類方法有 最短距離法 、 最長距離法 、 中間距離法 、 重心法 等。實(shí)驗(yàn)顯示 CLARANS方法比 PAM和 CLARA 更有效。 CLARANS(Clustering Large Application based upon RANdomized Search)方法是CLARA 方法的加強(qiáng)版，用以提高結(jié)果的質(zhì)量和伸縮性。 CLARA 方法的思想是：從所有的數(shù)據(jù)中取出 5 組樣本，對每個(gè)樣本實(shí)行 PAM 算法。如果平方 誤差減小則替換發(fā)生。 其他聚類 算法 1. Kmedoid 算法 Kmedoid 算法和 Kmeans 算法是最典型的劃分方法 ， 算法的處理思路基本相同， Kmedoid 算法有三種實(shí)現(xiàn)方式 PAM， CLARA 和 CLARANS。其主要優(yōu)點(diǎn)是它的處理速度很快 ， 其處理時(shí)間獨(dú)立于數(shù)據(jù)對象的數(shù)目 ， 只與量化空間中每一維的單元數(shù)目有關(guān)。只要臨近區(qū)域的密度 (對象或數(shù)據(jù)點(diǎn)的數(shù)目 )超過某個(gè)閾值 ，就繼續(xù)聚類。代表算法為 Kmeans 算法、Kmedoids 算法和 CLARANS 算法 ； (2)層次方法。基于聚類分析的工具已經(jīng)被加入到許多統(tǒng)計(jì)分析軟件包或系統(tǒng)中 ， 如 SPlus、 SPSS， 以及 SAS。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 7 3. 蘭氏 （ Lance） 距離 ? ???i iiiiYXYXYXD ),( () 蘭氏距離克服了明氏距離受量綱影響的缺點(diǎn)，但沒有考慮 多重相關(guān)性。時(shí)，則分別得絕對距離、歐式 （ Euclid） 距離、切比雪夫 （ Chebyshev）距離。 因?yàn)樗膹?fù)雜度是 O(n k t)，其中 n是所有對象的數(shù)目， k 是簇的數(shù)目， t 是迭代的次數(shù)。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 6 Kmeans 的基本思想 給定類的個(gè)數(shù) k，隨機(jī)挑選 k個(gè)對象為初始聚類中心，利用距離最近的原則， 將其余數(shù)據(jù)集對象分到 k個(gè)類中去，聚類的結(jié)果由 k個(gè)聚類中心來表達(dá)。 聚類的應(yīng)用越來越廣泛， 在經(jīng)濟(jì)學(xué)、 生物 學(xué)、氣象學(xué)、醫(yī)藥學(xué)、信息工程和工程技術(shù)等許多領(lǐng)域都有著十分重要的作用。既要找到滿足特定的約束，又要具有良好聚類特性的數(shù)據(jù)分組是一項(xiàng)具有挑戰(zhàn)性的任務(wù) ； (9)可解釋性和可用性：通常用戶希望聚類結(jié)果是可解釋的，可理解的和可用的。很多聚類算法擅長處理低維數(shù)據(jù)，一般只涉及兩到三維。聚類結(jié)果對于輸入?yún)?shù)很敏感，通常參數(shù)較難確定，尤其是對于含有高維對象的數(shù)據(jù)集更是如此。由于這個(gè)原因，聚類是觀察式學(xué)習(xí)，而不是示例式學(xué)習(xí)。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 4 2 研究 現(xiàn)狀及設(shè)計(jì)目標(biāo) 國內(nèi)外相關(guān)研究現(xiàn)狀 聚類分析作為統(tǒng)計(jì)學(xué)的一個(gè)分支，己被廣泛地研究了多年，主要集中 在基于距離的聚類分析。因此，從某種角度看，聚類分析是一種無監(jiān)督的學(xué)習(xí)過程，是基于觀察的學(xué)習(xí)而不是基于實(shí)例的學(xué)習(xí)。聚類將數(shù)據(jù)對象分組成 為若干個(gè)類或簇，使得在同一個(gè)簇中的對象之間具有較高的相似度，而不同簇中的對象差別很大，通過聚類，人們能夠識別密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式以及數(shù)據(jù)屬性之間有趣的相互關(guān)系。查詢優(yōu)化、決策支持、過程控制等，還可以用于數(shù)據(jù)自身的維護(hù)。人們把原始數(shù)據(jù)看作是形成知識的源泉，就像從礦石中采礦一樣。 常用的數(shù)據(jù)挖掘技術(shù)包括關(guān)聯(lián)分析、異類分析、分類與預(yù)測、聚類分析以及演化分析等 。 Clustering Analysis。首先介紹了聚類技術(shù)的相關(guān)概念。聚類主要應(yīng)用于模式識別中的語音識別、字符識別等，機(jī)器學(xué)習(xí)中的聚類算法應(yīng)用于圖像分割，圖像處理中，主要用于數(shù)據(jù)壓縮、信息檢索。 基于 Kmeans算法的平面點(diǎn)集聚類系統(tǒng) 院 系 北方軟件學(xué) 院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) （ 軟件工程 ） 班 級 學(xué) 號 姓 名 指導(dǎo)教師 負(fù)責(zé)教師 沈陽航空 航天大學(xué) 2021 年 6 月沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） I 摘 要 聚類是數(shù)據(jù)挖掘領(lǐng)域中重要的技術(shù)之一，用于發(fā)現(xiàn)數(shù)據(jù)中未知的分類。聚類的另一個(gè)主要應(yīng)用是數(shù)據(jù)挖掘、時(shí)空數(shù)據(jù)庫應(yīng)用、序列和異常數(shù)據(jù)分析等。其次重點(diǎn)對 Kmeans 算法進(jìn)行了分析研究， Kmeans 算法是一種基于劃分的方法，該算法的優(yōu)點(diǎn)是簡單易行，時(shí)間復(fù)雜度為 O(n)，并且適用 于 處理 大規(guī)模數(shù)據(jù)。 Kmeans 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） III 目 錄 1 緒論 .................................................................................................................................... 1 研究意義及背景 ......................................................................................................... 1 系統(tǒng)設(shè)計(jì)要求 ............................................................................................................