三種典型聚類算法在職員評(píng)定中的應(yīng)用(已發(fā)表)

1、i 三種典型聚類算法在職員評(píng)定中的應(yīng)用摘要：通過(guò)利用三種典型算法：Q型模糊聚類算法、K-Means算法及K-medians算法，對(duì)公司職員的年終評(píng)定進(jìn)行應(yīng)用分析，得到了不同的聚類結(jié)果，通過(guò)對(duì)結(jié)果的分析比較、探討，得出針對(duì)不同問(wèn)題，應(yīng)結(jié)合實(shí)際，有針對(duì)性地用不同算法更適合。并在此基礎(chǔ)上，對(duì)聚類算法的聚類過(guò)程、本文后續(xù)工作進(jìn)行了探討總結(jié)。關(guān)鍵詞：數(shù)據(jù)挖掘，聚類分析，Q-型模糊聚類，K-means算法，K-medians算法中圖分類號(hào)：。235文獻(xiàn)標(biāo)識(shí)碼：A1前言隨著信息化進(jìn)程的發(fā)展，如何借助計(jì)算機(jī)的強(qiáng)大處理功能，從海量的繁雜數(shù)據(jù)中發(fā)現(xiàn)對(duì)我們有意義的信息并指導(dǎo)我們對(duì)研究工作做出更為準(zhǔn)確、有效的預(yù)測(cè)和決

2、策，這正是數(shù)據(jù)挖掘技術(shù)需要解決的問(wèn)題。其中，聚類分析就是依據(jù)數(shù)據(jù)對(duì)象之間的關(guān)系及特點(diǎn)，使得同一組內(nèi)的對(duì)象具有較大的相似性，不同組中的對(duì)象具有較高的相異性1，解決大量數(shù)據(jù)間的某種分類關(guān)系問(wèn)題的一種重要方法。2三種典型聚類算法聚類算法有多種，本文選取三種主要的分類算法，從中探討它們的異同，得出相關(guān)主要結(jié)論。Q-型模糊聚類算法聚類分析根據(jù)分類對(duì)象的不同分為R型和Q型兩大類，R型是對(duì)變量指標(biāo)進(jìn)行分類處理，Q型是對(duì)樣品進(jìn)行分類處理，以下簡(jiǎn)單對(duì)Q型聚類進(jìn)行闡述。建立模糊關(guān)系X中的元素x.與x的接近程度，稱為相似系數(shù)r(其中r0,1)。相似系數(shù)r構(gòu)成的ijijijij模糊矩陣(r)是X上的模糊關(guān)系。其中確定

