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

1、<p><b>　　本科生畢業(yè)論文設計</b></p><p><b>　　二零一三年五月二日</b></p><p><b>　　目 錄</b></p><p>　　中文摘要、關(guān)鍵字 1</p><p><b>　　1 緒論 3</b>

2、</p><p>　　1.1 本文研究的背景和意義 3</p><p>　　1.2 聚類分析國內(nèi)外研究現(xiàn)狀 5</p><p>　　1.3 本文所做的主要工作 7</p><p>　　2 聚類算法的分析與研究 8</p><p>　　2.1 數(shù)據(jù)挖掘簡介 8</p><p>

3、　　2.2 聚類的基本知識 8</p><p>　　2.2.1 類的定義及表示 9</p><p>　　2.2.2 聚類的相似度量方法 9</p><p>　　2.2.3 聚類間的距離測度函數(shù) 11</p><p>　　2.2.4 聚類分析的一般步驟 12</p><p>　　2.3 常用的聚類分

4、析的方法介紹 13</p><p>　　2.3.1 基于劃分的方法 13</p><p>　　2.3.2 基于密度的方法 13</p><p>　　2.3.3 基于層次的算法 13</p><p>　　2.3.4 基于模型的算法 14</p><p>　　2.3.5 基于網(wǎng)格的算法 14</

5、p><p>　　2.4 常用的劃分聚類算法的分析 14</p><p>　　2.4.1 K-均值聚類算法 15</p><p>　　2.4.2 K-中心聚類法 15</p><p>　　2.5 本章小結(jié) 16</p><p>　　3 K一均值聚類算法的研究 17</p><p>

6、　　3.1 K-均值聚類算法介紹 17</p><p>　　3.1.1 K一均值聚類算法基本思想 17</p><p>　　3.1.2 K一均值聚類算法主要流程 17</p><p>　　3.2 K-均值聚類算法的主要缺陷及分析 18</p><p>　　3.3 本章小結(jié) 19</p><p>　　

7、4 K-均值聚類算法的實驗 20</p><p>　　4.1 實驗結(jié)果分析 20</p><p>　　4.2 本章小結(jié) 25</p><p>　　5 總結(jié)與展望 26</p><p>　　5.1 總結(jié) 25</p><p>　　5.2 展望 26</p><p><

8、b>　　參考文獻 28</b></p><p>　　英文摘要、關(guān)鍵字 31</p><p>　　論文題目：數(shù)據(jù)挖掘K均值算法實現(xiàn)</p><p>　　摘要：隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，現(xiàn)在的人們每一天都會面臨例如文本、圖像、視頻、音頻等各種數(shù)據(jù)形式，這些數(shù)據(jù)的數(shù)據(jù)量的大小是很驚人的。怎樣能夠很快的并且高效地從這些大量數(shù)據(jù)中挖掘提煉出它所蘊含的價值

9、，成為現(xiàn)在人們特別關(guān)注并且需要馬上解決的問題。數(shù)據(jù)挖掘(Data Mining，DM)正是因為這個才慢慢誕生出來。數(shù)據(jù)挖掘經(jīng)過一段時間的迅猛發(fā)展，誕生出了大量的理論結(jié)果和現(xiàn)實使用成果，它提供了許多工具和卓有成效的方法來解決問題。數(shù)據(jù)挖掘中有一項是很重要的研究領(lǐng)域，那就是聚類分析，這是一種對數(shù)據(jù)進行按照不同的依據(jù)將數(shù)據(jù)進行分組或者將數(shù)據(jù)進行劃分的方式。聚類無論在生物科學研究，還是在商務貿(mào)易中、圖像分析處理、網(wǎng)頁內(nèi)容分類等其他日常生活的領(lǐng)域

10、都得到了很好的應用。</p><p>　　根據(jù)使用的數(shù)據(jù)類型、使用的功能的不同、聚類需求的不同，目前的聚類算法大概有以下幾種：基于劃分的算法、基于層次的算法、基于密度的的算法、基于模型的算法以及基于網(wǎng)格的算法。在這之中，基于劃分的K-均值聚類算法是目前研究最成熟傳統(tǒng)經(jīng)典的算法。K-均值算法的應用領(lǐng)域特別廣泛，覆蓋范圍涉及語音頻率壓縮還有圖像及文本聚類，另外在數(shù)據(jù)預處理和神經(jīng)網(wǎng)絡結(jié)構(gòu)的任務分解等也發(fā)揮其重要用途。本

11、文所做的工作有：</p><p>　　本文第一部分：詳細介紹了本次論文研究的背景和目的，以及所選題目的考慮思路，還有在當前國際形式下，聚類分析在國際上的地位及國內(nèi)外研究成果綜述，最后介紹了本論文算法實現(xiàn)的內(nèi)容和論文整體布局安排。</p><p>　　第二部分：首先詳細描述了數(shù)據(jù)挖掘的來源發(fā)展還有它的概念定義，下面主要介紹聚類分析，包括聚類的基本概念原理等基礎(chǔ)性知識，介紹了聚類算法的內(nèi)部特性

12、，詳細描述了幾種目前聚類分析的方法，總結(jié)比較各個方法的特點及其長短處。最后對本論文所研究的基于劃分的聚類算法進一步討論都有哪幾種算法。</p><p>　　第三部分：這是本論文的重點，本論文所要討論的K-均值算法，從它的概念基本思想算法流程等方面對K-均值算法進行詳細系統(tǒng)的介紹，并且詳細分析了它的優(yōu)缺點。K-均值算法對初始值的選取比較敏感和對數(shù)據(jù)的輸入順序不同也會影響聚類等問題，所以本文針對該問題進行了驗證，通過

13、實驗證明了這兩個因素對聚類結(jié)果會有哪些影響。實驗表明，K-均值算法對初始值和數(shù)據(jù)輸入順序很敏感，但是這兩個對聚類結(jié)果影響的方面不同。本文通過六個實驗結(jié)果分析得出，改變初始點，對聚類結(jié)果的影響不大，只是會改變迭代次數(shù)，而且選取初始的連續(xù)的幾個數(shù)據(jù)為初始點迭代次數(shù)最少，雖然中間間隔的幾個數(shù)據(jù)作為初始點也出現(xiàn)了最小的迭代次數(shù)，但這對數(shù)據(jù)集來說有太多的不確定性，所以還是選擇最開始那幾個數(shù)據(jù)為數(shù)據(jù)聚類初始點；對于改變數(shù)據(jù)集的輸入順序，聚類結(jié)果與之

14、前的有很大的改變，實驗結(jié)果說明輸入順序不同既影響了聚類結(jié)果也影響了迭代次數(shù)。通過這些結(jié)論為以后用戶使用K-均值算法提供了很好的幫助，也為該算法的改進提供了參考。</p><p>　　關(guān)鍵詞：數(shù)據(jù)挖掘 聚類分析 K-means算法 實驗驗證</p><p><b>　　1 緒論</b></p><p>　　1.1 本文研究的背景和意

15、義</p><p>　　近年來，隨著科技的進步以及互聯(lián)網(wǎng)的普及，以計算機為代表的信息技術(shù)有了巨大發(fā)展，人們產(chǎn)生、發(fā)現(xiàn)、整理、利用數(shù)據(jù)的能力不斷提升。到目前為止，數(shù)據(jù)在我們的日常生活中無處不在，它廣泛應用于科學研究、政府日常辦公、軍事力量分析、企業(yè)管理電子商務、統(tǒng)計學分析等等各個領(lǐng)域。雖然我們知道這些數(shù)據(jù)的重要性，但是隨著時間越來越久，我們積累的數(shù)據(jù)量是不斷地在加大，相應的我們分析處理這些數(shù)據(jù)的能力也要增加，但是后

