本科畢業(yè)論文數(shù)據(jù)挖掘K均值算法實(shí)現(xiàn)

1、本科生畢業(yè)論文設(shè)計(jì)數(shù)據(jù)挖掘K-均值算法實(shí)現(xiàn)作者姓名：郝蓓指導(dǎo)教師：郭瑞強(qiáng)所在學(xué)院：數(shù)學(xué)與信息科學(xué)學(xué)院專業(yè)（系）：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)（屆）：2013屆計(jì)算機(jī)班二零一三年五月二日目 錄中文摘要、關(guān)鍵字 11 緒論 31.1 本文研究的背景和意義 31.2 聚類分析國(guó)內(nèi)外研究現(xiàn)狀 51.3 本文所做的主要工作 72 聚類算法的分析與研究 82.1 數(shù)據(jù)挖掘簡(jiǎn)介 82.2 聚類的基本知識(shí) 82.2.1 類的定義及表示 92.2.2 聚類的相似度量方法 92.2.3 聚類間的距離測(cè)度函數(shù) 112.2.4 聚類分析的一般步驟 122.3 常用的聚類分析的方法介紹 132.3.1 基于劃分的方法 132.

2、3.2 基于密度的方法 132.3.3 基于層次的算法 132.3.4 基于模型的算法 142.3.5 基于網(wǎng)格的算法 142.4 常用的劃分聚類算法的分析 142.4.1 K-均值聚類算法 152.4.2 K-中心聚類法 152.5 本章小結(jié) 163 K一均值聚類算法的研究 173.1 K-均值聚類算法介紹 173.1.1 K一均值聚類算法基本思想 173.1.2 K一均值聚類算法主要流程 173.2 K-均值聚類算法的主要缺陷及分析 183.3 本章小結(jié) 194 K-均值聚類算法的實(shí)驗(yàn) 204.1 實(shí)驗(yàn)結(jié)果分析 204.2 本章小結(jié) 255 總結(jié)與展望 265.1 總結(jié) 255.2 展望

3、26參考文獻(xiàn) 28英文摘要、關(guān)鍵字 31論文題目：數(shù)據(jù)挖掘K均值算法實(shí)現(xiàn)數(shù)學(xué)與信息科學(xué)學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)指導(dǎo)教師：郭瑞強(qiáng)作者：郝蓓摘要：隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，現(xiàn)在的人們每一天都會(huì)面臨例如文本、圖像、視頻、音頻等各種數(shù)據(jù)形式，這些數(shù)據(jù)的數(shù)據(jù)量的大小是很驚人的。怎樣能夠很快的并且高效地從這些大量數(shù)據(jù)中挖掘提煉出它所蘊(yùn)含的價(jià)值，成為現(xiàn)在人們特別關(guān)注并且需要馬上解決的問(wèn)題。數(shù)據(jù)挖掘(Data Mining，DM)正是因?yàn)檫@個(gè)才慢慢誕生出來(lái)。數(shù)據(jù)挖掘經(jīng)過(guò)一段時(shí)間的迅猛發(fā)展，誕生出了大量的理論結(jié)果和現(xiàn)實(shí)使用成果，它提供了許多工具和卓有成效的方法來(lái)解決問(wèn)題。數(shù)據(jù)挖掘中有一項(xiàng)是很重要的研究領(lǐng)域，那

4、就是聚類分析，這是一種對(duì)數(shù)據(jù)進(jìn)行按照不同的依據(jù)將數(shù)據(jù)進(jìn)行分組或者將數(shù)據(jù)進(jìn)行劃分的方式。聚類無(wú)論在生物科學(xué)研究，還是在商務(wù)貿(mào)易中、圖像分析處理、網(wǎng)頁(yè)內(nèi)容分類等其他日常生活的領(lǐng)域都得到了很好的應(yīng)用。根據(jù)使用的數(shù)據(jù)類型、使用的功能的不同、聚類需求的不同，目前的聚類算法大概有以下幾種：基于劃分的算法、基于層次的算法、基于密度的的算法、基于模型的算法以及基于網(wǎng)格的算法。在這之中，基于劃分的K-均值聚類算法是目前研究最成熟傳統(tǒng)經(jīng)典的算法。K-均值算法的應(yīng)用領(lǐng)域特別廣泛，覆蓋范圍涉及語(yǔ)音頻率壓縮還有圖像及文本聚類，另外在數(shù)據(jù)預(yù)處理和神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的任務(wù)分解等也發(fā)揮其重要用途。本文所做的工作有：本文第一部分：詳

5、細(xì)介紹了本次論文研究的背景和目的，以及所選題目的考慮思路，還有在當(dāng)前國(guó)際形式下，聚類分析在國(guó)際上的地位及國(guó)內(nèi)外研究成果綜述，最后介紹了本論文算法實(shí)現(xiàn)的內(nèi)容和論文整體布局安排。第二部分：首先詳細(xì)描述了數(shù)據(jù)挖掘的來(lái)源發(fā)展還有它的概念定義，下面主要介紹聚類分析，包括聚類的基本概念原理等基礎(chǔ)性知識(shí)，介紹了聚類算法的內(nèi)部特性，詳細(xì)描述了幾種目前聚類分析的方法，總結(jié)比較各個(gè)方法的特點(diǎn)及其長(zhǎng)短處。最后對(duì)本論文所研究的基于劃分的聚類算法進(jìn)一步討論都有哪幾種算法。第三部分：這是本論文的重點(diǎn)，本論文所要討論的K-均值算法，從它的概念基本思想算法流程等方面對(duì)K-均值算法進(jìn)行詳細(xì)系統(tǒng)的介紹，并且詳細(xì)分析了它的優(yōu)缺點(diǎn)。

6、K-均值算法對(duì)初始值的選取比較敏感和對(duì)數(shù)據(jù)的輸入順序不同也會(huì)影響聚類等問(wèn)題，所以本文針對(duì)該問(wèn)題進(jìn)行了驗(yàn)證，通過(guò)實(shí)驗(yàn)證明了這兩個(gè)因素對(duì)聚類結(jié)果會(huì)有哪些影響。實(shí)驗(yàn)表明，K-均值算法對(duì)初始值和數(shù)據(jù)輸入順序很敏感，但是這兩個(gè)對(duì)聚類結(jié)果影響的方面不同。本文通過(guò)六個(gè)實(shí)驗(yàn)結(jié)果分析得出，改變初始點(diǎn)，對(duì)聚類結(jié)果的影響不大，只是會(huì)改變迭代次數(shù)，而且選取初始的連續(xù)的幾個(gè)數(shù)據(jù)為初始點(diǎn)迭代次數(shù)最少，雖然中間間隔的幾個(gè)數(shù)據(jù)作為初始點(diǎn)也出現(xiàn)了最小的迭代次數(shù)，但這對(duì)數(shù)據(jù)集來(lái)說(shuō)有太多的不確定性，所以還是選擇最開始那幾個(gè)數(shù)據(jù)為數(shù)據(jù)聚類初始點(diǎn)；對(duì)于改變數(shù)據(jù)集的輸入順序，聚類結(jié)果與之前的有很大的改變，實(shí)驗(yàn)結(jié)果說(shuō)明輸入順序不同既影響了

7、聚類結(jié)果也影響了迭代次數(shù)。通過(guò)這些結(jié)論為以后用戶使用K-均值算法提供了很好的幫助，也為該算法的改進(jìn)提供了參考。關(guān)鍵詞：數(shù)據(jù)挖掘 聚類分析 K-means算法 實(shí)驗(yàn)驗(yàn)證1 緒論1.1 本文研究的背景和意義近年來(lái)，隨著科技的進(jìn)步以及互聯(lián)網(wǎng)的普及，以計(jì)算機(jī)為代表的信息技術(shù)有了巨大發(fā)展，人們產(chǎn)生、發(fā)現(xiàn)、整理、利用數(shù)據(jù)的能力不斷提升。到目前為止，數(shù)據(jù)在我們的日常生活中無(wú)處不在，它廣泛應(yīng)用于科學(xué)研究、政府日常辦公、軍事力量分析、企業(yè)管理電子商務(wù)、統(tǒng)計(jì)學(xué)分析等等各個(gè)領(lǐng)域。雖然我們知道這些數(shù)據(jù)的重要性，但是隨著時(shí)間越來(lái)越久，我們積累的數(shù)據(jù)量是不斷地在加大，相應(yīng)的我們分析處理這些數(shù)據(jù)的能力也要增加，但是后來(lái)數(shù)據(jù)

