聚類分析K-means算法研究

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

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

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

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

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

1問題的提出

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

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

2聚類算法分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

方法：

①任意選擇四個(gè)對(duì)象作為初始簇的中心；

②repeat；

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

本文原文

④更新簇的平均值，即計(jì)算每個(gè)簇中對(duì)象的平均值；

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

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

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

4結(jié)束語

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

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

參考文獻(xiàn)：

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

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

[3]杭燕.體育幼兒園現(xiàn)代體育課程模式的探索（上）[J].學(xué)前教育文薈,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]邵峰晶,于忠清.數(shù)據(jù)挖掘的原理與算法[M].北京：中國水利水電出版社,2003.

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

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

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

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

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

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

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