16、來數(shù)據(jù)量的增長速度已經(jīng)超出了我們的能力范圍，所以我們必將面臨的嚴峻問題是數(shù)據(jù)爆炸。難道真的沒有辦法可以很科學的處理這些海量數(shù)據(jù)嗎？事實并非如此，人類的智慧是無窮的，人們已經(jīng)通過理性的思維和恰當?shù)募夹g(shù)，將這些海量數(shù)據(jù)充分利用，使它們成為社會發(fā)展進步的強大的力量源泉。目前，廣泛使用的數(shù)據(jù)庫系統(tǒng)雖然具有高效率的錄入所有數(shù)據(jù)查詢所需數(shù)據(jù)統(tǒng)計數(shù)據(jù)類別等功能，但是并不能發(fā)現(xiàn)這些海量數(shù)據(jù)中蘊藏的內(nèi)部關(guān)聯(lián)規(guī)則，也無法從當前現(xiàn)在的數(shù)據(jù)情況去預測未來的數(shù)據(jù)

17、內(nèi)容的發(fā)展趨勢，更不可能做出決策判斷，使得人們逼不得已去面對“數(shù)據(jù)豐富而知識缺乏”的困鏡[1]。所以數(shù)據(jù)挖掘（Data Mining）技術(shù)因此就慢慢誕生了，并且快速的發(fā)</p><p>　　數(shù)據(jù)挖掘（Data Mining），也被叫做在已知的數(shù)據(jù)庫中對知識的發(fā)現(xiàn)（knowledge discovery ,KDD）,就是從數(shù)量巨大的、不完整的、有孤立點數(shù)據(jù)的、模糊的、隨機的數(shù)據(jù)中，提取發(fā)掘出來隱含在當中的、人們在這

18、之前不是特別了解的、但又是隱含有用的信息內(nèi)容和知識內(nèi)容的非平凡過程[2] 。原始的數(shù)據(jù)類型可以是多樣的，比如數(shù)據(jù)庫中的數(shù)據(jù)結(jié)構(gòu)化數(shù)據(jù)類型，那些圖像圖形資料及文字類資料是半結(jié)構(gòu)化的數(shù)據(jù)類型，當然也包括網(wǎng)絡互聯(lián)網(wǎng)上的那些數(shù)據(jù)我們稱它們?yōu)榘虢Y(jié)構(gòu)化的數(shù)據(jù)類型。我們可以通過歸納演繹等方法來發(fā)現(xiàn)知識，也可以用統(tǒng)計學的數(shù)學或非數(shù)學的方法總結(jié)數(shù)據(jù)來得到我們想要的信息。這些我們得到的信息內(nèi)容和知識內(nèi)容的過程就是挖掘的一個過程，我們把挖掘的知識可以應用到我

19、們的生活中，包括未來決策規(guī)劃、優(yōu)化信息管理方案、調(diào)整控制模式、改進查詢方案等等來更好的維護和利用我們現(xiàn)有的數(shù)據(jù)。所以數(shù)據(jù)挖掘涉及到的學科很廣泛，它是各個學科的交叉，它用到了人工智能數(shù)學統(tǒng)計學與數(shù)據(jù)庫等技術(shù)來實現(xiàn)它自己的目的，需要這些領(lǐng)域的工程技術(shù)人員來共同配合，尤其是數(shù)據(jù)庫管理人員。</p><p>　　現(xiàn)在的數(shù)據(jù)挖掘技術(shù)已經(jīng)開始走向科技產(chǎn)品研發(fā)及技術(shù)應用，不再是之前的單純的搞一下研究而已，我國市場經(jīng)濟制度在不斷

20、地完善與發(fā)展，經(jīng)濟實力也在不斷進步，現(xiàn)在我們的社會對數(shù)據(jù)挖掘技術(shù)的需求越來越強烈，目前我國很多的有眼光的軟件企業(yè)已經(jīng)將目光聚集于此，來研發(fā)更多適應市場需求的數(shù)據(jù)挖掘軟件產(chǎn)品，隨著市場日趨成熟，廣大消費者的應用需求也是慢慢變大，相信將來會有更多成熟的中國數(shù)據(jù)挖掘軟件面向市場。</p><p>　　聚類分析是數(shù)據(jù)挖掘的一個發(fā)現(xiàn)信息的方法，已經(jīng)被人們深入的研究了很長時間，主要的是對基于距離的聚類分析的研究。聚類是一種無

21、監(jiān)督的學習，分類正好與它相反，分類是一種有監(jiān)督的學習，聚類主要是劃分無標記的對象，使這些無標記的對象變的有意義，對預先定義的類與帶類標記的訓練實例不具有依賴性。所以聚類分析在我們的日常生活中的應用范圍非常廣泛：</p><p>　?、?在商業(yè)上，聚類可以根據(jù)消費者數(shù)據(jù)庫里面所記錄的數(shù)據(jù)信息，對消費者進行劃分，根據(jù)各個消費者的特征，以幫助市場營銷員按照市場需求及時調(diào)整貨物的擺放次序等一系列營銷計劃的實施；</

22、p><p>　?、?在社會學中，聚類用來發(fā)現(xiàn)目前社會結(jié)構(gòu)組成中潛在的社會結(jié)構(gòu)；</p><p>　　③ 在網(wǎng)絡挖掘中對互聯(lián)網(wǎng)上批量的數(shù)據(jù)信息進行有效的劃分與分類，實現(xiàn)信息的有效利用，對數(shù)據(jù)信息檢索效率方面有顯著提高；</p><p>　　④ 在生物信息學中，在大量的基因群中發(fā)現(xiàn)功能相似的基因組，對基因因功能不同進行劃分對其固有的結(jié)構(gòu)特征進行分析，來更好的為我們的醫(yī)學發(fā)展

23、提供有利條件；</p><p>　?、?在空間數(shù)據(jù)庫領(lǐng)域，聚類分析能對相似地理特征區(qū)域及它們的人和環(huán)境的不同特征進行識別，來研究地域文化提供條件。</p><p>　　本文主要選擇聚類分析中基于劃分的K-means算法并實現(xiàn)它的應用，對數(shù)據(jù)集的數(shù)據(jù)進行聚類分析。本文在實現(xiàn)它的基礎(chǔ)上，對該算法對初始值和數(shù)據(jù)輸入順序敏感的問題進行了驗證，通過六次試驗，分別對這個兩個方面進行驗證，并對聚類結(jié)果進

24、行分析比較，從而得出結(jié)論。本文通過對不同輸入條件的實驗驗證，得出K-均值算法對初始值得選擇和數(shù)據(jù)輸入順序是很敏感的結(jié)論，通過實驗結(jié)果可得出在今后使用K-均值算法時我們應該怎樣避免其聚類出不準確的聚類結(jié)果和今后改進算法應該改進的方向等問題。</p><p>　　1.2 聚類分析國內(nèi)外研究現(xiàn)狀</p><p>　　目前，國內(nèi)對于數(shù)據(jù)挖掘聚類分析的研究的集中部門還是科研單位和各大高校，國內(nèi)還沒

25、有公司企業(yè)專門從事聚類分析的研究，相對于外國來說起步較晚。各大科研機構(gòu)與高校對聚類的研究主要是對數(shù)據(jù)集聚類算法的設計并實現(xiàn)，以研究出來的算法為基礎(chǔ)對算法改進。目前人們已經(jīng)在統(tǒng)計分析軟件中應用一些聚類分析工具，如SAS等軟件。</p><p>　　為大型的數(shù)據(jù)庫尋求有效的聚類分析方法是目前聚類分析的主要研究工作，目前研究方向包括以下幾個方向：</p><p>　?。?）可伸縮性：目前的聚類算

26、法針對小型數(shù)據(jù)庫，數(shù)據(jù)量是幾百范圍內(nèi)的，對于有很龐大數(shù)據(jù)量的數(shù)據(jù)庫會造成結(jié)果的不穩(wěn)定性，可伸縮性強的算法就亟待的研發(fā)出來。</p><p>　?。?）屬性不同情況下的處理能力：現(xiàn)在開發(fā)出來的聚類算法所針對的數(shù)據(jù)類型都是數(shù)值型，但實際上的聚類類型的信息是不確定的，如二元數(shù)據(jù)、序數(shù)型的、分類型的等或者是所已知的各種數(shù)據(jù)類型的混合。</p><p>　?。?）聚類形狀：在歐幾里得距離的基礎(chǔ)上發(fā)現(xiàn)