8、量的增長(zhǎng)速度已經(jīng)超出了我們的能力范圍，所以我們必將面臨的嚴(yán)峻問(wèn)題是數(shù)據(jù)爆炸。難道真的沒(méi)有辦法可以很科學(xué)的處理這些海量數(shù)據(jù)嗎？事實(shí)并非如此，人類的智慧是無(wú)窮的，人們已經(jīng)通過(guò)理性的思維和恰當(dāng)?shù)募夹g(shù)，將這些海量數(shù)據(jù)充分利用，使它們成為社會(huì)發(fā)展進(jìn)步的強(qiáng)大的力量源泉。目前，廣泛使用的數(shù)據(jù)庫(kù)系統(tǒng)雖然具有高效率的錄入所有數(shù)據(jù)查詢所需數(shù)據(jù)統(tǒng)計(jì)數(shù)據(jù)類別等功能，但是并不能發(fā)現(xiàn)這些海量數(shù)據(jù)中蘊(yùn)藏的內(nèi)部關(guān)聯(lián)規(guī)則，也無(wú)法從當(dāng)前現(xiàn)在的數(shù)據(jù)情況去預(yù)測(cè)未來(lái)的數(shù)據(jù)內(nèi)容的發(fā)展趨勢(shì)，更不可能做出決策判斷，使得人們逼不得已去面對(duì)“數(shù)據(jù)豐富而知識(shí)缺乏”的困鏡1。所以數(shù)據(jù)挖掘（Data Mining）技術(shù)因此就慢慢誕生了，并且快速的發(fā)展

9、應(yīng)用社會(huì)的各個(gè)領(lǐng)域，表現(xiàn)了其堅(jiān)韌的生命力與適應(yīng)力。該技術(shù)就是從“數(shù)據(jù)礦山”中發(fā)現(xiàn)“知識(shí)的寶藏”。數(shù)據(jù)挖掘（Data Mining），也被叫做在已知的數(shù)據(jù)庫(kù)中對(duì)知識(shí)的發(fā)現(xiàn)（knowledge discovery ,KDD）,就是從數(shù)量巨大的、不完整的、有孤立點(diǎn)數(shù)據(jù)的、模糊的、隨機(jī)的數(shù)據(jù)中，提取發(fā)掘出來(lái)隱含在當(dāng)中的、人們?cè)谶@之前不是特別了解的、但又是隱含有用的信息內(nèi)容和知識(shí)內(nèi)容的非平凡過(guò)程2 。原始的數(shù)據(jù)類型可以是多樣的，比如數(shù)據(jù)庫(kù)中的數(shù)據(jù)結(jié)構(gòu)化數(shù)據(jù)類型，那些圖像圖形資料及文字類資料是半結(jié)構(gòu)化的數(shù)據(jù)類型，當(dāng)然也包括網(wǎng)絡(luò)互聯(lián)網(wǎng)上的那些數(shù)據(jù)我們稱它們?yōu)榘虢Y(jié)構(gòu)化的數(shù)據(jù)類型。我們可以通過(guò)歸納演繹等方法來(lái)發(fā)

10、現(xiàn)知識(shí)，也可以用統(tǒng)計(jì)學(xué)的數(shù)學(xué)或非數(shù)學(xué)的方法總結(jié)數(shù)據(jù)來(lái)得到我們想要的信息。這些我們得到的信息內(nèi)容和知識(shí)內(nèi)容的過(guò)程就是挖掘的一個(gè)過(guò)程，我們把挖掘的知識(shí)可以應(yīng)用到我們的生活中，包括未來(lái)決策規(guī)劃、優(yōu)化信息管理方案、調(diào)整控制模式、改進(jìn)查詢方案等等來(lái)更好的維護(hù)和利用我們現(xiàn)有的數(shù)據(jù)。所以數(shù)據(jù)挖掘涉及到的學(xué)科很廣泛，它是各個(gè)學(xué)科的交叉，它用到了人工智能數(shù)學(xué)統(tǒng)計(jì)學(xué)與數(shù)據(jù)庫(kù)等技術(shù)來(lái)實(shí)現(xiàn)它自己的目的，需要這些領(lǐng)域的工程技術(shù)人員來(lái)共同配合，尤其是數(shù)據(jù)庫(kù)管理人員?，F(xiàn)在的數(shù)據(jù)挖掘技術(shù)已經(jīng)開始走向科技產(chǎn)品研發(fā)及技術(shù)應(yīng)用，不再是之前的單純的搞一下研究而已，我國(guó)市場(chǎng)經(jīng)濟(jì)制度在不斷地完善與發(fā)展，經(jīng)濟(jì)實(shí)力也在不斷進(jìn)步，現(xiàn)在我們的社

11、會(huì)對(duì)數(shù)據(jù)挖掘技術(shù)的需求越來(lái)越強(qiáng)烈，目前我國(guó)很多的有眼光的軟件企業(yè)已經(jīng)將目光聚集于此，來(lái)研發(fā)更多適應(yīng)市場(chǎng)需求的數(shù)據(jù)挖掘軟件產(chǎn)品，隨著市場(chǎng)日趨成熟，廣大消費(fèi)者的應(yīng)用需求也是慢慢變大，相信將來(lái)會(huì)有更多成熟的中國(guó)數(shù)據(jù)挖掘軟件面向市場(chǎng)。聚類分析是數(shù)據(jù)挖掘的一個(gè)發(fā)現(xiàn)信息的方法，已經(jīng)被人們深入的研究了很長(zhǎng)時(shí)間，主要的是對(duì)基于距離的聚類分析的研究。聚類是一種無(wú)監(jiān)督的學(xué)習(xí)，分類正好與它相反，分類是一種有監(jiān)督的學(xué)習(xí)，聚類主要是劃分無(wú)標(biāo)記的對(duì)象，使這些無(wú)標(biāo)記的對(duì)象變的有意義，對(duì)預(yù)先定義的類與帶類標(biāo)記的訓(xùn)練實(shí)例不具有依賴性。所以聚類分析在我們的日常生活中的應(yīng)用范圍非常廣泛： 在商業(yè)上，聚類可以根據(jù)消費(fèi)者數(shù)據(jù)庫(kù)里面所記

12、錄的數(shù)據(jù)信息，對(duì)消費(fèi)者進(jìn)行劃分，根據(jù)各個(gè)消費(fèi)者的特征，以幫助市場(chǎng)營(yíng)銷員按照市場(chǎng)需求及時(shí)調(diào)整貨物的擺放次序等一系列營(yíng)銷計(jì)劃的實(shí)施； 在社會(huì)學(xué)中，聚類用來(lái)發(fā)現(xiàn)目前社會(huì)結(jié)構(gòu)組成中潛在的社會(huì)結(jié)構(gòu)； 在網(wǎng)絡(luò)挖掘中對(duì)互聯(lián)網(wǎng)上批量的數(shù)據(jù)信息進(jìn)行有效的劃分與分類，實(shí)現(xiàn)信息的有效利用，對(duì)數(shù)據(jù)信息檢索效率方面有顯著提高； 在生物信息學(xué)中，在大量的基因群中發(fā)現(xiàn)功能相似的基因組，對(duì)基因因功能不同進(jìn)行劃分對(duì)其固有的結(jié)構(gòu)特征進(jìn)行分析，來(lái)更好的為我們的醫(yī)學(xué)發(fā)展提供有利條件； 在空間數(shù)據(jù)庫(kù)領(lǐng)域，聚類分析能對(duì)相似地理特征區(qū)域及它們的人和環(huán)境的不同特征進(jìn)行識(shí)別，來(lái)研究地域文化提供條件。本文主要選擇聚類分析中基于劃分的K-mean

13、s算法并實(shí)現(xiàn)它的應(yīng)用，對(duì)數(shù)據(jù)集的數(shù)據(jù)進(jìn)行聚類分析。本文在實(shí)現(xiàn)它的基礎(chǔ)上，對(duì)該算法對(duì)初始值和數(shù)據(jù)輸入順序敏感的問(wèn)題進(jìn)行了驗(yàn)證，通過(guò)六次試驗(yàn)，分別對(duì)這個(gè)兩個(gè)方面進(jìn)行驗(yàn)證，并對(duì)聚類結(jié)果進(jìn)行分析比較，從而得出結(jié)論。本文通過(guò)對(duì)不同輸入條件的實(shí)驗(yàn)驗(yàn)證，得出K-均值算法對(duì)初始值得選擇和數(shù)據(jù)輸入順序是很敏感的結(jié)論，通過(guò)實(shí)驗(yàn)結(jié)果可得出在今后使用K-均值算法時(shí)我們應(yīng)該怎樣避免其聚類出不準(zhǔn)確的聚類結(jié)果和今后改進(jìn)算法應(yīng)該改進(jìn)的方向等問(wèn)題。1.2 聚類分析國(guó)內(nèi)外研究現(xiàn)狀目前，國(guó)內(nèi)對(duì)于數(shù)據(jù)挖掘聚類分析的研究的集中部門還是科研單位和各大高校，國(guó)內(nèi)還沒(méi)有公司企業(yè)專門從事聚類分析的研究，相對(duì)于外國(guó)來(lái)說(shuō)起步較晚。各大科研機(jī)構(gòu)與高

