全局中心聚類算法在課程序化中的應用*

段桂芹 劉 松 鄒臣嵩

（1.廣東松山職業技術學院計算機系 韶關 512126）（2.廣東松山職業技術學院機械工程系 韶關 512126）

（3.廣東松山職業技術學院電氣工程系 韶關 512126）

1 引言

聚類是指按照研究對象的某個特征，對其進行無監督的分類，其目的是根據研究對象自身的相似度差異，使不同簇之間的研究對象具有最小相似性，同一簇內的研究對象具有最大相似性［1］。迄今為止，研究人員已經提出了多種聚類算法，通常可以分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網格的方法、基于模型的方法。其中，K-means 算法是應用最為廣泛的劃分方法之一，但該算法對初始聚類中心和異常數據較為敏感，且不能用于發現非凸形狀的簇，因此聚類結果不穩定［2］。為了解決這些問題，研究人員針對簇中心的選擇與優化提出了新的計算方法［3～10］，從聚類準確率、聚類耗時以及整體聚類質量等多個方面對原始K均值算法進行了優化與改進，但大多數研究都是致力于利用樣本的分布信息優化初始聚類中心的選擇，而在序列聚類研究領域，除了需要選擇合適的初始聚類中心，還需要針對實際情況設計滿足要求的相似度計算規則，在現有的各種應用中，序列數據的相似性可以分為兩種：基于整體的序列相似性，常用于用戶交易序列；基于局部的序列相似性，常用于生物信息序列，但課程序列與戶交易序列和生物信息序列相比有諸多不同，因此，如何選擇并改進現有的聚類算法，將其應用至課程序列的聚類分析中是解決課程序化問題的關鍵。

2 相關算法的研究現狀

在聚類算法的改進方面，王實美［6］針對密度算法進行了改進，該算法使用M近鄰有向圖得到輸入參數，克服了密度算法對輸入參數難以確定的缺點，降低了參數對人工的依賴性，但是，由于該算法使用的是全局唯一密度參數，在非均勻密度數據集的聚類效果并不理想。熊忠陽［7］使用最大距離積法解決了最大最小距離法因選取初始聚類中心過于稠密而導致的聚類沖突等問題，與經典的密度聚類算法相比，該算法在密度算法基礎上，從高密度點集合中選取距離乘積最大的樣本作為聚類中心，但對于參數MinPts（鄰域密度閾值）沒有真正地實現自適應確定閾值，依然采用經驗方法選取，需要人工參與。翟東海［8］使用最大距離法選取初始簇中心改進了K-mean 聚類算法，解決了K-means算法的聚類結果不穩定、總迭代次數較多等問題。段桂芹［9］選取數據對象到樣本均值和當前聚類中心集合的距離乘積最大值法來確定新的初始聚類中心，克服了聚類結果對初始聚類中心的依賴性。鄒臣嵩［10］通過采集樣本的分布情況計算樣本的密度參數，構建高密度點集合，改進了最大距離乘積法，提升了聚類算法的準確率和時間性能。

在研究以上算法［3～10］以及相關文獻［11～13］的基礎上，本文提出通過選取k 個“首尾相連”且距離乘積最大的數據對象作為初始聚類中心，確定樣本集中數據對象的大致分布，簇中心迭代過程中，選取了與簇內樣本距離之和最小的數據對象作為簇中心。實驗測試表明，本文算法的聚類準確率、整體耗時、F 值等性能指標優于K-means 算法、文獻［7］和文獻［8］的算法。

3 全局中心聚類算法

全局中心聚類算法由距離矩陣構建、初始聚類中心選擇和簇中心迭代三部分構成：在距離矩陣構建時，使用距離公式計算各數據對象間的距離；在初始聚類中心選擇階段，從距離矩陣中選取k 個首尾相連且距離乘積最大的數據對象作為初始聚類中心集合Z，Z=｛Z1，Z2，…，Zk｝；在簇中心迭代過程中，根據集合Z 完成初次聚類，選取簇內最小距離和的樣本作為簇中心，生成臨時簇中心集合Z'=｛Z1'，Z2'，…，Zk｝'，再按最小距離將各樣本劃分到相應簇中，重復簇中心迭代過程，直至聚類誤差平方和函數收斂，完成聚類。

全局中心聚類算法中的相關定義、流程分別如下。

3.1 相關定義

