聚類分析K-means算法研究

導語：聚類分析K-means算法研究一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要：通過對聚類分析及其算法的論述，從多個方面對這些算法性能進行比較，同時以兒童生長發育時期的數據為例通過聚類分析的軟件和改進的K－means算法來進一步闡述聚類分析在數據挖掘中的實踐應用。

關鍵詞：數據挖掘；聚類分析；數據庫；聚類算法

隨著計算機硬件和軟件技術的飛速發展，尤其是數據庫技術的普及，人們面臨著日益擴張的數據海洋，原來的數據分析工具已無法有效地為決策者提供決策支持所需要的相關知識，從而形成一種獨特的現象“豐富的數據，貧乏的知識”。數據挖掘[1]又稱為數據庫中知識發現（KnowledgeDiscoveryfromDatabase，KDD），它是一個從大量數據中抽取挖掘出未知的、有價值的模式或規律等知識的復雜過程。目的是在大量的數據中發現人們感興趣的知識。

常用的數據挖掘技術包括關聯分析、異類分析、分類與預測、聚類分析以及演化分析等。由于數據庫中收集了大量的數據，聚類分析已經成為數據挖掘領域的重要技術之一。

1問題的提出

隨著社會的發展和人們生活水平的提高，優育觀念[2，3]逐漸滲透到每個家庭，小兒的生長發育越來越引起家長們的重視。中國每隔幾年都要進行全國兒童營養調查，然而用手工計算的方法在大量的數據中分析出其中的特點和規律，顯然是不現實的，也是不可行的。為了有效地解決這個問題，數據挖掘技術——聚類分析發揮了巨大的作用。

在數據挖掘領域，聚類算法經常遇到一些問題如聚類初始點的選擇[4]、模糊因子的確定[5]等，大部分均已得到解決。現在的研究工作主要集中在為大型的數據庫有效聚類分析尋找適當的方法、聚類算法對復雜分布數據和類別性數據聚類的有效性以及高維數據聚類技術等方面。本文通過對聚類分析算法的分析并重點從聚類分析的軟件工具和改進的K－means算法兩個方面來論證聚類分析在兒童生長發育時期中的應用。

2聚類算法分析

聚類[6]分析是直接比較各事物之間的性質，將性質相近的歸為一類，將性質差別較大的歸入不同的類。在醫學實踐中也經常需要做分類工作，如根據病人的一系列癥狀、體征和生化檢查的結果，判斷病人所患疾病的類型；或對一系列檢查方法及其結果，將之劃分成某幾種方法適合用于甲類病的檢查，另幾種方法適合用于乙類病的檢查，等等。聚類分析被廣泛研究了許多年。基于聚類分析的工具已經被加入到許多統計分析軟件包或系統中，如S－Plus、SPSS,以及SAS。

大體上，聚類算法[7]可以劃分為如下幾類：

（2）層次方法。該方法就是通過分解所給定的數據對象集來創建一個層次。它存在的缺陷就是在進行（組）分解或合并之后無法回溯。將循環再定位與層次方法結合起來使用常常是有效的，如BIRCH和CURE，就是基于這種組合方法設計的。

（3）基于密度的方法。只要臨近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類。DBSCAN是一個有代表性的基于密度的方法。它根據一個密度閾值來控制簇的增長。

（4）基于網格的方法。基于網格方法將對象空間劃分為有限數目的單元以形成網格結構。其主要優點是它的處理速度很快，其處理時間獨立于數據對象的數目，只與量化空間中每一維的單元數目有關。STING就是一個典型的基于網格的方法。

（5）基于模型的方法。該方法就是為每個聚類假設一個模型，然后再去發現符合相應模型的數據對象。它根據標準統計方法并考慮到噪聲或異常數據，可以自動確定聚類個數；因而它可以產生很魯棒的聚類方法。

數據挖掘在不同領域對聚類算法提出了各自特殊的要求,表1可以給聚類算法的研究和應用提供參考[7]。

3兒童生長發育的分析

聚類分析在數據挖掘中的應用主要有以下三個方面：

（1）聚類分析能作為一個獨立的工具來獲得數據的分布情況，觀察每個簇的特點，集中對特定的某些簇作進一步的分析。如：①聚類分析軟件v1.2。此軟件主要用于血型、蛋白質多態、品種聚類等方面的統計分析，可自動進行雜合度、多態信息含量、遺傳距離以及聚類的計算，并可自動畫出聚類圖。②SPSS統計軟件。SPSS軟件是一種專業的統計分析軟件，用于數據的各種分析，從而最終為企、事業的科學決策服務。其中采用聚類分析是理想的多變量統計技術，主要有分層聚類法和迭代聚類法。

本文通過一組兒童生長發育的數據運用SPSS工具進行分析，如表2所示。

運用SPSS工具調用K－meansCluster過程可完成由用戶指定類別數的大樣本資料的逐步聚類分析。逐步聚類分析就是先把被聚對象進行初始分類，然后逐步調整，得到最終分類。

為研究兒童生長發育的分期，筆者對1253名1月~7歲兒童進行了抽樣調查，分別對兒童的身高（cm）、體重（kg）、胸圍（cm）和坐高（cm）進行了測量。資料作如下整理：先把1月~7歲劃成19個月份段，分月份算出各指標的平均值，將第1月的各指標平均值與出生時的各指標平均值比較，求出月平均增長率（%），然后第2月起的各月份指標平均值均與前一月比較，求出月平均增長率（%）（表2）。將兒童生長發育時期分為四期，所以聚類的類別數為4，從而確定四個兒童生長發育期的起止區間。