14、校對(duì)聚類的研究主要是對(duì)數(shù)據(jù)集聚類算法的設(shè)計(jì)并實(shí)現(xiàn)，以研究出來(lái)的算法為基礎(chǔ)對(duì)算法改進(jìn)。目前人們已經(jīng)在統(tǒng)計(jì)分析軟件中應(yīng)用一些聚類分析工具，如SAS等軟件。為大型的數(shù)據(jù)庫(kù)尋求有效的聚類分析方法是目前聚類分析的主要研究工作，目前研究方向包括以下幾個(gè)方向：（1）可伸縮性：目前的聚類算法針對(duì)小型數(shù)據(jù)庫(kù)，數(shù)據(jù)量是幾百范圍內(nèi)的，對(duì)于有很龐大數(shù)據(jù)量的數(shù)據(jù)庫(kù)會(huì)造成結(jié)果的不穩(wěn)定性，可伸縮性強(qiáng)的算法就亟待的研發(fā)出來(lái)。（2）屬性不同情況下的處理能力：現(xiàn)在開發(fā)出來(lái)的聚類算法所針對(duì)的數(shù)據(jù)類型都是數(shù)值型，但實(shí)際上的聚類類型的信息是不確定的，如二元數(shù)據(jù)、序數(shù)型的、分類型的等或者是所已知的各種數(shù)據(jù)類型的混合。（3）聚類形狀：在歐

15、幾里得距離的基礎(chǔ)上發(fā)現(xiàn)所得的簇的形狀是球狀簇，它們有相近的距離與密度，形成一個(gè)簇，但是我們更希望能夠有一種算法實(shí)現(xiàn)各個(gè)不同形狀的簇。（4）決定結(jié)果的輸入?yún)?shù)：聚類算法的實(shí)現(xiàn)過(guò)程中相當(dāng)多的是必須讓用戶提前輸入想要聚類出來(lái)的簇?cái)?shù)K，當(dāng)前的算法對(duì)這些K的值是相當(dāng)敏感的，大型的數(shù)據(jù)流對(duì)這些要求很嚴(yán)格，對(duì)結(jié)果的影響很明顯，使用戶在輸入時(shí)加大了分析的工作難度，很難控制。（5）輸入數(shù)據(jù)的順序問(wèn)題：有的聚類算法對(duì)輸入數(shù)據(jù)的順序是有要求的，不同的輸入次序會(huì)有不同的聚類結(jié)果，這就特別需要對(duì)數(shù)據(jù)順序不敏感的算法開發(fā)出來(lái)，更好的適應(yīng)人們的要求。（6）高維數(shù)據(jù)的處理：含有若干維數(shù)據(jù)屬性的數(shù)據(jù)庫(kù)是很常見(jiàn)的，但是擅長(zhǎng)處理兩

16、維或三維的聚類算法才是目前成熟的應(yīng)用的算法，一旦高維數(shù)據(jù)需要聚類處理，這就是一個(gè)難題，這就需要算法有很強(qiáng)的實(shí)用性。（7）污染數(shù)據(jù)的發(fā)現(xiàn)：數(shù)據(jù)是一個(gè)不確定而且無(wú)限性的群體，我們不能保證數(shù)據(jù)集中的數(shù)據(jù)是完全集中的，難免會(huì)有個(gè)別的孤立點(diǎn)造成污染數(shù)據(jù)，影響整個(gè)結(jié)果，應(yīng)該開發(fā)出能智能識(shí)別這些孤立點(diǎn)的數(shù)據(jù)的算法，來(lái)優(yōu)化聚類結(jié)果，目前大部分是通過(guò)對(duì)目前算法進(jìn)行改進(jìn)來(lái)實(shí)現(xiàn)。（8）有約束條件的聚類：實(shí)際的聚類情況是有很多限制的條件的，在實(shí)現(xiàn)這些聚類時(shí)，既要按約束條件又要按聚類要求實(shí)現(xiàn)，是很有壓力和挑戰(zhàn)的一項(xiàng)任務(wù)。（9）可使用性和可解釋性：大多情況下的聚類結(jié)果，對(duì)于客戶來(lái)說(shuō)都希望它們簡(jiǎn)單易懂，一目了然，所以我們要

17、優(yōu)化聚類結(jié)果界面的研究，選擇適合每個(gè)客戶需求的聚類方法來(lái)滿足他們的需求。同時(shí)聚類分析算法主要著手于以下的幾個(gè)問(wèn)題的解決3：（1）初始值的選取及輸入順序?qū)Y(jié)果有何影響在數(shù)據(jù)挖掘的學(xué)科范圍內(nèi)尋找最優(yōu)解的過(guò)程是通過(guò)迭代不同的初始值實(shí)現(xiàn)，但是這個(gè)辦法不是很可靠，它的意思就是表示不能百分之百的確定找到最優(yōu)解。其實(shí)尋找最優(yōu)解就是在優(yōu)化原來(lái)的聚類的結(jié)果，通過(guò)重復(fù)聚類找到所設(shè)計(jì)的目標(biāo)函數(shù)的最優(yōu)解，但是這個(gè)目標(biāo)函數(shù)一般都不是有最值的函數(shù)，所以它的最小值并不是很容易確定，因?yàn)樗⒉晃ㄒ?，有可能找到的這個(gè)只是局部最小值，而不是全局最小，所以這種非完全單調(diào)函數(shù)的全局最小值的查找是目前最急著等待解決的問(wèn)題。（2）以小波

18、變換為基礎(chǔ)的聚類算法因?yàn)楫?dāng)前主要是對(duì)均值算法與模糊算法的研究改進(jìn)而得到的研究成果，這些研究成果使得目前的聚類分析算法提高了它的性能屬性。小波變換聚類算法同樣符合好的聚類算法的各項(xiàng)要求，目前對(duì)小波聚類的研究還有很大程度的空白，如果花大的精力進(jìn)一步研究會(huì)有更加深入的突破。（3）算法的效率改善提高的問(wèn)題聚類的效率問(wèn)題是目前一個(gè)很棘手的問(wèn)題，因?yàn)槿祟愒谶M(jìn)步，數(shù)據(jù)量會(huì)越來(lái)越龐大，應(yīng)該增強(qiáng)目前聚類算法對(duì)更大數(shù)據(jù)庫(kù)的處理能力，即增量聚類，使聚類算法在聚類的數(shù)量上有更好的彈性，盡量減少在工作時(shí)對(duì)龐大數(shù)據(jù)庫(kù)的掃描次數(shù)，進(jìn)一步提高它的工作效率。（4）數(shù)據(jù)庫(kù)類型目前，基于聚類算法的數(shù)據(jù)庫(kù)比較單一，僅僅包括關(guān)系或事務(wù)

19、數(shù)據(jù)庫(kù)，應(yīng)該著眼于其他數(shù)據(jù)庫(kù)類型應(yīng)用算法的研究，比如面向以屬性為內(nèi)容的數(shù)據(jù)庫(kù)、以文本為內(nèi)容的數(shù)據(jù)庫(kù)、各個(gè)不同時(shí)態(tài)為內(nèi)容的數(shù)據(jù)庫(kù)、地理數(shù)據(jù)庫(kù)多維數(shù)據(jù)庫(kù)等的算法開發(fā)，這是一項(xiàng)非常艱巨而且有意義的研究任務(wù)。聚類分析中的算法有很多種，詳細(xì)分析比較了各個(gè)算法的優(yōu)缺點(diǎn)，本文著重介紹了K-均值算法，分析它本身的算法優(yōu)點(diǎn)與不足，并對(duì)算法實(shí)現(xiàn)，著力于對(duì)影響該算法聚類結(jié)果的不同初始條件進(jìn)行驗(yàn)證，以更好在以后的實(shí)際應(yīng)用中使用它。K-均值算法是聚類分析最常用的算法之一。K-均值算法的應(yīng)用范圍非常廣泛，因?yàn)樗牟僮骱?jiǎn)單，適合處理龐大的數(shù)據(jù)集，但是它同時(shí)也暴露出自身的不足，如易陷入局部最優(yōu)解的結(jié)果里面、需要用戶提前輸入?yún)?/p>

20、數(shù)、發(fā)現(xiàn)簇的形狀比較單一等，已經(jīng)有很多專家對(duì)這些問(wèn)題進(jìn)行了改進(jìn)，文獻(xiàn)4作者通過(guò)最大最小距離和DBI聚類指標(biāo)解決了K-均值算法對(duì)初始值K的選擇問(wèn)題，能夠確定出最佳的聚類數(shù)目。文獻(xiàn)5的作者用K-均值算法與層次聚類算法進(jìn)行混合出一種新的聚類算法，充分發(fā)揮了層次聚類的精確性和K-均值的高效性。文獻(xiàn)6的作者對(duì)遺傳算法提出一種改進(jìn)算法，基于比變長(zhǎng)編碼，利用這種算法與K-均值結(jié)合解決了對(duì)初值選擇的敏感問(wèn)題等等，目前已經(jīng)有很多被發(fā)表出來(lái)的對(duì)K-均值的改進(jìn)的算法。1.3 本文所做的主要工作首先對(duì)數(shù)據(jù)挖掘這門學(xué)科的背景和發(fā)展前景做了分析，本文主要研究數(shù)據(jù)挖掘的聚類分析，所以介紹了聚類分析目前國(guó)內(nèi)外的地位與發(fā)展方向