27、所得的簇的形狀是球狀簇，它們有相近的距離與密度，形成一個簇，但是我們更希望能夠有一種算法實現(xiàn)各個不同形狀的簇。</p><p>　　（4）決定結(jié)果的輸入?yún)?shù)：聚類算法的實現(xiàn)過程中相當多的是必須讓用戶提前輸入想要聚類出來的簇數(shù)K，當前的算法對這些K的值是相當敏感的，大型的數(shù)據(jù)流對這些要求很嚴格，對結(jié)果的影響很明顯，使用戶在輸入時加大了分析的工作難度，很難控制。</p><p>　　（5）輸入

28、數(shù)據(jù)的順序問題：有的聚類算法對輸入數(shù)據(jù)的順序是有要求的，不同的輸入次序會有不同的聚類結(jié)果，這就特別需要對數(shù)據(jù)順序不敏感的算法開發(fā)出來，更好的適應人們的要求。</p><p>　?。?）高維數(shù)據(jù)的處理：含有若干維數(shù)據(jù)屬性的數(shù)據(jù)庫是很常見的，但是擅長處理兩維或三維的聚類算法才是目前成熟的應用的算法，一旦高維數(shù)據(jù)需要聚類處理，這就是一個難題，這就需要算法有很強的實用性。</p><p>　?。?

29、）污染數(shù)據(jù)的發(fā)現(xiàn)：數(shù)據(jù)是一個不確定而且無限性的群體，我們不能保證數(shù)據(jù)集中的數(shù)據(jù)是完全集中的，難免會有個別的孤立點造成污染數(shù)據(jù)，影響整個結(jié)果，應該開發(fā)出能智能識別這些孤立點的數(shù)據(jù)的算法，來優(yōu)化聚類結(jié)果，目前大部分是通過對目前算法進行改進來實現(xiàn)。</p><p>　?。?）有約束條件的聚類：實際的聚類情況是有很多限制的條件的，在實現(xiàn)這些聚類時，既要按約束條件又要按聚類要求實現(xiàn)，是很有壓力和挑戰(zhàn)的一項任務。</p

30、><p>　　（9）可使用性和可解釋性：大多情況下的聚類結(jié)果，對于客戶來說都希望它們簡單易懂，一目了然，所以我們要優(yōu)化聚類結(jié)果界面的研究，選擇適合每個客戶需求的聚類方法來滿足他們的需求。</p><p>　　同時聚類分析算法主要著手于以下的幾個問題的解決[3]：</p><p>　?。?）初始值的選取及輸入順序?qū)Y(jié)果有何影響</p><p>　　

31、在數(shù)據(jù)挖掘的學科范圍內(nèi)尋找最優(yōu)解的過程是通過迭代不同的初始值實現(xiàn)，但是這個辦法不是很可靠，它的意思就是表示不能百分之百的確定找到最優(yōu)解。其實尋找最優(yōu)解就是在優(yōu)化原來的聚類的結(jié)果，通過重復聚類找到所設計的目標函數(shù)的最優(yōu)解，但是這個目標函數(shù)一般都不是有最值的函數(shù)，所以它的最小值并不是很容易確定，因為它并不唯一，有可能找到的這個只是局部最小值，而不是全局最小，所以這種非完全單調(diào)函數(shù)的全局最小值的查找是目前最急著等待解決的問題。</p&g

32、t;<p>　?。?）以小波變換為基礎(chǔ)的聚類算法</p><p>　　因為當前主要是對均值算法與模糊算法的研究改進而得到的研究成果，這些研究成果使得目前的聚類分析算法提高了它的性能屬性。小波變換聚類算法同樣符合好的聚類算法的各項要求，目前對小波聚類的研究還有很大程度的空白，如果花大的精力進一步研究會有更加深入的突破。</p><p>　　（3）算法的效率改善提高的問題<

33、/p><p>　　聚類的效率問題是目前一個很棘手的問題，因為人類在進步，數(shù)據(jù)量會越來越龐大，應該增強目前聚類算法對更大數(shù)據(jù)庫的處理能力，即增量聚類，使聚類算法在聚類的數(shù)量上有更好的彈性，盡量減少在工作時對龐大數(shù)據(jù)庫的掃描次數(shù)，進一步提高它的工作效率。</p><p><b>　?。?）數(shù)據(jù)庫類型</b></p><p>　　目前，基于聚類算法的數(shù)據(jù)

34、庫比較單一，僅僅包括關(guān)系或事務數(shù)據(jù)庫，應該著眼于其他數(shù)據(jù)庫類型應用算法的研究，比如面向以屬性為內(nèi)容的數(shù)據(jù)庫、以文本為內(nèi)容的數(shù)據(jù)庫、各個不同時態(tài)為內(nèi)容的數(shù)據(jù)庫、地理數(shù)據(jù)庫多維數(shù)據(jù)庫等的算法開發(fā)，這是一項非常艱巨而且有意義的研究任務。</p><p>　　聚類分析中的算法有很多種，詳細分析比較了各個算法的優(yōu)缺點，本文著重介紹了K-均值算法，分析它本身的算法優(yōu)點與不足，并對算法實現(xiàn)，著力于對影響該算法聚類結(jié)果的不同初始

35、條件進行驗證，以更好在以后的實際應用中使用它。</p><p>　　K-均值算法是聚類分析最常用的算法之一。K-均值算法的應用范圍非常廣泛，因為它的操作簡單，適合處理龐大的數(shù)據(jù)集，但是它同時也暴露出自身的不足，如易陷入局部最優(yōu)解的結(jié)果里面、需要用戶提前輸入?yún)?shù)、發(fā)現(xiàn)簇的形狀比較單一等，已經(jīng)有很多專家對這些問題進行了改進，文獻[4]作者通過最大最小距離和DBI聚類指標解決了K-均值算法對初始值K的選擇問題，能夠確定

36、出最佳的聚類數(shù)目。文獻[5]的作者用K-均值算法與層次聚類算法進行混合出一種新的聚類算法，充分發(fā)揮了層次聚類的精確性和K-均值的高效性。文獻[6]的作者對遺傳算法提出一種改進算法，基于比變長編碼，利用這種算法與K-均值結(jié)合解決了對初值選擇的敏感問題等等，目前已經(jīng)有很多被發(fā)表出來的對K-均值的改進的算法。</p><p>　　1.3 本文所做的主要工作</p><p>　　首先對數(shù)據(jù)挖掘這

37、門學科的背景和發(fā)展前景做了分析，本文主要研究數(shù)據(jù)挖掘的聚類分析，所以介紹了聚類分析目前國內(nèi)外的地位與發(fā)展方向，以為下文展開作鋪墊，這方面閱讀了許多聚類相關(guān)文獻，許多新的聚類分析方法先后被各國的科研工作者提出并應用，這些在本文有詳細列舉。除此之外本文對聚類分析中的常用的五種方法做了簡要介紹，列舉了五種方法中目前比較常用的算法，并分析了每個算法的適用領(lǐng)域與基本思想。</p><p>　　本文著重討論的是基于劃分的聚類

38、分析方法中的K-means方法，對KM方法進行了詳細的介紹，包括基本思路工作流程等，本文通過分析KM算法的缺點，通過實驗驗證了對初始點的選取和數(shù)據(jù)輸入順序敏感的驗證，通過兩個實驗分別得出這兩個因素對聚類結(jié)果產(chǎn)生怎樣的影響并得出結(jié)論，實驗表明初始點不同只是影響聚類迭代的次數(shù)，對聚類結(jié)果的影響不明顯，只是少數(shù)數(shù)據(jù)的聚類結(jié)果發(fā)生改變；數(shù)據(jù)輸入順序的不同，不僅會改變數(shù)據(jù)聚類的迭代次數(shù)，也會讓聚類的結(jié)果發(fā)生明顯改變。</p><

