【正文】 似的基因組，對(duì)基因因功能不同進(jìn)行劃分對(duì)其固有的結(jié)構(gòu)特征進(jìn)行分析，來更好的為我們的醫(yī)學(xué)發(fā)展提供有利條件； ⑤ 在空間數(shù)據(jù)庫領(lǐng)域，聚類分析能對(duì)相似地理特征區(qū)域及它們的人和環(huán)境的不同特征進(jìn)行識(shí)別，來研究地域文化提供條件。 本文主要選擇聚類分析中基于劃分的 Kmeans 算法并實(shí)現(xiàn)它 的應(yīng)用，對(duì)數(shù)據(jù)集的數(shù)據(jù)進(jìn)行聚類分析。本文在實(shí)現(xiàn)它的基礎(chǔ)上，對(duì)該算法對(duì)初始值和數(shù)據(jù)輸入順序敏感的問題進(jìn)行了驗(yàn)證，通過六次試驗(yàn)，分別對(duì)這個(gè) 兩 個(gè)方面進(jìn)行驗(yàn)證，并對(duì)聚類結(jié)果進(jìn)行分析比較，從而得出結(jié)論。本文通過對(duì)不同輸入條件的實(shí)驗(yàn)驗(yàn)證，得出 K均值算法對(duì)初始值得選擇和數(shù)據(jù)輸入順序是很敏感的結(jié)論，通過實(shí)驗(yàn)結(jié)果可得出在今后使用 K均值算法時(shí)我們應(yīng)該怎樣避免其聚類出不準(zhǔn)確的聚類結(jié)果和今后改進(jìn)算法應(yīng)該改進(jìn)的方向等問題。 5 聚類分析國內(nèi)外研究現(xiàn)狀 目前，國內(nèi)對(duì)于數(shù)據(jù)挖掘聚類分析的研究的集中部門還是科研單位和各大高校，國內(nèi)還沒有公司企業(yè)專門從事聚類分析的研究，相對(duì)于外國來說起步較晚。各大科研機(jī)構(gòu)與高 校對(duì)聚類的研究主要是對(duì)數(shù)據(jù)集聚類算法的設(shè)計(jì)并實(shí)現(xiàn)，以研究出來的算法 為基礎(chǔ)對(duì)算法改進(jìn)。目前人們已經(jīng)在統(tǒng)計(jì)分析軟件中應(yīng)用一些聚類分析工具，如 SAS 等軟件。 為大型的數(shù)據(jù)庫尋求有效的 聚類分析方法是目前聚類分析的主要研究工作，目前研究方向包括以下幾個(gè)方向： （ 1） 可伸縮性：目前的聚類算法針對(duì)小型數(shù)據(jù)庫，數(shù)據(jù)量是幾百范圍內(nèi)的，對(duì)于有很龐大數(shù)據(jù)量的數(shù)據(jù)庫會(huì)造成結(jié)果的不穩(wěn)定性，可伸縮性強(qiáng)的算法就亟待的研發(fā)出來。 （ 2） 屬性不同情況下的處理能力：現(xiàn)在開發(fā)出來的聚類算法所針對(duì)的數(shù)據(jù)類型都是數(shù)值型，但實(shí)際上的聚類類型的信息是不確定的，如二元數(shù)據(jù)、序數(shù)型 的 、分類型 的 等或者是 所已知的 各種 數(shù)據(jù) 類型的混合。 （ 3）聚類形狀：在 歐幾里得距離 的基礎(chǔ)上 發(fā)現(xiàn)所得的簇的形狀是球狀簇，它們有相近的距離與密度，形成一個(gè)簇，但是我們更希望能夠有一種算法實(shí)現(xiàn)各個(gè)不同 形狀的簇。 （ 4）決定結(jié)果的輸入?yún)?shù)：聚類算法的實(shí)現(xiàn)過程中相當(dāng) 多 的是必須讓 用戶 提前輸入想要 聚類出來的簇?cái)?shù) K，當(dāng)前的算法對(duì)這些 K 的值是相當(dāng)敏感的，大型的數(shù)據(jù)流對(duì)這些要求很嚴(yán)格 ，對(duì)結(jié)果的影響很明 顯，使用戶在輸入時(shí)加大了分析的工作難度，很難 控制。 （ 5） 輸入數(shù)據(jù)的順序問題：有的聚類算法對(duì)輸入數(shù)據(jù)的順序是有要求的，不同的輸入次序會(huì)有不同的聚類結(jié)果，這就特別需要對(duì)數(shù)據(jù)順序不敏感的算法開發(fā)出來，更好的適應(yīng)人們的要求。 （ 6） 高維數(shù)據(jù)的處理：含有若干維數(shù)據(jù)屬性的數(shù)據(jù)庫是很常見的，但是擅長(zhǎng)處理 兩維或三維的聚類算法才是目前成熟的 應(yīng)用的算法，一旦高維數(shù)據(jù)需要聚類處理，這就是一個(gè)難題，這就需要算法有很強(qiáng)的實(shí)用性。 （ 7） 污染數(shù)據(jù)的發(fā)現(xiàn)：數(shù)據(jù)是一個(gè)不確定而且無限性的群體，我們不能保證數(shù)據(jù)集中的數(shù)據(jù)是完全集中的，難免會(huì) 有個(gè)別的孤立點(diǎn)造成污染數(shù)據(jù)，影響整個(gè)結(jié)果， 應(yīng)該開發(fā)出能智能識(shí)別這些孤立點(diǎn)的數(shù)據(jù)的算法，來優(yōu)化聚類結(jié)果，目前大部分是 通過對(duì)目前算法進(jìn)行改進(jìn)來實(shí)現(xiàn)。 6 （ 8） 有約束條件的聚類：實(shí)際的聚類情況是有很多限制的條件的，在實(shí)現(xiàn)這 些聚類時(shí)，既要按約束條件又要按聚類要求實(shí)現(xiàn)，是很有壓力和挑戰(zhàn)的 一項(xiàng)任務(wù)。 （ 9） 可 使 用性和可解釋性：大多情況下的聚類結(jié)果，對(duì)于客戶來說都希望它們簡(jiǎn)單易懂，一目了然，所以我們要優(yōu)化聚類結(jié)果界面的研究，選擇適合每個(gè)客戶需求的聚類方法來滿足他們的需求。 同時(shí)聚類分析算法主要著手于以 下的幾個(gè)問題的解決 [3]： （ 1） 初始值的選取及輸入順序?qū)Y(jié)果有何影響 在數(shù)據(jù)挖掘的學(xué)科范圍內(nèi)尋找最優(yōu)解的過程是通 過迭代不同的初始值實(shí)現(xiàn)，但是這個(gè)辦法不是很可靠，它的意思就是表示不能百分之百的 確定找到最優(yōu)解。其實(shí)尋找最優(yōu)解就是在優(yōu)化原來的聚類的結(jié)果，通過重復(fù)聚類 找到所設(shè)計(jì)的目標(biāo)函數(shù)的最優(yōu)解，但是這個(gè)目標(biāo)函數(shù)一般都不是有最值的 函數(shù)，所以它的最小值并不是很容易確定，因?yàn)樗⒉晃ㄒ?，有可能找到的這個(gè)只是局部最小值，而不 是全局最小，所以這種非完全單調(diào)函數(shù)的全局最小值的查找是目前最急著等待 解決的問題。 （ 2）以 小波變換 為基礎(chǔ)的 聚類算法 因?yàn)楫?dāng)前主要是對(duì)均值算法與模糊算法的研究改進(jìn)而得到的研究成果，這些研究成果使得目前的聚類分析算法提高了它的性能屬性。小波變換聚類算法同樣符合好的聚類算法的各項(xiàng)要求，目前對(duì)小波聚類的研究還有很大程度的空白，如果花大的精力進(jìn)一步研究會(huì)有更加深入的突破。 （ 3）算法的效率改善提高的 問題 聚類的效率 問題是目前一個(gè)很棘手的問題，因?yàn)槿祟愒谶M(jìn)步，數(shù)據(jù)量會(huì)越來越龐大，應(yīng)該增強(qiáng)目前聚類算法對(duì)更大數(shù)據(jù)庫的處理能力，即增量聚類，使 聚類算法在聚類的數(shù)量上有更好的彈性，盡量減少在工作時(shí)對(duì)龐大數(shù)據(jù)庫的掃描次數(shù)，進(jìn)一步提高它的工作效 率。 （ 4） 數(shù)據(jù)庫類型 目前，基于聚類算法的數(shù)據(jù)庫比較單一，僅僅包括關(guān)系或事務(wù)數(shù)據(jù)庫，應(yīng)該著眼于其他數(shù)據(jù)庫類型應(yīng)用算法的研究，比如面向 以 屬性 為內(nèi)容的 數(shù)據(jù)庫、 以 文本 為內(nèi)容的 數(shù)據(jù)庫、 各個(gè)不同 時(shí)態(tài) 為內(nèi)容的 數(shù)據(jù)庫、地理數(shù) 據(jù)庫多維數(shù)據(jù)庫等的算法開發(fā)，這是一項(xiàng)非常艱巨而且有意義的研究任務(wù) 。 7 聚類分析中的算法有很多種，詳細(xì)分析比較了各個(gè)算法的優(yōu)缺點(diǎn)，本文著重 介紹了K均值算法，分析它本身的算法優(yōu)點(diǎn)與不足，并對(duì)算法實(shí)現(xiàn)，著力于對(duì)影響該算法聚類結(jié)果的不同初始條件進(jìn)行驗(yàn)證 ，以 更好在以后的實(shí)際應(yīng)用中使用它 。 K均值算法是聚類分 析最常用的算法之一。 K均值算法的應(yīng)用范圍非常廣泛，因?yàn)樗牟僮骱?jiǎn)單，適合處理龐大的數(shù)據(jù)集，但是它同時(shí)也暴露出自身的不足，如易陷入局部最優(yōu)解的結(jié)果里面、需要用戶提前輸入?yún)?shù)、發(fā)現(xiàn)簇的形狀比較單一等，已經(jīng)有很多專家對(duì)這些問題進(jìn)行了改進(jìn)，文獻(xiàn) [4]作者通過最大最小距離和 DBI 聚類指標(biāo)解決了 K均值算法對(duì)初始值 K 的 選擇問題，能夠確定出最佳的聚類數(shù)目。文獻(xiàn) [5]的作者用 K均值算法與層次聚類算法進(jìn)行混合出一種新的聚類算法，充分發(fā)揮了層次聚類的精確性和K均值的高效性。文獻(xiàn) [6]的作者對(duì)遺傳算法提出一種改進(jìn)算法，基于比變長(zhǎng)編碼，利用這種算法與 K均值結(jié)合解決了對(duì)初值選擇的敏感問題等等，目前 已經(jīng)有很多被發(fā)表出來的對(duì) K均值的改進(jìn)的算法。 本文所做的主要工作 首先對(duì)數(shù)據(jù)挖掘這門學(xué)科的背景和發(fā)展前景做了分析，本文主 要研究數(shù)據(jù)挖掘的聚類分析，所以介紹了聚類分析目前國內(nèi)外的地位與發(fā)展方向，以為下文展開作鋪墊，這方面閱讀了許多聚類相 關(guān)文獻(xiàn)，許多新的聚類分析方法先后被各國的科研工作者提出并應(yīng)用，這些在本文有詳細(xì)列舉。除此之外本文對(duì)聚類分析中的常用的五種方法做了簡(jiǎn)要介紹，列舉了五種方法中 目前比較常用的算法，并分析了每個(gè)算法的適用領(lǐng)域與基本思想。 本文著重討論的是基于劃分的聚類分析方法中的 Kmeans 方法，對(duì) KM 方法進(jìn)行了詳細(xì)的介紹，包括基本思路工作流程等，本文通過分析 KM 算法的缺點(diǎn)，通過實(shí) 驗(yàn)驗(yàn)證了對(duì)初始點(diǎn)的選取和數(shù)據(jù)輸入順序 敏感的驗(yàn)證， 通過兩個(gè)實(shí)驗(yàn)分別得出這兩個(gè)因素對(duì)聚類結(jié)果產(chǎn)生怎樣的影響并得出結(jié)論，實(shí)驗(yàn)表明初始點(diǎn)不同只是影響聚類迭代的次數(shù)，對(duì)聚類結(jié)果的影響不明顯，只是少數(shù)數(shù)據(jù)的聚類結(jié)果發(fā)生改變；數(shù)據(jù)輸入順序的不同，不僅會(huì)改變數(shù)據(jù)聚類的迭代次數(shù)，也會(huì)讓聚類的結(jié)果發(fā)生明顯改變。 8 2 聚類算法的分析與研究 數(shù)據(jù)挖掘簡(jiǎn)介 數(shù)據(jù)挖掘（ Data Mining） ，也被叫做在已知的 數(shù)據(jù)庫中 對(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í)數(shù)據(jù)挖掘就是通過各種分析算法工具從巨大數(shù) 量的數(shù)據(jù)中挖掘所需要的數(shù)據(jù)與模型 兩者 關(guān)系的 一個(gè)過程，可以通過 得到的這些關(guān)系，對(duì)未來的數(shù)據(jù)與模型關(guān)系進(jìn)行預(yù)測(cè)。通常根據(jù)不同用 戶的需求，和他們所提供的數(shù)據(jù)類型，數(shù)據(jù)挖掘的數(shù)據(jù)庫的類型也是不一樣 的，通常包括關(guān)系數(shù)據(jù)庫 類型 、事物數(shù)據(jù)庫 類型 、多媒體數(shù)據(jù)庫 類型等。其中關(guān)系數(shù)據(jù)庫實(shí)際上就是使用 數(shù)學(xué) 學(xué)科上的 方法來處理數(shù)據(jù) 之間的關(guān)系 ，我們生活中隨處可見關(guān)系數(shù)據(jù)庫，比如交通部的車輛數(shù)據(jù)庫、銀行的客戶記錄等。事務(wù)數(shù)據(jù)庫一般是將幾個(gè)事務(wù)數(shù)據(jù)庫的數(shù)據(jù)一起導(dǎo)入 到只能用來讀數(shù)據(jù)的 數(shù)據(jù)挖掘 庫中，做成一個(gè)數(shù)據(jù)集市，然后把其作為挖掘的對(duì)象。多媒體數(shù)據(jù)庫 顧名思義就是包含大量視頻音頻文件，模式識(shí)別技術(shù)被用 于該領(lǐng)域。 數(shù)據(jù)挖掘包含很多類別，包括分類分析、聚類分析、關(guān)聯(lián)分析孤立點(diǎn)分析等其他分析。其中分類分析包括分類和回歸，分類分析是一種預(yù)測(cè)模型，通過現(xiàn)有數(shù)據(jù)預(yù)測(cè)將來的數(shù)據(jù)，如果預(yù)測(cè)的數(shù)據(jù)是離散的即叫做分類，如果是連續(xù)的即叫做回歸。聚類分析則是將大量數(shù)據(jù)中形似的數(shù)據(jù)分到一組，一個(gè)數(shù)據(jù)集大概包括幾組數(shù)據(jù)，聚類沒有明顯的屬性目標(biāo)，而是挖掘隱藏的屬性來進(jìn)行聚類，聚類分析中的 基于劃分的 K均值算法 是本文的研究對(duì)象。關(guān)聯(lián)分析分析數(shù)據(jù)與數(shù)據(jù)之間關(guān)聯(lián)關(guān)系還有它與其他數(shù)據(jù)的派生關(guān)系。孤立點(diǎn)分析 是針對(duì)那些遠(yuǎn)離 數(shù)據(jù)集的點(diǎn)，對(duì)不同的客 戶，別人的孤立點(diǎn)可能對(duì)于他來說是很重要的信息，孤立點(diǎn)分析就是對(duì)這些 遠(yuǎn)離數(shù)據(jù)集中心的 數(shù)據(jù)信息進(jìn)行挖掘。 孤立點(diǎn)的研究是將來我們必須重點(diǎn)研究的領(lǐng)域，因?yàn)閹讉€(gè)孤立點(diǎn)就會(huì)影響全局的聚類結(jié)果，這是不容忽視的。 聚類的基本知識(shí) 類的定義及表示 （ 1）類的定義 9 要想聚類操作首先要明確類的定義。 世界錯(cuò)綜復(fù)雜事物存在的方式也不盡相同，所以類的定義并不唯一。以下將 列 舉 出常用的類的定義： 設(shè)：含有 K 個(gè)樣本的集合 A， Mi 是其中的某個(gè)樣本， T 和 C 是范圍閥值，那么：如果任意的 Mi， Mj ∈ A，都有 D（ Mi， Mj）≤ T，則 A 稱為一類； （ 2）類的表示； 聚類的表示方法也是有不同的，一般用以下三種： ① 自然語言表示：直接用自然語言直觀的描述出這些數(shù)據(jù)是屬于哪個(gè)簇的； ② DNF 表示：用析取范式表示明了、簡(jiǎn)潔、易懂。例如： (36PT70)V(345AM1234)； ③ 聚類譜系圖：目前使用的聚類算法輸出結(jié)果大部分都是這種，這種方法表示非常詳細(xì)，它能表示出這些樣本自成一類的所有中間情況，而且都會(huì)有各個(gè)類的平臺(tái)高度，我們叫這種圖為標(biāo)度聚類譜系圖。 聚類的相似度量方法 聚類分析按照數(shù)據(jù)樣本性質(zhì)的相似 程度的大小進(jìn)行劃分，確定這些相似程度的大小必須有一個(gè)準(zhǔn)則來判斷它們的程度 大小，這個(gè)判斷準(zhǔn)則叫做相似度方法，主要是在距離和相似系數(shù)的不同。 距離：樣本點(diǎn)之間的相 似性我們就用某種距離函數(shù)表示，距離近的表示樣本點(diǎn)相似，具體計(jì)算時(shí)可以把樣本看做有 M 個(gè)屬性的變量，即這個(gè)樣本就是在一個(gè) M 維的空間中的一個(gè)點(diǎn)。 距離函數(shù)：設(shè) P 是所有樣本集合的集合名稱，如果滿足： ① 正定性 D(M， N)≥ 0， if M≠ N D(M， N)=0， if M=N ② 對(duì)稱性 D(M， N)=D(M， N) ③ 三角不等式 D(M,N)+D(N， L)≧ D(M， L) 我們稱它們?yōu)榫嚯x函數(shù)。 聚類分析中經(jīng)常使用的 的距離函數(shù)有： ① 明氏 (Minkowski)距離 11( , ) ( )p mmi j ik jkkd x x x x?????????? ………………………………………… () 10 當(dāng) m 取 1 時(shí)，則表示絕對(duì)距離，當(dāng) m 取 2 時(shí)就表示 歐式 (Euclid)距離，當(dāng) m 取無窮大時(shí)就表示 切比雪夫 (Chebyshev)距離。 如： 歐氏距離 1221( , ) ( )pi j ik jkkd x x x x??????????………………………………… () ② 馬氏 (Mahalanois)距離 11 2( , ) ( ) ( )Ti j i j i jd x x x x S x x???? ? ???……………………………… () 其中 S 是由樣品集 N（ 12, , .. . , , .. . ,jnx x x x）算得的協(xié)方差矩陣： 1111, ( ) ( )1nn Ti i iiix x S x x x xnn??? ? ? ????…………………………… …… () 樣品聚類一般情況下被叫做 Q 型聚類，是以 距離矩陣 為出發(fā)點(diǎn)的。明氏距離改進(jìn)后得到了馬氏距離，所有的 線性變換對(duì)于馬氏距離來說是不變的，多重相關(guān)性馬氏距離也把它 克服了。 ③ 方差加權(quán)距 離 12221()( , ) p ik jkij k kxxd x xs????? ?????…………………………………………… () 其中 221111, ( ) .1nnik k ik kiix x s x xnn??? ? ????…………………………….. () 在聚類分析中除了對(duì)樣本點(diǎn)聚類，對(duì)特征變量也要根據(jù)實(shí)際情況進(jìn)行聚類，所以對(duì)于特征向量而言，不必非用距離函數(shù)來確定它們的相似測(cè)度，還可以用相似系數(shù)。 相似系數(shù)：當(dāng)對(duì) 含有 k 個(gè)指標(biāo)的變量的數(shù)據(jù)集進(jìn)行聚類時(shí)，就用相似系數(shù)來