21、，以為下文展開作鋪墊，這方面閱讀了許多聚類相關(guān)文獻(xiàn)，許多新的聚類分析方法先后被各國(guó)的科研工作者提出并應(yīng)用，這些在本文有詳細(xì)列舉。除此之外本文對(duì)聚類分析中的常用的五種方法做了簡(jiǎn)要介紹，列舉了五種方法中目前比較常用的算法，并分析了每個(gè)算法的適用領(lǐng)域與基本思想。本文著重討論的是基于劃分的聚類分析方法中的K-means方法，對(duì)KM方法進(jìn)行了詳細(xì)的介紹，包括基本思路工作流程等，本文通過(guò)分析KM算法的缺點(diǎn)，通過(guò)實(shí)驗(yàn)驗(yàn)證了對(duì)初始點(diǎn)的選取和數(shù)據(jù)輸入順序敏感的驗(yàn)證，通過(guò)兩個(gè)實(shí)驗(yàn)分別得出這兩個(gè)因素對(duì)聚類結(jié)果產(chǎn)生怎樣的影響并得出結(jié)論，實(shí)驗(yàn)表明初始點(diǎn)不同只是影響聚類迭代的次數(shù)，對(duì)聚類結(jié)果的影響不明顯，只是少數(shù)數(shù)據(jù)的聚

22、類結(jié)果發(fā)生改變；數(shù)據(jù)輸入順序的不同，不僅會(huì)改變數(shù)據(jù)聚類的迭代次數(shù)，也會(huì)讓聚類的結(jié)果發(fā)生明顯改變。2 聚類算法的分析與研究2.1 數(shù)據(jù)挖掘簡(jiǎn)介數(shù)據(jù)挖掘（Data Mining），也被叫做在已知的數(shù)據(jù)庫(kù)中對(duì)知識(shí)的發(fā)現(xiàn)（knowledge discovery ,KDD）,就是從數(shù)量巨大的、不完整的、有孤立點(diǎn)數(shù)據(jù)的、模糊的、隨機(jī)的數(shù)據(jù)中，提取發(fā)掘出來(lái)隱含在當(dāng)中的、人們?cè)谶@之前不是特別了解的、但又是隱含有用的信息內(nèi)容和知識(shí)內(nèi)容的非平凡過(guò)程2。其實(shí)數(shù)據(jù)挖掘就是通過(guò)各種分析算法工具從巨大數(shù)量的數(shù)據(jù)中挖掘所需要的數(shù)據(jù)與模型兩者關(guān)系的一個(gè)過(guò)程，可以通過(guò)得到的這些關(guān)系，對(duì)未來(lái)的數(shù)據(jù)與模型關(guān)系進(jìn)行預(yù)測(cè)。通常根據(jù)不同

23、用戶的需求，和他們所提供的數(shù)據(jù)類型，數(shù)據(jù)挖掘的數(shù)據(jù)庫(kù)的類型也是不一樣的，通常包括關(guān)系數(shù)據(jù)庫(kù)類型、事物數(shù)據(jù)庫(kù)類型、多媒體數(shù)據(jù)庫(kù)類型等。其中關(guān)系數(shù)據(jù)庫(kù)實(shí)際上就是使用數(shù)學(xué)學(xué)科上的方法來(lái)處理數(shù)據(jù)之間的關(guān)系，我們生活中隨處可見(jiàn)關(guān)系數(shù)據(jù)庫(kù)，比如交通部的車輛數(shù)據(jù)庫(kù)、銀行的客戶記錄等。事務(wù)數(shù)據(jù)庫(kù)一般是將幾個(gè)事務(wù)數(shù)據(jù)庫(kù)的數(shù)據(jù)一起導(dǎo)入到只能用來(lái)讀數(shù)據(jù)的數(shù)據(jù)挖掘庫(kù)中，做成一個(gè)數(shù)據(jù)集市，然后把其作為挖掘的對(duì)象。多媒體數(shù)據(jù)庫(kù)顧名思義就是包含大量視頻音頻文件，模式識(shí)別技術(shù)被用于該領(lǐng)域。數(shù)據(jù)挖掘包含很多類別，包括分類分析、聚類分析、關(guān)聯(lián)分析孤立點(diǎn)分析等其他分析。其中分類分析包括分類和回歸，分類分析是一種預(yù)測(cè)模型，通過(guò)現(xiàn)有數(shù)

24、據(jù)預(yù)測(cè)將來(lái)的數(shù)據(jù)，如果預(yù)測(cè)的數(shù)據(jù)是離散的即叫做分類，如果是連續(xù)的即叫做回歸。聚類分析則是將大量數(shù)據(jù)中形似的數(shù)據(jù)分到一組，一個(gè)數(shù)據(jù)集大概包括幾組數(shù)據(jù)，聚類沒(méi)有明顯的屬性目標(biāo)，而是挖掘隱藏的屬性來(lái)進(jìn)行聚類，聚類分析中的基于劃分的K-均值算法是本文的研究對(duì)象。關(guān)聯(lián)分析分析數(shù)據(jù)與數(shù)據(jù)之間關(guān)聯(lián)關(guān)系還有它與其他數(shù)據(jù)的派生關(guān)系。孤立點(diǎn)分析是針對(duì)那些遠(yuǎn)離數(shù)據(jù)集的點(diǎn)，對(duì)不同的客戶，別人的孤立點(diǎn)可能對(duì)于他來(lái)說(shuō)是很重要的信息，孤立點(diǎn)分析就是對(duì)這些遠(yuǎn)離數(shù)據(jù)集中心的數(shù)據(jù)信息進(jìn)行挖掘。孤立點(diǎn)的研究是將來(lái)我們必須重點(diǎn)研究的領(lǐng)域，因?yàn)閹讉€(gè)孤立點(diǎn)就會(huì)影響全局的聚類結(jié)果，這是不容忽視的。2.2 聚類的基本知識(shí)2.2.1 類的定義

25、及表示（1）類的定義要想聚類操作首先要明確類的定義。世界錯(cuò)綜復(fù)雜事物存在的方式也不盡相同，所以類的定義并不唯一。以下將列舉出常用的類的定義：設(shè)：含有K個(gè)樣本的集合A，Mi是其中的某個(gè)樣本，T和C是范圍閥值，那么：如果任意的Mi，Mj A，都有D（Mi，Mj）T，則A稱為一類；（2）類的表示；聚類的表示方法也是有不同的，一般用以下三種： 自然語(yǔ)言表示：直接用自然語(yǔ)言直觀的描述出這些數(shù)據(jù)是屬于哪個(gè)簇的； DNF表示：用析取范式表示明了、簡(jiǎn)潔、易懂。例如：(36<PT<70)V(345<AM<1234)； 聚類譜系圖：目前使用的聚類算法輸出結(jié)果大部分都是這種，這種方法表示非常

26、詳細(xì)，它能表示出這些樣本自成一類的所有中間情況，而且都會(huì)有各個(gè)類的平臺(tái)高度，我們叫這種圖為標(biāo)度聚類譜系圖。2.2.2 聚類的相似度量方法聚類分析按照數(shù)據(jù)樣本性質(zhì)的相似程度的大小進(jìn)行劃分，確定這些相似程度的大小必須有一個(gè)準(zhǔn)則來(lái)判斷它們的程度大小，這個(gè)判斷準(zhǔn)則叫做相似度方法，主要是在距離和相似系數(shù)的不同。距離：樣本點(diǎn)之間的相似性我們就用某種距離函數(shù)表示，距離近的表示樣本點(diǎn)相似，具體計(jì)算時(shí)可以把樣本看做有M個(gè)屬性的變量，即這個(gè)樣本就是在一個(gè)M維的空間中的一個(gè)點(diǎn)。距離函數(shù)：設(shè)P是所有樣本集合的集合名稱，如果滿足： 正定性D(M，N)0，if MND(M，N)=0，if M=N 對(duì)稱性D(M，N)=D(

27、M，N) 三角不等式D(M,N)+D(N，L)D(M，L) 我們稱它們?yōu)榫嚯x函數(shù)。聚類分析中經(jīng)常使用的的距離函數(shù)有： 明氏(Minkowski)距離 (2.1)當(dāng)m取1時(shí)，則表示絕對(duì)距離，當(dāng)m取2時(shí)就表示歐式(Euclid)距離，當(dāng)m取無(wú)窮大時(shí)就表示切比雪夫(Chebyshev)距離。 如：歐氏距離 (2.2) 馬氏(Mahalanois)距離 (2.3) 其中 S 是由樣品集N（）算得的協(xié)方差矩陣： (2.3.1)樣品聚類一般情況下被叫做Q型聚類，是以距離矩陣為出發(fā)點(diǎn)的。明氏距離改進(jìn)后得到了馬氏距離，所有的線性變換對(duì)于馬氏距離來(lái)說(shuō)是不變的，多重相關(guān)性馬氏距離也把它克服了。 方差加權(quán)距離 (2

28、.4)其中 . (2.4.1)在聚類分析中除了對(duì)樣本點(diǎn)聚類，對(duì)特征變量也要根據(jù)實(shí)際情況進(jìn)行聚類，所以對(duì)于特征向量而言，不必非用距離函數(shù)來(lái)確定它們的相似測(cè)度，還可以用相似系數(shù)。相似系數(shù)：當(dāng)對(duì)含有k個(gè)指標(biāo)的變量的數(shù)據(jù)集進(jìn)行聚類時(shí)，就用相似系數(shù)來(lái)作為判斷所有變量之間的相似程度（或關(guān)聯(lián)程度）的標(biāo)準(zhǔn)指標(biāo)。一般地，若表示Cab變量Xa,Xb之間的相似系數(shù)，應(yīng)滿足：1）| Cab|1且Cab=1；2）Cab=1或Cab=1Xa=CXb；3）Cab=Cba；Cab的絕對(duì)值越與1接近，越說(shuō)明變量Xa,Xb之間的關(guān)聯(lián)性越大。相似系數(shù)中相關(guān)系數(shù)和夾角余弦是目前最經(jīng)常被使用的。（1）相關(guān)系數(shù)變量之間的相關(guān)系數(shù)我們可以