39、;p>　　2 聚類算法的分析與研究</p><p>　　2.1 數(shù)據(jù)挖掘簡介</p><p>　　數(shù)據(jù)挖掘（Data Mining），也被叫做在已知的數(shù)據(jù)庫中對知識的發(fā)現(xiàn)（knowledge discovery ,KDD）,就是從數(shù)量巨大的、不完整的、有孤立點數(shù)據(jù)的、模糊的、隨機的數(shù)據(jù)中，提取發(fā)掘出來隱含在當中的、人們在這之前不是特別了解的、但又是隱含有用的信息內(nèi)容和知識內(nèi)容的非

40、平凡過程[2]。其實數(shù)據(jù)挖掘就是通過各種分析算法工具從巨大數(shù)量的數(shù)據(jù)中挖掘所需要的數(shù)據(jù)與模型兩者關(guān)系的一個過程，可以通過得到的這些關(guān)系，對未來的數(shù)據(jù)與模型關(guān)系進行預測。通常根據(jù)不同用戶的需求，和他們所提供的數(shù)據(jù)類型，數(shù)據(jù)挖掘的數(shù)據(jù)庫的類型也是不一樣的，通常包括關(guān)系數(shù)據(jù)庫類型、事物數(shù)據(jù)庫類型、多媒體數(shù)據(jù)庫類型等。其中關(guān)系數(shù)據(jù)庫實際上就是使用數(shù)學學科上的方法來處理數(shù)據(jù)之間的關(guān)系，我們生活中隨處可見關(guān)系數(shù)據(jù)庫，比如交通部的車輛數(shù)據(jù)庫、銀行的客

41、戶記錄等。事務數(shù)據(jù)庫一般是將幾個事務數(shù)據(jù)庫的數(shù)據(jù)一起導入到只能用來讀數(shù)據(jù)的數(shù)據(jù)挖掘庫中，做成一個數(shù)據(jù)集市，然后把其作為挖掘的對象。多媒體數(shù)據(jù)庫顧名思義就是包含大量視頻音頻文件，模式識別技術(shù)被用于該領(lǐng)域。</p><p>　　數(shù)據(jù)挖掘包含很多類別，包括分類分析、聚類分析、關(guān)聯(lián)分析孤立點分析等其他分析。其中分類分析包括分類和回歸，分類分析是一種預測模型，通過現(xiàn)有數(shù)據(jù)預測將來的數(shù)據(jù)，如果預測的數(shù)據(jù)是離散的即叫做分類，如

42、果是連續(xù)的即叫做回歸。聚類分析則是將大量數(shù)據(jù)中形似的數(shù)據(jù)分到一組，一個數(shù)據(jù)集大概包括幾組數(shù)據(jù)，聚類沒有明顯的屬性目標，而是挖掘隱藏的屬性來進行聚類，聚類分析中的基于劃分的K-均值算法是本文的研究對象。關(guān)聯(lián)分析分析數(shù)據(jù)與數(shù)據(jù)之間關(guān)聯(lián)關(guān)系還有它與其他數(shù)據(jù)的派生關(guān)系。孤立點分析是針對那些遠離數(shù)據(jù)集的點，對不同的客戶，別人的孤立點可能對于他來說是很重要的信息，孤立點分析就是對這些遠離數(shù)據(jù)集中心的數(shù)據(jù)信息進行挖掘。孤立點的研究是將來我們必須重點研

43、究的領(lǐng)域，因為幾個孤立點就會影響全局的聚類結(jié)果，這是不容忽視的。</p><p>　　2.2 聚類的基本知識</p><p>　　2.2.1 類的定義及表示</p><p><b>　?。?）類的定義</b></p><p>　　要想聚類操作首先要明確類的定義。世界錯綜復雜事物存在的方式也不盡相同，所以類的定義并不唯

44、一。以下將列舉出常用的類的定義：</p><p>　　設：含有K個樣本的集合A，Mi是其中的某個樣本，T和C是范圍閥值，那么：如果任意的Mi，Mj ∈A，都有D（Mi，Mj）≤T，則A稱為一類；</p><p><b>　　（2）類的表示；</b></p><p>　　聚類的表示方法也是有不同的，一般用以下三種：</p><

45、;p>　?、?自然語言表示：直接用自然語言直觀的描述出這些數(shù)據(jù)是屬于哪個簇的；</p><p>　?、?DNF表示：用析取范式表示明了、簡潔、易懂。例如：</p><p>　　(36<PT<70)V(345<AM<1234)；</p><p>　?、?聚類譜系圖：目前使用的聚類算法輸出結(jié)果大部分都是這種，這種方法表示非常詳細，它能表示出

46、這些樣本自成一類的所有中間情況，而且都會有各個類的平臺高度，我們叫這種圖為標度聚類譜系圖。</p><p>　　2.2.2 聚類的相似度量方法</p><p>　　聚類分析按照數(shù)據(jù)樣本性質(zhì)的相似程度的大小進行劃分，確定這些相似程度的大小必須有一個準則來判斷它們的程度大小，這個判斷準則叫做相似度方法，主要是在距離和相似系數(shù)的不同。</p><p>　　距離：樣本點之

47、間的相似性我們就用某種距離函數(shù)表示，距離近的表示樣本點相似，具體計算時可以把樣本看做有M個屬性的變量，即這個樣本就是在一個M維的空間中的一個點。</p><p>　　距離函數(shù)：設P是所有樣本集合的集合名稱，如果滿足：</p><p>　　① 正定性D(M，N)≥0，if M≠N</p><p>　　D(M，N)=0，if M=N</p><p&g

48、t;　?、?對稱性D(M，N)=D(M，N)</p><p>　　③ 三角不等式D(M,N)+D(N，L)≧D(M，L) 我們稱它們?yōu)榫嚯x函數(shù)。</p><p>　　聚類分析中經(jīng)常使用的的距離函數(shù)有：</p><p>　?、?明氏(Minkowski)距離</p><p>　　………………………………………… (2.1)</p>

49、;<p>　　當m取1時，則表示絕對距離，當m取2時就表示歐式(Euclid)距離，當m取無窮大時就表示切比雪夫(Chebyshev)距離。</p><p><b>　　如：歐氏距離</b></p><p>　　………………………………… (2.2)</p><p>　?、?馬氏(Mahalanois)距離</p>

50、<p>　　……………………………… (2.3)</p><p>　　其中 S 是由樣品集N（）算得的協(xié)方差矩陣：</p><p>　　………………………………… (2.3.1)</p><p>　　樣品聚類一般情況下被叫做Q型聚類，是以距離矩陣為出發(fā)點的。明氏距離改進后得到了馬氏距離，所有的線性變換對于馬氏距離來說是不變的，多重相關(guān)性馬氏距離也把它

51、克服了。</p><p><b>　?、?方差加權(quán)距離</b></p><p>　　…………………………………………… (2.4)</p><p><b>　　其中 </b></p><p>　　…………………………….. (2.4.1)</p><p>　　在聚類分析中

52、除了對樣本點聚類，對特征變量也要根據(jù)實際情況進行聚類，所以對于特征向量而言，不必非用距離函數(shù)來確定它們的相似測度，還可以用相似系數(shù)。</p><p>　　相似系數(shù)：當對含有k個指標的變量的數(shù)據(jù)集進行聚類時，就用相似系數(shù)來作為判斷所有變量之間的相似程度（或關(guān)聯(lián)程度）的標準指標。一般地，若表示Cab變量Xa,Xb之間的相似系數(shù)，應滿足：</p><p>　　1）| Cab|≤1且Cab=1；&

53、lt;/p><p>　　2）Cab=1或Cab=—1→Xa=CXb；</p><p>　　3）Cab=Cba；</p><p>　　Cab的絕對值越與1接近，越說明變量Xa,Xb之間的關(guān)聯(lián)性越大。</p><p>　　相似系數(shù)中相關(guān)系數(shù)和夾角余弦是目前最經(jīng)常被使用的。</p><p><b>　?。?）相關(guān)系數(shù)&

