基于WFKP聚類算法的培養質量評估

張德珍，趙文波，高 鵬

(1.大連海事大學 信息科學技術學院，遼寧 大連 116026； 2.大連大學 經濟管理學院，遼寧 大連 116026)

0 引 言

傳統的培養質量評估方法如AHP模糊評價法[1]、灰色度評價法[2]，面對海量信息時效率低下、主觀性過強，存在著一定的局限性。基于聚類分析與培養質量評估在目的上的一致性，將聚類算法加以改進后應用于培養質量評估，有著較高的實用價值。文獻[3]通過引入小生境和禁忌算法思想，提高了算法的抗干擾性和聚類精度；文獻[4]使用線性擬合來自動選取初始簇中心，文獻[5]融合遺傳算法來選取初始簇中心，減少了初始簇中心選取不當對聚類穩定性的影響，但遺傳演變中的適應度函數不易設計，算法計算成本高昂；文獻[6]使用低密度區域來劃分高密度區域，適用于任意簇分布的聚類問題，但對實際應用中高維數據分布不均時聚類辨識能力偏低，準確率不高。以上聚類算法集中于對最佳聚類數目或初始簇中心的改進，只適用于數值屬性，無法處理培養質量評估中的分類屬性。FKP算法[7]使用海明距離處理分類屬性的特征差異，并引入了隸屬度的概念使其具備軟劃分的能力。但針對于培養質量評估，FKP算法未能考慮到樣本的總體差異和不同特征的權重差異，直接將其應用于培養質量評估會降低聚類準確性，不能達到最佳聚類效果。

針對上述問題，本文在FKP算法的基礎上，提出一種面向混合屬性的特征加權WFKP聚類算法。首先提出一種改進的分類屬性相異度計算公式，綜合考慮簇中所有樣本的整體差異，提高對樣本相似度的區分能力。然后在K近鄰算法[8]和MI(mutual information)的基礎上，在聚類中引入樣本數值特征和分類特征的權重分析，提高了聚類算法的準確率。最后通過UCI數據集驗證算法的有效性，并對某高校的培養質量數據集進行聚類分析，降低培養質量評估的工作量和復雜度，實現評估過程的智能化、規模化和精準化。

1 FKP聚類算法

FKP算法的基本思想是從樣本集中隨機選取k個樣本作為初始簇中心，計算各個樣本與初始簇中心的距離，將樣本對象劃分到距離最近的簇中，然后更新簇中心并不斷迭代此過程，最終簇中心的波動范圍小于指定的閾值時聚類結束。下面給出FKP聚類算法中的相關定義。

定義1 相異度：相異度表示兩個對象差異程度的數值度量，聚類的難點在于準確量化樣本xi和xj的相異度。FKP聚類算法中樣本xi和xj的相異度定義如下

(1)

式(1)的前半部分采用歐氏距離計算樣本的連續屬性的相異度，后半部分采用海明距離來表示離散屬性的相異度，歐式距離的定義如下

(2)

海明距離的定義如下

(3)

定義2 隸屬度：樣本xi屬于簇Cj的模糊程度定義為uij。 由于培養質量評估的指標眾多，部分指標具有模糊性和不確定性，不能把樣本嚴格地劃分到某個簇中，故應引入模糊集理論，考慮量化樣本間的模糊關系，從而準確客觀地描述樣本的分布特征，由Lagrange乘數法計算uij，uij的計算過程如下

(4)

定義3 目標函數：FKP算法的優化目標是簇間樣本相似程度最小化，簇內樣本相似程度最大化，即最小化所有樣本到簇中心的平方誤差和SSE(sum of squares due to error)，FKP算法的目標函數E(U,C) 如下

(5)

式中：k為聚類個數，U為n×k的模糊劃分矩陣，uij表示第i個樣本隸屬于簇Cj的模糊程度；ded(xi,cj) 為樣本xi與簇中心cj的數值屬性的相異度，δ(xi,cj) 為樣本xi與簇中心cj分類屬性的相異度；模糊因子α控制聚類的模糊程度，比例系數γ調節連續屬性和離散屬性的權值比例。

目標函數受限于以下約束條件

(6)

2 WFKP聚類算法的設計

針對海明距離忽略樣本特征關聯而導致的信息缺失問題，本文提出了一種改進的分類屬性相異性度量方式，在馬氏距離的計算中引入比例系數，改進協方差矩陣估計，降低高維數據集下對樣本數據的誤分率，用改進的相異度計算方法尋找樣本的K個近鄰點，用于樣本特征的權值分析。

