張 強(qiáng)

(安徽商貿(mào)職業(yè)技術(shù)學(xué)院，宿州 241002)

?

一種新的動(dòng)態(tài)聚類算法在高職就業(yè)分析中的應(yīng)用研究

張 強(qiáng)

(安徽商貿(mào)職業(yè)技術(shù)學(xué)院，宿州 241002)

為解決常用于就業(yè)數(shù)據(jù)信息分析的 K-means算法中初始化聚類中心敏感和容易陷入局部最優(yōu)值問題，提出了一種新的動(dòng)態(tài)聚類算法.該算法首先利用最近鄰聚類法獲得初始聚類中心，然后利用小類對(duì)合并條件進(jìn)行聚類合并，從而獲得更優(yōu)的聚類結(jié)果.以多個(gè)高職院校近幾年的就業(yè)數(shù)據(jù)為樣本信息，在數(shù)據(jù)預(yù)處理的基礎(chǔ)上，運(yùn)用提出的聚類方法進(jìn)行了聚類實(shí)驗(yàn)分析，并挖掘出與就業(yè)質(zhì)量相關(guān)的因素.最后的實(shí)驗(yàn)結(jié)果表明，文中提出的聚類方法聚類劃分效果更優(yōu).

數(shù)據(jù)挖掘；聚類；就業(yè)數(shù)據(jù)分析

0 引 言

當(dāng)前高職院校畢業(yè)生就業(yè)問題日益突出，同時(shí)就業(yè)質(zhì)量的好壞也成為社會(huì)普遍關(guān)注的問題[1]，如何更好的指導(dǎo)學(xué)生應(yīng)業(yè)，從海量的就業(yè)數(shù)據(jù)信息中挖掘出與就業(yè)有關(guān)的因素和潛在的聯(lián)系，是目前研究的熱點(diǎn)之一[2].本文針對(duì)K-means算法在聚類過程中出現(xiàn)初始化聚類中心敏感和容易陷入局部最優(yōu)值問題，提出了一種新的動(dòng)態(tài)聚類算法，抽取合肥地區(qū)幾所高職院校的就業(yè)數(shù)據(jù)信息為樣本數(shù)據(jù)，運(yùn)用提出的聚類算法進(jìn)行聚類分析，首先采用最近鄰聚類法生成初始聚類集[3]，然后采用合并條件對(duì)滿足合并要求的小類對(duì)進(jìn)行合并優(yōu)化[4]，從而獲得更優(yōu)的聚類結(jié)果.

1 動(dòng)態(tài)聚類算法

確定聚類的個(gè)數(shù)和相應(yīng)的聚類，是聚類分析要解決的兩個(gè)主要問題，而大多數(shù)研究卻只關(guān)注第二個(gè)問題，就是在已給定聚類個(gè)數(shù)的情況下進(jìn)行聚類.但事實(shí)上，對(duì)于很多數(shù)據(jù)，我們無法事先確定聚類的個(gè)數(shù).為解決聚類中最優(yōu)解的問題，在綜合考慮聚類算法的效率及性能的基礎(chǔ)上，本文提出了一種新的動(dòng)態(tài)聚類方法，該方法分為兩個(gè)階段：

(1)近鄰聚類階段：采用最近鄰聚類算法進(jìn)行初步聚類，并根據(jù)相異性和相似性度量過濾掉聚類中的異常類，構(gòu)建初始的聚類集.

(2)合并優(yōu)化階段：利用動(dòng)態(tài)的聚類評(píng)估函數(shù)，進(jìn)行聚類劃分，從而獲得接近最優(yōu)的聚類結(jié)果.

1.1 近鄰聚類

最近鄰聚類算法的思想是如果兩個(gè)距離最近的樣本直接的距離小于設(shè)定的閾值d,就可認(rèn)為它們屬于同一類.該算法是在數(shù)據(jù)相似度矩陣上進(jìn)行聚類的，采用歐幾里德距離作為樣本相似度的測(cè)試指標(biāo).樣本xi和xj的相似度計(jì)算公式為：