①激活數據管理窗口，定義變量名。雖然月份分組不做分析變量，但為了更直觀地了解聚類結果，也將之輸入數據庫。

②進行統計分析，在聚類方法上選擇Iterateandclassify指定初始類別中心點，按K－means算法作迭代分類。對聚類結果進行方差分析。

結果解釋：首先系統根據用戶的指定，按四類聚合確定初始聚類的各變量中心點，未經K－means算法迭代，其類別間距離并非最優；經迭代運算后類別間各變量中心值得到修正。

③對聚類結果的類別間距離進行方差分析。方差分析表明，類別間距離差異的概率值均小于0.001，即聚類效果好。這樣，原有19類（即原有的19個月份分組）聚合成四類，第一類含原有1類，第二類含原有1類，第三類含原有2類，第四類含原有15類。具體結果系統以變量名qcl_1存于原始數據庫中。

在原始數據庫（圖1）中，可清楚地看到聚類結果；參照專業知識，將兒童生長發育分期定為：

第一期，出生后至滿月，增長率最高；

第二期，第2個月起至第3個月，增長率次之；

第三期，第3個月起至第8個月，增長率減緩；

第四期，第8個月后，增長率顯著減緩。

圖1逐步聚類分析的分類結果

（2）運用聚類分析軟件可以很方便地對數據進行分析，利用分析的結果，在孩子生長發育時期合理安排好飲食，促進兒童健康快樂成長。同時，聚類分析可以作為其他算法（如特征和分類等）的預處理步驟，這些算法再在生成的簇上進行處理。本文以改進的K－means算法[9]為例來說明兒童生長發育時期的特征。算法描述如下：

算法：K－means。劃分的K－means算法基于簇中對象的平均值。

輸入：簇的數目k=4和輸入n=19的表2的數據。

輸出：四個簇，使平方誤差準則最小。

方法：

①任意選擇四個對象作為初始簇的中心；

②repeat；

③根據簇中對象的平均值，將每個對象（重新）賦給最類似的簇；

本文原文

④更新簇的平均值，即計算每個簇中對象的平均值；

⑤until不再發生變化。

在本算法中要用到以下幾個定義：

（3）聚類分析也可以進行孤立點的分析。經常存在一些數據對象，它們不符合數據的一般模型，這些數據對象被稱為孤立點。孤立點的分析有著廣泛的應用[12，13]，如欺詐檢測即探詢不尋常的信用卡使用或電信服務；此外，它在市場分析中可用于確定極低或極高收入的客戶的消費行為、或者在醫療分析中用于發現對多種治療方式的不尋常的反應。

4結束語

本文通過改進的K－means算法和聚類分析工具SPSS來對兒童生長發育期進行分析。

在科技發展的今天，隨著信息化產業的不斷發展，大量的數據迫切需要強有力的數據分析工具的出現，從而導致了數據挖掘的蓬勃發展，而聚類分析已經成為數據挖掘領域一個非常活躍的研究課題。用戶當然希望聚類的結果是可解釋的、可理解的和可應用的。如何選擇聚類方法和正確地使用聚類算法也是很重要的，而目前所使用的聚類算法均存在某方面的缺陷，也沒有統一的標準，因此如何使聚類算法成為像SQL語言那樣統一、標準的語言，還有待于計算機工作者的努力。

參考文獻：

［1］朱明.數據挖掘[M].合肥：中國科學技術大學出版社，2002：5－6.

[2]衛生部關于八省（自治區）嬰幼兒營養健康狀況調查報告[R].北京：新華出版社，2005:1－3.

[3]杭燕.體育幼兒園現代體育課程模式的探索（上）[J].學前教育文薈,2000（6）:10－12.

[4]GONZALEZT.Clusteringtominimizeandmaximuminterclusterdistance[J].TheoreticalComputerScience,1985,38（2－3）:293－306.

[5]PALNR,BEZDEKJC.Onclustervalidityforthefuzzyc－meansmodel[J].IEEETransactionsonFuzzySystems,1995,3(3):370－379.

[6]邵峰晶,于忠清.數據挖掘的原理與算法[M].北京：中國水利水電出版社,2003.

[7]HANJiawei,KAMBERM.Dataminingconceptsandtechniques[M].范明,孟小峰,等譯.北京：機械工業出版社.

[8]馬慶國.管理統計[M].北京：科學出版社,2002:3－120.

[9]WISHARTD.K－meansclusteringwithoutlierdetection:the25thAnnualConferenceoftheGermanClassificationSociety[C].Munich:UniversityofMunich,2001:14－16.

[10]左子葉,朱揚勇.基于數據挖掘聚類技術的信用評分評級[J].計算機應用與軟件,2004,21(4):1－3，101.

[11]何彬彬,方濤，郭達志.基于不確定性的空間聚類[J].計算機科學,2004,31(11):196－198.

[12]錢鋒,徐麟文.知識發現中的聚類分析及其應用[J].杭州師范學院學報:自然科學版,2001(2):34－37.

[13]許向東,張全壽.數據倉庫與數據挖掘的應用[J].計算機系統應用,1998(4):20－24.