2.1 分類屬性相異度改進

馬氏距離是基于樣本分布信息的一種無量綱距離，考慮到樣本的特征關聯，克服了海明距離的缺陷。

樣本的分布信息由協方差矩陣來刻畫，樣本xi與簇中心cj的馬氏距離定義如下

(7)

其中， ∑是樣本分布的協方差矩陣，是一個對稱的正定矩陣。協方差矩陣的計算是求解馬氏距離的關鍵，傳統的協方差矩陣計算方式如下

(8)

式(8)中用當前聚類下數據的樣本分布來作為馬氏距離的協方差矩陣，由于聚類前期簇中心位置改變較大，樣本分布不穩定，上述計算方法會導致較大的估計誤差進而降低算法的穩定性。為此我們增加了聚類中已分類樣本和未分類樣本的概率統計，引入了比例系數Φ，其定義如下

(9)

γ=1-|Cl|/|Clij|

(10)

式(10)中， |Cl| 是簇Cl中已有樣本的個數， |Clij| 是待分類樣本xi的第j個屬性值在簇Cl中出現的頻率。

∑為正定矩陣，根據矩陣理論，對其進行如下分解

(11)

(12)

2.2 數值屬性的權值計算

對于數值屬性的權值分析，文獻[9]采用粒子群的方法先將數值屬性離散化，但其離散過程具有較強主觀性。文獻[10]使用信息論來分析權值，這需要知道數值屬性的概率分布，培養質量數值屬性相互關聯且可能存在冗余，其概率分布不易獲得。本文利用改進的相異度尋找簇中心的K近鄰樣本，在此基礎上定義培養質量數據樣本的簇內離散度和簇間離散度，來計算數值屬性的權值。

Neark(xi) 是式(12)下得到的距離樣本xi最近的第K個樣本點，xi的K近鄰樣本定義如下

(13)

定義4 簇內離散度distinter， 表示簇Ck內的各數據對象的數值屬性Aj與此屬性的均值μjk的離散程度。從樣本集X隨機抽取樣本xi， 利用式(13)在與xi同類的簇內尋找xi的同類K近鄰樣本，記為Near_interj,j=1,2,…,k。 樣本xi與Near_interj在特征Al上的差異定義為如下

(14)

定義5 簇間離散度distexter， 表示各分組Ck內某連續屬性Aj的均值μjk與整個數據對象上此屬性的均值μj的離散程度。從樣本集X隨機抽取樣本xi， 利用式(13)在每個與xi不同類的簇內尋找xi的非同類K近鄰樣本，記為Near_exterj,j=1,2,…,k。 樣本xi與Near_exterj在特征Al上的差異定義如下

(15)

其中，C≠class(xi)。 樣本集X在特征Al上的權重更新公式如下

(16)

由式(16)可知，數值屬性的權值的主要由distinter和distexter的差值決定。distinter越小，distexter越大，樣本與Near_interj在該屬性上的相似度越高，樣本與其Near_exterj在該屬性上的相似度越低，該屬性對于聚類的區分度越好，其權重也就越大。

2.3 分類屬性的權值計算

分類屬性的概率分布通過數值統計即可得知，本文采用信息論中的MI來計算分類屬性權值。MI用來度量兩個隨機變量之間的相關性，表示在已知其中某個隨機變量的條件下，另一個隨機變量不確定性減少的程度。本文應用MI來衡量樣本分類屬性與聚類結果之間的依賴程度，從而求出樣本分類屬性對聚類的重要程度。

Dom(Al)={al|al=xil,1≤i≤n,p≤l≤m} 表示樣本集X第l個屬性的所有值組成的集合， |Dom(Al)| 表示分類屬性Al的取值個數。Av=Dom(Al=v) 表示xil=v的樣本子集，隨機變量R={Ci|i=1,2,…,k} 表示樣本的聚類結果，定義p(a),p(r),p(a,r) 分別表示Al和R的邊緣概率分布函數以及Al，R的聯合概率分布函數，其中

(17)

則分類屬性Al與聚類結果R之間的互信息MI定義如下

(18)

(19)

根據式(12)、式(15)和式(19)，WFKP算法對目標函數進行了相應的修正，修正后的目標函數如下

(20)

2.4 簇中心更新

