【正文】 目前已經(jīng)存在了很多中改進的算法，以后的工作是我們應(yīng)該對多種算法通過相同的數(shù)據(jù)集進行全方位的對比，通過對比得出的結(jié)果往往更加明確，從而分析出各個算法的因各個因素的不同受影響的范圍與程度，并將這些結(jié)論利用大量的數(shù)據(jù)集進行驗證，來作為每一個新的算法使用幫助，有助于用戶對大量算法的選擇起一個指導(dǎo)性的作用，更加方便我們使用。本次試驗改變了輸入順序反而使迭代次數(shù)增加，很可能再次改變輸入順序會讓迭代次數(shù)減少，這些都說明K均值算法對數(shù)據(jù)輸入順序特別敏感，因此我們得到的結(jié)論是：（1）當(dāng)我們聚類數(shù)據(jù)集迭代次數(shù)很多時，我們可以適當(dāng)改變一下數(shù)據(jù)的輸入順序；（2）K均值算法的聚類結(jié)果對數(shù)據(jù)輸入順序很敏感，與之前沒有改變順序之前的聚類結(jié)果差距很明顯，所以不要輕易變動數(shù)據(jù)集的輸入順序； 本章小結(jié)本章主要是實現(xiàn)K均值算法，并且在實現(xiàn)該算法的基礎(chǔ)上，對影響K均值聚類效果的兩方面因素初始點的選擇和數(shù)據(jù)輸入順序兩個方面的因素對聚類結(jié)果的影響情況進行驗證。K均值算法是數(shù)據(jù)挖掘聚類劃分算法中最基本的算法，雖然它本身在實際應(yīng)用的過程中存在不足，但是我們不能忽視它本身對數(shù)據(jù)集聚類的優(yōu)點，在有的實踐應(yīng)用中也取得了理想的效果，很多的算法也是以此為依據(jù)進行改進的，主要是對距離計算的改進，如PCLUSTER算法，就是基于K均值算法的一種改進，是啟發(fā)知識來判斷該數(shù)據(jù)集聚類對象M的最近的簇中心是否改變。它的思想為：對于每個輸入來說，不但獲勝單元的權(quán)值被加以修正以便適應(yīng)輸入值。在 Kmeans 算法中K值是要求提前必須給定的，但是這個值的選擇是相當(dāng)難以估計的。主要缺點：（1）K均值算法只是在簇的平均值已經(jīng)提前被定義了的情況時才能被使用，而這個前提對于處理符號屬性的數(shù)據(jù)并不適用。、3直至聚類中心不再發(fā)生變化。 K一均值聚類算法主要流程輸入：含有n個數(shù)據(jù)對象個數(shù)的數(shù)據(jù)庫和所需要的簇的數(shù)目k。算法的主要思想為通過采取一種反復(fù)的過程使數(shù)據(jù)集被分成不同的類別，進而使用評價結(jié)果的聚類性能標準的功能來實現(xiàn)的，從而使產(chǎn)生的每個群集的緊湊及獨立。 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)中心點聚類算法的聚類。KM算法的時間復(fù)雜性為0(xKM),x表示本次實驗一共迭代了多少次，K是聚類所生成的簇數(shù)，M是數(shù)據(jù)集的個數(shù)。 基于網(wǎng)格的算法網(wǎng)格的算法[14]的基本思想是將數(shù)據(jù)空間劃分為一定數(shù)量的格子，每次對數(shù)據(jù)的各種操作就在格子中進行操作，該算法的處理難易程度只與網(wǎng)格的數(shù)目有關(guān)，這是網(wǎng)格聚類算法的特點，常用的網(wǎng)格聚類算法有STING算法、WAVECLUSTER算法、CLIQUE算法。DENCLUE算法是通過影響函數(shù)來判斷空間密度的方法，這就對處理高維數(shù)據(jù)非常方便有效，所以該方法對用戶的參數(shù)的個數(shù)與種類非常敏感。 常用的聚類分析的方法介紹目前聚類分析算法的應(yīng)用技術(shù)日趨成熟，已經(jīng)有很多的聚類算法被提出來，但是算法種類增多，同時這些算法的融合會越來越明顯，使得各種算法的界限不明顯，但是目前大家默認的有五種劃分方法,分別是：以劃分為基礎(chǔ)的算法(Partitioning Methods)、以密度為基礎(chǔ)的算法(Density．basedMethods)、以層次的為基礎(chǔ)的算法(HierarchicalMethods)、以模型為基礎(chǔ)的算法(Model．based Methods)、以網(wǎng)格為基礎(chǔ)的算法(Grid．based Methods)。（1）相關(guān)系數(shù)變量之間的相關(guān)系數(shù)我們可以這樣定義為：…………………………….. ()實際上，只是變量之間的觀測值之間的相關(guān)系數(shù)而已。距離函數(shù)：設(shè)P是所有樣本集合的集合名稱，如果滿足：① 正定性D(M，N)≥0，if M≠ND(M，N)=0，if M=N② 對稱性D(M，N)=D(M，N)③ 三角不等式D(M,N)+D(N，L)≧D(M，L) 我們稱它們?yōu)榫嚯x函數(shù)。孤立點分析是針對那些遠離數(shù)據(jù)集的點，對不同的客戶，別人的孤立點可能對于他來說是很重要的信息，孤立點分析就是對這些遠離數(shù)據(jù)集中心的數(shù)據(jù)信息進行挖掘。通常根據(jù)不同用戶的需求，和他們所提供的數(shù)據(jù)類型，數(shù)據(jù)挖掘的數(shù)據(jù)庫的類型也是不一樣的，通常包括關(guān)系數(shù)據(jù)庫類型、事物數(shù)據(jù)庫類型、多媒體數(shù)據(jù)庫類型等。K均值算法的應(yīng)用范圍非常廣泛，因為它的操作簡單，適合處理龐大的數(shù)據(jù)集，但是它同時也暴露出自身的不足，如易陷入局部最優(yōu)解的結(jié)果里面、需要用戶提前輸入?yún)?shù)、發(fā)現(xiàn)簇的形狀比較單一等，已經(jīng)有很多專家對這些問題進行了改進，文獻[4]作者通過最大最小距離和DBI聚類指標解決了K均值算法對初始值K的選擇問題，能夠確定出最佳的聚類數(shù)目。同時聚類分析算法主要著手于以下的幾個問題的解決[3]：（1）初始值的選取及輸入順序?qū)Y(jié)果有何影響在數(shù)據(jù)挖掘的學(xué)科范圍內(nèi)尋找最優(yōu)解的過程是通過迭代不同的初始值實現(xiàn)，但是這個辦法不是很可靠，它的意思就是表示不能百分之百的確定找到最優(yōu)解。（2）屬性不同情況下的處理能力：現(xiàn)在開發(fā)出來的聚類算法所針對的數(shù)據(jù)類型都是數(shù)值型，但實際上的聚類類型的信息是不確定的，如二元數(shù)據(jù)、序數(shù)型的、分類型的等或者是所已知的各種數(shù)據(jù)類型的混合。所以聚類分析在我們的日常生活中的應(yīng)用范圍非常廣泛：① 在商業(yè)上，聚類可以根據(jù)消費者數(shù)據(jù)庫里面所記錄的數(shù)據(jù)信息，對消費者進行劃分，根據(jù)各個消費者的特征，以幫助市場營銷員按照市場需求及時調(diào)整貨物的擺放次序等一系列營銷計劃的實施；② 在社會學(xué)中，聚類用來發(fā)現(xiàn)目前社會結(jié)構(gòu)組成中潛在的社會結(jié)構(gòu)；③ 在網(wǎng)絡(luò)挖掘中對互聯(lián)網(wǎng)上批量的數(shù)據(jù)信息進行有效的劃分與分類，實現(xiàn)信息的有效利用，對數(shù)據(jù)信息檢索效率方面有顯著提高；④ 在生物信息學(xué)中，在大量的基因群中發(fā)現(xiàn)功能相似的基因組，對基因因功能不同進行劃分對其固有的結(jié)構(gòu)特征進行分析，來更好的為我們的醫(yī)學(xué)發(fā)展提供有利條件；⑤ 在空間數(shù)據(jù)庫領(lǐng)域，聚類分析能對相似地理特征區(qū)域及它們的人和環(huán)境的不同特征進行識別，來研究地域文化提供條件。數(shù)據(jù)挖掘（Data Mining），也被叫做在已知的數(shù)據(jù)庫中對知識的發(fā)現(xiàn)（knowledge discovery ,KDD）,就是從數(shù)量巨大的、不完整的、有孤立點數(shù)據(jù)的、模糊的、隨機的數(shù)據(jù)中，提取發(fā)掘出來隱含在當(dāng)中的、人們在這之前不是特別了解的、但又是隱含有用的信息內(nèi)容和知識內(nèi)容的非平凡過程[2] 。數(shù)據(jù)挖掘K均值算法實現(xiàn)畢業(yè)設(shè)計目 錄中文摘要、關(guān)鍵字 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英文摘要、關(guān)鍵字 311 緒論 本文研究的背景和意義近年來，隨著科技的進步以及互聯(lián)網(wǎng)的普及，以計算機為代表的信息技術(shù)有了巨大發(fā)展，人們產(chǎn)生、發(fā)現(xiàn)、整理、利用數(shù)據(jù)的能力不斷提升。原始的數(shù)據(jù)類型可以是多樣的，比如數(shù)據(jù)庫中的數(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ù)類型。本文主要選擇聚類分析中基于劃分的Kmeans算法并實現(xiàn)它的應(yīng)用，對數(shù)據(jù)集的數(shù)據(jù)進行聚類分析。（3）聚類形狀：在歐幾里得距離的基礎(chǔ)上發(fā)現(xiàn)所得的簇的形狀是球狀簇，它們有相近的距離與密度，形成一個簇，但是我們更希望能夠有一種算法實現(xiàn)各個不同形狀的簇。其實尋找最優(yōu)解就是在優(yōu)化原來的聚類的結(jié)果，通過重復(fù)聚類找到所設(shè)計的目標函數(shù)的最優(yōu)解，但是這個目標函數(shù)一般都不是有最值的函數(shù)，所以它的最小值并不是很容易確定，因為它并不唯一，有可能找到的這個只是局部最小值，而不是全局最小，所以這種非完全單調(diào)函數(shù)的全局最小值的查找是目前最急著等待解決的問題。文獻[5]的作者用K均值算法與層次聚類算法進行混合出一種新的聚類算法，充分發(fā)揮了層次聚類的精確性和K均值的高效性。其中關(guān)系數(shù)據(jù)庫實際上就是使用數(shù)學(xué)學(xué)科上的方法來處理數(shù)據(jù)之間的關(guān)系，我們生活中隨處可見關(guān)系數(shù)據(jù)庫，比如交通部的車輛數(shù)據(jù)庫、銀行的客戶記錄等。孤立點的研究是將來我們必須重點研究的領(lǐng)域，因為幾個孤立點就會影響全局的聚類結(jié)果，這是不容忽視的。聚類分析中經(jīng)常使用的的距離函數(shù)有： ① 明氏(Minkowski)距離………………………………………… ()當(dāng)m取1時，則表示絕對距離，當(dāng)m取2時就表示歐式(Euclid)距離，當(dāng)m取無窮大時就表示切比雪夫(Chebyshev)距離。相關(guān)系數(shù)表示兩個向量的相關(guān)程度是多少。 基于劃分的方法劃分算法[11]的基本思想就是通過迭代的方法將含有M個數(shù)據(jù)對象的數(shù)據(jù)集分成K個簇。 基于層次的算法層次聚類算法[1]有兩種不同的分解形式，分別是分裂和凝聚，它們的區(qū)別是聚類的方向不同。STING算法的主要思想是先在分層的結(jié)構(gòu)中存儲網(wǎng)格的統(tǒng)計信息，這些統(tǒng)計信息是提前計算出來的，數(shù)據(jù)對象的空間被分成許多格子，這些格子是按層次排列，高層的格子信息被劃為許多低層次的格子信息。因為該算法是定義在數(shù)值型的屬性上的，對該數(shù)據(jù)集假如還有其他屬性是不能識別的，所以該算法所得的并不是全局最優(yōu)解，而是局部的，而且也不能處理其他形狀的簇，只對凸形簇敏感。PAM算法對大數(shù)據(jù)集不具備高效性，一種新的算法也被人們提出來，它就是CLARA算法，該算法是對大的數(shù)據(jù)集進行N次的抽取小數(shù)據(jù)集樣本，并依次對這些小的數(shù)據(jù)集使用PAM算法，充分發(fā)揮PAM算法的優(yōu)勢，得到N個聚類結(jié)果，然后再從這N個聚類結(jié)果中選擇一個最優(yōu)解作為最終整個數(shù)據(jù)集的結(jié)果。這種算法不適合處理離散屬性，可是對于連續(xù)性具有較好的集聚效應(yīng)。輸出：k個簇。，得到K個聚類。在 Kmeans 算法中，首先要根據(jù)初始的聚類中心來確定一個適合的初始劃分，接著要對初始劃分開始進行進一步的優(yōu)化操作。實際情況下大部分時候提前是并不能確定給定的數(shù)據(jù)集應(yīng)劃分成多少個類別才最適合這個數(shù)據(jù)集。而且對于次勝單元則采用懲罰的方法以使其遠離輸入值。4 K均值聚類算法的實驗 實驗結(jié)果分析 實驗一：，對K均值算法進行了驗證，經(jīng)過實驗分別對150個數(shù)據(jù)的數(shù)據(jù)集選取不同初始點分別進行聚類，驗證不同的初始條件對最終聚類結(jié)果的影響情況，得到的聚類結(jié)果分別如下圖：令前三個數(shù)據(jù)p[1]p[2]p[3]作為初始聚類中心，： 初始點為第1 2 3序號的聚類圖把第p[4]p[