郭衛(wèi)霞,薛 濤,李 婷
(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710048)
隨著高校智能化、信息化建設(shè)的推進(jìn),大量的學(xué)生信息被存儲(chǔ)在教務(wù)系統(tǒng)中.近年來(lái),越來(lái)越多的高校開始關(guān)注學(xué)生的畢業(yè)流向與學(xué)生成績(jī)之間存在的關(guān)系,希望能夠通過(guò)分析其內(nèi)在關(guān)系建立模型,通過(guò)學(xué)生的成績(jī)預(yù)測(cè)出其可能的畢業(yè)流向.對(duì)于教務(wù)系統(tǒng)中存儲(chǔ)的學(xué)生數(shù)據(jù),雖然這些數(shù)據(jù)具有海量、雜亂、冗余等特點(diǎn),但是分析數(shù)據(jù)之間存在的關(guān)聯(lián)性和相似性[1],對(duì)這些數(shù)據(jù)進(jìn)行清洗、挖掘和分析,可以幫助教務(wù)人員更好地了解學(xué)生未來(lái)可能的畢業(yè)流向,對(duì)學(xué)生進(jìn)行更好的教育引導(dǎo).
目前,已有很多高校在教務(wù)數(shù)據(jù)分析領(lǐng)域做出了一些研究.龍松等[2]針對(duì)已畢業(yè)學(xué)生的在校學(xué)習(xí)成績(jī)和畢業(yè)去向等信息,利用判別分析建立費(fèi)歇爾判別函數(shù),對(duì)即將畢業(yè)的學(xué)生的就業(yè)去向進(jìn)行預(yù)測(cè);林秀科等[3]運(yùn)用決策樹分類算法對(duì)學(xué)生成績(jī)綜合分析,挖掘出對(duì)學(xué)生畢業(yè)產(chǎn)生影響的關(guān)鍵課程;陳甲華[4]通過(guò)分析學(xué)生成績(jī)數(shù)據(jù)運(yùn)用改進(jìn)后的Apriori算法建立了大學(xué)成績(jī)關(guān)聯(lián)規(guī)則分析模型;韓霖[5-6]等研究了影響大學(xué)生就業(yè)的因素,并基于遺傳算法的神經(jīng)網(wǎng)絡(luò)模型建立了數(shù)學(xué)模型.研究教務(wù)數(shù)據(jù)間的內(nèi)在關(guān)系具有重要意義,例如可以通過(guò)對(duì)往屆學(xué)生的學(xué)科成績(jī)和畢業(yè)流向進(jìn)行分析,發(fā)掘之間存在的關(guān)聯(lián),預(yù)測(cè)學(xué)生的畢業(yè)情況,幫助廣大畢業(yè)生更好地實(shí)現(xiàn)就業(yè).
目前大部分高校對(duì)于校務(wù)研究中學(xué)生成績(jī)信息的綜合分析和挖掘還明顯不夠,本文以西安工程大學(xué)2017屆學(xué)生四年的成績(jī)?yōu)橐罁?jù),分析其和畢業(yè)流向之間的關(guān)系.針對(duì)大量的學(xué)生成績(jī)與其畢業(yè)流向的數(shù)據(jù),給出一種基于Hadoop[7-8]的Canopy-K-means并行算法.Canopy-K-means算法解決了傳統(tǒng)K-means算法初始簇中心選擇敏感的問(wèn)題,提高了算法聚類的準(zhǔn)確度,基于MapReduce[9-10]編程模型實(shí)現(xiàn)其并行化,提高算法執(zhí)行效率.
本文采用Hadoop云計(jì)算主/從(Master/Slave)架構(gòu)實(shí)現(xiàn)海量教務(wù)數(shù)據(jù)的存儲(chǔ)和分布式計(jì)算[11],通過(guò)數(shù)據(jù)挖掘算法實(shí)現(xiàn)對(duì)數(shù)據(jù)中潛在的有價(jià)值信息的挖掘分析,發(fā)現(xiàn)數(shù)據(jù)間存在的內(nèi)在關(guān)系并進(jìn)行分析預(yù)測(cè)等,圖1為基于Hadoop的教務(wù)數(shù)據(jù)分析模型架構(gòu).
如圖1所示,數(shù)據(jù)源端將預(yù)處理后的學(xué)生成績(jī)及其畢業(yè)流向數(shù)據(jù)上傳至Master.Master一方面要對(duì)源數(shù)據(jù)進(jìn)行業(yè)務(wù)模型轉(zhuǎn)換和業(yè)務(wù)數(shù)據(jù)抽取,提取有價(jià)值的維度建立數(shù)據(jù)維度模型;另一方面,Master還要對(duì)數(shù)據(jù)進(jìn)行挖掘分析和業(yè)務(wù)趨勢(shì)預(yù)測(cè),建立數(shù)據(jù)挖掘模型.數(shù)據(jù)管理模塊依據(jù)數(shù)據(jù)維度模型將數(shù)據(jù)分塊存儲(chǔ)到各Slave上并記錄其存儲(chǔ)位置,同時(shí)Master還要管理各Slave相應(yīng)任務(wù)的執(zhí)行.
圖 1 基于Hadoop的教務(wù)數(shù)據(jù)分析模型架構(gòu)Fig.1 The architecture of educational data analysis based on Hadoop
主節(jié)點(diǎn)收到分析請(qǐng)求,會(huì)根據(jù)任務(wù)種類的不同選取不同數(shù)據(jù)挖掘算法,Master節(jié)點(diǎn)將維度分解后的任務(wù)分配給各從節(jié)點(diǎn),Slave接收到分配的任務(wù)之后,各節(jié)點(diǎn)從HDFS[12]中讀取數(shù)據(jù)進(jìn)行并行化的子任務(wù)處理,配合主節(jié)點(diǎn)選擇的挖掘算法執(zhí)行數(shù)據(jù)分析任務(wù),從而實(shí)現(xiàn)海量數(shù)據(jù)的分析,快速、高效地獲取數(shù)據(jù)中有價(jià)值的信息.
K-means是一種較為經(jīng)典的基于劃分的聚類挖掘算法[13-14],該算法快速簡(jiǎn)單、易于實(shí)現(xiàn),具有良好的可伸縮性,被廣泛應(yīng)用于文本分類、文本分析[15-16]等領(lǐng)域.
設(shè)數(shù)據(jù)集集合D={x1,x2,…,xn},xi=(xi1,xi2,…,xin),xj=(xj1,xj2,…,xjn),
則樣本xi與樣本xj之間的歐氏距離為
全局誤差函數(shù)(本文選其作為有效性函數(shù))為
式中:E為誤差;k為聚類中心個(gè)數(shù);Si為k個(gè)類中的一個(gè);ui是Si的中心;xj是Si中的任意元素.
傳統(tǒng)K-means算法中,對(duì)于初始簇中心的選擇是隨機(jī)的,這種隨機(jī)性容易在迭代中形成大量冗余,使聚類結(jié)果陷入局部最優(yōu),造成聚類效果不理想等問(wèn)題.為了解決傳統(tǒng)K-means算法對(duì)于初始簇中心選擇的盲目性問(wèn)題,提高聚類質(zhì)量,給出了一種Canopy-K-means改進(jìn)算法.
Canopy-K-means算法的主要思想就是預(yù)先通過(guò)Canopy算法對(duì)原始數(shù)據(jù)集進(jìn)行粗糙聚類,快速得到k個(gè)Canopy中心和k個(gè)可以相互重疊的Canopy,然后將其作為下一步K-means算法的初始聚類中心,對(duì)同一Canopy內(nèi)的數(shù)據(jù)進(jìn)行精確聚類,直到得到穩(wěn)定的簇類中心.Canopy之間的可重疊性能夠達(dá)到消除孤立點(diǎn)的作用,提高算法的容錯(cuò)性;預(yù)先給K-means算法指定初始簇中心,可減少計(jì)算量,加快算法收斂速度,提高聚類結(jié)果的準(zhǔn)確性.
Canopy算法過(guò)程如下:
(1) 設(shè)置2個(gè)區(qū)域半徑t1,t2且滿足t1>t2;
(2) 首先從數(shù)據(jù)集中隨機(jī)選取1個(gè)數(shù)據(jù)點(diǎn)作為Canopy的中心點(diǎn),遍歷整個(gè)數(shù)據(jù)集,將與該中心點(diǎn)之間的距離小于或等于t1的數(shù)據(jù)點(diǎn)歸入此Canopy中;
(3) 若距離小于t2,則把該數(shù)據(jù)點(diǎn)從原始數(shù)據(jù)集中剔除,直到整個(gè)數(shù)據(jù)集為空.
由以上過(guò)程可知,Canopy算法的執(zhí)行效率受最初設(shè)置的2個(gè)區(qū)域半徑t1,t2影響較大,當(dāng)t1過(guò)大時(shí),會(huì)使同1個(gè)數(shù)據(jù)點(diǎn)屬于多個(gè)Canopy,加大了聚類過(guò)程中的計(jì)算開銷;當(dāng)t2過(guò)大時(shí),會(huì)使得最終聚類的個(gè)數(shù)較少,可能會(huì)使整個(gè)聚類過(guò)程陷入局部最優(yōu)[17].
為了避免聚類過(guò)程陷入局部最優(yōu),應(yīng)該將Canopy算法的初始中心點(diǎn)之間的距離設(shè)置得盡可能遠(yuǎn)一些[18].本文采用“最小最大原則”[19]來(lái)改進(jìn)Canopy算法,確定Canopy聚類的初始中心點(diǎn).其基本思想如下:
(1) 首先在數(shù)據(jù)集C={x1,x2,…,xi}中隨機(jī)選擇一個(gè)點(diǎn)作為第1個(gè)中心點(diǎn)xA;
(2) 計(jì)算數(shù)據(jù)集中其余數(shù)據(jù)點(diǎn)到xA的最小距離,從中選取距離最大的點(diǎn)作為第2個(gè)中心點(diǎn)xB;
(3) 繼續(xù)計(jì)算數(shù)據(jù)集中其余數(shù)據(jù)點(diǎn)到xA,xB的最小距離min{d(xi,xj),j=A,B},選取這些最小距離中的最大者max{min[d(xi,xj)],j=A,B}作為第3個(gè)中心點(diǎn)xC.
以此類推,最終所有的Canopy初始中心點(diǎn){xA,xB,…,xK}應(yīng)滿足:
其中min[d(xi,xj)]表示數(shù)據(jù)集中其余各點(diǎn)與已確定的前K-1個(gè)Canopy中心點(diǎn)的最小距離的集合,Distmin(xK)則表示待確定的第K個(gè)Canopy中心點(diǎn)xK距已確定的前K-1個(gè)Canopy中心點(diǎn)的距離應(yīng)為所有最短距離中的最大者.
運(yùn)用“最小最大原則”的方法選取Canopy中心點(diǎn),可以有效避免Canopy參數(shù)t2的設(shè)置[18].根據(jù)上述方法,在MapReduce進(jìn)行數(shù)據(jù)分析時(shí)可歸約為:Canopy粗聚類結(jié)果類別數(shù)少于或超過(guò)類別真實(shí)值時(shí),Distmin(xK)小幅度變化;當(dāng) Canopy粗聚類結(jié)果類別數(shù)接近類別真實(shí)值時(shí),該距離變化幅度較大[18,20].因此,為了確定Canopy中心點(diǎn)的最優(yōu)個(gè)數(shù)以及區(qū)域半徑t1,參照文獻(xiàn)[21]中的邊界識(shí)別思想,引入了表示Dist(xK)變化幅度的深度指標(biāo)Depth(i),其定義為
Depth(i)=|Distmin(i)-Distmin(i-1)|+|Distmin(i+1)-Distmin(i)|.
當(dāng)i達(dá)到最優(yōu)聚類時(shí),Depth(i)取值最大,那么最優(yōu)的初始聚類中心點(diǎn)即為Canopy集合中的前i個(gè)點(diǎn),同時(shí)設(shè)置區(qū)域半徑t1=Distmin(i),從而確保目前聚類中心點(diǎn)最終均能落在Canopy范圍內(nèi).
基于“最小最大原則”改進(jìn)的Canopy算法不僅解決了盲目設(shè)置Canopy參數(shù)t1,t2的問(wèn)題,而且使傳統(tǒng)選取Canopy中心點(diǎn)的問(wèn)題得以改善,以便得到更穩(wěn)定的Canopy聚類中心點(diǎn)集合,為K-means提供有效、精準(zhǔn)的聚類中心,使聚類結(jié)果更加精確.
圖2為Canopy聚類結(jié)果示意圖,實(shí)線圓圈為Canopy算法粗糙聚類后生成的可相互重疊的Canopy,虛線圓圈表示其最終所屬的簇.由圖2可以發(fā)現(xiàn)通過(guò)Canopy算法預(yù)先聚類后,任意2個(gè)不屬于同一個(gè)Canopy的數(shù)據(jù)點(diǎn)最終不可能屬于同一個(gè)簇[22].因此K-means精確聚類時(shí)則不必計(jì)算不處于同一個(gè)Canopy的數(shù)據(jù)點(diǎn)之間的距離.如簇A、C、D都只屬于一個(gè)Canopy,而簇B、E則屬于2個(gè)Canopy.點(diǎn)x、y均被2個(gè)Canopy包括,則在K-means精確聚類時(shí),只需計(jì)算點(diǎn)x、y分別到這2個(gè)包含它們的Canopy中心的距離,即可完成劃分,確定其最終所屬的簇.
圖 2 Canopy聚類結(jié)果示意圖Fig.2 The diagram of Canopy clustering result
在MapReduce編程框架下,Canopy-K-means算法的并行化實(shí)現(xiàn)劃分為若干Job,執(zhí)行流程如圖3所示.
圖 3 Canopy-K-means并行算法的數(shù)據(jù)挖掘執(zhí)行流程Fig.3 Data mining execution process of Canopy-K-means parallel algorithm
Canopy-K-means并行算法的MapReduce計(jì)算步驟如下:
(1) 將存儲(chǔ)在HDFS上的教務(wù)數(shù)據(jù)按行分片處理,并發(fā)送給n個(gè)待執(zhí)行Map任務(wù)的節(jié)點(diǎn);
(2) 每個(gè)Mapper輸入一個(gè)
(3) Reducer接收Mapper的輸出值,將key值相同的Canopy進(jìn)行合并,重新計(jì)算Canopy中心點(diǎn),得到全局的Canopy中心點(diǎn);
(4) 將n個(gè)Canopy分別發(fā)送給n個(gè)Mapper作為分片數(shù)據(jù),將已經(jīng)得到的Canopy中心點(diǎn)作為K-means聚類的初始簇中心,用K-means算法對(duì)每個(gè)Canopy中的數(shù)據(jù)進(jìn)行精確聚類,輸出key為簇編號(hào),value為簇中心點(diǎn);
(5) Combiner接收Mapper的輸出值,將key值相同的簇進(jìn)行合并且輸出給Reducer;
(6) Reducer更新每一個(gè)簇中心,最終得到全局的簇中心,并將教務(wù)數(shù)據(jù)劃分至每一個(gè)簇中;
(7) 此時(shí)判斷有效性函數(shù)是否達(dá)到閾值,若沒(méi)有達(dá)到閾值迭代步驟4~6,反之則輸出最終K個(gè)簇的信息作為聚類的最終結(jié)果,至此聚類過(guò)程結(jié)束.
表 1 教務(wù)數(shù)據(jù)集相關(guān)參數(shù)Table 1 Related parameters of educational data set
實(shí)驗(yàn)環(huán)境:實(shí)驗(yàn)使用Ubuntu 16.04.3作為系統(tǒng)環(huán)境,JDK版本為1.8.0_161,搭建了基于Apache Hadoop 2.6.5的4個(gè)節(jié)點(diǎn)的集群,包括1個(gè)Master節(jié)點(diǎn)和3個(gè)Slave節(jié)點(diǎn).
實(shí)驗(yàn)數(shù)據(jù)為西安工程大學(xué)2017屆畢業(yè)生四年的學(xué)習(xí)成績(jī)及其畢業(yè)流向情況.數(shù)據(jù)集相關(guān)參數(shù)如表1所示.
3.2.1 性能驗(yàn)證實(shí)驗(yàn) 為了驗(yàn)證改進(jìn)后的Canopy-K-means算法的有效性,選用教務(wù)數(shù)據(jù)的部分?jǐn)?shù)據(jù)集,分別采用傳統(tǒng)K-means算法和改進(jìn)后的Canopy-K-means算法進(jìn)行對(duì)比實(shí)驗(yàn),通過(guò)聚類準(zhǔn)確率參數(shù)進(jìn)行衡量比較.
如圖4所示,改進(jìn)后的Canopy-K-means算法的聚類準(zhǔn)確率可提高約14%.聚類結(jié)果的參數(shù)表明,改進(jìn)后的Canopy-K-means算法具有更好的聚類效果.
3.2.2 單機(jī)集群對(duì)比實(shí)驗(yàn) 為了驗(yàn)證MapReduce并行模式下對(duì)于海量數(shù)據(jù)的處理效率,選用改進(jìn)后的Canopy-K-means算法,針對(duì)教務(wù)數(shù)據(jù)的部分?jǐn)?shù)據(jù)集,分別進(jìn)行單機(jī)模式下和MapReduce并行模式下1~4個(gè)節(jié)點(diǎn)的數(shù)據(jù)聚類實(shí)驗(yàn),并計(jì)算聚類收斂時(shí)間.
單機(jī)模式和MapReduce并行模式下的聚類收斂時(shí)間對(duì)比如圖5所示.由圖5可知,當(dāng)數(shù)據(jù)規(guī)模較小時(shí),MapReduce多節(jié)點(diǎn)模式下和單機(jī)模式相比,收斂時(shí)間沒(méi)有明顯的縮短.這是由于數(shù)據(jù)量較小時(shí)聚類時(shí)間較短,Hadoop在并行節(jié)點(diǎn)的任務(wù)啟動(dòng)和分配上需要花費(fèi)一定的時(shí)間,因而并沒(méi)有體現(xiàn)出并行處理的高效性;當(dāng)數(shù)據(jù)量達(dá)到一定規(guī)模時(shí), MapReduce模式下多節(jié)點(diǎn)并行處理數(shù)據(jù)的效率明顯優(yōu)于單機(jī)模式,并且節(jié)點(diǎn)數(shù)越多,聚類效率越高.數(shù)據(jù)量較大時(shí),MapReduce 多節(jié)點(diǎn)模式下相比單機(jī)模式收斂速度提高約2.1倍.另外,可以發(fā)現(xiàn)隨著節(jié)點(diǎn)數(shù)的增加,算法處理數(shù)據(jù)的速度的增長(zhǎng)率逐漸變緩,這是因?yàn)镠adoop平臺(tái)上的節(jié)點(diǎn)數(shù)越多,節(jié)點(diǎn)間的通信時(shí)間花費(fèi)越大.綜上,本文采用的并行挖掘算法對(duì)于處理海量教務(wù)數(shù)據(jù)在速度方面有所提高.
圖 4 K-means算法改進(jìn)前后收斂時(shí)間對(duì)比 圖 5 單機(jī)和MapReduce并行模式下聚類聚類效果 Fig.4 K-means algorithm clustering effect on before and after Fig.5 Comparison of cluster convergence time with stand-alone and MapReduce parallel mode
3.2.3 教務(wù)數(shù)據(jù)聚類分析實(shí)驗(yàn) 基于Hadoop平臺(tái)和改進(jìn)后的Canopy-K-means算法,針對(duì)教務(wù)數(shù)據(jù)集完成聚類任務(wù).根據(jù)數(shù)據(jù)預(yù)處理后得到的學(xué)生信息特征向量,將畢業(yè)去向相似的學(xué)生進(jìn)行聚類,同時(shí)得出該院學(xué)生的畢業(yè)流向分布情況以及每類學(xué)生的成績(jī)水平曲線.
以RJGC數(shù)據(jù)集為例,該院學(xué)生的畢業(yè)流向分布情況如圖6所示,由聚類結(jié)果可知該院學(xué)生就業(yè)情況良好,讀研、進(jìn)入外企和私企的學(xué)生占大多數(shù).
圖 6 RJGC學(xué)院學(xué)生畢業(yè)去向分布情況 圖 7 各類學(xué)生成績(jī)水平曲線 Fig.6 RJGC College students graduate distribution Fig.7 Various students′ performance level curve
不同畢業(yè)流向的學(xué)生成績(jī)水平曲線如圖7所示.以RJGC數(shù)據(jù)集為例,根據(jù)畢業(yè)流向?qū)W生最終分為九類.圖中成績(jī)等級(jí)0~4分別代表優(yōu)、良、中、及格、不及格,暫定學(xué)生的畢業(yè)流向與成績(jī)?yōu)榱技耙陨系恼n程關(guān)系較密切,此處選取3門作為最終與該畢業(yè)流向關(guān)聯(lián)最為密切的課程,如果某畢業(yè)去向的相關(guān)課程中成績(jī)?yōu)榱技耙陨系恼n程較多或者不足3門時(shí),按課程成績(jī)由高到低選取前3門作為最終結(jié)果.由此進(jìn)行簡(jiǎn)單統(tǒng)計(jì)分析可得出,RJGC學(xué)院的學(xué)生畢業(yè)流向?yàn)閲?guó)有企業(yè)時(shí),與馬克思主義基本原理、計(jì)算機(jī)科學(xué)導(dǎo)論和微機(jī)原理與接口技術(shù)這3門課程關(guān)系較密切;畢業(yè)流向?yàn)闄C(jī)關(guān)時(shí),與嵌入式系統(tǒng)軟件設(shè)計(jì)、微機(jī)原理和形勢(shì)與政策等課程關(guān)系較密切;未就業(yè)的同學(xué)大多為網(wǎng)頁(yè)設(shè)計(jì)、編譯原理及計(jì)算機(jī)科學(xué)導(dǎo)論等課程基礎(chǔ)較為不扎實(shí).
根據(jù)圖7的分析結(jié)果,教務(wù)人員可以根據(jù)學(xué)生對(duì)未來(lái)從事工作的打算對(duì)學(xué)生進(jìn)行更好的教育引導(dǎo),并對(duì)一些對(duì)畢業(yè)流向影響較大的課程加以重視.當(dāng)然,由于初始數(shù)據(jù)維度較高,缺省數(shù)據(jù)較多,實(shí)驗(yàn)結(jié)果存在一定的誤差性及不穩(wěn)定性.
本文以海量教務(wù)數(shù)據(jù)為基礎(chǔ),采用基于Hadoop的Canopy-K-means并行算法,研究了學(xué)生成績(jī)與畢業(yè)流向之間的內(nèi)在關(guān)系.首先,對(duì)于傳統(tǒng)K-means聚類算法存在的確定初始聚類中心的隨機(jī)性問(wèn)題,利用基于“最小最大原則”的Canopy算法快速獲取聚類中心,將其作為K-means算法的初始聚類中心,可大大減少計(jì)算量,相比傳統(tǒng)K-means算法,聚類收斂時(shí)間縮短約2.1倍,準(zhǔn)確率提高約15%.
其次,采用基于Hadoop的Canopy-K-means并行算法對(duì)教務(wù)數(shù)據(jù)進(jìn)行分析研究.通過(guò)對(duì)學(xué)生成績(jī)及其畢業(yè)流向數(shù)據(jù)的預(yù)處理,提取學(xué)生必修課程成績(jī)及其畢業(yè)去向等特征,建立數(shù)據(jù)向量維度,然后用改進(jìn)后的Canopy-K-means算法對(duì)數(shù)據(jù)進(jìn)行聚類分析,并以MapReduce模型實(shí)現(xiàn)算法的并行化,最后對(duì)聚類結(jié)果進(jìn)行分析,提取每一類學(xué)生成績(jī)的特征.挖掘教務(wù)數(shù)據(jù)中有價(jià)值的信息,分析學(xué)生畢業(yè)流向與其必修課程成績(jī)之間的關(guān)系,對(duì)教務(wù)人員預(yù)測(cè)學(xué)生未來(lái)的畢業(yè)流向,更好地教育引導(dǎo)學(xué)生具有重要的指導(dǎo)意義.
在下一步的工作中,將增加實(shí)驗(yàn)對(duì)象的涉及面,多層次多角度地進(jìn)行關(guān)聯(lián)分析,多維地考慮影響學(xué)生畢業(yè)流向的相關(guān)因素,對(duì)算法模型做進(jìn)一步的優(yōu)化,并結(jié)合分析模型的聚類結(jié)果,通過(guò)學(xué)生成績(jī)對(duì)其未來(lái)的畢業(yè)流向進(jìn)行預(yù)測(cè).