基于聚類分析的Ｋ－ｍｅａｎｓ算法研究及應(yīng)用

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

關(guān)鍵詞：數(shù)據(jù)挖掘；聚類分析；數(shù)據(jù)庫；聚類算法 

中圖分類號：TP311文獻標(biāo)志碼：A

文章編號：1001－3695(2007)05－0166－03

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

常用的數(shù)據(jù)挖掘技術(shù)包括關(guān)聯(lián)分析、異類分析、分類與預(yù)測、聚類分析以及演化分析等。由于數(shù)據(jù)庫中收集了大量的數(shù)據(jù)，聚類分析已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的重要技術(shù)之一。

1問題的提出

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

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

2聚類算法分析

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

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

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

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

（4）基于網(wǎng)格的方法。基于網(wǎng)格方法將對象空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)。其主要優(yōu)點是它的處理速度很快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。STING 就是一個典型的基于網(wǎng)格的方法。

（5）基于模型的方法。該方法就是為每個聚類假設(shè)一個模型，然后再去發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對象。它根據(jù)標(biāo)準(zhǔn)統(tǒng)計方法并考慮到噪聲或異常數(shù)據(jù)，可以自動確定聚類個數(shù)；因而它可以產(chǎn)生很魯棒的聚類方法。

數(shù)據(jù)挖掘在不同領(lǐng)域?qū)垲愃惴ㄌ岢隽烁髯蕴厥獾囊螅?可以給聚類算法的研究和應(yīng)用提供參考[7]。

3兒童生長發(fā)育的分析

聚類分析在數(shù)據(jù)挖掘中的應(yīng)用主要有以下三個方面：

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

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

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

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

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

②進行統(tǒng)計分析，在聚類方法上選擇Iterate and classify指定初始類別中心點，按K－means算法作迭代分類。對聚類結(jié)果進行方差分析。

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

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

在原始數(shù)據(jù)庫（圖1）中，可清楚地看到聚類結(jié)果；參照專業(yè)知識，將兒童生長發(fā)育分期定為：

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

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

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

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

圖1逐步聚類分析的分類結(jié)果

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

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

輸入：簇的數(shù)目k=4和輸入n=19的表2的數(shù)據(jù)。

輸出：四個簇，使平方誤差準(zhǔn)則最小。

方法：

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

②repeat；

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

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

⑤until 不再發(fā)生變化。

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

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

4結(jié)束語

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

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

參考文獻：

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

[2]衛(wèi)生部關(guān)于八省（自治區(qū)）嬰幼兒營養(yǎng)健康狀況調(diào)查報告[R].北京：新華出版社，2005:1－3.

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

[4]GONZALEZ T.Clustering to minimize and maximum intercluster distance[J].Theoretical Computer Science，1985，38（2－3）:293－306.

[5]PAL N R，BEZDEK J C.On cluster validity for the fuzzy c－means model[J].IEEE Transactions on Fuzzy Systems，1995，3(3):370－379.

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

[7]HAN Jiawei，KAMBER M.Data mining concepts and techniques[M].范明，孟小峰，等譯.北京： 機械工業(yè)出版社.

[8]馬慶國.管理統(tǒng)計[M].北京：科學(xué)出版社，2002:3－120.

[9]WISHART D.K－means clustering with outlier detection:the 25th Annual Conference of the German Classification Society[C].Munich:University of Munich，2001:14－16.

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

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

[12]錢鋒，徐麟文.知識發(fā)現(xiàn)中的聚類分析及其應(yīng)用[J].杭州師范學(xué)院學(xué)報:自然科學(xué)版，2001(2):34－37.

[13]許向東，張全壽.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘的應(yīng)用[J].計算機系統(tǒng)應(yīng)用，1998(4):20－24.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”