【文章內(nèi)容簡(jiǎn)介】 LARA和CLARANS。Kmeans算法后面我們會(huì)重點(diǎn)介紹。PAM(Partition Around Medoid)方法：對(duì)于一個(gè)數(shù)據(jù)庫(kù)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ù)庫(kù)處理能得到很好的結(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)版，專(zhuān)門(mén)用于處理大量數(shù)據(jù)。CLARA方法的思想是：從所有的數(shù)據(jù)中取出5組樣本，對(duì)每個(gè)樣本實(shí)行PAM算法。比較5組的平方誤差，選取最小的作為輸出結(jié)果。CLARA方法的確在處理大數(shù)據(jù)量時(shí)提高了運(yùn)算速度，但是它所得出來(lái)的結(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)去替換它，如果替換成功則重新開(kāi)始。如果嘗試幾次（參數(shù)由人給出）沒(méi)有發(fā)現(xiàn)更好的結(jié)果，就認(rèn)為已經(jīng)達(dá)到局部最優(yōu)。CLARANS方法的復(fù)雜度是O(N2)。實(shí)驗(yàn)顯示CLARANS方法比PAM和CLARA更有效。2. 層次聚類(lèi)法層次聚類(lèi)法也稱(chēng)系統(tǒng)聚類(lèi)法，是目前實(shí)際工作中用得最多的一類(lèi)算法。層次聚類(lèi)是將類(lèi)由多變少的一種方法，分類(lèi)的步驟如下：(1)各樣品各成一類(lèi)，這時(shí)有n類(lèi)；(2)計(jì)算各樣品之間的距離，將最近的兩個(gè)樣品歸為一類(lèi)；(3)計(jì)算新類(lèi)與其余各類(lèi)的距離，再將距離最近的兩類(lèi)合并，這時(shí)如果類(lèi)的個(gè)數(shù)仍大于1，則再繼續(xù)重復(fù)上述步驟，直到所有樣品歸為一類(lèi)，則停止。樣品之間的距離有不同的定義方法，類(lèi)與類(lèi)之間也同樣有不同的距離的定義方法，這樣就產(chǎn)生了不同的層次聚類(lèi)方法。常用的層次聚類(lèi)方法有最短距離法、最長(zhǎng)距離法、中間距離法、重心法等。基于Kmeans算法的平面點(diǎn)集聚類(lèi)系統(tǒng)是對(duì)已知的多個(gè)平面點(diǎn)根據(jù)用戶對(duì)聚類(lèi)中心的數(shù)量設(shè)置后通過(guò)Kmeans聚類(lèi)算法的分析后得出相應(yīng)結(jié)果。通過(guò)數(shù)據(jù)測(cè)試能夠充分體現(xiàn)出Kmeans算法的優(yōu)點(diǎn)。以上是理論方面的目標(biāo)，在實(shí)踐方面要做到編碼較優(yōu)，運(yùn)行程序耗時(shí)較短，占內(nèi)存較少。 經(jīng)濟(jì)效益分析本系統(tǒng)旨在通過(guò)對(duì)Kmeans算法的深入理解和使用后，在親身體驗(yàn)Kmeans算法的應(yīng)用過(guò)程中深切體會(huì)Kmeans算法的優(yōu)點(diǎn)和缺點(diǎn)，為以后不斷完善此算法做好準(zhǔn)備。3 關(guān)鍵問(wèn)題及分析 研究設(shè)計(jì)中要解決的問(wèn)題本系統(tǒng)主要是根據(jù)Kmeans算法的基本思想，設(shè)計(jì)實(shí)現(xiàn)一個(gè)基于Kmeans算法下的平面點(diǎn)集聚類(lèi)系統(tǒng)，并通過(guò)系統(tǒng)界面輸入和輸出結(jié)果。根據(jù)上述過(guò)程中，有一個(gè)關(guān)鍵問(wèn)題，即Kmeans算法的運(yùn)算過(guò)程以及Kmeans在C語(yǔ)言中的實(shí)現(xiàn)。下面重點(diǎn)介紹Kmeans算法的運(yùn)算過(guò)程。，是一種被廣泛應(yīng)用于科學(xué)研究和工業(yè)應(yīng)用中的經(jīng)典聚類(lèi)算法。Kmeans算法的核心思想是把n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類(lèi)，使每個(gè)聚類(lèi)中的數(shù)據(jù)點(diǎn)到該聚類(lèi)中心的平方和最小，算法處理過(guò)程：輸入：聚類(lèi)個(gè)數(shù)k，包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集。輸出：k個(gè)聚類(lèi)。(1)從n個(gè)數(shù)據(jù)對(duì)象中任意選取k個(gè)對(duì)象作為初始的聚類(lèi)中心。(2)分別計(jì)算每個(gè)對(duì)象到各個(gè)聚類(lèi)中心的距離，把對(duì)象分配到距離最近的聚類(lèi)中。(3)所有對(duì)象分配完成后，重新計(jì)算k個(gè)聚類(lèi)的中心。(4)與前一次計(jì)算得到的k個(gè)聚類(lèi)中心比較，如果聚類(lèi)中心發(fā)生變化，轉(zhuǎn)(2)，否則轉(zhuǎn)(5)。(5)輸出聚類(lèi)結(jié)果。首先從n個(gè)數(shù)據(jù)對(duì)象中任意選擇k個(gè)對(duì)象作為初始聚類(lèi)中心；而對(duì)于所剩下的其它對(duì)象，則根據(jù)他們與這些聚類(lèi)中心的相似度（距離），分別將他們分配給與其最相似的（聚類(lèi)中心所代表的）聚類(lèi)。然后再計(jì)算每個(gè)新聚類(lèi)的聚類(lèi)中心（該聚類(lèi)中所有對(duì)象的均值）。不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開(kāi)始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)，具體定義如下： ()其中E為數(shù)據(jù)庫(kù)中所有對(duì)象的均方差之和；p為代表對(duì)象的空間中的一個(gè)點(diǎn)；m1為聚類(lèi)c1的均值（p和m1均是多維的）。：各聚類(lèi)本身盡可能的緊湊，而各聚類(lèi)間盡可能的分開(kāi)。 Kmeans算法流程圖Kmeans算法優(yōu)點(diǎn)是可以處理大數(shù)據(jù)集，Kmeans算法是相對(duì)可伸縮的和高效率的，因?yàn)樗挠?jì)算復(fù)雜度為O(nkt)，其中n為對(duì)象個(gè)數(shù)，k為聚類(lèi)個(gè)數(shù)，t為迭代次數(shù)，通常有r≦n，k≦n，因此它的復(fù)雜度通常也用O(n)表示。 前期工作在開(kāi)發(fā)程序之前，首先大量翻閱Kmeans算法相關(guān)資料，以求達(dá)到充分理解Kmeans算法的整個(gè)運(yùn)算流程，根據(jù)C++。 關(guān)鍵技術(shù)本系統(tǒng)是由C++和MFC技術(shù)在Microsoft Visual Studio環(huán)境下開(kāi)發(fā)完成的，下面將分別予以介紹。 Kmeans算法Kmeans 算法是劃分聚類(lèi)算法的典型代表，實(shí)質(zhì)上該算法基于簇中對(duì)象的平均值。為了達(dá)到全局最優(yōu)，基于劃分的聚類(lèi)會(huì)要求窮舉所有可能的劃分。算法的處理過(guò)程如下： 算法的輸入：簇的數(shù)目k和數(shù)據(jù)庫(kù)中的對(duì)象。 算法的輸出：使得平方誤差準(zhǔn)則最小的k個(gè)簇。方法如下： (1)從整個(gè)樣本n中，任意選擇k個(gè)對(duì)象作為初始的簇的中心mi(i=1,2,…k)； (2)，計(jì)算數(shù)據(jù)集中的每個(gè)p 到k 個(gè)簇中心的距離d ( p , mi )； (3)找到每個(gè)對(duì)象p的最小的d(p, mi)，將p歸入到與mi相同的簇中； (4)遍歷完所有對(duì)象之后， mi的值，作為新的簇中心； (5)重新將整個(gè)數(shù)據(jù)集中的對(duì)象賦給最類(lèi)似的簇。這個(gè)過(guò)程反復(fù)進(jìn)行直至平方誤差準(zhǔn)則最小。 ()其中i=(xi1, xi2,…, xin)和j=(ji1, ji2,…,jin)是兩個(gè)n維數(shù)據(jù)對(duì)象。 ()其中的mk代表第k個(gè)簇的簇中心，N代表第k個(gè)簇中數(shù)據(jù)對(duì)象的個(gè)數(shù)。 相關(guān)技術(shù)介紹C++語(yǔ)言發(fā)展大概可以分為三個(gè)階段：第一階段從80年代到1995年。這一階段C++語(yǔ)言基本上是傳統(tǒng)類(lèi)型上的面向?qū)ο笳Z(yǔ)言，并且憑借著接近C語(yǔ)言的效率，在工業(yè)界使用的開(kāi)發(fā)語(yǔ)言中占據(jù)了相當(dāng)大份額；第二階段從1995年到2000年，這一階段由于標(biāo)準(zhǔn)模板庫(kù)（STL）和后來(lái)的Boost等程序庫(kù)的出現(xiàn)，泛型程序設(shè)計(jì)在C++中占據(jù)了越來(lái)越多的比重性。當(dāng)然，同時(shí)由于Java、C等語(yǔ)言的出現(xiàn)和硬件價(jià)格的大規(guī)模下降，C++受到了一定的沖擊； 　　第三階段從2000年至今，由于以Loki、MPL等程序庫(kù)為代表的產(chǎn)生式編程和模板編程的出現(xiàn)，C++出現(xiàn)了發(fā)展歷史上又一個(gè)新的高峰，這些新技術(shù)的出現(xiàn)以及和原有技術(shù)的融合，使C++已經(jīng)成為當(dāng)今主流程序設(shè)計(jì)語(yǔ)言中最復(fù)雜的一員。MFC，微軟基礎(chǔ)類(lèi)（Microsoft Foundation Classes），同VCL類(lèi)似，是一種Application Framework，隨微軟Visual C++ 開(kāi)發(fā)工具發(fā)布。（截止2011年3月），并且發(fā)布了中文版。該類(lèi)庫(kù)提供一組通用的可重用的類(lèi)庫(kù)供開(kāi)發(fā)人員使用。大部分類(lèi)均從CObject 直接或間接派生，只有少部分類(lèi)例外。MFC是Win API與C++的結(jié)合，API，即微軟提供的Windows下應(yīng)用程序的編程語(yǔ)言接口，是一種軟件編程的規(guī)范，但不是一種程序開(kāi)發(fā)語(yǔ)言本身，可以允許用戶使用各種各樣的第三方的編程語(yǔ)言來(lái)進(jìn)行對(duì)Windows下應(yīng)用程序的開(kāi)發(fā)，使這些被開(kāi)發(fā)出來(lái)的應(yīng)用程序能在Windows下運(yùn)行， MFC是微軟對(duì)API函數(shù)的專(zhuān)用C++封裝，這種結(jié)合一方面讓用戶使用微軟的專(zhuān)業(yè)C++ SDK來(lái)進(jìn)行Windows下應(yīng)用程序的開(kāi)發(fā)變得容易，因?yàn)镸FC是對(duì)API的封裝，微軟