54、lt;/b></p><p>　　變量之間的相關(guān)系數(shù)我們可以這樣定義為：</p><p>　　…………………………….. (2.5)</p><p>　　實際上，只是變量之間的觀測值之間的相關(guān)系數(shù)而已。相關(guān)系數(shù)表示兩個向量的相關(guān)程度是多少。</p><p><b>　?。?）夾角余弦</b></p>

55、<p>　　變量的觀測值 ，其夾角余弦我們可以這樣定義為：</p><p>　　……………………………………… (2.6)</p><p>　　變量聚類一般情況下被叫作為 R 型聚類。一般R 型聚類，相似系數(shù)矩陣 C 是數(shù)據(jù)集聚類的出發(fā)點，相似系數(shù)矩陣不僅能夠使用相關(guān)矩陣，而且能夠使用夾角余弦矩陣。</p><p>　　2.2.3 聚類間的距離測度函

56、數(shù)</p><p>　　對于不同的兩個類，如果他們之間距離可定義，那么就用如下幾種定義方式來定義他們的距離：</p><p>　?。?）最短距離法：顧名思義它表示兩個類中的元素，相離最近的兩個元素的距離來表示這兩個類之間距離，公式表示為：</p><p>　　…………………………………… (2.7)</p><p>　?。?）最長距離法：跟

57、最短距離法類似，表示兩類之間距離的是兩類中距離最遠的元素，公式為：</p><p>　　………………………………….. (2.8)</p><p>　?。?）類平均法：求出兩個類中任意兩個數(shù)據(jù)的平均距離，用求出來的這個數(shù)據(jù)來表示這兩個類的平均距離，這就是類平均法，我們可以用下面的公式來表示：</p><p>　　………………………………… (2.9)</p

58、><p>　?。?）重心距離法：它的定義表示兩個類之間重心相鄰的距離為類距離,公式表示為：</p><p>　　………………………… (2.10)</p><p>　　其中類的重心公式為： （也就是各元素的平均向量之間的距離）</p><p>　　（5）離差平方和距離：用類中各元素的離差平方和的總和得到兩個類Gr和Gk的直徑分別是Dr和Dk,類

59、Gr+k=Gr Y Gk,用這種方法盡量讓類間的離差平方和大，而類內(nèi)部的元素間的值小，公式表示為：</p><p>　　……………………………. (2.11)</p><p>　　其中類直徑：有的把類中相距最遠的兩個元素的距離作為直徑，也有的將類中各元素指標的離差平方和的和作為直徑，離差平方和的計算公式為：</p><p>　　…………………………………………

60、(2.12)</p><p>　　2.2.4 聚類分析的一般步驟</p><p>　　聚類分析的步驟大體可以分為四步[9-10]：</p><p>　?。?）數(shù)據(jù)的預處理：就是在拿到一個數(shù)據(jù)集的時候，首先分析對這個數(shù)據(jù)的聚類分析要求，并根據(jù)這個要求對現(xiàn)在的數(shù)據(jù)集做降維或者特征標準化等初步的處理操作，也就是去掉沒用的特征值。</p><p>

61、　?。?）特征的選擇及提?。簩τ诘谝徊降玫降男畔ⅲM一步細分，就是將預處理后的信息再選擇最有效的特征，并將選擇出來的特征用向量的方法轉(zhuǎn)換成新的有效突出特征，以供聚類分組時作為分組判定的條件。</p><p>　?。?）聚類：這就要用到前面的相似性度量函數(shù)，選擇距離函數(shù)還是選擇相似系數(shù)等方法來度量選出來的有效特征值的相似度，進而完成對該數(shù)據(jù)集的聚類分析。</p><p>　?。?）評估結(jié)果：

62、結(jié)果進行分析，看有沒有完成預定的要求，并根據(jù)聚類方法的評價標準對結(jié)果進行科學評估，即聚類分析的九個方面的要求是否滿足，然后根據(jù)評估結(jié)果判斷是否對本次的分析過程進行改進，以及怎樣改進。</p><p>　　2.3 常用的聚類分析的方法介紹</p><p>　　目前聚類分析算法的應用技術(shù)日趨成熟，已經(jīng)有很多的聚類算法被提出來，但是算法種類增多，同時這些算法的融合會越來越明顯，使得各種算法的界

63、限不明顯，但是目前大家默認的有五種劃分方法,分別是：以劃分為基礎(chǔ)的算法(Partitioning Methods)、以密度為基礎(chǔ)的算法(Density．basedMethods)、以層次的為基礎(chǔ)的算法(HierarchicalMethods)、以模型為基礎(chǔ)的算法(Model．based Methods)、以網(wǎng)格為基礎(chǔ)的算法(Grid．based Methods)。</p><p>　　2.3.1 基于劃分的方法

64、</p><p>　　劃分算法[11]的基本思想就是通過迭代的方法將含有M個數(shù)據(jù)對象的數(shù)據(jù)集分成K個簇。具體步驟是，用戶首先給定所要劃分的簇的個數(shù)K，算法先進行初步劃分為K組，然后用迭代的方法反復再進行分組，每次新得到的分組比前一次要優(yōu)化，是否優(yōu)化的判定標準是同組數(shù)據(jù)之間以及不同組數(shù)據(jù)之間的相似程度，同組相似程度越大組間相似程度越小分組越優(yōu)化，目前常用的算法有K-means算法、K-medoid算法以及以它們?yōu)榛?/p>

65、礎(chǔ)的算法的各種改進。以劃分為基礎(chǔ)的聚類算法將在后面的章節(jié)做重點介紹。</p><p>　　2.3.2 基于密度的方法</p><p>　　基于密度的算法[12]與其他的算法最大的不同在于不是以元素間的距離作為判斷標準，而是根據(jù)數(shù)據(jù)對象的分布密度來判斷，正因為如此該算法有助于發(fā)現(xiàn)數(shù)據(jù)集中的噪聲數(shù)據(jù)，減少噪聲數(shù)據(jù)對聚類結(jié)果的影響，所以密度的方法可以對任意形狀的簇聚類，基本思想是將密度較大的區(qū)

66、域識別出來，形成連在一起的密度域，并將他們歸為一類。目前比較傳統(tǒng)的的以密度為基礎(chǔ)的聚類的方法有三種，這三種算法包括是：GDBSCAN算法、OPTICS算法、DENCLUE算法。其中OPTICS算法不是直接進行聚類，而是計算出一個簇的次序，以方便自動聚類和交互聚類分析。DBSCAN算法是檢驗數(shù)據(jù)對象周圍的數(shù)據(jù)個數(shù)是否超過了用戶規(guī)定的范圍。DENCLUE算法是通過影響函數(shù)來判斷空間密度的方法，這就對處理高維數(shù)據(jù)非常方便有效，所以該方法對用戶

67、的參數(shù)的個數(shù)與種類非常敏感。</p><p>　　2.3.3 基于層次的算法</p><p>　　層次聚類算法[1]有兩種不同的分解形式，分別是分裂和凝聚，它們的區(qū)別是聚類的方向不同。其中分裂的層次算法也是一種自頂向下的聚類方法，顧名思義分裂的過程就是將一個分裂為多個，一開始是將所有的數(shù)據(jù)放進一個初始的簇中，對這個簇進行分裂，每次迭代都會有一個更小的簇被分裂出來，最終結(jié)果是每個數(shù)據(jù)只單一

68、的對應唯一的一個簇結(jié)束。而凝聚的層次算法正好與分裂相反，是自底向上將小的簇聚類為大的簇，在一開始的時候數(shù)據(jù)集中每一個數(shù)據(jù)對象為一個小的簇，逐步的與相鄰的簇合并最終成為一個簇時終止。比較經(jīng)常被使用的以層次為基礎(chǔ)的的聚類算法有：BIRCH算法 、CURE算法 、ROCK算法、CHAMELEON算法等。</p><p>　　2.3.4 基于模型的算法</p><p>　　基于模型的聚類分析算法

