基于全局K-means算法的高校學(xué)生成績(jī)分析

谷欣超，徐福祥，楊勇，曲福恒

（1.長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022；2.長(zhǎng)春師范大學(xué)，長(zhǎng)春 130032）

在當(dāng)代大學(xué)中，成績(jī)對(duì)于學(xué)生非常重要，分?jǐn)?shù)高可以為評(píng)選獎(jiǎng)學(xué)金評(píng)選加分，也可以在找工作時(shí)，比其他人更加容易吸引招聘公司的注意力，所以，為了提高高校學(xué)生學(xué)習(xí)成績(jī)，應(yīng)該對(duì)學(xué)生成績(jī)進(jìn)行分析，從中挖掘出影響學(xué)生成績(jī)的主要因素，針對(duì)學(xué)生的缺點(diǎn)培養(yǎng)學(xué)生，為學(xué)生構(gòu)建一套合理且高效的教學(xué)方法。常用的成績(jī)分析方法包括聚類分析［1-2］方法、決策樹算法、關(guān)聯(lián)規(guī)則等。聚類分析方法是目前最具應(yīng)用前景的成績(jī)分析方法之一，該方法的優(yōu)點(diǎn)在于其結(jié)論形式簡(jiǎn)明、直觀，容易從中發(fā)現(xiàn)隱含的規(guī)律。K-means［3-4］算法是一種重要的聚類算法，由McQueen在1976年提出。K-means算法的目標(biāo)是將N維的M個(gè)點(diǎn)劃分為K個(gè)簇，使準(zhǔn)確率和召回率達(dá)到最大值。K-means算法主要有兩個(gè)缺點(diǎn)：（1）對(duì)簇的數(shù)目進(jìn)行先驗(yàn)固定；（2）隨機(jī)選擇初始聚類中心。本文將全局K-means算法應(yīng)用于成績(jī)分析中，全局K-means算法改進(jìn)了初始類簇中心的確定過程，減少了初始聚類中心的篩選對(duì)于K-means算法產(chǎn)生的負(fù)面影響。應(yīng)用于學(xué)生成績(jī)分析中，能夠得到更加準(zhǔn)確的聚類效果。

1 聚類分析方法

在學(xué)生成績(jī)分析［1］中主要應(yīng)用聚類分析［5］方法。常用的聚類分析方法包括K-means［6］算法、K-中心點(diǎn)［7］、OPTICS［8］、FCM［9］算法和 SOM［10］算法等。聚類分析是將大量的數(shù)據(jù)對(duì)象，按照數(shù)據(jù)之間性質(zhì)的差異，分成多個(gè)類或簇，每一個(gè)類簇中的數(shù)據(jù)具有較高的相似度，不同類簇之間，存在一定的差別。聚類分析方法主要分為四種方法，在文中簡(jiǎn)單介紹基于劃分和基于層次的兩種聚類方法。

基于劃分［11］的聚類方法，能夠?qū)崿F(xiàn)同一類的數(shù)據(jù)點(diǎn)之間的距離足夠近，不同類的數(shù)據(jù)點(diǎn)之間的距離足夠遠(yuǎn)的聚類效果。首先確定要?jiǎng)澐值臄?shù)據(jù)種類K，然后選擇幾個(gè)聚類中心，作為初始劃分；在此基礎(chǔ)上，依據(jù)預(yù)先確定的啟發(fā)式算法對(duì)數(shù)據(jù)進(jìn)行迭代重置，最后獲得K類數(shù)據(jù)以實(shí)現(xiàn)算法預(yù)計(jì)的聚類效果。該方法中常用于成績(jī)分析的算法包括K-means算法、K-medoids［12］算法等。

基于層次［13］的聚類方法，其主要原理是先將每個(gè)對(duì)象看作一個(gè)簇或類，然后將這些簇或類進(jìn)行合并，得到較大的簇或類，所合成的類簇達(dá)到算法設(shè)定的結(jié)束條件后停止。通常，層次聚類屬于凝聚型層次聚類，簇間相似度的定義決定了類與類之間的差異。層次聚類的主要優(yōu)點(diǎn)在于不需要預(yù)先定義聚類數(shù)，在聚類時(shí)，能夠發(fā)現(xiàn)數(shù)據(jù)之間的層次關(guān)系。這一聚類方法的缺點(diǎn)在于計(jì)算量太大，而且在聚類的過程中會(huì)聚類成鏈狀。