對式(20)求最小值以獲得最優解，需要遍歷樣本集所有可能的簇劃分，理論上屬于NP-Hard問題。本文采用貪心策略，通過對簇中心迭代更新尋找其近似最優解，文獻[11]證明了經有限次迭代后目標函數可以收斂于局部最優解。本文在對簇中心進行迭代更新時，增加對屬性權重的計算，快速篩除冗余屬性，有效減少迭代次數，提高聚類效率。對簇中心cj的第l(1≤l≤p) 個數值屬性cjl的更新公式如下

(21)

對于簇中心ci的第l(p+1≤l≤m) 個分類屬性cil的更新公式如下

(22)

其中，s滿足如下定義

(23)

綜上，WFKP聚類算法描述如下。

步驟1 指定聚類類別K[12]，初始化簇中心[13]。

步驟2 初始化迭代次數t=0， 初始化簇中心矩陣C(t)， 初始化目標函數值E(t)=0。

步驟3 利用式(4)計算迭代模糊劃分矩陣U(t)。

步驟4 利用式(15)計算數值屬性的權值矩陣Wn(t)， 利用式(19)分類屬性的權值矩陣Wc(t)。

步驟5 利用式(21)、式(22)更新簇中心。

3 實驗結果與分析

在UCI數據集和培養質量數據集上驗證WFKP算法的有效性和實用性，選取KP算法、FKP算法、IG-F-KP算法、GK-KP作為對比算法。算法使用C#語言實現，運行在Window10操作系統上，實驗的硬件配置為：Intel(R) Core(TM) i7-8700K CPU @3.70 GHz，內存為8.0 GB。

3.1 UCI標準數據集驗證

本文使用的數據集為Iris Plants(簡稱Iris)、Credit Approval(簡稱Credit)、Heart Disease(簡稱Heart)以及Wisconsin Breast Cancer(簡稱Breast)，數據集的相關描述見表1。

表1 UCI數據集描述

實驗采用準確率(Accuracy)來驗證WFKP算法的有效性和魯棒性[14]。假設樣本集中樣本數為n，Ai表示樣本正確分到第i類的樣本數，k為聚類數目，則準確率的計算公式如下

(24)

聚類分析中參數的設置至關重要，對UCI數據的驗證中，參數k由UCI數據集指定，模糊因子α設置為2[15]，停止閾值設置為0.0001，λ取分類屬性與連續屬性的比值。不同算法在Credit數據集的準確率如圖1所示。

圖1 不同算法在Credit數據集的準確率

從圖1可以看出，KP算法在Credit數據集上準確率最低，在其基礎上改進而來的各種聚類算法準確率得到了顯著的提升。其中，WFKP算法在Credit上的準確率明顯高于傳統的K-Prototype的算法，與其它聚類算法相比準確率也處于較高水平。

不同算法在表1所示數據集上進行對比實驗，各算法的平均準確率見表2。

表2 不同算法的平均準確率

從表2可以看出，在相同數據集上，WFKP算法在Iris上的準確率最高，比GK-KP算法平均提升1.4%，比IG-F-KP算法平均提升3.2%；WFKP算法在Heart上的準確率最低，略低于GK-KP算法0.7%，高于IG-F-KP算法0.4%。WFKP算法的在UCI數據集上的整體準確率要高于其它對比算法，驗證了算法的有效性。

為了進一步檢驗WFKP算法在表1所示數據集上的聚類性能，本文結合PCA算法和t-SNE高維數據可視化算法[16]，保留原有數據結構的基礎上對表1中的數據集進行降維分析，直觀展示聚類效果。WFKP算法的聚類可視化結果如圖2～圖5所示。

圖2 Iris數據集：聚類可視化效果

圖4 Heart數據集：聚類可視化效果

圖5 Breast數據集：聚類可視化效果

觀察圖2～圖5可以發現，WFKP聚類算法在4種UCI數據集上均具有良好的可分性。其中，Iris數據集只有4個特征維度的數值屬性，其數據集相對簡單，數據重疊部分最小，聚類分布效果最為良好。Heart具有7個維度的數值屬性和8個維度的分類屬性，這基本與研究生培養質量評估數據集的特征維度相符合。WFKP在Heart數據集上的重疊部分多于Iris，聚類效果略差于Iris，但也有較好的聚類可分性，這驗證了WFKP聚類算法的有效性和魯棒性。

3.2 培養質量數據集驗證

培養質量評估首先需要確立評估指標體系，評估指標體系是基于培養質量評估的內涵構造的具體的可量化的評價準則。文獻[17]結合德爾菲法和層次分析法構建出多角度深層次的培養質量評價指標體系，避免過多的評價特征造成維數災難。在文獻[17]的基礎上，結合高校研究生培養的實際需求，構建如表3所示培養質量評估指標體系。

