【正文】 n recognition and so on. Clustering algorithms in machine learning are applied in image segmentation and image processing which can be used to deal with data pression and information search. Another important application is applied in data mining, space database, sequence and anomaly data analysis and other fields such as statistic, biology, geognosy, geography and market. This paper is about the research of Kmeans. At first， some related concepts of clustering are given. The chief point of the paper is the research on Kmeans. Kmeans, O(n) time plexity, is a partition method that it is easy to use and can work well with large data set. The system is to achieve its algorithm and interface. Keywords: Data Mining。其次重點(diǎn)對 Kmeans 算法進(jìn)行了分析研究， Kmeans 算法是一種基于劃分的方法，該算法的優(yōu)點(diǎn)是簡單易行，時(shí)間復(fù)雜度為 O(n)，并且適用 于 處理 大規(guī)模數(shù)據(jù)。 本文是對聚類算法 Kmeans 的研究。聚類的另一個(gè)主要應(yīng)用是數(shù)據(jù)挖掘、時(shí)空數(shù)據(jù)庫應(yīng)用、序列和異常數(shù)據(jù)分析等。聚類算法是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和模式識別等研究方向的重要研究內(nèi)容之一，在識別數(shù)據(jù)對象的內(nèi)在關(guān)系方面，具有極其重 要的作用。 基于 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ù)中未知的分類。聚類分析已經(jīng)有了很長的研究歷史，其重要性已經(jīng)越來越受到人們的肯定。聚類主要應(yīng)用于模式識別中的語音識別、字符識別等，機(jī)器學(xué)習(xí)中的聚類算法應(yīng)用于圖像分割，圖像處理中，主要用于數(shù)據(jù)壓縮、信息檢索。此外，聚類還應(yīng)用于統(tǒng)計(jì)科學(xué)，同時(shí)，在生物學(xué)、地質(zhì)學(xué)、地理學(xué)以及市場營銷等方面也有著重要的作用。首先介紹了聚類技術(shù)的相關(guān)概念。 本系統(tǒng)主要是對其進(jìn)行 算法和 界面實(shí)現(xiàn)。 Clustering Analysis。 數(shù)據(jù)挖掘 （ Data Mining） 又稱為數(shù)據(jù)庫中知識發(fā) 現(xiàn) （ Knowledge Discovery form Database，KDD） ，它是一個(gè)從大量數(shù)據(jù)中抽取挖掘出未知的、有價(jià)值的模式或規(guī)律等知識的復(fù)雜過程 。 常用的數(shù)據(jù)挖掘技術(shù)包括關(guān)聯(lián)分析、異類分析、分類與預(yù)測、聚類分析以及演化分析等 。 研究意義及背景 面對信息技術(shù)的日新月異，人們利用信息技術(shù)生產(chǎn)和搜集數(shù)據(jù)的能力大幅度提高， 大量的數(shù)據(jù)庫被用于商業(yè)管理、政府辦公、科學(xué)研究和工程開發(fā)等等，要想使數(shù)據(jù)真正成為一個(gè)公司的資源，只有充分利用它為公司自身的業(yè)務(wù)決策和戰(zhàn)略發(fā)展服務(wù)才行，否則大量的數(shù)據(jù)可能成為包袱，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)技術(shù)應(yīng)運(yùn) 而 生，并得以蓬勃發(fā)展，越來越顯示出其強(qiáng)大的生命力。人們把原始數(shù)據(jù)看作是形成知識的源泉，就像從礦石中采礦一樣。發(fā)現(xiàn)知識的方法可以是數(shù)學(xué)的，也可以是非數(shù)學(xué)的可以是演繹的，也可以是歸納的。查詢優(yōu)化、決策支持、過程控制等，還可以用于數(shù)據(jù)自身的維護(hù)。它匯聚了不同領(lǐng)域沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 2 的研究者，尤其是數(shù)據(jù)庫、人工智能、數(shù)理統(tǒng)計(jì)、可視化、并行計(jì)算等方面的學(xué)者和工程技術(shù)人員。聚類將數(shù)據(jù)對象分組成 為若干個(gè)類或簇，使得在同一個(gè)簇中的對象之間具有較高的相似度，而不同簇中的對象差別很大，通過聚類，人們能夠識別密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式以及數(shù)據(jù)屬性之間有趣的相互關(guān)系。聚類分析將大量數(shù)據(jù)劃分為性質(zhì)相同的子類，便于了解數(shù)據(jù)的分布情況。因此，從某種角度看，聚類分析是一種無監(jiān)督的學(xué)習(xí)過程，是基于觀察的學(xué)習(xí)而不是基于實(shí)例的學(xué)習(xí)。 具體要求： (1)通過界面實(shí)現(xiàn)平面點(diǎn)集的輸入輸出 ； (2)利用 Kmeans 聚類技術(shù)對平面點(diǎn)集進(jìn)行聚類 ； (3)通過平面圖顯示聚類結(jié)果 。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 4 2 研究 現(xiàn)狀及設(shè)計(jì)目標(biāo) 國內(nèi)外相關(guān)研究現(xiàn)狀 聚類分析作為統(tǒng)計(jì)學(xué)的一個(gè)分支，己被廣泛地研究了多年，主要集中 在基于距離的聚類分析。 在機(jī)器學(xué)習(xí)領(lǐng)域，聚類是無指導(dǎo)學(xué)習(xí)的一個(gè)例子。由于這個(gè)原因，聚類是觀察式學(xué)習(xí)，而不是示例式學(xué)習(xí)。 聚類分析的研究工作集中在為大型數(shù)據(jù)庫的有效和實(shí)際的聚類分析尋求適當(dāng)?shù)姆椒?，目前的研究方向包括下列幾個(gè)方面 ： (1)算法的可伸縮性：在很多聚類算法中，數(shù)據(jù)對象小于 200 個(gè)的小數(shù)據(jù)集合上魯棒性執(zhí)行多種數(shù)據(jù)模型；而對于包含幾百萬個(gè)數(shù)據(jù)對象的大規(guī)模數(shù)據(jù)庫進(jìn)行聚類時(shí)，將會(huì)導(dǎo)致有不同的偏差結(jié)果，這就需要聚類算法具有高度的可伸縮性，能有效地處理海量數(shù)據(jù) ； (2)處理不同類型屬性的能力：設(shè)計(jì)的很多算法是用于聚類數(shù)值類型的數(shù)據(jù)，但在實(shí)際應(yīng)用中可能要求聚類其他類型的數(shù)據(jù)，如分類 /標(biāo)稱類型 (categofical／nominal)，序數(shù)型 (ordinal)，二元 (binary)數(shù)據(jù)，或者這些數(shù)據(jù)類型的混合 ； (3)發(fā)現(xiàn)任意形狀的聚 類：許多聚類算法是基于歐幾里德距離，趨向于發(fā)現(xiàn)具有相近密度和尺寸的球狀簇。聚類結(jié)果對于輸入?yún)?shù)很敏感，通常參數(shù)較難確定，尤其是對于含有高維對象的數(shù)據(jù)集更是如此。如對于同一個(gè)數(shù)據(jù)集合，以不同的順序提交給同一個(gè) 算法時(shí)，可能產(chǎn)生差別很大的聚類結(jié)果。很多聚類算法擅長處理低維數(shù)據(jù)，一般只涉及兩到三維。聚類數(shù)據(jù)對象在高維空間是非常有挑戰(zhàn)性的，尤其是考慮到這樣的數(shù)據(jù)可能高度偏斜，非常稀疏 ； (7)處理噪聲數(shù)據(jù)的能力：在現(xiàn)實(shí)應(yīng)用中絕大多數(shù)的數(shù)據(jù)都包含了孤立點(diǎn)，空缺、未知數(shù)據(jù)或者錯(cuò)誤的數(shù)據(jù)。既要找到滿足特定的約束，又要具有良好聚類特性的數(shù)據(jù)分組是一項(xiàng)具有挑戰(zhàn)性的任務(wù) ； (9)可解釋性和可用性：通常用戶希望聚類結(jié)果是可解釋的，可理解的和可用的。 現(xiàn)行研究存在的問題及解決辦法 聚類就是根據(jù)最大化類內(nèi)的相似性、最小化類間的相似性原則對數(shù)據(jù)對象進(jìn)行分組的一個(gè)過程。 聚類的應(yīng)用越來越廣泛， 在經(jīng)濟(jì)學(xué)、 生物 學(xué)、氣象學(xué)、醫(yī)藥學(xué)、信息工程和工程技術(shù)等許多領(lǐng)域都有著十分重要的作用。 人們已經(jīng)提出了很多聚類算法，比如有基于劃分的 KMEANS 算法、 CLARANS 算法 ； 基于層次的 BIRCH 算法、 CURE 算法 ； 基于 網(wǎng)格 的 STING 算法、 WaveCluster算法等。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 6 Kmeans 的基本思想 給定類的個(gè)數(shù) k，隨機(jī)挑選 k個(gè)對象為初始聚類中心，利用距離最近的原則， 將其余數(shù)據(jù)集對象分到 k個(gè)類中去，聚類的結(jié)果由 k個(gè)聚類中心來表達(dá)。在每一輪中，依據(jù) k個(gè)參照點(diǎn)將其周圍的點(diǎn)分別組成 k個(gè)類，而每個(gè)類的幾何中心將被作為下一輪迭代的參照點(diǎn)，迭代使得選取的參照點(diǎn)越來越接近真實(shí)的類幾何中心，使得類內(nèi)對象的相似性最大，類間對象的相似性最小。 因?yàn)樗膹?fù)雜度是 O(n k t)，其中 n是所有對象的數(shù)目， k 是簇的數(shù)目， t 是迭代的次數(shù)。 聚類分析中常用的距離計(jì)算函數(shù) 當(dāng)前聚類分析中常用距離計(jì)算算法有明氏距離、馬氏距離、蘭氏距離。時(shí)，則分別得絕對距離、歐式 （ Euclid） 距離、切比雪夫 （ Chebyshev）距離。 2. 馬氏 （ Mahalanois） 距離 ? ? ???? 1 )()(),( YXYXYXD T () ∑是樣本矩陣 A 的協(xié)方差陣，是總體分布的協(xié)差估計(jì)量。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 7 3. 蘭氏 （ Lance） 距離 ? ???i iiiiYXYXYXD ),( () 蘭氏距離克服了明氏距離受量綱影響的缺點(diǎn)，但沒有考慮 多重相關(guān)性。在醫(yī)學(xué)實(shí)踐中也經(jīng)常需要做分類工作 ， 如根據(jù)病人的一系列癥狀、體征和生化檢查的結(jié)果 ， 判斷病人所患疾病的類型 ； 或?qū)σ幌盗袡z查方法及其結(jié)果 ， 將之劃分成某幾種方法適合用于甲類病的檢查 ， 另幾種方法適合用于乙類病的檢查 ， 等等?；诰垲惙治龅墓ぞ咭呀?jīng)被加入到許多統(tǒng)計(jì)分析軟件包或系統(tǒng)中 ， 如 SPlus、 SPSS， 以及 SAS。 給定一個(gè)包含 n個(gè)對象或數(shù)據(jù)行 ， 劃分方法將數(shù)據(jù)集劃分為 k個(gè)子集 (劃分 )。代表算法為 Kmeans 算法、Kmedoids 算法和 CLARANS 算法 ； (2)層次方法。它存在的缺陷就是在進(jìn)行 (組 )分解或合并之后無法回溯。只要臨近區(qū)域的密度 (對象或數(shù)據(jù)點(diǎn)的數(shù)目 )超過某個(gè)閾值 ，就繼續(xù)聚類。它根據(jù)一個(gè)密度閾值來控制簇的增長 ； (4)基于網(wǎng)格的方法。其主要優(yōu)點(diǎn)是它的處理速度很快 ， 其處理時(shí)間獨(dú)立于數(shù)據(jù)對象的數(shù)目 ， 只與量化空間中每一維的單元數(shù)目有關(guān)。該方法就是為每個(gè)聚類假設(shè)一個(gè)模型 ， 然后再去發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對象。 其他聚類 算法 1. Kmedoid 算法 Kmedoid 算法和 Kmeans 算法是最典型的劃分方法 ， 算法的處理思路基本相同， Kmedoid 算法有三種實(shí)現(xiàn)方式 PAM， CLARA 和 CLARANS。 PAM(Partition Around Medoid)方法：對于一個(gè)數(shù)據(jù)庫 D， D 中含有 N 個(gè)元素：作為參數(shù)需給出要生成的簇的個(gè)數(shù) K(1≤ k≤ N)。如果平方 誤差減小則替換發(fā)生。需要用 N－ k 個(gè)點(diǎn)替換 k 個(gè)點(diǎn)，每次替換都要檢驗(yàn) N－ k次代價(jià)函數(shù)，所以復(fù)雜度是 O(N(N－ k) 2)。 CLARA 方法的思想是：從所有的數(shù)據(jù)中取出 5 組樣本，對每個(gè)樣本實(shí)行 PAM 算法。 CLARA 方法的確在處理大數(shù)據(jù)量時(shí)提高了運(yùn)算速度，但是它所得出來的結(jié)果只是關(guān)于樣本點(diǎn)最優(yōu)的，并不是所有數(shù)據(jù)的最優(yōu)解。 CLARANS(Clustering Large Application based upon RANdomized Search)方法是CLARA 方法的加強(qiáng)版，用以提高結(jié)果的質(zhì)量和伸縮性。如果嘗試幾次 （ 參數(shù)由人給出 ） 沒有發(fā)現(xiàn)更好的 結(jié)果，就認(rèn)為已經(jīng)達(dá)到局部最優(yōu)。實(shí)驗(yàn)顯示 CLARANS方法比 PAM和 CLARA 更有效。 層次聚類是將類由多變少的一種方法，分類的步驟如下： 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 9 (1)各樣品各成一類，這時(shí)有 n類 ； (2)計(jì)算各樣品之間的距離，將最近的兩個(gè)樣品歸為一類； (3)計(jì)算新類與其余各類的距離，再將距離最近的兩類合并，這時(shí)如果類的個(gè)數(shù)仍大于 1，則再繼續(xù)重復(fù)上述步驟，直到所有樣品歸為一類，則停止。 常用的層次聚類方法有 最短距離法 、 最長距離法 、 中間距離法 、 重心法 等。通過數(shù)據(jù)測試能夠充分體現(xiàn)出 Kmeans 算法的優(yōu)點(diǎn)。 經(jīng)濟(jì)效益分析 本系統(tǒng)旨在 通過對 Kmeans 算法的深入理解和使用后，在親身體