69、[1]中的模型指的是數(shù)學模型，該算法是將數(shù)據(jù)集與某種算法形成最佳的擬合，該算法能夠利用統(tǒng)計學的方法，根據(jù)擬合的數(shù)據(jù)模型自動確定聚類的個數(shù)K，該算法的魯棒性很強?；谀Ｐ退惴òㄉ窠?jīng)網(wǎng)絡方法[13]和統(tǒng)計方法，神經(jīng)網(wǎng)絡方法的思想是將每一個聚類描述為某個標本，通過度量函數(shù)的計算，將新的數(shù)據(jù)對象分到相對應的標本中，最終完成聚類。而統(tǒng)計方法將每一個聚類結(jié)果通過概率描述的方式表示出來，該方法比較適用于概念聚類。</p><p&

70、gt;　　2.3.5 基于網(wǎng)格的算法</p><p>　　網(wǎng)格的算法[14]的基本思想是將數(shù)據(jù)空間劃分為一定數(shù)量的格子，每次對數(shù)據(jù)的各種操作就在格子中進行操作，該算法的處理難易程度只與網(wǎng)格的數(shù)目有關(guān)，這是網(wǎng)格聚類算法的特點，常用的網(wǎng)格聚類算法有STING算法、WAVECLUSTER算法、CLIQUE算法。STING算法的主要思想是先在分層的結(jié)構(gòu)中存儲網(wǎng)格的統(tǒng)計信息，這些統(tǒng)計信息是提前計算出來的，數(shù)據(jù)對象的空間被

71、分成許多格子，這些格子是按層次排列，高層的格子信息被劃為許多低層次的格子信息。CLIQUE算法是網(wǎng)格與密度結(jié)合的算法，它的工作過程是將數(shù)據(jù)空間劃分成不相關(guān)的網(wǎng)格，然后判斷網(wǎng)格是否是密集的，判斷標準是空間中的每一個維度，再將判斷出來的屬于密集的網(wǎng)格進行求交的操作，并檢查這些交集是否連通良好，然后生成最小覆蓋的簇。WAVECLUSTER算法是通過把數(shù)據(jù)比作信號來判斷，多維數(shù)據(jù)對應的是多維的信號，首先要做的也是將數(shù)據(jù)空間劃分為網(wǎng)格，該算法利用

72、的是小波變換算法，使數(shù)據(jù)空間成為頻域空間，在數(shù)據(jù)空間中利用某一函數(shù)對這些數(shù)據(jù)做卷積，最終就能得到聚類結(jié)果。</p><p>　　2.4 常用的劃分聚類算法的分析</p><p>　　劃分的算法中最常用的就是K-均值算法和K中心值聚類算法和基于它們的改進算法，分別詳細介紹這兩種算法，本章的距離函數(shù)選取的是使用目前最常用的歐氏距離。</p><p>　　2.4.1

73、K-均值聚類算法</p><p>　　K-均值算法是利用算法迭代的思想[15-16]，通過多次迭代改變不同簇的重心并將數(shù)據(jù)元素放到新的簇中，直到最終的聚類函數(shù)收斂時停止即可得到最終的聚類結(jié)果。本算法的計算公式表示為：</p><p>　　KM(X,C)=∑j=1∑xjcj||Xi-Wj||2(j<=k) ；……………………………………… (2.13)</p><

74、p>　　Wj=∑xj∈cj(xi/|cj|),j=1,2,…..,K；………………………………………………. (2.14)</p><p>　　這個定義的公式是假設每個數(shù)組只有唯一的數(shù)據(jù)型的屬性值。該算法要用戶期望的聚類結(jié)果的組數(shù)作為輸入值K，而每個簇內(nèi)的初始數(shù)據(jù)是根據(jù)電腦隨機分配的，也可以依次取前K個元素，該迭代算法直到?jīng)]有數(shù)據(jù)元素再被分到不同的組中時就是算法結(jié)束的時候。KM算法的時間復雜性為0(xKM

75、),x表示本次實驗一共迭代了多少次，K是聚類所生成的簇數(shù)，M是數(shù)據(jù)集的個數(shù)。因為該算法是定義在數(shù)值型的屬性上的，對該數(shù)據(jù)集假如還有其他屬性是不能識別的，所以該算法所得的并不是全局最優(yōu)解，而是局部的，而且也不能處理其他形狀的簇，只對凸形簇敏感。</p><p>　　K-均值算法多次迭代的最終結(jié)果就是使目標函數(shù)KM（）最小值，通過該公式我們發(fā)現(xiàn)該算法必須預先選好初始點，對初始點有很強烈的依賴性，如果該初始點選取不合適

76、會影響整個結(jié)果，這是該算法的一個缺點，可以改進的地方是用層次聚類等方法能夠提前計算出比較合適的初始點，再開始聚類。除此之外K-均值算法還有其他缺點，它在時間上并不具備高效性。為了找到全局最優(yōu)解，必須謹慎選取初值和簇數(shù)，還可以計算簇內(nèi)的方差，如果方差值很大就可以選擇將該簇分裂為兩個簇來提高有效性，方差值過小而且比設置的最小值還要小就要考慮合并兩個簇。</p><p>　　2.4.2 K-中心聚類法</p&g

77、t;<p>　　已經(jīng)介紹過KM算法對簇中心的選取非常敏感，選取不恰當會對聚類結(jié)果產(chǎn)生影響，這是KM算法的缺陷，如果有一個與簇中心點相距很遠的點被選為初始點就會非常明顯的影響聚類質(zhì)量。但是數(shù)據(jù)集中這種孤立點難免會出現(xiàn)，所以為了減少這種噪音數(shù)據(jù)對聚類結(jié)果的影響，K-中心聚類算法[17-20]出現(xiàn)，它與KM算法最大的區(qū)別是它是用最接近中心的那個數(shù)據(jù)對象來代表這個簇，而不是用所有數(shù)據(jù)對象的均值來代表該簇，這樣有效的避免了噪音數(shù)據(jù)的

78、干擾，這也是K-中心聚類算法與KM算法唯一的區(qū)別，其他的步驟大相徑庭，沒有太大的區(qū)別。它所用的目標函數(shù)公式是：</p><p>　　J=∑j=1∑x∈Wi||x-mj||…………………………………………… (2.15)</p><p>　　其中Wi表示數(shù)據(jù)集中的人一個對象，mj表示該簇的中心，該算法除了不受孤立點影響之外還不受數(shù)據(jù)輸入順序的影響。</p><p>

79、　　K-中心算法中的最早的PAM算法只適用小規(guī)模數(shù)據(jù)集聚類的算法，該算法的主要的思想是電腦自動隨機選出數(shù)據(jù)集中的K個數(shù)據(jù)對象為初始簇中的初始數(shù)據(jù)，然后根據(jù)距離函數(shù)計算剩余數(shù)據(jù)跟各個初始數(shù)據(jù)的距離，并挑選出距離最小的初始簇，將該點歸入到該簇中，并計算新的簇代表，即迭代這些操作，持續(xù)到?jīng)]有非代表的數(shù)據(jù)對象替換現(xiàn)在的簇代表對象為止，從而實現(xiàn)中心點聚類算法的聚類。</p><p>　　PAM算法對大數(shù)據(jù)集不具備高效性，一

80、種新的算法也被人們提出來，它就是CLARA算法，該算法是對大的數(shù)據(jù)集進行N次的抽取小數(shù)據(jù)集樣本，并依次對這些小的數(shù)據(jù)集使用PAM算法，充分發(fā)揮PAM算法的優(yōu)勢，得到N個聚類結(jié)果，然后再從這N個聚類結(jié)果中選擇一個最優(yōu)解作為最終整個數(shù)據(jù)集的結(jié)果。為了保證最終結(jié)果的可靠，抽樣過程中必須遵循隨機性，除此之外還要掌握好抽樣的規(guī)模大小，要適度，不能盲目抽取浪費時間，把握效率和效果的充分平衡。</p><p><b>

