聚類分析K-means算法研究
時間:2022-10-25 07:57:00
導(dǎo)語:聚類分析K-means算法研究一文來源于網(wǎng)友上傳,不代表本站觀點(diǎn),若需要原創(chuàng)文章可咨詢客服老師,歡迎參考。
摘要:通過對聚類分析及其算法的論述,從多個方面對這些算法性能進(jìn)行比較,同時以兒童生長發(fā)育時期的數(shù)據(jù)為例通過聚類分析的軟件和改進(jìn)的K-means算法來進(jìn)一步闡述聚類分析在數(shù)據(jù)挖掘中的實(shí)踐應(yīng)用。
關(guān)鍵詞:數(shù)據(jù)挖掘;聚類分析;數(shù)據(jù)庫;聚類算法
隨著計算機(jī)硬件和軟件技術(shù)的飛速發(fā)展,尤其是數(shù)據(jù)庫技術(shù)的普及,人們面臨著日益擴(kuò)張的數(shù)據(jù)海洋,原來的數(shù)據(jù)分析工具已無法有效地為決策者提供決策支持所需要的相關(guān)知識,從而形成一種獨(dú)特的現(xiàn)象“豐富的數(shù)據(jù),貧乏的知識”。數(shù)據(jù)挖掘[1]又稱為數(shù)據(jù)庫中知識發(fā)現(xiàn)(KnowledgeDiscoveryfromDatabase,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ā)育越來越引起家長們的重視。中國每隔幾年都要進(jìn)行全國兒童營養(yǎng)調(diào)查,然而用手工計算的方法在大量的數(shù)據(jù)中分析出其中的特點(diǎn)和規(guī)律,顯然是不現(xiàn)實(shí)的,也是不可行的。為了有效地解決這個問題,數(shù)據(jù)挖掘技術(shù)——聚類分析發(fā)揮了巨大的作用。
在數(shù)據(jù)挖掘領(lǐng)域,聚類算法經(jīng)常遇到一些問題如聚類初始點(diǎn)的選擇[4]、模糊因子的確定[5]等,大部分均已得到解決。現(xiàn)在的研究工作主要集中在為大型的數(shù)據(jù)庫有效聚類分析尋找適當(dāng)?shù)姆椒?、聚類算法對?fù)雜分布數(shù)據(jù)和類別性數(shù)據(jù)聚類的有效性以及高維數(shù)據(jù)聚類技術(shù)等方面。本文通過對聚類分析算法的分析并重點(diǎn)從聚類分析的軟件工具和改進(jìn)的K-means算法兩個方面來論證聚類分析在兒童生長發(fā)育時期中的應(yīng)用。
2聚類算法分析
聚類[6]分析是直接比較各事物之間的性質(zhì),將性質(zhì)相近的歸為一類,將性質(zhì)差別較大的歸入不同的類。在醫(yī)學(xué)實(shí)踐中也經(jīng)常需要做分類工作,如根據(jù)病人的一系列癥狀、體征和生化檢查的結(jié)果,判斷病人所患疾病的類型;或?qū)σ幌盗袡z查方法及其結(jié)果,將之劃分成某幾種方法適合用于甲類病的檢查,另幾種方法適合用于乙類病的檢查,等等。聚類分析被廣泛研究了許多年?;诰垲惙治龅墓ぞ咭呀?jīng)被加入到許多統(tǒng)計分析軟件包或系統(tǒng)中,如S-Plus、SPSS,以及SAS。
大體上,聚類算法[7]可以劃分為如下幾類:
(2)層次方法。該方法就是通過分解所給定的數(shù)據(jù)對象集來創(chuàng)建一個層次。它存在的缺陷就是在進(jìn)行(組)分解或合并之后無法回溯。將循環(huán)再定位與層次方法結(jié)合起來使用常常是有效的,如BIRCH和CURE,就是基于這種組合方法設(shè)計的。
(3)基于密度的方法。只要臨近區(qū)域的密度(對象或數(shù)據(jù)點(diǎn)的數(shù)目)超過某個閾值,就繼續(xù)聚類。DBSCAN是一個有代表性的基于密度的方法。它根據(jù)一個密度閾值來控制簇的增長。
(4)基于網(wǎng)格的方法?;诰W(wǎng)格方法將對象空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)。其主要優(yōu)點(diǎn)是它的處理速度很快,其處理時間獨(dú)立于數(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ū)垲愃惴ㄌ岢隽烁髯蕴厥獾囊?表1可以給聚類算法的研究和應(yīng)用提供參考[7]。
3兒童生長發(fā)育的分析
聚類分析在數(shù)據(jù)挖掘中的應(yīng)用主要有以下三個方面:
(1)聚類分析能作為一個獨(dú)立的工具來獲得數(shù)據(jù)的分布情況,觀察每個簇的特點(diǎn),集中對特定的某些簇作進(jìn)一步的分析。如:①聚類分析軟件v1.2。此軟件主要用于血型、蛋白質(zhì)多態(tài)、品種聚類等方面的統(tǒng)計分析,可自動進(jìn)行雜合度、多態(tài)信息含量、遺傳距離以及聚類的計算,并可自動畫出聚類圖。②SPSS統(tǒng)計軟件。SPSS軟件是一種專業(yè)的統(tǒng)計分析軟件,用于數(shù)據(jù)的各種分析,從而最終為企、事業(yè)的科學(xué)決策服務(wù)。其中采用聚類分析是理想的多變量統(tǒng)計技術(shù),主要有分層聚類法和迭代聚類法。
本文通過一組兒童生長發(fā)育的數(shù)據(jù)運(yùn)用SPSS工具進(jìn)行分析,如表2所示。
運(yùn)用SPSS工具調(diào)用K-meansCluster過程可完成由用戶指定類別數(shù)的大樣本資料的逐步聚類分析。逐步聚類分析就是先把被聚對象進(jìn)行初始分類,然后逐步調(diào)整,得到最終分類。
為研究兒童生長發(fā)育的分期,筆者對1253名1月~7歲兒童進(jìn)行了抽樣調(diào)查,分別對兒童的身高(cm)、體重(kg)、胸圍(cm)和坐高(cm)進(jìn)行了測量。資料作如下整理:先把1月~7歲劃成19個月份段,分月份算出各指標(biāo)的平均值,將第1月的各指標(biāo)平均值與出生時的各指標(biāo)平均值比較,求出月平均增長率(%),然后第2月起的各月份指標(biāo)平均值均與前一月比較,求出月平均增長率(%)(表2)。將兒童生長發(fā)育時期分為四期,所以聚類的類別數(shù)為4,從而確定四個兒童生長發(fā)育期的起止區(qū)間。
①激活數(shù)據(jù)管理窗口,定義變量名。雖然月份分組不做分析變量,但為了更直觀地了解聚類結(jié)果,也將之輸入數(shù)據(jù)庫。
②進(jìn)行統(tǒng)計分析,在聚類方法上選擇Iterateandclassify指定初始類別中心點(diǎn),按K-means算法作迭代分類。對聚類結(jié)果進(jìn)行方差分析。
結(jié)果解釋:首先系統(tǒng)根據(jù)用戶的指定,按四類聚合確定初始聚類的各變量中心點(diǎn),未經(jīng)K-means算法迭代,其類別間距離并非最優(yōu);經(jīng)迭代運(yùn)算后類別間各變量中心值得到修正。
③對聚類結(jié)果的類別間距離進(jìn)行方差分析。方差分析表明,類別間距離差異的概率值均小于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)運(yùn)用聚類分析軟件可以很方便地對數(shù)據(jù)進(jìn)行分析,利用分析的結(jié)果,在孩子生長發(fā)育時期合理安排好飲食,促進(jìn)兒童健康快樂成長。同時,聚類分析可以作為其他算法(如特征和分類等)的預(yù)處理步驟,這些算法再在生成的簇上進(jìn)行處理。本文以改進(jìn)的K-means算法[9]為例來說明兒童生長發(fā)育時期的特征。算法描述如下:
算法:K-means。劃分的K-means算法基于簇中對象的平均值。
輸入:簇的數(shù)目k=4和輸入n=19的表2的數(shù)據(jù)。
輸出:四個簇,使平方誤差準(zhǔn)則最小。
方法:
①任意選擇四個對象作為初始簇的中心;
②repeat;
③根據(jù)簇中對象的平均值,將每個對象(重新)賦給最類似的簇;
本文原文
④更新簇的平均值,即計算每個簇中對象的平均值;
⑤until不再發(fā)生變化。
在本算法中要用到以下幾個定義:
(3)聚類分析也可以進(jìn)行孤立點(diǎn)的分析。經(jīng)常存在一些數(shù)據(jù)對象,它們不符合數(shù)據(jù)的一般模型,這些數(shù)據(jù)對象被稱為孤立點(diǎn)。孤立點(diǎn)的分析有著廣泛的應(yīng)用[12,13],如欺詐檢測即探詢不尋常的信用卡使用或電信服務(wù);此外,它在市場分析中可用于確定極低或極高收入的客戶的消費(fèi)行為、或者在醫(yī)療分析中用于發(fā)現(xiàn)對多種治療方式的不尋常的反應(yīng)。
4結(jié)束語
本文通過改進(jìn)的K-means算法和聚類分析工具SPSS來對兒童生長發(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)域一個非?;钴S的研究課題。用戶當(dāng)然希望聚類的結(jié)果是可解釋的、可理解的和可應(yīng)用的。如何選擇聚類方法和正確地使用聚類算法也是很重要的,而目前所使用的聚類算法均存在某方面的缺陷,也沒有統(tǒng)一的標(biāo)準(zhǔn),因此如何使聚類算法成為像SQL語言那樣統(tǒng)一、標(biāo)準(zhǔn)的語言,還有待于計算機(jī)工作者的努力。
參考文獻(xià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]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)計[M].北京:科學(xué)出版社,2002:3-120.
[9]WISHARTD.K-meansclusteringwithoutlierdetection:the25thAnnualConferenceoftheGermanClassificationSociety[C].Munich:UniversityofMunich,2001:14-16.
[10]左子葉,朱揚(yáng)勇.基于數(shù)據(jù)挖掘聚類技術(shù)的信用評分評級[J].計算機(jī)應(yīng)用與軟件,2004,21(4):1-3,101.
[11]何彬彬,方濤,郭達(dá)志.基于不確定性的空間聚類[J].計算機(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].計算機(jī)系統(tǒng)應(yīng)用,1998(4):20-24.