張 強(qiáng)

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

?

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

張 強(qiáng)

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

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

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

0 引 言

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

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

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

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

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

1.1 近鄰聚類(lèi)

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

(1)

算法的具體聚類(lèi)步驟如下：

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

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

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

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

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

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

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

(2)

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 各聚類(lèi)間的距離

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

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

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

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

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

2.4 聚類(lèi)效果分析

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

圖1 聚類(lèi)精度比較

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

3 小 結(jié)

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

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

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

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

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

[5] 孫 昱,魯漢榕. 一種基于內(nèi)聚力的自合并聚類(lè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