張德珍，趙文波，高 鵬

(1.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026； 2.大連大學(xué) 經(jīng)濟(jì)管理學(xué)院，遼寧 大連 116026)

0 引 言

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

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

1 FKP聚類算法

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

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

(1)

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

(2)

海明距離的定義如下

(3)

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

(4)

定義3 目標(biāo)函數(shù)：FKP算法的優(yōu)化目標(biāo)是簇間樣本相似程度最小化，簇內(nèi)樣本相似程度最大化，即最小化所有樣本到簇中心的平方誤差和SSE(sum of squares due to error)，F(xiàn)KP算法的目標(biāo)函數(shù)E(U,C) 如下

(5)

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

目標(biāo)函數(shù)受限于以下約束條件

(6)

2 WFKP聚類算法的設(shè)計

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

2.1 分類屬性相異度改進(jìn)

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

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

(7)

其中， ∑是樣本分布的協(xié)方差矩陣，是一個對稱的正定矩陣。協(xié)方差矩陣的計算是求解馬氏距離的關(guān)鍵，傳統(tǒng)的協(xié)方差矩陣計算方式如下

(8)

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

(9)

γ=1-|Cl|/|Clij|

(10)

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

∑為正定矩陣，根據(jù)矩陣?yán)碚?，對其進(jìn)行如下分解

(11)

(12)

2.2 數(shù)值屬性的權(quán)值計算

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

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

(13)

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

(14)

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

(15)

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

(16)

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

2.3 分類屬性的權(quán)值計算

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

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

(17)

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

(18)

(19)

根據(jù)式(12)、式(15)和式(19)，WFKP算法對目標(biāo)函數(shù)進(jìn)行了相應(yīng)的修正，修正后的目標(biāo)函數(shù)如下

(20)

2.4 簇中心更新

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

(21)

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

(22)

其中，s滿足如下定義

(23)

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

3.1 UCI標(biāo)準(zhǔn)數(shù)據(jù)集驗證

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

表1 UCI數(shù)據(jù)集描述

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

(24)

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

圖1 不同算法在Credit數(shù)據(jù)集的準(zhǔn)確率

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

不同算法在表1所示數(shù)據(jù)集上進(jìn)行對比實驗，各算法的平均準(zhǔn)確率見表2。

表2 不同算法的平均準(zhǔn)確率

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

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

圖2 Iris數(shù)據(jù)集：聚類可視化效果

圖4 Heart數(shù)據(jù)集：聚類可視化效果

圖5 Breast數(shù)據(jù)集：聚類可視化效果

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

3.2 培養(yǎng)質(zhì)量數(shù)據(jù)集驗證

培養(yǎng)質(zhì)量評估首先需要確立評估指標(biāo)體系，評估指標(biāo)體系是基于培養(yǎng)質(zhì)量評估的內(nèi)涵構(gòu)造的具體的可量化的評價準(zhǔn)則。文獻(xiàn)[17]結(jié)合德爾菲法和層次分析法構(gòu)建出多角度深層次的培養(yǎng)質(zhì)量評價指標(biāo)體系，避免過多的評價特征造成維數(shù)災(zāi)難。在文獻(xiàn)[17]的基礎(chǔ)上，結(jié)合高校研究生培養(yǎng)的實際需求，構(gòu)建如表3所示培養(yǎng)質(zhì)量評估指標(biāo)體系。

表3 研究生培養(yǎng)質(zhì)量評估指標(biāo)體系

參照表3構(gòu)建的評估指標(biāo)體系，采集某高校2015級至2018級14 268名研究生培養(yǎng)信息，將其映射為11維的特征向量，獲得14 268×11維的培養(yǎng)質(zhì)量數(shù)據(jù)集。數(shù)據(jù)集中的部分樣本數(shù)據(jù)見表4。

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

表4 研究生培養(yǎng)質(zhì)量樣本數(shù)據(jù)(數(shù)值屬性)

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

(25)

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

SC的計算公式如下

(26)

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

對培養(yǎng)質(zhì)量數(shù)據(jù)進(jìn)行聚類分析時，參數(shù)k設(shè)為4，λ的值設(shè)置為1.1，模糊因子的取值對培養(yǎng)質(zhì)量的聚類分析影響較大，設(shè)置多組實驗對模糊因子不同值進(jìn)行聚類分析，實驗結(jié)果見表6。

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

表6 培養(yǎng)質(zhì)量聚類評估的輪廓系數(shù)

輪廓系數(shù)值為0.851，算法在培養(yǎng)質(zhì)量數(shù)據(jù)集上達(dá)到最佳的聚類效果。

設(shè)定模糊因子α的值為1.5，利用WFKP算法對培養(yǎng)質(zhì)量數(shù)據(jù)進(jìn)行聚類分析，當(dāng)目標(biāo)函數(shù)收斂后，獲得研究生培養(yǎng)質(zhì)量評估要素的權(quán)重分析，如圖6所示。研究生培養(yǎng)質(zhì)量的聚類統(tǒng)計結(jié)果如圖7所示。

圖6 培養(yǎng)質(zhì)量屬性權(quán)重分析

圖7 培養(yǎng)質(zhì)量聚類類別統(tǒng)計

通過對培養(yǎng)質(zhì)量的權(quán)重分析(圖6)和WFKP加權(quán)聚類的各類別占比統(tǒng)計分析(圖7)，得出以下結(jié)論。

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

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

4 結(jié)束語

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