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

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

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

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

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

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

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

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

8、（最大化）所有對象與其參照點之間的相似度之和的原則來執(zhí)行的，適用于類數(shù)固定，偏好球形的聚類3。3三種聚類分析方法在公司職員評定中的分析比較應該三種方法對對公司年終員工進行考核（限于篇幅僅以9名員工，4個指標為例），把客戶評價指標量化，根據(jù)考核要求用4級評分制，優(yōu)對應5分，良對應4分，一般對應3分，差對應2分?？己藘?nèi)容及規(guī)范化數(shù)據(jù)后見表1。表1員工考核表及規(guī)范化員客戶數(shù)產(chǎn)品數(shù)其它工作數(shù)客戶評價工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三種聚類算法的運算結(jié)果3.1.1Q型模糊聚類結(jié)果：由表一規(guī)范化后的數(shù)據(jù)，本文按絕對值減數(shù)法根據(jù)(2)式計算相似系數(shù)，取c=0.3。rij將表中數(shù)據(jù)代入公式，可以得到模糊相似矩陣,然后用最大樹法聚類，做出最大樹如圖1：圖1最大樹法聚類根據(jù)模糊統(tǒng)計量的計算以及經(jīng)驗判斷結(jié)果見下表，表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時，用F統(tǒng)計量檢驗，測得F=5.531F(3,5)G=0.05),且根據(jù)實際情況a分為四類正好符合需要的評測分類數(shù)，無需再進行九=0.85時的F統(tǒng)計量檢驗。3.1.2k-means和k-medians聚類結(jié)果依題取k=4,則聚類結(jié)果如下(由于篇幅計算過程省略)：表3k-means和k-medians聚類過程 第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é)束，可見通過迭代運算，K-medians聚類算法在迭代步數(shù)上少于K-means聚類算法。3.2.算法比較分析由上表7可知，K-medians聚類算法在迭代速度上優(yōu)于K-means聚類算法，且K-medians聚類算法和Q型聚類算法對該數(shù)據(jù)處理的聚類結(jié)果相同，但是K-means聚類算法

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

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

14、25謝季堅，劉承平模糊數(shù)學方法及其應用M武漢：華中科技大學出版社，2000：96葉苗群，基于混合K中心點的Web客戶聚類，嘉興學院學報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