設 X 為含有 n 個樣本的集合，X=｛X1，X2，…，Xn｝，各樣本的特征數為 p，則第 i 個樣本若該集合可劃分為k 個簇，每簇含樣本m 個，簇中心集合為Z，則可用以下方式表示該集 合 ，既 Cluster=｛Cluster1，Cluster2，…，Cluster｝k，Cluster∈X，Z=｛Z1，Z2，…，Z｝k（k＜n）。

定義1空間兩點間的歐氏距離定義為

式中i=1，2，…，n；j=1，2，…，n；w=1，2，…，p。

定義2樣本集X的空間距離矩陣X'

定義3第k簇中樣本Xi的簇內距離和定義為

定義4第k簇的簇內距離和矩陣定義為

定義5將第k 簇的簇內距離和最小的樣本Xi作為的中心，即

定義6聚類誤差平方和E的定義為

式中 q 是樣本集 X 中的某個樣本，Zi是簇 Clusteri的中心。

3.2 算法描述

步驟1：根據式（1）計算樣本集X中各數據對象之間的距離，得到距離矩陣X'；

步驟2：根據式（2）構建樣本集X的空間距離矩陣X'；

步驟3：在X'中選擇滿足k 個首尾相連且距離乘積最大的數據對象作為初始聚類中心，即選擇滿足的 k 個數據對象加入簇中心集合Z 中；

步驟4：將各樣本按最小距離劃分至對應的簇中；

步驟5：使用式（3）、（4）計算出簇內距離和矩陣，根據式（5）從中篩選出滿足條件的新簇中心存入集合Z'中；

步驟6：重復步驟5，更新各簇的中心，直到|Z'|=k，再用Z'取代Z；

步驟7：重復步驟4；

步驟8：根據式（6）計算聚類結果評價指標，判斷是否收斂，如果收斂，則聚類算法結束，否則轉到步驟4繼續執行。

4 實驗仿真與分析

實驗運行環境：CPU Intel Core i3-3240 3.4GHz，硬盤1T，內存4G，操作系統Win7（64 位），仿真軟件使用Matlab 2011b，實驗數據集詳見表1。在有效性驗證方面，采用聚類總耗時、Rand 指數、Jaccard系數和聚類準確率等指標對K-means算法、文獻［7］、文獻［8］和本文算法進行了比較，其中K-means算法的實驗結果是其運行30次的平均值。

表1 UCI數據集

4.1 聚類準確率和時間性能對比

圖1～圖5 是K-means算法、文獻［7～8］算法和本文算法在UCI數據集的聚類準確率、初始中心選擇耗時、簇中心更新耗時、迭代次數、聚類總耗時的實驗對比結果。觀察圖1 可知，在iris 和wine 數據上，本文算法的聚類準確率明顯高于K-means 算法，略高于文獻［7～8］算法，在 Haberman、sonar 和soybean 數據集上的聚類準確率明顯高于其他三種算法。

由圖2可知，由于K-means算法隨機選取初始聚類中心，無需額外計算，故耗時少，而文獻［7～8］和本文優化了初始聚類中心選擇過程，增加了計算開銷，因此耗時較多。此外，由于本文算法先對整個樣本集的距離矩陣進行了求解，并用全局中心法篩選初始聚類中心，在計算量方面開銷較大，因此耗時高于文獻［7～8］。

從圖3 可以看出，本文算法的簇中心更新耗時小于K-means 算法和文獻［7～8］算法，主要原因在于在該階段，本文算法的簇中心與簇內樣本距離之和最小，簇中心被其他樣本緊密圍繞，每一次更新，都會使得簇中心的位置和樣本的分布情況更加清晰，進而減少了更新次數和更新耗時。

圖1 聚類準確率比較

圖2 初始中心選擇耗時比較

圖3 簇中心更新耗時比較

從圖4、圖5 可知，本文算法在迭代次數、總耗時方面優于其他三種算法，這是由于K-means算法的隨機性導致準則函數易陷入局部極小、導致總迭代次數不穩定，此外，文獻［7～8］并未對簇中心更新進行優化，依然沿用均值中心算法，未能更好地體現中心點在簇中的代表性，而本文算法在初始中心選擇階段篩選出的聚類中心相對分散，基本反映了樣本的大致分布，相對而言，具有較強代表性，此外，在簇更新階段，選取了與簇內樣本距離之和最小的數據對象作為簇中心，在整體上快速得逼近了全局最優解，減少迭代次數，降低運算耗時。

圖4 迭代次數比較

圖5 聚類總耗時比較

4.2 其他外部評價指標對比