81、;　　2.5 本章小結(jié)</b></p><p>　　本章詳細介紹了聚類分析相關(guān)的基礎(chǔ)知識，分析了它的定義，屬性，表示方法，相似性測量度，距離函數(shù)等方面。并對常用的五種聚類分析的方法：劃分的方法、密度方法、層次的方法、網(wǎng)格的方法、模型的方法，進行詳細介紹，并簡要敘述了各方法中常用算法的基本思想和優(yōu)缺點，最后著重詳細的介紹了基于劃分的兩種聚類分析算法：K-均值算法和K-中心值算法。</p>

82、<p>　　3 K一均值聚類算法的研究</p><p>　　3.1 K-均值聚類算法介紹</p><p>　　k-means算法[21-23]是在1967年MacQueen第一次發(fā)現(xiàn)并提出來的，也被稱為K-平均或K-均值聚類算法。為應用最廣泛的一種聚類方法。主要特點為將每個群集子集內(nèi)的所有數(shù)據(jù)樣本的平均值作為集群的代表點。算法的主要思想為通過采取一種反復的過程使數(shù)據(jù)集被分成

83、不同的類別，進而使用評價結(jié)果的聚類性能標準的功能來實現(xiàn)的，從而使產(chǎn)生的每個群集的緊湊及獨立。這種算法不適合處理離散屬性，可是對于連續(xù)性具有較好的集聚效應。</p><p>　　3.1.1 K一均值聚類算法基本思想</p><p>　　K-means算法的工作原理可以總結(jié)為：首先，要從數(shù)據(jù)集中自動隨機選擇K個點作為初始聚類中心，然后分別將每種樣品計算其與集群的距離，樣品分類的標準為其與聚

84、類中心的距離。利用距離函數(shù)計算出每一個新生成的所要作聚類的數(shù)據(jù)對象的平均距離值，并用這個平均距離值來作為新的聚類中心，倘若相鄰兩次計算所得到的聚類中心點并沒有發(fā)生一點的改變，那么就能夠證明樣本調(diào)整過程就算完成了，也就是表示聚類準則函數(shù)目前達到了收斂。本算法有一個明顯的特點，就是在迭代過程中要對每個樣本的分類結(jié)果進行驗證觀察是不是正確。假如是不正確的，那么則需要對聚類進行調(diào)整。等所有的樣本調(diào)整完成以后，然后下一步就是對聚類中心的修改，從而

85、開始進入下一次迭代過程中去。倘若在某一次迭代算法過程中，所有樣本的分類結(jié)果是正確的，無需調(diào)整，聚類中心也沒會出現(xiàn)有一點任何變化，那么這表明該聚類函數(shù)收斂，從而算法就結(jié)束了。</p><p>　　3.1.2 K一均值聚類算法主要流程</p><p>　　輸入：含有n個數(shù)據(jù)對象個數(shù)的數(shù)據(jù)庫和所需要的簇的數(shù)目k。</p><p>　　輸出：k個簇。平方誤差準則達到最小。

86、</p><p><b>　　算法描述：</b></p><p>　?。?） 從 n個數(shù)據(jù)對象中自動隨機的選擇 k 個對象來作為初始狀態(tài)的的聚類中心； </p><p>　?。?） 根據(jù)各個聚類對象的均值（即每個簇的中心點），來計算各個數(shù)據(jù)對象與所有中心對象之間的距離。并以最短距離的為依據(jù)要求對相應的對象進行再一次的劃分； </p&g

87、t;<p>　?。?） 重新計算各個發(fā)生了變化的聚類的均值（即距離中心對象）； </p><p>　?。?） 循環(huán)過程（2）到（3）直至各個聚類不再發(fā)生變化為止。</p><p><b>　　算法步驟： </b></p><p>　　1.為各個聚類確定一個初始的聚類中心，這樣就可以產(chǎn)生K 個初始聚類中心。 </p>

88、<p>　　2.按最小距離的原則把樣本集中的樣本分配到最鄰近聚類。</p><p>　　3.把各聚類中的樣本均值規(guī)定為新的聚類中心。</p><p>　　4.重復執(zhí)行步驟2、3直至聚類中心不再發(fā)生變化。</p><p>　　5.結(jié)束過程，得到K個聚類。</p><p>　　3.2 K-均值聚類算法的主要缺陷及分析</p&g

89、t;<p><b>　　主要優(yōu)點：</b></p><p>　　（1）作為解決聚類問題而出現(xiàn)的一種傳統(tǒng)經(jīng)典算法，具有簡單、快速的特點。</p><p>　　對于較大數(shù)據(jù)集的聚類分析來說，該算法相比較而言是可伸縮和高效率的。因為它的時間復雜度是0 (n k x ) 。其中, n 是所有對象的個數(shù), k 是所需要的簇的個數(shù), x 是迭代發(fā)生了多少次。通常情況

90、下有k <<n 且x <<n 。</p><p>　?。?）當結(jié)果簇是密集的，而且簇與簇之間的區(qū)別較為明顯時, 它的效果比較較好。</p><p><b>　　主要缺點：</b></p><p>　?。?）K-均值算法只是在簇的平均值已經(jīng)提前被定義了的情況時才能被使用，而這個前提對于處理符號屬性的數(shù)據(jù)并不適用。在 K-m

91、eans 算法中，首先要根據(jù)初始的聚類中心來確定一個適合的初始劃分，接著要對初始劃分開始進行進一步的優(yōu)化操作。聚類結(jié)果對這個初始點的選擇是相當敏感的。倘若初始值選擇的不合適很可能造成不能得到準確的聚類結(jié)果的后果。這也是K-means算法目前存在的一個主要問題。對于該問題的解決，許多算法采用遺傳算法——GA，例如可以采用遺傳算法GA來進行初始化操作，而且內(nèi)部聚類準則被當做評價指標。</p><p>　?。?）必須事

92、先給出k值（想要生成的簇的個數(shù)）。并且對初值很敏感：不同的初始K值，也許將導致不同結(jié)果。在 K-means 算法中K值是要求提前必須給定的，但是這個值的選擇是相當難以估計的。實際情況下大部分時候提前是并不能確定給定的數(shù)據(jù)集應劃分成多少個類別才最適合這個數(shù)據(jù)集。這也是該算法的一個缺點。有的算法是通過采用類的自動識別它的初始數(shù)據(jù)集的分類和合并來得到較為合適聚類的簇數(shù)。例如 ISODATA 算法。對 K-means 算法中的聚類數(shù)目K 值的確

93、定有很多方法，有的是根據(jù)方差分析理論結(jié)合應用混合 F 統(tǒng)計量來得到最合適分類數(shù)，并且采用模糊劃分熵的方法來驗證其合理性。有的使用一種結(jié)合了全協(xié)方差矩陣的RPCL算法，而且逐步刪去那些僅僅包含很少數(shù)據(jù)量的訓練數(shù)據(jù)的類。還有的使用一種名為次勝者受罰的學習競爭規(guī)從而自動決定類的合理數(shù)目。它的思想為：對于每個輸入來說，不但獲勝單元的權(quán)值被加以修正以便適應輸入值。而且對于次勝單元則采用懲罰的方法以使其遠離輸入值。</p><p

94、>　?。?）該算法對“噪聲數(shù)據(jù)”以及孤立的點數(shù)據(jù)是相當敏感的，即使少量的該類數(shù)據(jù)也可以對平均值產(chǎn)生相當大的影響。</p><p>　　（4）從 K-means 算法流程中可以清楚的看到，該算法的實現(xiàn)原理要求必須不斷地對樣本進行分類，并且必須不斷地計算更新調(diào)整后的新的聚類中心。所以當數(shù)據(jù)量很大時，算法的時間復雜度是非常大的。因此需要對算法的時間復雜度時刻進行關(guān)注、審查以滿足時間等的要求。例如可以利用一定的相似

95、性準則來排除一些近似的聚類中心的侯選集。</p><p><b>　　3.3 本章小結(jié)</b></p><p>　　本章主要是針對K-均值算法作了系統(tǒng)的分析，介紹了它的基本定義、基本思想、主要流程，最后詳細分析了該算法在實際應用中的優(yōu)點和不足。K-均值算法是數(shù)據(jù)挖掘聚類劃分算法中最基本的算法，雖然它本身在實際應用的過程中存在不足，但是我們不能忽視它本身對數(shù)據(jù)集聚類的