29、這樣定義為：. (2.5)實(shí)際上，只是變量之間的觀測(cè)值之間的相關(guān)系數(shù)而已。相關(guān)系數(shù)表示兩個(gè)向量的相關(guān)程度是多少。（2）夾角余弦變量的觀測(cè)值 ，其夾角余弦我們可以這樣定義為： (2.6)變量聚類一般情況下被叫作為 R 型聚類。一般R 型聚類，相似系數(shù)矩陣 C 是數(shù)據(jù)集聚類的出發(fā)點(diǎn)，相似系數(shù)矩陣不僅能夠使用相關(guān)矩陣，而且能夠使用夾角余弦矩陣。2.2.3 聚類間的距離測(cè)度函數(shù)對(duì)于不同的兩個(gè)類，如果他們之間距離可定義，那么就用如下幾種定義方式來(lái)定義他們的距離：（1）最短距離法：顧名思義它表示兩個(gè)類中的元素，相離最近的兩個(gè)元素的距離來(lái)表示這兩個(gè)類之間距離，公式表示為： (2.7)（2）最長(zhǎng)距離法：跟最短

30、距離法類似，表示兩類之間距離的是兩類中距離最遠(yuǎn)的元素，公式為： . (2.8)（3）類平均法：求出兩個(gè)類中任意兩個(gè)數(shù)據(jù)的平均距離，用求出來(lái)的這個(gè)數(shù)據(jù)來(lái)表示這兩個(gè)類的平均距離，這就是類平均法，我們可以用下面的公式來(lái)表示： (2.9)（4）重心距離法：它的定義表示兩個(gè)類之間重心相鄰的距離為類距離,公式表示為： (2.10)其中類的重心公式為： （也就是各元素的平均向量之間的距離）（5）離差平方和距離：用類中各元素的離差平方和的總和得到兩個(gè)類Gr和Gk的直徑分別是Dr和Dk,類Gr+k=Gr Y Gk,用這種方法盡量讓類間的離差平方和大，而類內(nèi)部的元素間的值小，公式表示為： . (2.11)其中類直

31、徑：有的把類中相距最遠(yuǎn)的兩個(gè)元素的距離作為直徑，也有的將類中各元素指標(biāo)的離差平方和的和作為直徑，離差平方和的計(jì)算公式為： (2.12)2.2.4 聚類分析的一般步驟聚類分析的步驟大體可以分為四步9-10：（1）數(shù)據(jù)的預(yù)處理：就是在拿到一個(gè)數(shù)據(jù)集的時(shí)候，首先分析對(duì)這個(gè)數(shù)據(jù)的聚類分析要求，并根據(jù)這個(gè)要求對(duì)現(xiàn)在的數(shù)據(jù)集做降維或者特征標(biāo)準(zhǔn)化等初步的處理操作，也就是去掉沒(méi)用的特征值。（2）特征的選擇及提取：對(duì)于第一步得到的信息，進(jìn)一步細(xì)分，就是將預(yù)處理后的信息再選擇最有效的特征，并將選擇出來(lái)的特征用向量的方法轉(zhuǎn)換成新的有效突出特征，以供聚類分組時(shí)作為分組判定的條件。（3）聚類：這就要用到前面的相似性度量

32、函數(shù)，選擇距離函數(shù)還是選擇相似系數(shù)等方法來(lái)度量選出來(lái)的有效特征值的相似度，進(jìn)而完成對(duì)該數(shù)據(jù)集的聚類分析。（4）評(píng)估結(jié)果：結(jié)果進(jìn)行分析，看有沒(méi)有完成預(yù)定的要求，并根據(jù)聚類方法的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)結(jié)果進(jìn)行科學(xué)評(píng)估，即聚類分析的九個(gè)方面的要求是否滿足，然后根據(jù)評(píng)估結(jié)果判斷是否對(duì)本次的分析過(guò)程進(jìn)行改進(jìn)，以及怎樣改進(jìn)。2.3 常用的聚類分析的方法介紹目前聚類分析算法的應(yīng)用技術(shù)日趨成熟，已經(jīng)有很多的聚類算法被提出來(lái)，但是算法種類增多，同時(shí)這些算法的融合會(huì)越來(lái)越明顯，使得各種算法的界限不明顯，但是目前大家默認(rèn)的有五種劃分方法,分別是：以劃分為基礎(chǔ)的算法(Partitioning Methods)、以密度為基礎(chǔ)的算法

33、(DensitybasedMethods)、以層次的為基礎(chǔ)的算法(HierarchicalMethods)、以模型為基礎(chǔ)的算法(Modelbased Methods)、以網(wǎng)格為基礎(chǔ)的算法(Gridbased Methods)。2.3.1 基于劃分的方法劃分算法11的基本思想就是通過(guò)迭代的方法將含有M個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集分成K個(gè)簇。具體步驟是，用戶首先給定所要?jiǎng)澐值拇氐膫€(gè)數(shù)K，算法先進(jìn)行初步劃分為K組，然后用迭代的方法反復(fù)再進(jìn)行分組，每次新得到的分組比前一次要優(yōu)化，是否優(yōu)化的判定標(biāo)準(zhǔn)是同組數(shù)據(jù)之間以及不同組數(shù)據(jù)之間的相似程度，同組相似程度越大組間相似程度越小分組越優(yōu)化，目前常用的算法有K-mean

34、s算法、K-medoid算法以及以它們?yōu)榛A(chǔ)的算法的各種改進(jìn)。以劃分為基礎(chǔ)的聚類算法將在后面的章節(jié)做重點(diǎn)介紹。2.3.2 基于密度的方法基于密度的算法12與其他的算法最大的不同在于不是以元素間的距離作為判斷標(biāo)準(zhǔn)，而是根據(jù)數(shù)據(jù)對(duì)象的分布密度來(lái)判斷，正因?yàn)槿绱嗽撍惴ㄓ兄诎l(fā)現(xiàn)數(shù)據(jù)集中的噪聲數(shù)據(jù)，減少噪聲數(shù)據(jù)對(duì)聚類結(jié)果的影響，所以密度的方法可以對(duì)任意形狀的簇聚類，基本思想是將密度較大的區(qū)域識(shí)別出來(lái)，形成連在一起的密度域，并將他們歸為一類。目前比較傳統(tǒng)的的以密度為基礎(chǔ)的聚類的方法有三種，這三種算法包括是：GDBSCAN算法、OPTICS算法、DENCLUE算法。其中OPTICS算法不是直接進(jìn)行聚類，而

35、是計(jì)算出一個(gè)簇的次序，以方便自動(dòng)聚類和交互聚類分析。DBSCAN算法是檢驗(yàn)數(shù)據(jù)對(duì)象周圍的數(shù)據(jù)個(gè)數(shù)是否超過(guò)了用戶規(guī)定的范圍。DENCLUE算法是通過(guò)影響函數(shù)來(lái)判斷空間密度的方法，這就對(duì)處理高維數(shù)據(jù)非常方便有效，所以該方法對(duì)用戶的參數(shù)的個(gè)數(shù)與種類非常敏感。2.3.3 基于層次的算法層次聚類算法1有兩種不同的分解形式，分別是分裂和凝聚，它們的區(qū)別是聚類的方向不同。其中分裂的層次算法也是一種自頂向下的聚類方法，顧名思義分裂的過(guò)程就是將一個(gè)分裂為多個(gè)，一開始是將所有的數(shù)據(jù)放進(jìn)一個(gè)初始的簇中，對(duì)這個(gè)簇進(jìn)行分裂，每次迭代都會(huì)有一個(gè)更小的簇被分裂出來(lái)，最終結(jié)果是每個(gè)數(shù)據(jù)只單一的對(duì)應(yīng)唯一的一個(gè)簇結(jié)束。而凝聚的層