(1)

算法的具體聚類步驟如下：

(1)選取未聚類的任意一個(gè)樣本作為x1第一個(gè)聚類C1的聚類中心，C1=x1，設(shè)定相似度閾值為d1.

(2)取下一個(gè)樣本x2，計(jì)算x2到x1的距離d21：若d21<=d1，則x2∈C1聚類；否則將x2作為新類C2的聚類中心，C2=x2，設(shè)定相似度閾值為d2.

(3)設(shè)存在K個(gè)聚類C1至Ck，繼續(xù)取樣本xi，分別計(jì)算xi與K個(gè)聚類中心的相似度，若xi與聚類Cj的聚類中心的相似度dij

(4)重復(fù)執(zhí)行步驟3，直至所有的樣本分類完畢，獲得初始聚類集C.

1.2 聚類合并優(yōu)化

由于最近鄰聚類算法在聚類中會(huì)產(chǎn)生很多子類，需要進(jìn)行適當(dāng)?shù)暮喜?yōu)化，才能獲得滿意的聚類效果.事實(shí)上，任何一個(gè)類或者延伸形狀的類族可以用多個(gè)中心表示，為此我們提出了小類合并算法，該算法采用內(nèi)聚力為合并條件[5].為更好的描述聚類合并的過程，首先引入幾個(gè)定義：

定義1：類Ci中的一個(gè)樣本xi與另一個(gè)類Cj的粘合能力為con(xi,Cj)：

(2)

(3)

基于內(nèi)聚力的小類合并算法步驟如下：

(1)輸入初始聚類集C=C={C1，C2，…CN}；

(2)計(jì)算所有子類之間的內(nèi)聚力coh(Ci,Cj)和所有類間內(nèi)聚力平均值coh*，并將作為合并條件，若coh(Ci,Cj)

(3)對(duì)所有小類對(duì)進(jìn)行判斷，根據(jù)評(píng)估函數(shù)看它們是否滿足合并要求；

(4)將所有滿足合并要求的小類對(duì)進(jìn)行篩選，并組成一個(gè)隊(duì)列；

(5)從隊(duì)列中選擇出對(duì)頭，如果隊(duì)列為空，則轉(zhuǎn)步驟(7)；

(6)根據(jù)合并條件判斷對(duì)頭這兩個(gè)小類是否可以合并，轉(zhuǎn)步驟(5)；

(7)合并聚類結(jié)束.

2 動(dòng)態(tài)聚類在高職就業(yè)分析中的應(yīng)用

將動(dòng)態(tài)聚類算法運(yùn)用于高職學(xué)生就業(yè)信息數(shù)據(jù)庫，對(duì)相關(guān)的就業(yè)數(shù)據(jù)進(jìn)行聚類分析，挖掘出一些有用的信息，使得高職院校在就業(yè)宣傳，就業(yè)規(guī)劃設(shè)計(jì)及專業(yè)設(shè)置等方面提供決策依據(jù)，從而實(shí)現(xiàn)使得畢業(yè)生能夠更快更好的就業(yè).

2.1 數(shù)據(jù)采集

本研究中，收集了合肥地區(qū)3所高校學(xué)生就業(yè)信息數(shù)據(jù)庫中的近3年的畢業(yè)生就業(yè)信息，就業(yè)數(shù)據(jù)真實(shí)可靠，且數(shù)據(jù)來自于不同高校，因此具有實(shí)用性和廣泛性.就業(yè)信息從大的方向來分，可分為個(gè)人基本信息、教育信息、就業(yè)信息和就業(yè)質(zhì)量四個(gè)部分，而不同數(shù)據(jù)部分中的數(shù)據(jù)屬性可能會(huì)出現(xiàn)重復(fù)或者與聚類分析無關(guān)，因此要對(duì)采集到的數(shù)據(jù)信息進(jìn)行處理.

2.2 數(shù)據(jù)預(yù)處理

