【正文】 niiinniiiix x x xsr ssx x x x? ? ? ?????? ? ? ?? ? ? ?????????????… ………………………….. () 實(shí)際上 ， r?? 只 是變量 ,??xx之間 的觀測值 1 2 1 2( , , .. ., ) ( , , .. ., )TTnnx x x x x x? ? ? ? ? ?與之間的相關(guān)系數(shù) 而已。 ③ 方差加權(quán)距 離 12221()( , ) p ik jkij k kxxd x xs????? ?????…………………………………………… () 其中 221111, ( ) .1nnik k ik kiix x s x xnn??? ? ????…………………………….. () 在聚類分析中除了對樣本點(diǎn)聚類，對特征變量也要根據(jù)實(shí)際情況進(jìn)行聚類，所以對于特征向量而言，不必非用距離函數(shù)來確定它們的相似測度，還可以用相似系數(shù)。 距離函數(shù)：設(shè) P 是所有樣本集合的集合名稱，如果滿足： ① 正定性 D(M， N)≥ 0， if M≠ N D(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è)：含有 K 個樣本的集合 A， Mi 是其中的某個樣本， T 和 C 是范圍閥值，那么：如果任意的 Mi， Mj ∈ A，都有 D（ Mi， Mj）≤ T，則 A 稱為一類； （ 2）類的表示； 聚類的表示方法也是有不同的，一般用以下三種： ① 自然語言表示：直接用自然語言直觀的描述出這些數(shù)據(jù)是屬于哪個簇的； ② DNF 表示：用析取范式表示明了、簡潔、易懂。孤立點(diǎn)分析 是針對那些遠(yuǎn)離 數(shù)據(jù)集的點(diǎn)，對不同的客 戶，別人的孤立點(diǎn)可能對于他來說是很重要的信息，孤立點(diǎn)分析就是對這些 遠(yuǎn)離數(shù)據(jù)集中心的 數(shù)據(jù)信息進(jìn)行挖掘。 數(shù)據(jù)挖掘包含很多類別，包括分類分析、聚類分析、關(guān)聯(lián)分析孤立點(diǎn)分析等其他分析。通常根據(jù)不同用 戶的需求，和他們所提供的數(shù)據(jù)類型，數(shù)據(jù)挖掘的數(shù)據(jù)庫的類型也是不一樣 的，通常包括關(guān)系數(shù)據(jù)庫 類型 、事物數(shù)據(jù)庫 類型 、多媒體數(shù)據(jù)庫 類型等。除此之外本文對聚類分析中的常用的五種方法做了簡要介紹，列舉了五種方法中 目前比較常用的算法，并分析了每個算法的適用領(lǐng)域與基本思想。 K均值算法的應(yīng)用范圍非常廣泛，因?yàn)樗牟僮骱唵危m合處理龐大的數(shù)據(jù)集，但是它同時也暴露出自身的不足，如易陷入局部最優(yōu)解的結(jié)果里面、需要用戶提前輸入?yún)?shù)、發(fā)現(xiàn)簇的形狀比較單一等，已經(jīng)有很多專家對這些問題進(jìn)行了改進(jìn)，文獻(xiàn) [4]作者通過最大最小距離和 DBI 聚類指標(biāo)解決了 K均值算法對初始值 K 的 選擇問題，能夠確定出最佳的聚類數(shù)目。 （ 3）算法的效率改善提高的 問題 聚類的效率 問題是目前一個很棘手的問題，因?yàn)槿祟愒谶M(jìn)步，數(shù)據(jù)量會越來越龐大，應(yīng)該增強(qiáng)目前聚類算法對更大數(shù)據(jù)庫的處理能力，即增量聚類，使 聚類算法在聚類的數(shù)量上有更好的彈性，盡量減少在工作時對龐大數(shù)據(jù)庫的掃描次數(shù)，進(jìn)一步提高它的工作效 率。 同時聚類分析算法主要著手于以 下的幾個問題的解決 [3]： （ 1） 初始值的選取及輸入順序?qū)Y(jié)果有何影響 在數(shù)據(jù)挖掘的學(xué)科范圍內(nèi)尋找最優(yōu)解的過程是通 過迭代不同的初始值實(shí)現(xiàn)，但是這個辦法不是很可靠，它的意思就是表示不能百分之百的 確定找到最優(yōu)解。 （ 6） 高維數(shù)據(jù)的處理：含有若干維數(shù)據(jù)屬性的數(shù)據(jù)庫是很常見的，但是擅長處理 兩維或三維的聚類算法才是目前成熟的 應(yīng)用的算法，一旦高維數(shù)據(jù)需要聚類處理，這就是一個難題，這就需要算法有很強(qiáng)的實(shí)用性。 （ 2） 屬性不同情況下的處理能力：現(xiàn)在開發(fā)出來的聚類算法所針對的數(shù)據(jù)類型都是數(shù)值型，但實(shí)際上的聚類類型的信息是不確定的，如二元數(shù)據(jù)、序數(shù)型 的 、分類型 的 等或者是 所已知的 各種 數(shù)據(jù) 類型的混合。 5 聚類分析國內(nèi)外研究現(xiàn)狀 目前，國內(nèi)對于數(shù)據(jù)挖掘聚類分析的研究的集中部門還是科研單位和各大高校，國內(nèi)還沒有公司企業(yè)專門從事聚類分析的研究，相對于外國來說起步較晚。所以聚類分析在我們的日常生活中的應(yīng)用范圍非常廣泛： ① 在商業(yè)上，聚類可以根據(jù)消費(fèi)者數(shù)據(jù)庫里面所記錄的數(shù)據(jù)信息，對消費(fèi)者進(jìn)行劃分，根據(jù)各個消費(fèi)者的特征，以幫助市場營銷員按照市場需求及時調(diào)整貨物的擺放次序等一系列營銷計(jì)劃 的實(shí)施； ② 在社會學(xué)中，聚類用來發(fā)現(xiàn)目前社會結(jié)構(gòu)組成中潛在的社會結(jié)構(gòu)； ③ 在網(wǎng)絡(luò)挖掘中對互聯(lián)網(wǎng)上批量的數(shù)據(jù)信息進(jìn)行有效的劃分與分類，實(shí)現(xiàn)信息的有效利用，對 數(shù)據(jù)信息 檢索效率 方面有 顯著提高； ④ 在生物信息學(xué)中，在 大量的基因群中發(fā)現(xiàn)功能相似的基因組，對基因因功能不同進(jìn)行劃分對其固有的結(jié)構(gòu)特征進(jìn)行分析，來更好的為我們的醫(yī)學(xué)發(fā)展提供有利條件； ⑤ 在空間數(shù)據(jù)庫領(lǐng)域，聚類分析能對相似地理特征區(qū)域及它們的人和環(huán)境的不同特征進(jìn)行識別，來研究地域文化提供條件。所以數(shù)據(jù)挖掘涉及到的學(xué) 4 科很廣泛，它 是各個學(xué)科的交叉 ，它用到了人工智能數(shù)學(xué)統(tǒng)計(jì)學(xué)與數(shù)據(jù)庫等技術(shù)來實(shí)現(xiàn)它自己的目的，需要這些領(lǐng)域的工程技術(shù)人員來共同配合，尤其是數(shù)據(jù)庫管理人員。 數(shù)據(jù)挖掘（ Data Mining） ，也被叫做在已知的 數(shù)據(jù)庫中 對 知識的發(fā)現(xiàn)（ knowledge discovery ,KDD） ,就是 從數(shù)量巨大的、不完整的、有孤立點(diǎn)數(shù)據(jù)的、模糊的、隨機(jī)的數(shù)據(jù)中，提取發(fā)掘出來隱含在當(dāng)中的、人們在這之前不是特別了解的、但又是隱含 有用的信息 內(nèi)容 和知識 內(nèi)容 的非平凡過程 [2] 。難道真的沒有辦法可以很科學(xué)的處理這些海 量數(shù)據(jù)嗎？事實(shí)并非如此，人類的智慧是無窮的，人們已經(jīng)通過理性的思維和恰當(dāng)?shù)募夹g(shù)，將這些海量數(shù)據(jù)充分利用，使它們成為社會發(fā)展進(jìn)步的 強(qiáng)大的力量源泉。通過這些結(jié)論為以后用戶使用 K均值算法提供了很好的幫助，也為該算法的改進(jìn)提供了參考。 第三部分： 這 是本論文的重點(diǎn)，本論文所要討論的 K均值算法，從它的概念基本思想算法流程等方面對 K均值算法進(jìn)行詳細(xì) 系統(tǒng)的介紹，并且詳細(xì)分析了它的優(yōu)缺點(diǎn) 。 K均值算法的應(yīng)用領(lǐng)域特別廣泛，覆蓋范圍涉及語音頻率 壓縮 還有 圖像及文本聚類，另外在數(shù)據(jù)預(yù)處理和神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的任務(wù)分解等也發(fā)揮其重要用途。數(shù)據(jù)挖掘中有一項(xiàng)是很重要的研究領(lǐng)域，那就是聚類分析，這是一種對數(shù)據(jù)進(jìn)行按照不同的依據(jù)將數(shù)據(jù)進(jìn)行分組或者將數(shù)據(jù)進(jìn)行劃分的方式。 本科生畢業(yè)論文設(shè)計(jì) 數(shù)據(jù)挖掘 K均值算法 實(shí)現(xiàn) 作者姓名： 郝蓓 指導(dǎo)教師： 郭瑞強(qiáng) 所在學(xué)院： 數(shù)學(xué)與信息科學(xué)學(xué)院 專 業(yè) （ 系 ） ： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級 （ 屆 ） ： 2022 屆 計(jì)算機(jī)班 二零一三 年 五月二日 目 錄 中文摘要、關(guān)鍵字 .......................................................... 1 1 緒論 ................................................................... 3 本文研究的背景和意義 ................................................ 3 聚類分析國內(nèi)外研究現(xiàn)狀 .............................................. 5 本文所做的主要工作 .................................................. 7 2 聚類算法的分析與研究 ................................................... 8 數(shù)據(jù)挖掘簡介 ........................................................ 8 聚類的基本知識 ...................................................... 8 類的定義及表示 ................................................... 8 聚類的相似度量方法 ............................................... 9 聚類間的距離測度函數(shù) ............................................ 11 聚類分析的一般步驟 .............................................. 12 常用的聚類分析的方法介紹 ........................................... 13 基于劃分的方法 .................................................. 13 基于密度的方法 .................................................. 13 基于層次的算法 .................................................. 13 基于模型的算法 .................................................. 14 基于網(wǎng)格的算法 .................................................. 14 常用的劃分聚類算法的分析 ........................................... 14 K均值聚類算法 .................................................. 14 K中心聚類法 .................................................... 15 本章小結(jié) ........................................................... 16 3 K 一均值聚類算法的研究 ................................................ 17 K均值聚類算法介紹 ................................................. 17 K 一均值聚類算法基本思想 ........................................ 17 K 一均值聚類算法主要流程 ........................................ 17 K均值聚類算法的主要缺陷及分析 ..................................... 18 本章小結(jié) ........................................................... 19 4 K均值聚類算法的實(shí)驗(yàn) .................................................. 20 實(shí)驗(yàn)結(jié)果分析 ....................................................... 20 本章小結(jié) ........................................................... 25 5 總結(jié)與展望 ............................................................ 26 總結(jié) ............................................................... 26 展望 ............................................................... 26 參考文獻(xiàn) ................................................................. 28 英文摘要、關(guān)鍵字 ......................................................... 31 1 論文題目：數(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)在的人們每一天都會面臨例如文本、圖像、視頻、音頻等各種數(shù)據(jù)形式，這些數(shù)據(jù)的數(shù)據(jù)量的大小是很驚人的。數(shù)據(jù)挖掘經(jīng)過一段時間的迅猛發(fā)展，誕生出了大量的理論結(jié)果和現(xiàn)實(shí)使用成果，它提供了許多工具和卓有成效的方法來解決問題。在這之中 ，基于劃分的 K均值聚類算法是目前研究最成熟傳統(tǒng)經(jīng)典的算法 。最后對本論文所研究的基于劃分的聚類算法 進(jìn)一步討論都有哪幾種算法。 本文通過六個實(shí)驗(yàn)結(jié)果分析得出 ，改變初始點(diǎn)，對聚類結(jié)果的影響不大，只是會改