【正文】 本科生畢業(yè)論文設(shè)計(jì) 數(shù)據(jù)挖掘 K均值算法 實(shí)現(xiàn) 作者姓名： 郝蓓 指導(dǎo)教師： 郭瑞強(qiáng) 所在學(xué)院： 數(shù)學(xué)與信息科學(xué)學(xué)院 專 業(yè) （ 系 ） ： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí) （ 屆 ） ： 2022 屆 計(jì)算機(jī)班 二零一三 年 五月二日 目 錄 中文摘要、關(guān)鍵字 .......................................................... 1 1 緒論 ................................................................... 3 本文研究的背景和意義 ................................................ 3 聚類分析國(guó)內(nèi)外研究現(xiàn)狀 .............................................. 5 本文所做的主要工作 .................................................. 7 2 聚類算法的分析與研究 ................................................... 8 數(shù)據(jù)挖掘簡(jiǎn)介 ........................................................ 8 聚類的基本知識(shí) ...................................................... 8 類的定義及表示 ................................................... 8 聚類的相似度量方法 ............................................... 9 聚類間的距離測(cè)度函數(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)在的人們每一天都會(huì)面臨例如文本、圖像、視頻、音頻等各種數(shù)據(jù)形式，這些數(shù)據(jù)的數(shù)據(jù)量的大小是很驚人的。怎樣能夠很快的并且高效地從這些大量數(shù)據(jù)中挖掘提煉出它所蘊(yùn)含的價(jià)值，成為現(xiàn)在人們特別關(guān)注并且需要馬上解決的問題。數(shù)據(jù)挖掘 (Data Mining， DM)正是因?yàn)檫@個(gè)才慢慢誕生出來。數(shù)據(jù)挖掘經(jīng)過一段時(shí)間的迅猛發(fā)展，誕生出了大量的理論結(jié)果和現(xiàn)實(shí)使用成果，它提供了許多工具和卓有成效的方法來解決問題。數(shù)據(jù)挖掘中有一項(xiàng)是很重要的研究領(lǐng)域，那就是聚類分析，這是一種對(duì)數(shù)據(jù)進(jìn)行按照不同的依據(jù)將數(shù)據(jù)進(jìn)行分組或者將數(shù)據(jù)進(jìn)行劃分的方式。聚類無論在生物科 學(xué)研究，還是在商務(wù)貿(mào)易中 、圖像 分析 處理、 網(wǎng)頁內(nèi)容 分類等其他 日常生活的領(lǐng)域都得到了很好的 應(yīng)用。 根據(jù) 使用的數(shù)據(jù)類型、使用的功能的不同、聚類需求 的不同，目前的聚類算法大概有以下幾種：基于劃分的算法、基于層次 的算法、基于密度的的算法、基 于模型的算法以及基于網(wǎng)格的算法。在這之中 ，基于劃分的 K均值聚類算法是目前研究最成熟傳統(tǒng)經(jīng)典的算法 。 K均值算法的應(yīng)用領(lǐng)域特別廣泛，覆蓋范圍涉及語音頻率 壓縮 還有 圖像及文本聚類，另外在數(shù)據(jù)預(yù)處理和神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的任務(wù)分解等也發(fā)揮其重要用途。本文所做的工作有： 本文第一部分：詳細(xì)介紹了本次論文研究的背景和目的，以及 所選題目的考慮思路，還有在當(dāng)前國(guó)際形式下，聚類分 析在國(guó)際上的地位及國(guó)內(nèi)外研究成果綜述，最后介紹了本論文算法實(shí)現(xiàn)的內(nèi)容和論文整體布局 安排。 第二部分：首先詳細(xì)描述了數(shù)據(jù)挖掘的來源發(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) 。 K 2 均值算法對(duì)初始值的 選取比較敏感和對(duì)數(shù)據(jù)的輸入順序不同也會(huì)影響聚類等問題，所以本文針對(duì)該問題進(jìn)行了驗(yàn)證，通過實(shí)驗(yàn)證明了 這兩個(gè)因素對(duì)聚類結(jié)果會(huì)有哪些 影響 。實(shí)驗(yàn)表明， K均值算法對(duì)初始值和數(shù)據(jù)輸入順序很敏感， 但是這兩個(gè)對(duì)聚類結(jié)果影響的方面不同。 本文通過六個(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ù)集來說有太多的不確定性，所以還是選擇最開始那幾個(gè)數(shù)據(jù)為數(shù)據(jù)聚類初始點(diǎn)；對(duì)于改變數(shù)據(jù)集的輸入順序，聚類結(jié)果與之前的有很大的改變，實(shí)驗(yàn)結(jié)果說明輸入順序不同既影響了聚類結(jié)果也影響了迭代次數(shù)。通過這些結(jié)論為以后用戶使用 K均值算法提供了很好的幫助，也為該算法的改進(jìn)提供了參考。 關(guān)鍵 詞 ：數(shù)據(jù)挖掘 聚類分析 Kmeans 算法 實(shí)驗(yàn)驗(yàn)證 3 1 緒論 本文研究的背景和意義 近年來，隨著科技的進(jìn)步以及互聯(lián)網(wǎng)的普及，以計(jì)算機(jī)為代表的信息技術(shù)有了巨大發(fā)展，人們產(chǎn)生、發(fā)現(xiàn)、整理、利用數(shù)據(jù)的能力不斷提升。到目前為止，數(shù)據(jù)在我們的日常生活中無處不在，它廣泛應(yīng)用于科學(xué)研究、政府日常辦公、軍事力量分析、企業(yè)管理電子商務(wù)、統(tǒng)計(jì)學(xué)分析等等各個(gè)領(lǐng)域。雖然我們知道這些數(shù)據(jù)的重要性，但是隨著時(shí)間越來越久，我們積累的數(shù)據(jù)量是不斷地在加大，相應(yīng)的我們分析處理這些數(shù)據(jù)的能力也要增 加，但是后來數(shù)據(jù)量的增長(zhǎng)速度已經(jīng)超出了我們的能力范圍，所以我們必 將面臨的嚴(yán)峻問題是數(shù)據(jù)爆炸。難道真的沒有辦法可以很科學(xué)的處理這些海 量數(shù)據(jù)嗎？事實(shí)并非如此，人類的智慧是無窮的，人們已經(jīng)通過理性的思維和恰當(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ī)則，也無法從當(dāng)前 現(xiàn)在的數(shù)據(jù)情況 去預(yù)測(cè)未來的 數(shù)據(jù)內(nèi)容的發(fā)展趨勢(shì)，更不可能做出決策判斷，使得人們逼不得已去面對(duì)“數(shù)據(jù)豐富而知識(shí)缺乏”的困 鏡 [1]。所以數(shù)據(jù)挖掘（ Data Mining） 技術(shù)因此就慢慢誕 生了，并且快速的發(fā)展應(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ā)掘出來隱含在當(dāng)中的、人們?cè)谶@之前不是特別了解的、但又是隱含 有用的信息 內(nèi)容 和知識(shí) 內(nèi)容 的非平凡過程 [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ù)類型。我們可以通過歸納演繹等方法來發(fā)現(xiàn)知識(shí)，也可以用統(tǒng)計(jì)學(xué)的數(shù)學(xué)或非數(shù)學(xué)的方法總結(jié)數(shù)據(jù)來得到我們想要的信息。這些我們得到的信息 內(nèi)容和知識(shí)內(nèi)容 的過程就是挖掘的 一個(gè) 過程，我們把挖掘的知識(shí)可以應(yīng)用到我們的生活中，包括未來決策規(guī)劃、優(yōu)化信息管理方案、調(diào)整控制模式、改進(jìn)查詢方案等等來更好的維護(hù)和利用我們 現(xiàn)有的數(shù)據(jù)。所以數(shù)據(jù)挖掘涉及到的學(xué) 4 科很廣泛，它 是各個(gè)學(xué)科的交叉 ，它用到了人工智能數(shù)學(xué)統(tǒng)計(jì)學(xué)與數(shù)據(jù)庫(kù)等技術(shù)來實(shí)現(xiàn)它自己的目的，需要這些領(lǐng)域的工程技術(shù)人員來共同配合，尤其是數(shù)據(jù)庫(kù)管理人員。 現(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)在我們的社會(huì)對(duì)數(shù)據(jù)挖掘技術(shù)的需求越來越強(qiáng)烈，目前我國(guó)很多的有眼光的軟件企業(yè)已經(jīng)將目光聚集于此，來研發(fā)更多適應(yīng)市場(chǎng)需求的數(shù)據(jù)挖掘軟件產(chǎn)品，隨著市場(chǎng)日趨成熟，廣大消費(fèi)者的應(yīng)用需求也是慢慢變大，相信將來會(huì)有更多成熟的中國(guó)數(shù)據(jù)挖掘軟 件面向市場(chǎng)。 聚類分析是數(shù)據(jù)挖掘的一個(gè)發(fā)現(xiàn)信息的方法，已經(jīng)被人們深入的研究了很長(zhǎng)時(shí)間，主要的是對(duì)基于距離的聚類分析的研究。聚類是一種無監(jiān)督的學(xué)習(xí)，分類正好與它相反，分類是一種有監(jiān)督的學(xué)習(xí)，聚類主要是劃分無標(biāo)記的對(duì)象，使這些無標(biāo)記的對(duì)象變的有意義，對(duì)預(yù)先定義的類與帶類標(biāo)記的訓(xùn)練實(shí)例不具有依賴性。所以聚類分析在我們的日常生活中的應(yīng)用范圍非常廣泛： ① 在商業(yè)上，聚類可以根據(jù)消費(fèi)者數(shù)據(jù)庫(kù)里面所記錄的數(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é)中，聚類用來發(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)功能相