聚類前是否有效的對(duì)數(shù)據(jù)進(jìn)行預(yù)處理將影響挖掘的效果與質(zhì)量，因此在進(jìn)行數(shù)據(jù)聚類挖掘之前要進(jìn)行必要的數(shù)據(jù)預(yù)處理，文中的處理過程主要有以下幾步：

(1)數(shù)據(jù)清洗.對(duì)就業(yè)信息數(shù)據(jù)庫中無效的數(shù)據(jù)記錄進(jìn)行刪除，而對(duì)遺漏數(shù)據(jù)的處理主要是通過忽略該條數(shù)據(jù)記錄、均值填補(bǔ)、缺省值填補(bǔ)等方法進(jìn)行處理.

(2)抽取數(shù)據(jù)屬性.從四部分?jǐn)?shù)據(jù)信息中抽取出與就業(yè)有關(guān)的屬性，如性別、專業(yè)課成績(jī)、外語等級(jí)、計(jì)算機(jī)等級(jí)、技能等級(jí)、課外兼職經(jīng)歷、是否黨員、就業(yè)單位、工資情況等屬性.由于屬性間存在聯(lián)系或者將多個(gè)屬性相結(jié)合也能反映就業(yè)情況，如可以講工作環(huán)境、工資滿意度及有無發(fā)展前景等屬性合并，生成就業(yè)質(zhì)量屬性.

(3)數(shù)據(jù)轉(zhuǎn)換.由于屬性數(shù)據(jù)取值范圍不固定，因此要對(duì)屬性進(jìn)行離散化處理，并采用加權(quán)法進(jìn)行歸一化處理.如專業(yè)課成績(jī)是由各個(gè)學(xué)期所學(xué)的不同專業(yè)課程成績(jī)組成，數(shù)據(jù)量較大，因此要進(jìn)行綜合處理，把各專業(yè)成績(jī)進(jìn)行加權(quán)匯總或求平均和，然后根據(jù)加權(quán)值把專業(yè)課成績(jī)分為四級(jí)：優(yōu)、良、較好、差.

考慮到數(shù)據(jù)運(yùn)算過程的運(yùn)算量，文中僅選擇了與就業(yè)相關(guān)的8個(gè)屬性，如表1所示.

表1 就業(yè)數(shù)據(jù)屬性項(xiàng)

2.3 數(shù)據(jù)聚類分析

為了檢測(cè)本文提出的動(dòng)態(tài)聚類算法的有效性，從就業(yè)數(shù)據(jù)信息庫中隨機(jī)抽取出15條記錄，并進(jìn)行了歸一化處理，作為聚類用的測(cè)試樣本數(shù)據(jù)，如表2所示.

表2 處理后的就業(yè)樣本數(shù)據(jù)

采用本文提出的動(dòng)態(tài)聚類算法，進(jìn)行第一階段的最近鄰聚類分析，獲得6個(gè)聚類結(jié)果作為初始聚類集C：

C={{1,4,7},{8,12},{3,5,6,9,13},{15},{2,10},{11,14}}

在第二階段，采用內(nèi)聚力為合并條件將小類對(duì)進(jìn)行合并，獲得4個(gè)聚類結(jié)果作為最終的聚類集：

C={{1,4,7,8,12},{3,5,6,9,13},{15},{2,10,11,14}}

根據(jù)歐式距離公式，計(jì)算各聚類間的距離如表3所示.

表3 各聚類間的距離

由表3可知4個(gè)聚類間的距離很大，而各個(gè)聚類內(nèi)部樣本數(shù)據(jù)間的距離很小，實(shí)現(xiàn)了樣本數(shù)據(jù)在不同聚類間的差異和同一聚類之間的相似.

從第一類{1,4,7,8,12}聚類結(jié)果可以看出，該組樣本數(shù)據(jù)的就業(yè)質(zhì)量偏低，其特點(diǎn)是樣本數(shù)據(jù)都是女生，專業(yè)成績(jī)一般，很少是學(xué)生干部且就業(yè)和所學(xué)專業(yè)幾乎不相關(guān).