關于算法聚類結果的評價，除采用常用的聚類準確率、迭代次數和各階段聚類耗時之外，還采用Rand等四個評價指標［14］對聚類結果進行了比較分析。觀察表2～表5 的對比結果可知，本文算法在UCI的5個數據集上的聚類外部評價指標全部優于其他4種算法。

表2 Rand指數比較

表3 Jaccard系數比較

表4 Adjusted Rand Index參數比較

表5 F值比較

從上述UCI數據集的對比實驗結果可以得出：本文算法在多種聚類結果的評價指標中展現出更佳的聚類質量、更快的收斂速度和更高的穩定性，可以應用于實際數據的聚類。

5 算法在課程序列聚類中的應用

5.1 樣本數據結構

原始數據由前導課程、后續課程、開設學期三個關聯關系構成，表6是26名課程專家之一填寫的課程關系數據表。

在對原始樣本數據預處理時，將“項目”定義為有前導后續關系的兩門課程的組合，如前導課程為A，后續課程為B，則用項目“AB”表示二者關系，因此候選項目集由A 到M 的13 個元素中的兩個相異元素有序排列而成，既｛AB，AC，AD，…，MJ，MK，ML｝，共包含156個項目，每個項目都表達了兩門課程的先后組合關系［15］。據此，表6 可由項目子集｛GA，LA，HB，FB，BM，…，DL，IL，LA，BM，KM｝表示；同理可以構建出其他25 個項目子集，共同組成新的序列樣本集，預處理后的序列樣本集由318 條序列事務構成。

5.2 序列間的相似性度量

序列數據的相似性可以分為兩種：基于整體的序列相似性和基于局部的序列相似性，前者常用于生物信息序列，后者常用于用戶交易序列［16～17］。但課程序列與戶交易序列和生物信息序列相比有諸多不同：首先，一門課程在序列中是不允許重復的，即一門課只教授一次，而用戶交易和生物信息序列中的元素是可以重復的；其次，在序列元素的數量上，用戶交易的元素數量很大，生物信息的元素數量很少，課程序列的元素介于兩者之間；再次，用戶交易序列更強調時間的點，課程序列更強調先后的序；最后，生物信息序列強調空間的物理結構，課程序列更強調行為的邏輯結構。針對課程序列的特殊性以及課程體系的構建需求，序列間的相似度與距離定義如下。

定義7結構相似度。假設Xi和Xj是序列樣本集中的兩個樣本，則Xi和Xj的結構相似度Ssim（Xi，X）j：

其中Stru（X）i、Stru（X）j分別表示Xi和Xj各自包含的元素的集合；|Stru（X）i∩Stru（X）j|表示Xi和Xj共有元素個數，|Stru（X）i∪Stru（X）j|表示Xi和Xj所包含的全部元素的個數。Ssim（Xi，X）j的取值范圍是［0，1］，當其值為0 時，表示二者的結構無任何相似性；當其值為1 時，表示二者的結構全部一致。

定義8內容相似度：

其中Con（tX）i、Con（tX）j表示Xi和Xj所包含的項目的集合。

定義9序列相似度由結構相似度與內容相似度共同構成，為二者均值，即：

定義10序列間的距離定義為

5.3 基于全局中心聚類算法的課程體系構建

使用式（7～10）計算序列樣本集中各樣本之間的距離，得到距離矩陣X'，結合全局中心聚類算法，完成聚類。

需要特別指出的是：序列聚類后的每一簇序列形成一條課程路徑，針對一種崗位能力的培養。由于機電設備維修與管理專業有五個入職崗位，每個崗位的核心課程約 7 門，因此對 K=3，4，5 都進行了聚類分析，且每簇選取聚類中心及距其最近的8 條序列用于課程結構的生成，聚類計算結果如表7 所示。

表7 崗位課程聚類結果

對表7 的聚類結果進行整理，刪除相同聚類和元素個數大于等于8 的聚類，對剩余的6 個聚類分別計算其元素排序支持度，形成6 條鏈路；對孤立元素，計算其與聚類元素的排序支持度，得到1 條崗位課程排序鏈路，具體結果如表8。

表8 崗位課程排序結果

6 結語

本文用全局中心法對K-means 算法和最大距離乘積聚類算法進行了改進，得到了具有代表性的初始聚類中心，在簇中心迭代階段，選取簇內距離和最小的樣本作為簇中心，減少了迭代次數，提高了算法的運算速度，對比測試表明，本文算法對聚類中心的選取合理、有效。在實際應用中，使用新算法對現代學徒制的職業能力及課程體系的相關數據進行了聚類分析，解決了課程序列的有效聚類問題，為課程結構的合理設計給出了理論依據。