3、相似系數(shù)r的方法很多。ijnxnij在實(shí)際的聚類問(wèn)題中，先通過(guò)數(shù)據(jù)標(biāo)準(zhǔn)化后，通過(guò)建立X上的模糊關(guān)系或模糊相似關(guān)系，以模糊相似矩陣為基礎(chǔ)來(lái)討論分類問(wèn)題，然后用最大樹(shù)法進(jìn)行分類，根據(jù)閥值即可得出聚類結(jié)果。結(jié)果評(píng)價(jià)準(zhǔn)則為了評(píng)價(jià)聚類結(jié)果的好壞，需要定義準(zhǔn)則函數(shù)，聚類問(wèn)題轉(zhuǎn)化為使準(zhǔn)則函數(shù)取極值的優(yōu)化問(wèn)題。一般的聚類分析要解決兩個(gè)問(wèn)題，一個(gè)是如何確定類的個(gè)數(shù)，即把n個(gè)樣本聚成多少類才合適，另一個(gè)是在給定類的個(gè)數(shù)c的情況下，如何把n個(gè)樣本聚成c個(gè)類。針對(duì)第一種問(wèn)題，在模糊聚類分析中，對(duì)于不同的九(0,11,可以得到不同的分類，從而形成動(dòng)態(tài)模糊聚類圖。但許多實(shí)際問(wèn)題中如何根據(jù)九的值來(lái)確定樣本的具體分類。常用的

4、兩種方法有2：(1)按照實(shí)際需要，由專家結(jié)合專業(yè)知識(shí)來(lái)確定值九，得出在水平上的等價(jià)分類。(2)用F統(tǒng)計(jì)量確定最佳值九。設(shè)論域U=x,xx為樣本空間(樣本總數(shù)為n),而每個(gè)樣本x.由m個(gè)特征(即12ni由試驗(yàn)或觀察得到的m個(gè)數(shù)據(jù))：x=(x,xx)(i=1,2,.n)。得到原始數(shù)據(jù)矩陣，其ii1i2im中x=1x(k=1,2,.,m).x稱為總體樣本的中心向量。kniki=1設(shè)對(duì)應(yīng)于九值的分類數(shù)為r,第j類的樣本數(shù)為n.，第j類的樣本記為：x(j),x(j),.x(j),j12nj第j類的聚類中心為向量x(j)=(x(j),x(,),x(j)，其中x(j)為第k個(gè)特征的平均值：12mkn.x(j

5、)=+x(j)(k=1,2,m)knikji=1作F統(tǒng)計(jì)量其中|x(j)-x=理(x(j)-x)2為類與類之間的距離kkHk=1，卜(j)-x(j)為類內(nèi)樣本間的距離。(1)(1)式遵從自由度為(r1，nr)的F分布。因此，F(xiàn)值越大，說(shuō)明類與類之間的距離越大，表明類與類之間的差異越大，分類就越好。如果FF(r-1,n-r)G=0.05),則根據(jù)數(shù)理統(tǒng)計(jì)分析理論知道類與類之間差異是顯a著的，說(shuō)明分類比較合理，如果滿足不等式FF(r-1,n-r)(a=0.05)的F值不止一個(gè)，a則可以進(jìn)一步考查差(F-F)的大小，從較大者中找一個(gè)滿意的F值就行了，即就圓滿a的解決了存在的第一個(gè)問(wèn)題。k-means

6、聚類算法K-means即K均值聚類算法。該算法根據(jù)聚類中心的均值進(jìn)行分類劃分，其處理過(guò)程如下：首先，隨機(jī)選擇k個(gè)對(duì)象，初始代表一個(gè)類的中心值。其次，對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與類中心的距離，將它賦予最近的類，然后重新計(jì)算每個(gè)類的平均值。這個(gè)過(guò)程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。通常，采用平方誤差準(zhǔn)則，其定義如下：=工|p-m|2zp mpuCii_ICTi其中，E表示所有聚類對(duì)象的平方誤差的和，p是聚類對(duì)象，m是類C的各聚類對(duì)象ii的平均值，C表示類C的聚類對(duì)象的數(shù)目。ii由于該方法對(duì)初值敏感，不同的初值、種子點(diǎn)、聚類個(gè)數(shù)K、初始劃分等都可能會(huì)導(dǎo)致不同的聚類結(jié)果，此外，均值體現(xiàn)的是數(shù)據(jù)集的整體特征，而

7、掩蓋了數(shù)據(jù)本身的特性，由于目標(biāo)函數(shù)局部極小值點(diǎn)的存在，該算法可能會(huì)陷入局部最優(yōu),無(wú)法達(dá)到全局最優(yōu)，因此應(yīng)用范圍有一定的局限性。K-medians聚類算法K-medians方法的基本策略是通過(guò)避免孤立點(diǎn)，而選擇類中最中心的對(duì)象作為參照點(diǎn)，然后計(jì)算其它點(diǎn)與這些參照點(diǎn)的距離，再按照距離重新聚類，分配給最近的一個(gè)簇，直到數(shù)據(jù)點(diǎn)不再改變所屬的類為止,以此改進(jìn)聚類的質(zhì)量。聚類結(jié)果的質(zhì)量用一個(gè)代價(jià)函數(shù)來(lái)估算，該函數(shù)可以度量對(duì)象與其參照對(duì)象之間的平均相似度。與K均值方法比較,這種劃分方法,不采用簇中對(duì)象的平均值來(lái)作為參照點(diǎn),而是找出簇中位置最中心的對(duì)象，即中心點(diǎn)來(lái)代表簇，然后通過(guò)分組排序。該方法也是基于最小化

8、（最大化）所有對(duì)象與其參照點(diǎn)之間的相似度之和的原則來(lái)執(zhí)行的，適用于類數(shù)固定，偏好球形的聚類3。3三種聚類分析方法在公司職員評(píng)定中的分析比較應(yīng)該三種方法對(duì)對(duì)公司年終員工進(jìn)行考核（限于篇幅僅以9名員工，4個(gè)指標(biāo)為例），把客戶評(píng)價(jià)指標(biāo)量化，根據(jù)考核要求用4級(jí)評(píng)分制，優(yōu)對(duì)應(yīng)5分，良對(duì)應(yīng)4分，一般對(duì)應(yīng)3分，差對(duì)應(yīng)2分。考核內(nèi)容及規(guī)范化數(shù)據(jù)后見(jiàn)表1。表1員工考核表及規(guī)范化員客戶數(shù)產(chǎn)品數(shù)其它工作數(shù)客戶評(píng)價(jià)工A3000.6253003003良0.67B3601900.4300優(yōu)1C2800600.2100良0.67D2200.125800.361001良0.67E3000.625500.1400般0.33F3

9、200.75700.29100.1優(yōu)1G20001701200.2優(yōu)0(2)迭代次數(shù)K-means聚類算法K-medians聚類算法 H3000.625400.0700.3差0.33I.上60Q3751200.64100.1良0.673.1三種聚類算法的運(yùn)算結(jié)果3.1.1Q型模糊聚類結(jié)果：由表一規(guī)范化后的數(shù)據(jù)，本文按絕對(duì)值減數(shù)法根據(jù)(2)式計(jì)算相似系數(shù)，取c=0.3。rij將表中數(shù)據(jù)代入公式，可以得到模糊相似矩陣,然后用最大樹(shù)法聚類，做出最大樹(shù)如圖1：圖1最大樹(shù)法聚類根據(jù)模糊統(tǒng)計(jì)量的計(jì)算以及經(jīng)驗(yàn)判斷結(jié)果見(jiàn)下表，表2Q型模糊聚類結(jié)果九I類II類III類IVV類類0.8A，C，E，H，IDGB，F(xiàn)

10、0.85A，CDGB，F(xiàn)E，HI在九=0.8時(shí)，用F統(tǒng)計(jì)量檢驗(yàn)，測(cè)得F=5.531F(3,5)G=0.05),且根據(jù)實(shí)際情況a分為四類正好符合需要的評(píng)測(cè)分類數(shù)，無(wú)需再進(jìn)行九=0.85時(shí)的F統(tǒng)計(jì)量檢驗(yàn)。3.1.2k-means和k-medians聚類結(jié)果依題取k=4,則聚類結(jié)果如下(由于篇幅計(jì)算過(guò)程省略)：表3k-means和k-medians聚類過(guò)程 第C1=(A,B,C)C1=(A,B,C)0C2=(D,E)C2=(D,E)次C3=(F,G)C3=(F,G)C4=(H,I)C4=(H,I)第C1=(A,E,F,H)C1=(A,C,E,F,H)1C2=(C,D)C2=(D)次C3=(G,I)C