36、次算法正好與分裂相反，是自底向上將小的簇聚類為大的簇，在一開始的時(shí)候數(shù)據(jù)集中每一個(gè)數(shù)據(jù)對(duì)象為一個(gè)小的簇，逐步的與相鄰的簇合并最終成為一個(gè)簇時(shí)終止。比較經(jīng)常被使用的以層次為基礎(chǔ)的的聚類算法有：BIRCH算法 、CURE算法 、ROCK算法、CHAMELEON算法等。2.3.4 基于模型的算法基于模型的聚類分析算法1中的模型指的是數(shù)學(xué)模型，該算法是將數(shù)據(jù)集與某種算法形成最佳的擬合，該算法能夠利用統(tǒng)計(jì)學(xué)的方法，根據(jù)擬合的數(shù)據(jù)模型自動(dòng)確定聚類的個(gè)數(shù)K，該算法的魯棒性很強(qiáng)?；谀Ｐ退惴òㄉ窠?jīng)網(wǎng)絡(luò)方法13和統(tǒng)計(jì)方法，神經(jīng)網(wǎng)絡(luò)方法的思想是將每一個(gè)聚類描述為某個(gè)標(biāo)本，通過(guò)度量函數(shù)的計(jì)算，將新的數(shù)據(jù)對(duì)象分到相

37、對(duì)應(yīng)的標(biāo)本中，最終完成聚類。而統(tǒng)計(jì)方法將每一個(gè)聚類結(jié)果通過(guò)概率描述的方式表示出來(lái)，該方法比較適用于概念聚類。2.3.5 基于網(wǎng)格的算法網(wǎng)格的算法14的基本思想是將數(shù)據(jù)空間劃分為一定數(shù)量的格子，每次對(duì)數(shù)據(jù)的各種操作就在格子中進(jìn)行操作，該算法的處理難易程度只與網(wǎng)格的數(shù)目有關(guān)，這是網(wǎng)格聚類算法的特點(diǎn)，常用的網(wǎng)格聚類算法有STING算法、WAVECLUSTER算法、CLIQUE算法。STING算法的主要思想是先在分層的結(jié)構(gòu)中存儲(chǔ)網(wǎng)格的統(tǒng)計(jì)信息，這些統(tǒng)計(jì)信息是提前計(jì)算出來(lái)的，數(shù)據(jù)對(duì)象的空間被分成許多格子，這些格子是按層次排列，高層的格子信息被劃為許多低層次的格子信息。CLIQUE算法是網(wǎng)格與密度結(jié)合的算

38、法，它的工作過(guò)程是將數(shù)據(jù)空間劃分成不相關(guān)的網(wǎng)格，然后判斷網(wǎng)格是否是密集的，判斷標(biāo)準(zhǔn)是空間中的每一個(gè)維度，再將判斷出來(lái)的屬于密集的網(wǎng)格進(jìn)行求交的操作，并檢查這些交集是否連通良好，然后生成最小覆蓋的簇。WAVECLUSTER算法是通過(guò)把數(shù)據(jù)比作信號(hào)來(lái)判斷，多維數(shù)據(jù)對(duì)應(yīng)的是多維的信號(hào)，首先要做的也是將數(shù)據(jù)空間劃分為網(wǎng)格，該算法利用的是小波變換算法，使數(shù)據(jù)空間成為頻域空間，在數(shù)據(jù)空間中利用某一函數(shù)對(duì)這些數(shù)據(jù)做卷積，最終就能得到聚類結(jié)果。2.4 常用的劃分聚類算法的分析劃分的算法中最常用的就是K-均值算法和K中心值聚類算法和基于它們的改進(jìn)算法，分別詳細(xì)介紹這兩種算法，本章的距離函數(shù)選取的是使用目前最常用

39、的歐氏距離。2.4.1 K-均值聚類算法 K-均值算法是利用算法迭代的思想15-16，通過(guò)多次迭代改變不同簇的重心并將數(shù)據(jù)元素放到新的簇中，直到最終的聚類函數(shù)收斂時(shí)停止即可得到最終的聚類結(jié)果。本算法的計(jì)算公式表示為：KM(X,C)=j=1xjcj|Xi-Wj|2(j<=k) ； (2.13)Wj=xjcj(xi/|cj|),j=1,2,.,K；. (2.14)這個(gè)定義的公式是假設(shè)每個(gè)數(shù)組只有唯一的數(shù)據(jù)型的屬性值。該算法要用戶期望的聚類結(jié)果的組數(shù)作為輸入值K，而每個(gè)簇內(nèi)的初始數(shù)據(jù)是根據(jù)電腦隨機(jī)分配的，也可以依次取前K個(gè)元素，該迭代算法直到?jīng)]有數(shù)據(jù)元素再被分到不同的組中時(shí)就是算法結(jié)束的時(shí)候。

40、KM算法的時(shí)間復(fù)雜性為0(xKM),x表示本次實(shí)驗(yàn)一共迭代了多少次，K是聚類所生成的簇?cái)?shù)，M是數(shù)據(jù)集的個(gè)數(shù)。因?yàn)樵撍惴ㄊ嵌x在數(shù)值型的屬性上的，對(duì)該數(shù)據(jù)集假如還有其他屬性是不能識(shí)別的，所以該算法所得的并不是全局最優(yōu)解，而是局部的，而且也不能處理其他形狀的簇，只對(duì)凸形簇敏感。K-均值算法多次迭代的最終結(jié)果就是使目標(biāo)函數(shù)KM（）最小值，通過(guò)該公式我們發(fā)現(xiàn)該算法必須預(yù)先選好初始點(diǎn)，對(duì)初始點(diǎn)有很強(qiáng)烈的依賴性，如果該初始點(diǎn)選取不合適會(huì)影響整個(gè)結(jié)果，這是該算法的一個(gè)缺點(diǎn)，可以改進(jìn)的地方是用層次聚類等方法能夠提前計(jì)算出比較合適的初始點(diǎn)，再開始聚類。除此之外K-均值算法還有其他缺點(diǎn)，它在時(shí)間上并不具備高效性。

41、為了找到全局最優(yōu)解，必須謹(jǐn)慎選取初值和簇?cái)?shù)，還可以計(jì)算簇內(nèi)的方差，如果方差值很大就可以選擇將該簇分裂為兩個(gè)簇來(lái)提高有效性，方差值過(guò)小而且比設(shè)置的最小值還要小就要考慮合并兩個(gè)簇。2.4.2 K-中心聚類法已經(jīng)介紹過(guò)KM算法對(duì)簇中心的選取非常敏感，選取不恰當(dāng)會(huì)對(duì)聚類結(jié)果產(chǎn)生影響，這是KM算法的缺陷，如果有一個(gè)與簇中心點(diǎn)相距很遠(yuǎn)的點(diǎn)被選為初始點(diǎn)就會(huì)非常明顯的影響聚類質(zhì)量。但是數(shù)據(jù)集中這種孤立點(diǎn)難免會(huì)出現(xiàn)，所以為了減少這種噪音數(shù)據(jù)對(duì)聚類結(jié)果的影響，K-中心聚類算法17-20出現(xiàn)，它與KM算法最大的區(qū)別是它是用最接近中心的那個(gè)數(shù)據(jù)對(duì)象來(lái)代表這個(gè)簇，而不是用所有數(shù)據(jù)對(duì)象的均值來(lái)代表該簇，這樣有效的避免了噪

42、音數(shù)據(jù)的干擾，這也是K-中心聚類算法與KM算法唯一的區(qū)別，其他的步驟大相徑庭，沒(méi)有太大的區(qū)別。它所用的目標(biāo)函數(shù)公式是：J=j=1xWi|x-mj| (2.15)其中Wi表示數(shù)據(jù)集中的人一個(gè)對(duì)象，mj表示該簇的中心，該算法除了不受孤立點(diǎn)影響之外還不受數(shù)據(jù)輸入順序的影響。 K-中心算法中的最早的PAM算法只適用小規(guī)模數(shù)據(jù)集聚類的算法，該算法的主要的思想是電腦自動(dòng)隨機(jī)選出數(shù)據(jù)集中的K個(gè)數(shù)據(jù)對(duì)象為初始簇中的初始數(shù)據(jù)，然后根據(jù)距離函數(shù)計(jì)算剩余數(shù)據(jù)跟各個(gè)初始數(shù)據(jù)的距離，并挑選出距離最小的初始簇，將該點(diǎn)歸入到該簇中，并計(jì)算新的簇代表，即迭代這些操作，持續(xù)到?jīng)]有非代表的數(shù)據(jù)對(duì)象替換現(xiàn)在的簇代表對(duì)象為止，從而實(shí)