96、優(yōu)點，在有的實踐應用中也取得了理想的效果，很多的算法也是以此為依據(jù)進行改進的，主要是對距離計算的改進，如P-CLUSTER算法，就是基于K-均值算法的一種改進，是啟發(fā)知識來判斷該數(shù)據(jù)集聚類對象M的最近的簇中心是否改變。</p><p>　　4 K-均值聚類算法的實驗</p><p>　　4.1 實驗結(jié)果分析 </p><p><b>　　實驗一：<

97、;/b></p><p>　　本文測試采用的是從數(shù)據(jù)堂下載的c-fat500-10.txt數(shù)據(jù)集，對K-均值算法進行了驗證，經(jīng)過實驗分別對150個數(shù)據(jù)的數(shù)據(jù)集選取不同初始點分別進行聚類，驗證不同的初始條件對最終聚類結(jié)果的影響情況，得到的聚類結(jié)果分別如下圖：</p><p>　　令前三個數(shù)據(jù)p[1]p[2]p[3]作為初始聚類中心，如圖4.1所示：</p><p&g

98、t;　　圖4.1 初始點為第1 2 3序號的聚類圖</p><p>　　把第p[4]p[5]p[6]個數(shù)據(jù)作為初始聚類中心，得到的聚類結(jié)果如圖4.2所示：</p><p>　　圖4.2 初始點為第4 5 6序號的聚類圖</p><p>　　把第p[100]p[101]p[102]個數(shù)據(jù)作為初始聚類中心，得到的聚類結(jié)果如圖4.3所示：</p><

99、p>　　圖4.3 初始點為第100 101 102序號的聚類圖</p><p>　　把第p[1]p[10]p[100]個數(shù)據(jù)作為初始聚類中心，結(jié)果如圖4.4所示：</p><p>　　圖4.4 初始點為第1 10 100序號的聚類</p><p><b>　　實驗分析與結(jié)論：</b></p><p>　　分析：由

100、以上聚類結(jié)果發(fā)現(xiàn)，不同的初始值的選取對聚類結(jié)果并不是造成很大影響，比較圖4.1和圖4.2可得，初始值選取的不同，只是造成聚類結(jié)果中極少數(shù)的數(shù)據(jù)發(fā)生變化，如數(shù)據(jù)20、27，聚類的迭代次數(shù)發(fā)生了改變由5次變?yōu)?次，還有不同點就是，聚類結(jié)果的輸出順序也發(fā)生了變化；對比圖4.3和圖4.2的聚類結(jié)果圖可得，選擇第100、101、102個數(shù)據(jù)與選擇第4、5、6個數(shù)據(jù)作為初始點的聚類結(jié)果是一樣的，不同之處就是數(shù)據(jù)聚類的輸出順序有所改變，可是圖4.3的

101、迭代次數(shù)又比圖4.2的迭代次數(shù)增多，變?yōu)?次；前三次的實驗是選取連續(xù)的數(shù)據(jù)作為初始點，在第四次的實驗中，選取第1、10、100個數(shù)據(jù)不連續(xù)的這三個數(shù)據(jù)作為初始值，從結(jié)果圖可以看出，本次實驗與第一次的聚類結(jié)果和迭代次數(shù)都相同，只是數(shù)據(jù)輸出順序有所改變。</p><p>　　結(jié)論：首先對比四個圖的聚類結(jié)果，并沒有因為初始點選取的不同而發(fā)生大的改變，只是改變了迭代次數(shù)，其中選取最前面的三個數(shù)據(jù)和后面某一不連續(xù)的數(shù)據(jù)為初

102、始點時迭代次數(shù)最少。實驗表明：K-均值算法對初始值得敏感體現(xiàn)在對聚類結(jié)果的迭代次數(shù)上，選取合理的初始點有助于我們高效率的完成聚類工作，用最少的時間完成我們所需要的結(jié)果為我們更好的應用在實際生活上。因此，從這此實驗我們得到的結(jié)論是：</p><p>　?。?）盡量選擇數(shù)據(jù)最開始的連續(xù)的點作為初始點，這樣可以用最少的迭代次數(shù)完成聚類；</p><p>　?。?）改變K-均值算法的初始點可以影響

103、數(shù)據(jù)集的迭代次數(shù)，對聚類結(jié)果影響不大；</p><p>　?。?）每次初始值的改變也會造成數(shù)據(jù)輸出順序的改變，即使是在聚類結(jié)果不變的情況下。</p><p><b>　　實驗二：</b></p><p>　　本次試驗是驗證不同的數(shù)據(jù)輸入順序，對聚類結(jié)果的影響，實驗的數(shù)據(jù)集為了更具說服力，還是用實驗一中的數(shù)據(jù)，不同之處是，此次實驗只是將數(shù)據(jù)集中的

104、后75個數(shù)放到前面，也就是與前75個數(shù)調(diào)換一下順序，本次試驗只是驗證數(shù)據(jù)集輸入順序的改變對聚類結(jié)果的影響，所以只選取兩種初始值進行驗證，與實驗一進行對比，可得實驗結(jié)果如下：</p><p>　　令前三個數(shù)據(jù)p[1]p[2]p[3]作為初始聚類中心，如圖4.5所示：</p><p>　　圖4.5 數(shù)據(jù)輸入順序改變聚類圖1</p><p>　　把第p[4]p[5]p[

105、6]個數(shù)據(jù)作為初始聚類中心，得到的聚類結(jié)果如圖4.6所示：</p><p>　　圖4.6 數(shù)據(jù)輸入順序改變聚類圖2</p><p><b>　　實驗分析與結(jié)論：</b></p><p>　　分析：本次實驗主要是與之前的數(shù)據(jù)順序不同時所得的聚類結(jié)果，由圖4.5與圖4.1，圖4.6與圖4.2的對比結(jié)果可得出，改變了數(shù)據(jù)的輸入順序，造成聚類結(jié)果有很

106、大的改變，同時迭代次數(shù)也增加了，這說明K-均值算法對數(shù)據(jù)輸入順序的敏感性不僅體現(xiàn)在迭代次數(shù)上，而且更會改變數(shù)據(jù)的迭代次數(shù)。另外，再對比圖4.5與圖4.6的結(jié)果，雖然兩次的聚類結(jié)果是一樣的，但是迭代的次數(shù)當選取第4、5、6個數(shù)據(jù)為初始點比選取第1、2、3個數(shù)據(jù)為初始點迭代次數(shù)有所增加，聚類結(jié)果的輸出順序也有所改變，同時也驗證了實驗一的結(jié)論。</p><p>　　結(jié)論：由實驗可得K-均值算法對數(shù)據(jù)集的輸入順序也是敏感

107、的，不同的的順序會有不同的聚類結(jié)果，這也是今后改進算法可以嘗試的方向，也可以在應用該算法時，通過改變數(shù)據(jù)集的輸入順序來適當提高聚類效果。本次試驗改變了輸入順序反而使迭代次數(shù)增加，很可能再次改變輸入順序會讓迭代次數(shù)減少，這些都說明K-均值算法對數(shù)據(jù)輸入順序特別敏感，因此我們得到的結(jié)論是：</p><p>　?。?）當我們聚類數(shù)據(jù)集迭代次數(shù)很多時，我們可以適當改變一下數(shù)據(jù)的輸入順序；</p><p

108、>　?。?）K-均值算法的聚類結(jié)果對數(shù)據(jù)輸入順序很敏感，與之前沒有改變順序之前的聚類結(jié)果差距很明顯，所以不要輕易變動數(shù)據(jù)集的輸入順序；</p><p><b>　　4.2 本章小結(jié)</b></p><p>　　本章主要是實現(xiàn)K-均值算法，并且在實現(xiàn)該算法的基礎(chǔ)上，對影響K-均值聚類效果的兩方面因素初始點的選擇和數(shù)據(jù)輸入順序兩個方面的因素對聚類結(jié)果的影響情況進行