2 全局K-means聚類

K-means算法是目前最常用的聚類算法之一。該算法主要的優(yōu)點(diǎn)在于容易實(shí)現(xiàn)且高效，能夠得到局部最優(yōu)解；但缺點(diǎn)也很明顯，需要聚類的對(duì)象數(shù)目越多，收斂速度越慢，而且傳統(tǒng)的K-means算法在聚類過程中，使用隨機(jī)選擇的初始聚類中心，隨著迭代過程的進(jìn)行，會(huì)產(chǎn)生明顯的聚類偏差。K-means算法可以將數(shù)據(jù)中相似的對(duì)象歸到同一集群中，且K-means算法不受集群對(duì)象的限制。對(duì)象的性質(zhì)相似性越高，算法的聚類效果越好。在使用K-means算法進(jìn)行聚類分析時(shí)，先隨機(jī)選擇K個(gè)點(diǎn)，作為初始聚類中心；然后將其他數(shù)據(jù)點(diǎn)劃分到距離K個(gè)初始聚類中心最近的簇中，完成一次迭代過程；每次迭代后，計(jì)算每一類數(shù)據(jù)點(diǎn)的均值，更新類簇中心。重復(fù)前兩步操作，直至得到的聚類中心點(diǎn)不再變化，則完成聚類過程。

本文使用一種全局K-means算法分析學(xué)生成績(jī)。全局K-means算法是在K-means算法的基礎(chǔ)上，改進(jìn)了初始聚類中心的選擇過程，優(yōu)化傳統(tǒng)的K-means算法。全局K-means算法的主要原理是基于遞增來實(shí)現(xiàn)全局最優(yōu)化。該算法選取的聚類中心點(diǎn)不需要依賴于初始值，而是計(jì)算已知聚類中心點(diǎn)與其他數(shù)據(jù)點(diǎn)的聚類平方誤差函數(shù)值，然后選擇函數(shù)值最小的數(shù)據(jù)點(diǎn)，作為下一簇最佳初始聚類中心。在全局K-means算法中，一次迭代過程需要運(yùn)行N次（N表示數(shù)據(jù)量）K-means算法搜索數(shù)據(jù)集，以找到一個(gè)數(shù)據(jù)點(diǎn)使聚類平方誤差函數(shù)值最小，并將此數(shù)據(jù)點(diǎn)作為下一個(gè)簇的初始聚類中心。而K-means算法使用隨機(jī)選取的初始聚類中心點(diǎn)，隨著迭代過程的進(jìn)行，聚類結(jié)果中產(chǎn)生的聚類誤差會(huì)越來越大。全局K-means算法以犧牲時(shí)間為代價(jià)，為每一個(gè)簇選擇最佳的初始聚類中心點(diǎn)，減少了迭代過程中產(chǎn)生的聚類誤差。

全局K-means聚類算法，簡(jiǎn)化了聚類過程，將一個(gè)問題，劃分成多個(gè)子問題。該算法使用一種增量的方法，在每一次迭代過程中計(jì)算下一個(gè)簇的初始聚類中心點(diǎn)。其算法描述如下：

Step1［初始化］計(jì)算出樣本集的質(zhì)心，將其作為第一個(gè)最佳聚簇中心，設(shè)置i=1；

Step2［結(jié)束條件］i=i+1，當(dāng)i＞ K 時(shí)，算法終止；

Step3［查找下一簇最佳初始聚類中心］當(dāng)前已知 i-1個(gè)最佳聚類中心，為m1，m2，…，mi-1，可以將剩余樣本作為最佳聚簇中心，然后計(jì)算它們與已知的i-1個(gè)最優(yōu)聚類中心的誤差平方準(zhǔn)則函數(shù)。使此函數(shù)最小的樣本點(diǎn)，被選為第i個(gè)最佳聚簇中心，即 K=i的最佳聚類中心為b1，b2，…，bi-1，運(yùn)行K-means算法。誤差平方準(zhǔn)則函數(shù)如下：