43、現(xiàn)中心點(diǎn)聚類算法的聚類。PAM算法對(duì)大數(shù)據(jù)集不具備高效性，一種新的算法也被人們提出來(lái)，它就是CLARA算法，該算法是對(duì)大的數(shù)據(jù)集進(jìn)行N次的抽取小數(shù)據(jù)集樣本，并依次對(duì)這些小的數(shù)據(jù)集使用PAM算法，充分發(fā)揮PAM算法的優(yōu)勢(shì)，得到N個(gè)聚類結(jié)果，然后再?gòu)倪@N個(gè)聚類結(jié)果中選擇一個(gè)最優(yōu)解作為最終整個(gè)數(shù)據(jù)集的結(jié)果。為了保證最終結(jié)果的可靠，抽樣過(guò)程中必須遵循隨機(jī)性，除此之外還要掌握好抽樣的規(guī)模大小，要適度，不能盲目抽取浪費(fèi)時(shí)間，把握效率和效果的充分平衡。2.5 本章小結(jié)本章詳細(xì)介紹了聚類分析相關(guān)的基礎(chǔ)知識(shí)，分析了它的定義，屬性，表示方法，相似性測(cè)量度，距離函數(shù)等方面。并對(duì)常用的五種聚類分析的方法：劃分的方法、

44、密度方法、層次的方法、網(wǎng)格的方法、模型的方法，進(jìn)行詳細(xì)介紹，并簡(jiǎn)要敘述了各方法中常用算法的基本思想和優(yōu)缺點(diǎn)，最后著重詳細(xì)的介紹了基于劃分的兩種聚類分析算法：K-均值算法和K-中心值算法。3 K一均值聚類算法的研究3.1 K-均值聚類算法介紹k-means算法21-23是在1967年MacQueen第一次發(fā)現(xiàn)并提出來(lái)的，也被稱為K-平均或K-均值聚類算法。為應(yīng)用最廣泛的一種聚類方法。主要特點(diǎn)為將每個(gè)群集子集內(nèi)的所有數(shù)據(jù)樣本的平均值作為集群的代表點(diǎn)。算法的主要思想為通過(guò)采取一種反復(fù)的過(guò)程使數(shù)據(jù)集被分成不同的類別，進(jìn)而使用評(píng)價(jià)結(jié)果的聚類性能標(biāo)準(zhǔn)的功能來(lái)實(shí)現(xiàn)的，從而使產(chǎn)生的每個(gè)群集的緊湊及獨(dú)立。這種算

45、法不適合處理離散屬性，可是對(duì)于連續(xù)性具有較好的集聚效應(yīng)。3.1.1 K一均值聚類算法基本思想K-means算法的工作原理可以總結(jié)為：首先，要從數(shù)據(jù)集中自動(dòng)隨機(jī)選擇K個(gè)點(diǎn)作為初始聚類中心，然后分別將每種樣品計(jì)算其與集群的距離，樣品分類的標(biāo)準(zhǔn)為其與聚類中心的距離。利用距離函數(shù)計(jì)算出每一個(gè)新生成的所要作聚類的數(shù)據(jù)對(duì)象的平均距離值，并用這個(gè)平均距離值來(lái)作為新的聚類中心，倘若相鄰兩次計(jì)算所得到的聚類中心點(diǎn)并沒(méi)有發(fā)生一點(diǎn)的改變，那么就能夠證明樣本調(diào)整過(guò)程就算完成了，也就是表示聚類準(zhǔn)則函數(shù)目前達(dá)到了收斂。本算法有一個(gè)明顯的特點(diǎn)，就是在迭代過(guò)程中要對(duì)每個(gè)樣本的分類結(jié)果進(jìn)行驗(yàn)證觀察是不是正確。假如是不正確的，那

46、么則需要對(duì)聚類進(jìn)行調(diào)整。等所有的樣本調(diào)整完成以后，然后下一步就是對(duì)聚類中心的修改，從而開始進(jìn)入下一次迭代過(guò)程中去。倘若在某一次迭代算法過(guò)程中，所有樣本的分類結(jié)果是正確的，無(wú)需調(diào)整，聚類中心也沒(méi)會(huì)出現(xiàn)有一點(diǎn)任何變化，那么這表明該聚類函數(shù)收斂，從而算法就結(jié)束了。3.1.2 K一均值聚類算法主要流程輸入：含有n個(gè)數(shù)據(jù)對(duì)象個(gè)數(shù)的數(shù)據(jù)庫(kù)和所需要的簇的數(shù)目k。輸出：k個(gè)簇。平方誤差準(zhǔn)則達(dá)到最小。算法描述：（1） 從 n個(gè)數(shù)據(jù)對(duì)象中自動(dòng)隨機(jī)的選擇 k 個(gè)對(duì)象來(lái)作為初始狀態(tài)的的聚類中心； （2） 根據(jù)各個(gè)聚類對(duì)象的均值（即每個(gè)簇的中心點(diǎn)），來(lái)計(jì)算各個(gè)數(shù)據(jù)對(duì)象與所有中心對(duì)象之間的距離。并以最短距離的為依據(jù)要求對(duì)

47、相應(yīng)的對(duì)象進(jìn)行再一次的劃分； （3） 重新計(jì)算各個(gè)發(fā)生了變化的聚類的均值（即距離中心對(duì)象）； （4） 循環(huán)過(guò)程（2）到（3）直至各個(gè)聚類不再發(fā)生變化為止。算法步驟： 1.為各個(gè)聚類確定一個(gè)初始的聚類中心，這樣就可以產(chǎn)生K 個(gè)初始聚類中心。 2.按最小距離的原則把樣本集中的樣本分配到最鄰近聚類。3.把各聚類中的樣本均值規(guī)定為新的聚類中心。4.重復(fù)執(zhí)行步驟2、3直至聚類中心不再發(fā)生變化。5.結(jié)束過(guò)程，得到K個(gè)聚類。3.2 K-均值聚類算法的主要缺陷及分析主要優(yōu)點(diǎn)：（1）作為解決聚類問(wèn)題而出現(xiàn)的一種傳統(tǒng)經(jīng)典算法，具有簡(jiǎn)單、快速的特點(diǎn)。對(duì)于較大數(shù)據(jù)集的聚類分析來(lái)說(shuō)，該算法相比較而言是可伸縮和高效率的。

48、因?yàn)樗臅r(shí)間復(fù)雜度是0 (n k x ) 。其中, n 是所有對(duì)象的個(gè)數(shù), k 是所需要的簇的個(gè)數(shù), x 是迭代發(fā)生了多少次。通常情況下有k <<n 且x <<n 。（2）當(dāng)結(jié)果簇是密集的，而且簇與簇之間的區(qū)別較為明顯時(shí), 它的效果比較較好。主要缺點(diǎn)：（1）K-均值算法只是在簇的平均值已經(jīng)提前被定義了的情況時(shí)才能被使用，而這個(gè)前提對(duì)于處理符號(hào)屬性的數(shù)據(jù)并不適用。在 K-means 算法中，首先要根據(jù)初始的聚類中心來(lái)確定一個(gè)適合的初始劃分，接著要對(duì)初始劃分開始進(jìn)行進(jìn)一步的優(yōu)化操作。聚類結(jié)果對(duì)這個(gè)初始點(diǎn)的選擇是相當(dāng)敏感的。倘若初始值選擇的不合適很可能造成不能得到準(zhǔn)確的聚類結(jié)

49、果的后果。這也是K-means算法目前存在的一個(gè)主要問(wèn)題。對(duì)于該問(wèn)題的解決，許多算法采用遺傳算法GA，例如可以采用遺傳算法GA來(lái)進(jìn)行初始化操作，而且內(nèi)部聚類準(zhǔn)則被當(dāng)做評(píng)價(jià)指標(biāo)。（2）必須事先給出k值（想要生成的簇的個(gè)數(shù)）。并且對(duì)初值很敏感：不同的初始K值，也許將導(dǎo)致不同結(jié)果。在 K-means 算法中K值是要求提前必須給定的，但是這個(gè)值的選擇是相當(dāng)難以估計(jì)的。實(shí)際情況下大部分時(shí)候提前是并不能確定給定的數(shù)據(jù)集應(yīng)劃分成多少個(gè)類別才最適合這個(gè)數(shù)據(jù)集。這也是該算法的一個(gè)缺點(diǎn)。有的算法是通過(guò)采用類的自動(dòng)識(shí)別它的初始數(shù)據(jù)集的分類和合并來(lái)得到較為合適聚類的簇?cái)?shù)。例如 ISODATA 算法。對(duì) K-means