表3 研究生培養質量評估指標體系

參照表3構建的評估指標體系，采集某高校2015級至2018級14 268名研究生培養信息，將其映射為11維的特征向量，獲得14 268×11維的培養質量數據集。數據集中的部分樣本數據見表4。

由于培養質量數據之間具有量綱差異性，不便于比較，本文采用極差正視化方法將每個樣本的數值屬性縮放到0～1

表4 研究生培養質量樣本數據(數值屬性)

的范圍，轉化為無量綱數值，便于不同單位或量級的指標進行比較和加權[18]，極差正式化方法如式(25)所示。對培養質量數據數值屬性進行極差正視化處理處后的樣本數據見表5

(25)

WFKP是無監督算法，培養質量這種無標簽的數據，在沒有先驗知識的前提下無法直接通過準確率來驗證聚類算法的有效性，我們使用輪廓系數SC(silhouette coef-ficient)來驗證WFKP在培養質量數據集的聚類性能。

SC的計算公式如下

(26)

式中：ai體現聚類的凝聚度，表示樣本i到簇Ci內其它樣本的平均距離，bi體現聚類的分離度，表示樣本i與簇Cl(l≠i)內樣本的平均距離。SC結合了聚類的凝聚度和分離度，區間取值為[-1,1]。SC值越接近于1，表示聚類的凝聚度越大，分離度越小，聚類效果越好。

對培養質量數據進行聚類分析時，參數k設為4，λ的值設置為1.1，模糊因子的取值對培養質量的聚類分析影響較大，設置多組實驗對模糊因子不同值進行聚類分析，實驗結果見表6。

從表6可以看出，當模糊因子值為1.5時，算法的平均

表6 培養質量聚類評估的輪廓系數

輪廓系數值為0.851，算法在培養質量數據集上達到最佳的聚類效果。

設定模糊因子α的值為1.5，利用WFKP算法對培養質量數據進行聚類分析，當目標函數收斂后，獲得研究生培養質量評估要素的權重分析，如圖6所示。研究生培養質量的聚類統計結果如圖7所示。

圖6 培養質量屬性權重分析

圖7 培養質量聚類類別統計

通過對培養質量的權重分析(圖6)和WFKP加權聚類的各類別占比統計分析(圖7)，得出以下結論。

(1)研究生培養質量評估要素中，權重最高的是導師學術成果和學生論文質量，4年的平均權重值分別是17.4%和13.5%；權重最低的是本科院校層次和研究生入學成績，權重占比分別是4.3%和2.6%。學術氛圍和科研創新的權重逐年上升，生源素質的權重略有下降。導師學術成果的權重由2015級的14.4%上升至2018級的19.1%，學生入學成績的權重由2015級的2.8%下降至2018級的2.5%。這說明，導師的學術水平和培養過程精細化要求起著至關重要的作用，而本科院校層次和研究生入學類型對培養階段影響較小，研究生的培養質量重在培養，研究生入學后應在導師的指導下把更多精力投入到學術研究中，提高自身科研能力。

(2)研究生培養質量聚類類別中，平均占比最大的是B類和C類，分別占比31%和35.2%；平均占比最小的是A類和D類，分別占比12%和21.7%，研究生培養質量整體呈現兩頭小中間大的分布。學校逐年加強導師學術能力的考核和學生科研能力的培養，研究生教育改革取得一定的進步，A類研究生占比由10%上升至15%，B類研究生占比由34%下降到28%。C類和D類研究生占比基本穩定在57%，研究生培養質量還有較大的提升空間。

4 結束語

傳統模糊聚類算法未能考慮樣本間的總體差異，忽略樣本的特征關聯和特征權值，降低了算法結果的穩定性和準確性。針對此問題，在馬氏距離的協方差矩陣估計中引入比例系數來計算分類屬性相異度，利用新的相異度來尋找樣本點的K個近鄰點，用于計算樣本的簇內和簇間相異度分析數值特征的權值，通過計算分類特征和聚類結果之間的互信息分析分類特征的權值。在UCI真實數據集上驗證了WFKP算法的有效性和魯棒性，并將本文算法應用到研究生培養質量評估中。通過對培養質量數據集進行聚類分析，刻畫研究生培養質量的分布比例，重點分析不同評估要素對培養質量的影響權值，為高校提升培養質量提供相應的決策支持。