Step4 讓 mj=bj，j=1，2，…，i，轉(zhuǎn)到Step2；

全局K-means算法的流程圖如圖1所示。

圖1 全局K-means算法流程圖

3 聚類有效性

聚類有效性［14］，是指使用聚類有效性評(píng)價(jià)函數(shù)評(píng)估每次迭代過程中聚類效果的方法，來衡量算法的聚類效果的優(yōu)劣。本文使用I Index［15］聚類有效性驗(yàn)證指標(biāo)作為聚類有效性函數(shù)，來衡量全局K-means算法在高校學(xué)生成績(jī)中的聚類效果。I Index指標(biāo)通過計(jì)算各聚類中心距離的最大值，來度量組間的分離度；使用聚類中各成員與聚類中心點(diǎn)的距離之和度量組內(nèi)的分離度，且I Index取值愈大，則分組效果愈佳。I Index主要原理可以由公式（2）表示：

式中，M表示聚類數(shù)；s表示第i聚類組的法向單位向量；CMi表示第i聚類的中心向量；d(s,CMi)表示向量s和CMi的歐幾里得距離。

4 基于全局K-means的學(xué)生成績(jī)分析

全局K-means算法是在K-means算法的基礎(chǔ)上，改進(jìn)了K-means算法選擇初始類簇中心的過程，減小了算法聚類的偏差，能夠得到更加準(zhǔn)確的聚類結(jié)果。鑒于全局K-means算法的原理和特點(diǎn)，采用全局K-means算法分析學(xué)生的表現(xiàn)，從而獲得簡(jiǎn)潔、直觀、準(zhǔn)確的聚類結(jié)果。此外，在全局K-means算法的聚類分析過程中，聚類個(gè)數(shù)需要提前確定，為解決此問題，本文使用I Index有效性函數(shù)，衡量算法在不同聚類數(shù)情況下聚類效果的優(yōu)劣，選擇對(duì)應(yīng)于最優(yōu)聚類結(jié)果的聚類數(shù)來對(duì)學(xué)生成績(jī)進(jìn)行分析。

基于全局K-means算法進(jìn)行學(xué)生成績(jī)分析的具體流程如下：

算法輸入：待聚類數(shù)據(jù)集X={x1，x2，…，xn}，xi∈RD（1，2，…，N）

算法輸出：最佳聚類數(shù)M及聚類中心（k1，k2，…，kbest）。

（1）初始參數(shù)：生成聚類數(shù)的搜索范圍［1，Mmax］，令M=1；

（2）設(shè)置終止條件：令M=M+1，若M＞Mmax，則完成迭代過程；

（3）使用基于全局K-means算法將X聚類為M類，并得到聚類中心點(diǎn)（k1，k2，…，kbest）；

（4）利用聚類中心點(diǎn)（k1，k2，…，kbest）求出聚類數(shù)M對(duì)應(yīng)的（2）式中的有效性指標(biāo)I(M)的值。

（5）選擇最大的有效性指標(biāo)對(duì)應(yīng)的聚類數(shù)M，作為最佳聚類數(shù)。

本文選擇處理的數(shù)據(jù)為某校學(xué)生四個(gè)學(xué)科的期末成績(jī)，人數(shù)100人，其中部分?jǐn)?shù)據(jù)如表1所示。

表1 100名學(xué)生四個(gè)學(xué)科期末成績(jī)

將所有學(xué)生數(shù)據(jù)以csv文件存儲(chǔ)，在程序中讀入csv文件，使用基于全局K-means算法對(duì)數(shù)據(jù)進(jìn)行聚類分析，得到聚類數(shù)、聚類中心以及聚類中的樣例數(shù)，如表2所示。

表2 100名學(xué)生四科期末成績(jī)初始聚類中心（保留整數(shù)）及樣例數(shù)

圖2 聚類分析結(jié)果柱狀圖

