【正文】 數(shù)據(jù)挖掘K均值算法實現(xiàn)畢業(yè)設計目 錄中文摘要、關鍵字 11 緒論 3 本文研究的背景和意義 3 聚類分析國內(nèi)外研究現(xiàn)狀 5 本文所做的主要工作 72 聚類算法的分析與研究 8 數(shù)據(jù)挖掘簡介 8 聚類的基本知識 8 類的定義及表示 9 聚類的相似度量方法 9 聚類間的距離測度函數(shù) 11 聚類分析的一般步驟 12 常用的聚類分析的方法介紹 13 基于劃分的方法 13 基于密度的方法 13 基于層次的算法 13 基于模型的算法 14 基于網(wǎng)格的算法 14 常用的劃分聚類算法的分析 14 K均值聚類算法 15 K中心聚類法 15 本章小結(jié) 163 K一均值聚類算法的研究 17 K均值聚類算法介紹 17 K一均值聚類算法基本思想 17 K一均值聚類算法主要流程 17 K均值聚類算法的主要缺陷及分析 18 本章小結(jié) 194 K均值聚類算法的實驗 20 實驗結(jié)果分析 20 本章小結(jié) 255 總結(jié)與展望 26 總結(jié) 25 展望 26參考文獻 28英文摘要、關鍵字 311 緒論 本文研究的背景和意義近年來，隨著科技的進步以及互聯(lián)網(wǎng)的普及，以計算機為代表的信息技術(shù)有了巨大發(fā)展，人們產(chǎn)生、發(fā)現(xiàn)、整理、利用數(shù)據(jù)的能力不斷提升。到目前為止，數(shù)據(jù)在我們的日常生活中無處不在，它廣泛應用于科學研究、政府日常辦公、軍事力量分析、企業(yè)管理電子商務、統(tǒng)計學分析等等各個領域。雖然我們知道這些數(shù)據(jù)的重要性，但是隨著時間越來越久，我們積累的數(shù)據(jù)量是不斷地在加大，相應的我們分析處理這些數(shù)據(jù)的能力也要增加，但是后來數(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)部關聯(lián)規(guī)則，也無法從當前現(xiàn)在的數(shù)據(jù)情況去預測未來的數(shù)據(jù)內(nèi)容的發(fā)展趨勢，更不可能做出決策判斷，使得人們逼不得已去面對“數(shù)據(jù)豐富而知識缺乏”的困鏡[1]。所以數(shù)據(jù)挖掘（Data Mining）技術(shù)因此就慢慢誕生了，并且快速的發(fā)展應用社會的各個領域，表現(xiàn)了其堅韌的生命力與適應力。該技術(shù)就是從“數(shù)據(jù)礦山”中發(fā)現(xiàn)“知識的寶藏”。數(shù)據(jù)挖掘（Data Mining），也被叫做在已知的數(shù)據(jù)庫中對知識的發(fā)現(xiàn)（knowledge discovery ,KDD）,就是從數(shù)量巨大的、不完整的、有孤立點數(shù)據(jù)的、模糊的、隨機的數(shù)據(jù)中，提取發(fā)掘出來隱含在當中的、人們在這之前不是特別了解的、但又是隱含有用的信息內(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)容的過程就是挖掘的一個過程，我們把挖掘的知識可以應用到我們的生活中，包括未來決策規(guī)劃、優(yōu)化信息管理方案、調(diào)整控制模式、改進查詢方案等等來更好的維護和利用我們現(xiàn)有的數(shù)據(jù)。所以數(shù)據(jù)挖掘涉及到的學科很廣泛，它是各個學科的交叉，它用到了人工智能數(shù)學統(tǒng)計學與數(shù)據(jù)庫等技術(shù)來實現(xiàn)它自己的目的，需要這些領域的工程技術(shù)人員來共同配合，尤其是數(shù)據(jù)庫管理人員?，F(xiàn)在的數(shù)據(jù)挖掘技術(shù)已經(jīng)開始走向科技產(chǎn)品研發(fā)及技術(shù)應用，不再是之前的單純的搞一下研究而已，我國市場經(jīng)濟制度在不斷地完善與發(fā)展，經(jīng)濟實力也在不斷進步，現(xiàn)在我們的社會對數(shù)據(jù)挖掘技術(shù)的需求越來越強烈，目前我國很多的有眼光的軟件企業(yè)已經(jīng)將目光聚集于此，來研發(fā)更多適應市場需求的數(shù)據(jù)挖掘軟件產(chǎn)品，隨著市場日趨成熟，廣大消費者的應用需求也是慢慢變大，相信將來會有更多成熟的中國數(shù)據(jù)挖掘軟件面向市場。聚類分析是數(shù)據(jù)挖掘的一個發(fā)現(xiàn)信息的方法，已經(jīng)被人們深入的研究了很長時間，主要的是對基于距離的聚類分析的研究。聚類是一種無監(jiān)督的學習，分類正好與它相反，分類是一種有監(jiān)督的學習，聚類主要是劃分無標記的對象，使這些無標記的對象變的有意義，對預先定義的類與帶類標記的訓練實例不具有依賴性。所以聚類分析在我們的日常生活中的應用范圍非常廣泛：① 在商業(yè)上，聚類可以根據(jù)消費者數(shù)據(jù)庫里面所記錄的數(shù)據(jù)信息，對消費者進行劃分，根據(jù)各個消費者的特征，以幫助市場營銷員按照市場需求及時調(diào)整貨物的擺放次序等一系列營銷計劃的實施；② 在社會學中，聚類用來發(fā)現(xiàn)目前社會結(jié)構(gòu)組成中潛在的社會結(jié)構(gòu)；③ 在網(wǎng)絡挖掘中對互聯(lián)網(wǎng)上批量的數(shù)據(jù)信息進行有效的劃分與分類，實現(xiàn)信息的有效利用，對數(shù)據(jù)信息檢索效率方面有顯著提高；④ 在生物信息學中，在大量的基因群中發(fā)現(xiàn)功能相似的基因組，對基因因功能不同進行劃分對其固有的結(jié)構(gòu)特征進行分析，來更好的為我們的醫(yī)學發(fā)展提供有利條件；⑤ 在空間數(shù)據(jù)庫領域，聚類分析能對相似地理特征區(qū)域及它們的人和環(huán)境的不同特征進行識別，來研究地域文化提供條件。本文主要選擇聚類分析中基于劃分的Kmeans算法并實現(xiàn)它的應用，對數(shù)據(jù)集的數(shù)據(jù)進行聚類分析。本文在實現(xiàn)它的基礎上，對該算法對初始值和數(shù)據(jù)輸入順序敏感的問題進行了驗證，通過六次試驗，分別對這個兩個方面進行驗證，并對聚類結(jié)果進行分析比較，從而得出結(jié)論。本文通過對不同輸入條件的實驗驗證，得出K均值算法對初始值得選擇和數(shù)據(jù)輸入順序是很敏感的結(jié)論，通過實驗結(jié)果可得出在今后使用K均值算法時我們應該怎樣避免其聚類出不準確的聚類結(jié)果和今后改進算法應該改進的方向等問題。 聚類分析國內(nèi)外研究現(xiàn)狀目前，國內(nèi)對于數(shù)據(jù)挖掘聚類分析的研究的集中部門還是科研單位和各大高校，國內(nèi)還沒有公司企業(yè)專門從事聚類分析的研究，相對于外國來說起步較晚。各大科研機構(gòu)與高校對聚類的研究主要是對數(shù)據(jù)集聚類算法的設計并實現(xiàn)，以研究出來的算法為基礎對算法改進。目前人們已經(jīng)在統(tǒng)計分析軟件中應用一些聚類分析工具，如SAS等軟件。為大型的數(shù)據(jù)庫尋求有效的聚類分析方法是目前聚類分析的主要研究工作，目前研究方向包括以下幾個方向：（1）可伸縮性：目前的聚類算法針對小型數(shù)據(jù)庫，數(shù)據(jù)量是幾百范圍內(nèi)的，對于有很龐大數(shù)據(jù)量的數(shù)據(jù)庫會造成結(jié)果的不穩(wěn)定性，可伸縮性強的算法就亟待的研發(fā)出來。（2）屬性不同情況下的處理能力：現(xiàn)在開發(fā)出來的聚類算法所針對的數(shù)據(jù)類型都是數(shù)值型，但實際上的聚類類型的信息是不確定的，如二元數(shù)據(jù)、序數(shù)型的、分類型的等或者是所已知的各種數(shù)據(jù)類型的混合。（3）聚類形狀：在歐幾里得距離的基礎上發(fā)現(xiàn)所得的簇的形狀是球狀簇，它們有相近的距離與密度，形成一個簇，但是我們更希望能夠有一種算法實現(xiàn)各個不同形狀的簇。（4）決定結(jié)果的輸入?yún)?shù)：聚類算法的實現(xiàn)過程中相當多的是必須讓用戶提前輸入想要聚類出來的簇數(shù)K，當前的算法對這些K的值是相當敏感的，大型的數(shù)據(jù)流對這些要求很嚴格，對結(jié)果的影響很明顯，使用戶在輸入時加大了分析的工作難度，很難控制。（5）輸入數(shù)據(jù)的順序問題：有的聚類算法對輸入數(shù)據(jù)的順序是有要求的，不同的輸入次序會有不同的聚類結(jié)果，這就特別需要對數(shù)據(jù)順序不敏感的算法開發(fā)出來，更好的適應人們的要求。（6）高維數(shù)據(jù)的處理：含有若干維數(shù)據(jù)屬性的數(shù)據(jù)庫是很常見的，但是擅長處理兩維或三維的聚類算法才是目前成熟的應用的算法，一旦高維數(shù)據(jù)需要聚類處理，這就是一個難題，這就需要算法有很強的實用性。（7）污染數(shù)據(jù)的發(fā)現(xiàn)：數(shù)據(jù)是一個不確定而且無限性的群體，我們不能保證數(shù)據(jù)集中的數(shù)據(jù)是完全集中的，難免會有個別的孤立點造成污染數(shù)據(jù)，影響整個結(jié)果，應該開發(fā)出能智能識別這些孤立點的數(shù)據(jù)的算法，來優(yōu)化聚類結(jié)果，目前大部分是通過對目前算法進行改進來實現(xiàn)。（8）有約束條件的聚類：實際的聚類情況是有很多限制的條件的，在實現(xiàn)這些聚類時，既要按約束條件又要按聚類要求實現(xiàn)，是很有壓力和挑戰(zhàn)的一項任務。（9）可使用性和可解釋性：大多情況下的聚類結(jié)果，對于客戶來說都希望它們簡單易懂，一目了然，所以我們要優(yōu)化聚類結(jié)果界面的研究，選擇適合每個客戶需求的聚類方法來滿足他們的需求。同時聚類分析算法主要著手于以下的幾個問題的解決[3]：（1）初始值的選取及輸入順序?qū)Y(jié)果有何影響在數(shù)據(jù)挖掘的學科范圍內(nèi)尋找最優(yōu)解的過程是通過迭代不同的初始值實現(xiàn)，但是這個辦法不是很可靠，它的意思就是表示不能百分之百的確定找到最優(yōu)解。其實尋找最優(yōu)解就是在優(yōu)化原來的聚類的結(jié)果，通過重復聚類找到所設計的目標函數(shù)的最優(yōu)解，但是這個目標函數(shù)一般都不是有最值的函數(shù)，所以它的最小值并不是很容易確定，因為它并不唯一，有可能找到的這個只是局部最小值，而不是全局最小，所以這種非完全單調(diào)函數(shù)的全局最小值的查找是目前最急著等待解決的問題。（2）以小波變換為基礎的聚類算法因為當前主要是對均值算法與模糊算法的研究改進而得到的研究成果，這些研究成果使得目前的聚類分析算法提高了它的性能屬性。小波變換聚類算法同樣符合好的聚類算法的各項要求，目前對小波聚類的研究還有很大程度的空白，如果花大的精力進一步研究會有更加深入的突破。（3）算法的效率改善提高的問題聚類的效率問題是目前一個很棘手的問題，因為人類在進步，數(shù)據(jù)量會越來越龐大，應該增強目前聚類算法對更大數(shù)據(jù)庫的處理能力，即增量聚類，使聚類算法在聚類的數(shù)量上有更好的彈性，盡量減少在工作時對龐大數(shù)據(jù)庫的掃描次數(shù)，進一步提高它的工作效率。（4）數(shù)據(jù)庫類型目前，基于聚類算法的數(shù)據(jù)庫比較單一，僅僅包括關系或事務數(shù)據(jù)庫，應該著眼于其他數(shù)據(jù)庫類型應用算法的研究，比如面向以屬性為內(nèi)容的數(shù)據(jù)庫、以文本為內(nèi)容的數(shù)據(jù)庫、各個不同時態(tài)為內(nèi)容的數(shù)據(jù)庫、地理數(shù)據(jù)庫多維數(shù)據(jù)庫等的算法開發(fā)，這是一項非常艱巨而且有意義的研究任務。聚類分析中的算法有很多種，詳細分析比較了各個算法的優(yōu)缺點，本文著重介紹了K均值算法，分析它本身的算法優(yōu)點與不足，并對算法實現(xiàn)，著力于對影響該算法聚類結(jié)果的不同初始條件進行驗證，以更好在以后的實際應用中使用它。K均值算法是聚類分析最常用的算法之一。K均值算法的應用范圍非常廣泛，因為它的操作簡單，適合處理龐大的數(shù)據(jù)集，但是它同時也暴露出自身的不足，如易陷入局部最優(yōu)解的結(jié)果里面、需要用戶提前輸入?yún)?shù)、發(fā)現(xiàn)簇的形狀比較單一等，已經(jīng)有很多專家對這些問題進行了改進，文獻[4]作者通過最大最小距離和DBI聚類指標解決了K均值算法對初始值K的選擇問題，能夠確定出最佳的聚類數(shù)目。文獻[5]的作者用K均值算法與層次聚類算法進行混合出一種新的聚類算法，充分發(fā)揮了層次聚類的精確性和K均值的高效性。文獻[6]的作者對遺傳算法提出一種改進算法，基于比變長編碼，利用這種算法與K均值結(jié)合解決了對初值選擇的敏感問題等等，目前已經(jīng)有很多被發(fā)表出來的對K均值的改進的算法。 本文所做的主要工作首先對數(shù)據(jù)挖掘這門學科的背景和發(fā)展前景做了分析，本文主要研究數(shù)據(jù)挖掘的聚類分析，所以介紹了聚類分析目前國內(nèi)外的地位與發(fā)展方向，以為下文展開作鋪墊，這方面閱讀了許多聚類相關文獻，許多新的聚類分析方法先后被各國的科研工作者提出并應用，這些在本文有詳細列舉。除此之外本文對聚類分析中的常用的五種方法做了簡要介紹，列舉了五種方法中目前比較常用的算法，并分析了每個算法的適用領域與基本思想。本文著重討論的是基于劃分的聚類分析方法中的Kmeans方法，對KM方法進行了詳