【文章內(nèi)容簡介】 研究存在的問題及解決辦法 聚類就是根據(jù)最大化類內(nèi)的相似性、最小化類間的相似性原則對(duì)數(shù)據(jù)對(duì)象進(jìn)行分組的一個(gè)過程。其結(jié)果就是一個(gè)個(gè)由數(shù)據(jù)對(duì)象組成的簇，每個(gè)簇內(nèi)的對(duì)象之間具有很高的相似性， 而簇間的對(duì)象則很不相似。 聚類的應(yīng)用越來越廣泛， 在經(jīng)濟(jì)學(xué)、 生物 學(xué)、氣象學(xué)、醫(yī)藥學(xué)、信息工程和工程技術(shù)等許多領(lǐng)域都有著十分重要的作用。因此，對(duì)聚類的要求也越來越高，提出準(zhǔn)確且又高效的聚類算法刻不容緩。 人們已經(jīng)提出了很多聚類算法，比如有基于劃分的 KMEANS 算法、 CLARANS 算法 ； 基于層次的 BIRCH 算法、 CURE 算法 ； 基于 網(wǎng)格 的 STING 算法、 WaveCluster算法等。但是這些算法都存在著不足， 所以就存在如何選擇 參數(shù)的問題，不適當(dāng)?shù)倪x擇將會(huì)大大影響算法的結(jié)果。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 6 Kmeans 的基本思想 給定類的個(gè)數(shù) k，隨機(jī)挑選 k個(gè)對(duì)象為初始聚類中心，利用距離最近的原則， 將其余數(shù)據(jù)集對(duì)象分到 k個(gè)類中去，聚類的結(jié)果由 k個(gè)聚類中心來表達(dá)。算法采用迭代更新的方法，通過判定給定的聚類目標(biāo)函數(shù)，每一次迭代過程都向目標(biāo)函數(shù)值減少的方向進(jìn)行。在每一輪中，依據(jù) k個(gè)參照點(diǎn)將其周圍的點(diǎn)分別組成 k個(gè)類，而每個(gè)類的幾何中心將被作為下一輪迭代的參照點(diǎn)，迭代使得選取的參照點(diǎn)越來越接近真實(shí)的類幾何中心，使得類內(nèi)對(duì)象的相似性最大，類間對(duì)象的相似性最小。 Kmeans 的 優(yōu)點(diǎn) K means 算法有 三個(gè)優(yōu)點(diǎn) ： (1) 是解決聚類問題的一種經(jīng)典算法，簡單、快捷 ； (2) 對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和 高效率的 。 因?yàn)樗膹?fù)雜度是 O(n k t)，其中 n是所有對(duì)象的數(shù)目， k 是簇的數(shù)目， t 是迭代的次數(shù)。通常 kn 且 tn； (3) 當(dāng)結(jié)果簇是密集的，而簇與簇之間的區(qū)別明顯時(shí)，它的效果較好 。 聚類分析中常用的距離計(jì)算函數(shù) 當(dāng)前聚類分析中常用距離計(jì)算算法有明氏距離、馬氏距離、蘭氏距離。 1. 明氏 （ Minkowski） 距離 qqi iiqYXYX1}{),(D ? ?? () 當(dāng) q 取 1， 2， ∞。時(shí)，則分別得絕對(duì)距離、歐式 （ Euclid） 距離、切比雪夫 （ Chebyshev）距離。本系統(tǒng)所應(yīng)用的距離算法是歐氏距離。 2. 馬氏 （ Mahalanois） 距離 ? ? ???? 1 )()(),( YXYXYXD T () ∑是樣本矩陣 A 的協(xié)方差陣，是總體分布的協(xié)差估計(jì)量。馬氏距離是明氏距離的改進(jìn)，它對(duì)于一切線性變換是不變的，克服了明氏距離受量綱影響的缺點(diǎn)；馬氏距離也部分克服了多重相關(guān)性。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 7 3. 蘭氏 （ Lance） 距離 ? ???i iiiiYXYXYXD ),( () 蘭氏距離克服了明氏距離受量綱影響的缺點(diǎn)，但沒有考慮 多重相關(guān)性。 聚類方法分析 聚類分析是直接比較各事物之間的性質(zhì) ， 將性質(zhì)相近的歸為一類 ， 將性質(zhì)差別較大的歸入不同的類。在醫(yī)學(xué)實(shí)踐中也經(jīng)常需要做分類工作 ， 如根據(jù)病人的一系列癥狀、體征和生化檢查的結(jié)果 ， 判斷病人所患疾病的類型 ； 或?qū)σ幌盗袡z查方法及其結(jié)果 ， 將之劃分成某幾種方法適合用于甲類病的檢查 ， 另幾種方法適合用于乙類病的檢查 ， 等等。聚類分析被廣泛研究了許多年。基于聚類分析的工具已經(jīng)被加入到許多統(tǒng)計(jì)分析軟件包或系統(tǒng)中 ， 如 SPlus、 SPSS， 以及 SAS。 大體上 ， 聚類算法可以劃分為如下幾類 ： (1)劃分方法。 給定一個(gè)包含 n個(gè)對(duì)象或數(shù)據(jù)行 ， 劃分方法將數(shù)據(jù)集劃分為 k個(gè)子集 (劃分 )。其中每個(gè)子集均代表一個(gè)聚類 ( k=n )。代表算法為 Kmeans 算法、Kmedoids 算法和 CLARANS 算法 ； (2)層次方法。該方法就是通過分解所給定的數(shù)據(jù)對(duì)象集來創(chuàng)建一個(gè)層次。它存在的缺陷就是在進(jìn)行 (組 )分解或合并之后無法回溯。將循環(huán)再定位與層次方法結(jié)合起來使用常常是有效的 ， 如 BIRCH 和 CURE， 就是基于這種組合方法設(shè)計(jì)的 ； (3)基于密度的方法。只要臨近區(qū)域的密度 (對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目 )超過某個(gè)閾值 ，就繼續(xù)聚類。 DBSCAN 是一個(gè)有代表性的基于密度的方法。它根據(jù)一個(gè)密度閾值來控制簇的增長 ； (4)基于網(wǎng)格的方法。基于網(wǎng)格方法將對(duì)象空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)。其主要優(yōu)點(diǎn)是它的處理速度很快 ， 其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目 ， 只與量化空間中每一維的單元數(shù)目有關(guān)。 STING 就是一個(gè)典型的基于網(wǎng)格的方法 ； (5)基于模型的方法。該方法就是為每個(gè)聚類假設(shè)一個(gè)模型 ， 然后再去發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對(duì)象。它根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并考慮到噪聲或異常數(shù)據(jù) ， 可以自動(dòng)沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 8 確定聚類個(gè)數(shù) ； 因而它可以產(chǎn)生很多的聚類方法。 其他聚類 算法 1. Kmedoid 算法 Kmedoid 算法和 Kmeans 算法是最典型的劃分方法 ， 算法的處理思路基本相同， Kmedoid 算法有三種實(shí)現(xiàn)方式 PAM， CLARA 和 CLARANS。 Kmeans 算法后面我們會(huì)重點(diǎn)介紹。 PAM(Partition Around Medoid)方法：對(duì)于一個(gè)數(shù)據(jù)庫 D， D 中含有 N 個(gè)元素：作為參數(shù)需給出要生成的簇的個(gè)數(shù) K(1≤ k≤ N)。 PAM 方法首先隨機(jī)選擇 k 個(gè)對(duì)象作為簇的中心，對(duì)于每一個(gè)中心點(diǎn) O[j]， PAM 方法試圖用所有 N－ k個(gè)非中心點(diǎn)替換它。如果平方 誤差減小則替換發(fā)生。 PAM 方法對(duì)于小 數(shù)據(jù)庫處理能得到很好的結(jié)果，但是它的計(jì)算代價(jià)非常高。需要用 N－ k 個(gè)點(diǎn)替換 k 個(gè)點(diǎn)，每次替換都要檢驗(yàn) N－ k次代價(jià)函數(shù)，所以復(fù)雜度是 O(N(N－ k) 2)。 CLARA(Clustering LARge Application)方法：是 PAM 方法的增強(qiáng)版，專門用于處理大量數(shù)據(jù)。 CLARA 方法的思想是：從所有的數(shù)據(jù)中取出 5 組樣本，對(duì)每個(gè)樣本實(shí)行 PAM 算法。比較 5 組的平方 誤差，選取最小的作為輸出結(jié)果。 CLARA 方法的確在處理大數(shù)據(jù)量時(shí)提高了運(yùn)算速度，但是它所得出來的結(jié)果只是關(guān)于樣本點(diǎn)最優(yōu)的，并不是所有數(shù)據(jù)的最優(yōu)解。 CLARA 方法結(jié)果的優(yōu)劣依賴于采樣方法。 CLARANS(Clustering Large Application based upon RANdomized Search)方法是CLARA 方法的加強(qiáng)版，用以提高結(jié)果的質(zhì)量和伸縮性。 CLARANS 方法的思想是：任意從 k 個(gè)中心點(diǎn)中取出一個(gè)點(diǎn)，從 N－ k 中任意取一個(gè)點(diǎn)去替換它，如果替換成功則重新開始。如果嘗試幾次 （ 參數(shù)由人給出 ） 沒有發(fā)現(xiàn)更好的 結(jié)果，就認(rèn)為已經(jīng)達(dá)到局部最優(yōu)。 CLARANS方法的復(fù)雜度是 O(N2)。實(shí)驗(yàn)顯示 CLARANS方法比 PAM和 CLARA 更有效。 2. 層次聚類法 層次聚類法也稱系統(tǒng)聚類法，是目前實(shí)際工作中用得最多的一類算法。 層次聚類是將類由多變少的一種方法，分類的步驟如下： 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 9 (1)各樣品各成一類，這時(shí)有 n類 ； (2)計(jì)算各樣品之間的距離，將最近的兩個(gè)樣品歸為一類； (3)計(jì)算新類與其余各類的距離，再將距離最近的兩類合并，這時(shí)如果類的個(gè)數(shù)仍大于 1，則再繼續(xù)重復(fù)上述步驟，直到所有樣品歸為一類，則停止。 樣品之間的距離有不同的定義方法，類與類之間也同樣有不同的距離的定義方法，這樣就產(chǎn)生了不同的層次聚類方法。 常用的層次聚類方法有 最短距離法 、 最長距離法 、 中間距離法 、 重心法 等。 設(shè)計(jì)目標(biāo) 基于 Kmeans 算法的平面點(diǎn)集聚類系統(tǒng)是對(duì)已知的多個(gè)平面點(diǎn)根據(jù)用戶對(duì)聚類中心的數(shù)量設(shè)置后通過 Kmeans 聚類算法的分析后得出相應(yīng)結(jié)果。通過數(shù)據(jù)測試能夠充分體現(xiàn)出 Kmeans 算法的優(yōu)點(diǎn)。 以上是理論方面的目標(biāo)，在實(shí)踐方面要做到編碼較優(yōu)，運(yùn)行程序耗時(shí)較短，占內(nèi)存較少。 經(jīng)濟(jì)效益分析 本系統(tǒng)旨在 通過對(duì) Kmeans 算法的深入理解和使用后，在親身體驗(yàn) Kmeans 算法的應(yīng)用過程中深切體會(huì) Kmeans 算法的優(yōu)點(diǎn)和缺點(diǎn)，為以后不斷完善此算法做好準(zhǔn)備。 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 10 3 關(guān)鍵問題及分 析 研究設(shè)計(jì)中要解決的問題 本系統(tǒng)主要是根據(jù) Kmeans 算法的基本思想，設(shè)計(jì)實(shí)現(xiàn)一個(gè)基于 Kmeans 算法下的平面點(diǎn)集聚類系統(tǒng)，并通過系統(tǒng)界面輸入和輸出結(jié)果 。 根據(jù)上述過程中，有一個(gè)關(guān)鍵問題，即 Kmeans 算法的運(yùn)算過程 以及 Kmeans在 C 語言中的實(shí)現(xiàn)。下面重點(diǎn)介紹 Kmeans 算法的運(yùn)算過程。 在 1967 年提出的 Kmeans 算法，是一種被廣泛應(yīng)用于科學(xué)研究和工業(yè)應(yīng)用中的經(jīng)典聚類算法。 Kmeans 算法的核心思想是把 n個(gè)數(shù)據(jù)對(duì)象劃分為 k個(gè)聚類，使每個(gè)聚類中的數(shù)據(jù)點(diǎn)到該聚類中 心的平方和最小，算法處理過程： 輸入：聚類個(gè)數(shù) k，包含 n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集。 輸出： k個(gè)聚類。 (1)從 n個(gè)數(shù)據(jù)對(duì)象中任意選取 k個(gè)對(duì)象作為初始的聚類中心。 (2)分別計(jì)算每個(gè)對(duì)象到各個(gè)聚類中心的距離，把對(duì)象分配到距離最近的聚類中。 (3)所有對(duì)象分配完成后，重新計(jì)算 k個(gè)聚類的中心。 (4)與前一次計(jì)算得到的 k個(gè)聚類中心比較，如果聚類中心發(fā)生變化，轉(zhuǎn) (2)，否則轉(zhuǎn) (5)。 (5)輸出聚類結(jié)果。 首先從 n個(gè)數(shù)據(jù)對(duì)象中任意選擇 k 個(gè)對(duì)象作為初始聚類中心；而對(duì)于所剩下的其它對(duì)象，則根據(jù)他們與這些聚類中心的相似度 （ 距離 ） ，分別將他們分配給與其最相似的 （ 聚類中心所代表的 ） 聚類。 然后再計(jì)算每個(gè) 新聚類的聚類中心 （ 該聚類中所有對(duì)象的均值 ） 。不斷重復(fù)這沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 11 一過程直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測度函數(shù)，具體定義如下： 21 11? ?? ? ?? ki cp mpE () 其中 E 為數(shù)據(jù)庫中所有對(duì)象的均方差之和； p 為代表對(duì)象的空間中的一個(gè)點(diǎn)；m1為聚類 c1的均值 （ p 和 m1均是多維的 ） 。 公式 所示聚類標(biāo)準(zhǔn)旨在使所獲得的 k 個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊， 而各聚類間盡可能的分開。 開 始輸 入 聚 類 個(gè) 數(shù) k , n初 始 化 k 個(gè) 聚 類中 心分 配 各 個(gè) 數(shù) 據(jù) 對(duì) 象 到距 離 最 近 的 類 中輸 出 聚 類 結(jié) 果重 新 計(jì) 算 各 個(gè) 聚 類 的中 心是 否 收 斂結(jié) 束是否 圖 Kmeans算法流程圖 沈陽航空航天大學(xué)畢業(yè)設(shè)計(jì)（論文） 12 Kmeans 算法優(yōu)點(diǎn)是可以處理大數(shù)據(jù)集， Kmeans 算法是相對(duì)可伸縮的和高效率的，因?yàn)樗挠?jì)算復(fù)雜度為 O(nkt)，其中 n為對(duì)象個(gè)數(shù)， k 為聚類個(gè)數(shù)， t 為迭代次數(shù)，通常有 r≦ n， k≦ n，因此它的復(fù)雜度通常也用 O(n)表示。 前期工作 在開發(fā)程序之前，首先大量翻閱 Kmeans 算法相關(guān)資料，以求達(dá)到充分理解Kmeans 算法的整個(gè)運(yùn)算流程，根據(jù) C++的相關(guān)技術(shù)實(shí)現(xiàn)公式 中所達(dá)到的要求 。 關(guān)鍵技術(shù) 本系統(tǒng)是由 C++和 MFC 技術(shù)在 Microsoft Visual Studio 環(huán)境下開發(fā)完成的，下面將分別予以介紹。 Kmeans 算法 Kmeans 算法是劃分聚類算法的典型代表，實(shí)質(zhì)上該算法基于簇中對(duì)象的平均值。為了達(dá)到全局