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