11、3=(G,I)C4=(B)C4=(B)第C1=(A,E,H)C1=(A,C,E,H,I)2C2=(C,D)C2=(D)次C3=(G,I)C3=(G)C4=(B,F)C4=(B,F)第C1=(A,E,H,I)3C2=(C,D)次C3=(G)C=(B,F)k-means在第三次迭代結(jié)束，k-medians在第二次迭代結(jié)束，可見(jiàn)通過(guò)迭代運(yùn)算，K-medians聚類算法在迭代步數(shù)上少于K-means聚類算法。3.2.算法比較分析由上表7可知，K-medians聚類算法在迭代速度上優(yōu)于K-means聚類算法，且K-medians聚類算法和Q型聚類算法對(duì)該數(shù)據(jù)處理的聚類結(jié)果相同，但是K-means聚類算法

12、的聚類結(jié)果和前兩者稍有不同。而K-means聚類算法中存在差異的一項(xiàng)II類：C,D，結(jié)合原始數(shù)據(jù)分析，我們可以知道，C相對(duì)別人來(lái)說(shuō)差異性不是很大，而D是相對(duì)別人在擔(dān)任其它工作方面相當(dāng)突出的，因此有必要將D單獨(dú)列出來(lái)，而將C歸入相似的一類I類。進(jìn)一步分析發(fā)現(xiàn)，K-medians聚類算法和Q型聚類分析算法的聚類結(jié)果中反觀他們的工作業(yè)績(jī)，I類員工為工作水平及客戶評(píng)價(jià)都很好的員工，11類員工為各個(gè)方面一般的員工，111類為擔(dān)任其他工作量較多者，W類為研發(fā)新產(chǎn)品突出的員工，可知以上分析，符合實(shí)際情況。4結(jié)束語(yǔ)聚類分析是數(shù)據(jù)挖掘中的一個(gè)重要研究方向，本文將其中三種重要的算法用于公司員工年終評(píng)定，并對(duì)不同的

13、聚類結(jié)果進(jìn)行比較和分析，研究不同聚類算法在特定領(lǐng)域中的可行性和效率的優(yōu)略。對(duì)一個(gè)特定的數(shù)據(jù)集，很難選擇一個(gè)最合適的聚類算法進(jìn)行分析。因此，我們有些時(shí)候只能針對(duì)具體問(wèn)題、具體數(shù)據(jù)提出某種方法。隨著研究的深入，針對(duì)海量數(shù)據(jù)，如何構(gòu)造在計(jì)算速度和計(jì)算效果即算法性能方面均優(yōu)于上述的聚類算法也是一個(gè)重要的課題，另外，如何結(jié)合可視化的計(jì)算機(jī)技術(shù)，來(lái)設(shè)計(jì)專業(yè)的應(yīng)用軟件也是一個(gè)新的研究熱點(diǎn)。圖2聚類過(guò)程圖參考文獻(xiàn)JiaweiHan.MichelineKamber.DataminingconceptsandtechniquesMBeijing:BeijingHigherEducationPress，2001：2

14、25謝季堅(jiān)，劉承平模糊數(shù)學(xué)方法及其應(yīng)用M武漢：華中科技大學(xué)出版社，2000：96葉苗群，基于混合K中心點(diǎn)的Web客戶聚類，嘉興學(xué)院學(xué)報(bào)J.2005,17(3)：54Threekindsrepresentativecluster-algorithmapplicationintheclerkappraisingPENGGao-huia,GUANGuo-quanb,HEChun-huac(a.DepartmentofMathematicsandInformationScience,NorthChinaInstituteofWaterConservancyandHydroelectricPower,Z

15、hengzhou450008,China;b.SchoolofInformationEngineeringandComputer,JiangxiAgriculturalUniversity,Nanchang330045,China;c.CollegeofInformationandManagementScience,HenanAgriculturalUniversity,Zhengzhou450002,China)Abstract：bydiscussingthreeimportantclusteralgorithm:Q-type,K-means、K-medians,thenderivesomeconclusionsbyapplyingthemtothestaffyear-end-assessmentinacompany.diversitypro