50、 算法中的聚類數(shù)目K 值的確定有很多方法，有的是根據(jù)方差分析理論結(jié)合應(yīng)用混合 F 統(tǒng)計(jì)量來(lái)得到最合適分類數(shù)，并且采用模糊劃分熵的方法來(lái)驗(yàn)證其合理性。有的使用一種結(jié)合了全協(xié)方差矩陣的RPCL算法，而且逐步刪去那些僅僅包含很少數(shù)據(jù)量的訓(xùn)練數(shù)據(jù)的類。還有的使用一種名為次勝者受罰的學(xué)習(xí)競(jìng)爭(zhēng)規(guī)從而自動(dòng)決定類的合理數(shù)目。它的思想為：對(duì)于每個(gè)輸入來(lái)說(shuō)，不但獲勝單元的權(quán)值被加以修正以便適應(yīng)輸入值。而且對(duì)于次勝單元?jiǎng)t采用懲罰的方法以使其遠(yuǎn)離輸入值。（3）該算法對(duì)“噪聲數(shù)據(jù)”以及孤立的點(diǎn)數(shù)據(jù)是相當(dāng)敏感的，即使少量的該類數(shù)據(jù)也可以對(duì)平均值產(chǎn)生相當(dāng)大的影響。（4）從 K-means 算法流程中可以清楚的看到，該算法的

51、實(shí)現(xiàn)原理要求必須不斷地對(duì)樣本進(jìn)行分類，并且必須不斷地計(jì)算更新調(diào)整后的新的聚類中心。所以當(dāng)數(shù)據(jù)量很大時(shí)，算法的時(shí)間復(fù)雜度是非常大的。因此需要對(duì)算法的時(shí)間復(fù)雜度時(shí)刻進(jìn)行關(guān)注、審查以滿足時(shí)間等的要求。例如可以利用一定的相似性準(zhǔn)則來(lái)排除一些近似的聚類中心的侯選集。3.3 本章小結(jié)本章主要是針對(duì)K-均值算法作了系統(tǒng)的分析，介紹了它的基本定義、基本思想、主要流程，最后詳細(xì)分析了該算法在實(shí)際應(yīng)用中的優(yōu)點(diǎn)和不足。K-均值算法是數(shù)據(jù)挖掘聚類劃分算法中最基本的算法，雖然它本身在實(shí)際應(yīng)用的過(guò)程中存在不足，但是我們不能忽視它本身對(duì)數(shù)據(jù)集聚類的優(yōu)點(diǎn)，在有的實(shí)踐應(yīng)用中也取得了理想的效果，很多的算法也是以此為依據(jù)進(jìn)行改進(jìn)的

52、，主要是對(duì)距離計(jì)算的改進(jìn)，如P-CLUSTER算法，就是基于K-均值算法的一種改進(jìn)，是啟發(fā)知識(shí)來(lái)判斷該數(shù)據(jù)集聚類對(duì)象M的最近的簇中心是否改變。4 K-均值聚類算法的實(shí)驗(yàn)4.1 實(shí)驗(yàn)結(jié)果分析 實(shí)驗(yàn)一：本文測(cè)試采用的是從數(shù)據(jù)堂下載的c-fat500-10.txt數(shù)據(jù)集，對(duì)K-均值算法進(jìn)行了驗(yàn)證，經(jīng)過(guò)實(shí)驗(yàn)分別對(duì)150個(gè)數(shù)據(jù)的數(shù)據(jù)集選取不同初始點(diǎn)分別進(jìn)行聚類，驗(yàn)證不同的初始條件對(duì)最終聚類結(jié)果的影響情況，得到的聚類結(jié)果分別如下圖：令前三個(gè)數(shù)據(jù)p1p2p3作為初始聚類中心，如圖4.1所示：圖4.1 初始點(diǎn)為第1 2 3序號(hào)的聚類圖把第p4p5p6個(gè)數(shù)據(jù)作為初始聚類中心，得到的聚類結(jié)果如圖4.2所示：圖4.

53、2 初始點(diǎn)為第4 5 6序號(hào)的聚類圖把第p100p101p102個(gè)數(shù)據(jù)作為初始聚類中心，得到的聚類結(jié)果如圖4.3所示：圖4.3 初始點(diǎn)為第100 101 102序號(hào)的聚類圖 把第p1p10p100個(gè)數(shù)據(jù)作為初始聚類中心，結(jié)果如圖4.4所示：圖4.4 初始點(diǎn)為第1 10 100序號(hào)的聚類實(shí)驗(yàn)分析與結(jié)論：分析：由以上聚類結(jié)果發(fā)現(xiàn)，不同的初始值的選取對(duì)聚類結(jié)果并不是造成很大影響，比較圖4.1和圖4.2可得，初始值選取的不同，只是造成聚類結(jié)果中極少數(shù)的數(shù)據(jù)發(fā)生變化，如數(shù)據(jù)20、27，聚類的迭代次數(shù)發(fā)生了改變由5次變?yōu)?次，還有不同點(diǎn)就是，聚類結(jié)果的輸出順序也發(fā)生了變化；對(duì)比圖4.3和圖4.2的聚類結(jié)果

54、圖可得，選擇第100、101、102個(gè)數(shù)據(jù)與選擇第4、5、6個(gè)數(shù)據(jù)作為初始點(diǎn)的聚類結(jié)果是一樣的，不同之處就是數(shù)據(jù)聚類的輸出順序有所改變，可是圖4.3的迭代次數(shù)又比圖4.2的迭代次數(shù)增多，變?yōu)?次；前三次的實(shí)驗(yàn)是選取連續(xù)的數(shù)據(jù)作為初始點(diǎn)，在第四次的實(shí)驗(yàn)中，選取第1、10、100個(gè)數(shù)據(jù)不連續(xù)的這三個(gè)數(shù)據(jù)作為初始值，從結(jié)果圖可以看出，本次實(shí)驗(yàn)與第一次的聚類結(jié)果和迭代次數(shù)都相同，只是數(shù)據(jù)輸出順序有所改變。結(jié)論：首先對(duì)比四個(gè)圖的聚類結(jié)果，并沒(méi)有因?yàn)槌跏键c(diǎn)選取的不同而發(fā)生大的改變，只是改變了迭代次數(shù)，其中選取最前面的三個(gè)數(shù)據(jù)和后面某一不連續(xù)的數(shù)據(jù)為初始點(diǎn)時(shí)迭代次數(shù)最少。實(shí)驗(yàn)表明：K-均值算法對(duì)初始值得敏感

55、體現(xiàn)在對(duì)聚類結(jié)果的迭代次數(shù)上，選取合理的初始點(diǎn)有助于我們高效率的完成聚類工作，用最少的時(shí)間完成我們所需要的結(jié)果為我們更好的應(yīng)用在實(shí)際生活上。因此，從這此實(shí)驗(yàn)我們得到的結(jié)論是：（1）盡量選擇數(shù)據(jù)最開始的連續(xù)的點(diǎn)作為初始點(diǎn)，這樣可以用最少的迭代次數(shù)完成聚類；（2）改變K-均值算法的初始點(diǎn)可以影響數(shù)據(jù)集的迭代次數(shù)，對(duì)聚類結(jié)果影響不大；（3）每次初始值的改變也會(huì)造成數(shù)據(jù)輸出順序的改變，即使是在聚類結(jié)果不變的情況下。實(shí)驗(yàn)二：本次試驗(yàn)是驗(yàn)證不同的數(shù)據(jù)輸入順序，對(duì)聚類結(jié)果的影響，實(shí)驗(yàn)的數(shù)據(jù)集為了更具說(shuō)服力，還是用實(shí)驗(yàn)一中的數(shù)據(jù)，不同之處是，此次實(shí)驗(yàn)只是將數(shù)據(jù)集中的后75個(gè)數(shù)放到前面，也就是與前75個(gè)數(shù)調(diào)換一

56、下順序，本次試驗(yàn)只是驗(yàn)證數(shù)據(jù)集輸入順序的改變對(duì)聚類結(jié)果的影響，所以只選取兩種初始值進(jìn)行驗(yàn)證，與實(shí)驗(yàn)一進(jìn)行對(duì)比，可得實(shí)驗(yàn)結(jié)果如下：令前三個(gè)數(shù)據(jù)p1p2p3作為初始聚類中心，如圖4.5所示：圖4.5 數(shù)據(jù)輸入順序改變聚類圖1把第p4p5p6個(gè)數(shù)據(jù)作為初始聚類中心，得到的聚類結(jié)果如圖4.6所示：圖4.6 數(shù)據(jù)輸入順序改變聚類圖2實(shí)驗(yàn)分析與結(jié)論：分析：本次實(shí)驗(yàn)主要是與之前的數(shù)據(jù)順序不同時(shí)所得的聚類結(jié)果，由圖4.5與圖4.1，圖4.6與圖4.2的對(duì)比結(jié)果可得出，改變了數(shù)據(jù)的輸入順序，造成聚類結(jié)果有很大的改變，同時(shí)迭代次數(shù)也增加了，這說(shuō)明K-均值算法對(duì)數(shù)據(jù)輸入順序的敏感性不僅體現(xiàn)在迭代次數(shù)上，而且更會(huì)改變數(shù)據(jù)的迭代次數(shù)。另外，再對(duì)比圖4.5與圖4.6的結(jié)果，雖然兩次的聚類結(jié)果是一樣的，但是