從第二類{3,5,6,9,13}聚類結(jié)果可以看出，該組樣本數(shù)據(jù)就業(yè)質(zhì)量較好，其特點(diǎn)是樣本數(shù)據(jù)大部分是女生，學(xué)生干部居多且都有兼職經(jīng)歷，而綜合能力一般，就業(yè)和所學(xué)專有一定相關(guān)性.

而第三類{15}聚類結(jié)果從表3可以看出，該類與其他幾個(gè)類的距離都很大且只有一個(gè)樣本數(shù)據(jù)，因此可將該類判定為異類.

從第四類{2,10,11,14}聚類結(jié)果可以看出，該組樣本數(shù)據(jù)的就業(yè)質(zhì)量是最高的一類，其特點(diǎn)是樣本數(shù)據(jù)都是男生，綜合能力強(qiáng)，大部分都擔(dān)任過學(xué)生干部且有兼職經(jīng)歷，就業(yè)和所學(xué)專業(yè)幾乎對(duì)口或具有相關(guān)性.

2.4 聚類效果分析

為驗(yàn)證本文提出的動(dòng)態(tài)聚類算法的聚類效果，采用相同的數(shù)據(jù)集，將文中提出的聚類算法和經(jīng)典的k均值算法在聚類精度方面進(jìn)行了對(duì)比，結(jié)果如圖1所示.

圖1 聚類精度比較

從圖1可以看出，本文算法在聚類準(zhǔn)確度上優(yōu)于K均值聚類法，且在數(shù)據(jù)量較大時(shí)聚類個(gè)數(shù)為7個(gè)的時(shí)候，準(zhǔn)確度最高.

3 小 結(jié)

以高職院校畢業(yè)生數(shù)據(jù)信息為研究對(duì)象，提出了一種動(dòng)態(tài)的聚類算法，對(duì)相關(guān)的就業(yè)數(shù)據(jù)進(jìn)行聚類分析.研究目的是，通過挖掘出的一些有用信息，為高職院校在教育改革及就業(yè)工作提供依據(jù)和參考，從而實(shí)現(xiàn)畢業(yè)生能夠更快更好的就業(yè).

[1] 賈瑞玉.數(shù)據(jù)挖掘技術(shù)在高職就業(yè)分析中的應(yīng)用研究[D].安徽大學(xué),2010:8-13.

[2] 楊斷利,張 銳,王文顯.基于模糊決策樹的高校就業(yè)數(shù)據(jù)挖掘研究[J]. 河北農(nóng)業(yè)大學(xué)學(xué)報(bào),2012,35(2): 111-114.

[3] 基于FCM的類合并聚類算法研究[D].重慶大學(xué)碩士論文,2009:30-35.

[4] 林有城,等.基于多類合并的Pso_means聚類算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,18(2):160-166.

[5] 孫 昱,魯漢榕. 一種基于內(nèi)聚力的自合并聚類算法[J].空軍雷達(dá)學(xué)院學(xué)報(bào),2004,18(4),57-59.

A New Dynamic Clustering Algorithm for Analyzing Employment Data of Vocational College

ZHANG Qiang

(Anhui Business College,Suzhou 241002, China)

K-means algorithm for analyzing the employment data of vocational college is unable to solve the problems of the sensitivity of initialization and premature convergence. This paper proposes a new dynamic clustering algorithm. Firstly,the algorithm selects the initial cluster center by the nearest neighbor algorithm, and then carries out cluster merging based on merging condition to obtain the best clustering results. Taking the recent graduates of higher vocational colleges of education information and employment information data as the research object, on the basis of data pretreatment,and using the proposed dynamic clustering algorithm for the analysis of the sample data,the factors related to the quality of employment are found. The experimental results show that the algorithm present in this paper has a better cluster category effect.

data mining: clustering: employment data analysis

2014-11-06

安徽高校省級(jí)自然科學(xué)研究項(xiàng)目(kj2013z090).

張 強(qiáng)(1982- )，男，碩士，講師，研究方向：計(jì)算機(jī)應(yīng)用技術(shù).

TP391

A

1671-119X(2015)02-0047-04