根據(jù)表2和圖2可以看出，算法將100名學(xué)生的四門課程成績(jī)分成四類。四類結(jié)果在分?jǐn)?shù)上表現(xiàn)出了很明顯的層次感。在聚類中心1中，課程成績(jī)均偏低，且低于其它三類，但與同組數(shù)據(jù)相比，差異相對(duì)較小。聚類中心2、3處，課程成績(jī)屬于中等及偏上層次，每一聚類中，課程成績(jī)相近。聚類中心四中，總體成績(jī)高于其他三個(gè)聚類中心。所以，根據(jù)上表結(jié)論，針對(duì)聚類中心1中的學(xué)生，應(yīng)該修改教學(xué)方法，并可借鑒聚類四中學(xué)生的學(xué)習(xí)方法，培養(yǎng)學(xué)生，讓其在自己成績(jī)較差學(xué)科中找到更加適合自己學(xué)習(xí)方法。并且，針對(duì)有些同學(xué)部分課程成績(jī)較高，但存在成績(jī)非常低的課程，學(xué)校應(yīng)該針對(duì)這類偏科的同學(xué)，設(shè)計(jì)針對(duì)性的培養(yǎng)方案，讓其能在偏科的科目中發(fā)現(xiàn)感興趣的知識(shí)，以此引導(dǎo)該學(xué)生主動(dòng)去發(fā)現(xiàn)、去學(xué)習(xí)。

為了對(duì)比全局K-means算法與傳統(tǒng)的K-means算法的聚類效果，對(duì)兩種算法在進(jìn)行學(xué)生成績(jī)聚類分析時(shí)的聚類中心坐標(biāo)和簇內(nèi)平均距離進(jìn)行對(duì)比，如表3所示。

表3 算法參數(shù)對(duì)比

對(duì)比試驗(yàn)主要比較兩種算法的類內(nèi)平均距離，以達(dá)到對(duì)比聚類效果的目的。兩種算法進(jìn)行對(duì)比試驗(yàn)使用的數(shù)據(jù)為某校學(xué)生四個(gè)學(xué)科的期末成績(jī)，人數(shù)100人。通過表3能夠知道，使用全局K-means算法對(duì)學(xué)生成績(jī)進(jìn)行聚類分析時(shí)，類內(nèi)數(shù)據(jù)的平均距離要小于傳統(tǒng)K-means算法的類內(nèi)數(shù)據(jù)的平均距離，說明利用全局K-means算法進(jìn)行聚類分析得到的聚類結(jié)果中，數(shù)據(jù)之間的距離更近，數(shù)據(jù)的分布更加緊密。所以全局K-means算法的聚類效果要優(yōu)于傳統(tǒng)的K-means算法。

5 結(jié)論

學(xué)生成績(jī)分析作為評(píng)價(jià)學(xué)生學(xué)習(xí)方法、學(xué)習(xí)態(tài)度的一個(gè)重要過程，衡量學(xué)校教學(xué)質(zhì)量的主要方法，隨著教育信息化的發(fā)展，實(shí)現(xiàn)高效、準(zhǔn)確的學(xué)生成績(jī)分析，對(duì)于學(xué)生成績(jī)?cè)u(píng)價(jià)，具有非常重要的應(yīng)用價(jià)值。本文使用全局K-means算法與I Index算法相結(jié)合，來執(zhí)行無監(jiān)督的學(xué)生成績(jī)分析，且聚類個(gè)數(shù)由聚類有效性指標(biāo)自動(dòng)確定。在實(shí)驗(yàn)中，通過對(duì)100名學(xué)生的四門期末成績(jī)進(jìn)行實(shí)驗(yàn)，驗(yàn)證了算法的可行性，得到了簡(jiǎn)明直觀的聚類效果，并且聚類算法對(duì)學(xué)生成績(jī)的分析結(jié)果反應(yīng)出學(xué)生當(dāng)前的學(xué)習(xí)計(jì)劃以及學(xué)習(xí)方法不當(dāng)。可以通過對(duì)學(xué)生成績(jī)的分析，為了提升學(xué)生成績(jī)，制定更加合理的學(xué)習(xí)計(jì)劃和教學(xué)方案。