k-means 聚類分析算法在人工智能+個性化學(xué)習(xí)系統(tǒng)中的應(yīng)用

浦慧忠

（無錫城市職業(yè)技術(shù)學(xué)院，江蘇 無錫 214153）

0 引言

通常情況下，人們在逛電商網(wǎng)站時都會收到一些推銷活動的通知，但該客戶之前并沒有關(guān)注過那些商品。那么，這些電商網(wǎng)站是依據(jù)什么決定給客戶推銷該商品的呢？究其原因就在于電商網(wǎng)站會根據(jù)用戶的年齡、性別、地址以及歷史數(shù)據(jù)等等信息，將其分為：“年輕白領(lǐng)”、“一家三口”、“家有一老”、”初得子女“等類型，在此基礎(chǔ)上就會根據(jù)用戶的特征類型，向其推送不同的優(yōu)惠活動。研究中，利用這些數(shù)據(jù)將用戶分為不同的類別時，就會用到聚類分析。

研究可知，聚類就是將一個數(shù)據(jù)集劃分為若干組或類的過程。通過對數(shù)據(jù)進(jìn)行分組（目的），若組內(nèi)的相似性越大、組間的差距越大，聚類效果就越好（評價標(biāo)準(zhǔn)）。而聚類分析就是致力于發(fā)現(xiàn)這些數(shù)據(jù)對象之間的關(guān)系，期寄在相似的基礎(chǔ)上收集數(shù)據(jù)來分類。聚類大多是應(yīng)用在數(shù)據(jù)挖掘、數(shù)據(jù)分析領(lǐng)域，并屬于機(jī)器學(xué)習(xí)中非監(jiān)督學(xué)習(xí)的范疇。目前，已經(jīng)比較成功地解決了低維數(shù)據(jù)的聚類問題。但由于實際應(yīng)用中存在數(shù)據(jù)的復(fù)雜性，特別是面對高維數(shù)據(jù)和大型數(shù)據(jù)的情況下，現(xiàn)有算法的性能則亟待改進(jìn)。

隨著技術(shù)的進(jìn)步，數(shù)據(jù)收集越來越容易，導(dǎo)致數(shù)據(jù)庫規(guī)模越來越大、復(fù)雜性越來越高，其維度（屬性）通常可以達(dá)到成百上千維，甚至更高。因此，許多在低維數(shù)據(jù)空間表現(xiàn)良好的聚類方法往往在高維空間上無法獲得好的效果（圖1 為二維和三維空間下的聚類結(jié)果對比）。聚類效果的好壞主要取決于2 個因素：一是衡量距離的方法（distance measurement），二是聚類算法（algorithm）的選擇。聚類分析的核心是選擇合適的聚類算法，目前許多聚類算法在小于200 個數(shù)據(jù)對象的情況下成效明顯，但對于一個大規(guī)模數(shù)據(jù)庫，將導(dǎo)致結(jié)果有很大的偏差。因此，亟需研發(fā)出一個具有高度可伸縮性的聚類算法。迄今為止，高維聚類分析已成為一個重要研究方向，同時也是聚類技術(shù)的難點。

圖1 二維、三維空間下的聚類Fig.1 Clustering in two-dimensional and three-dimensional spaces

1 k-means 算法

通過研究經(jīng)典和常用的聚類方法，并分析比較各自的優(yōu)缺點后可以發(fā)現(xiàn)：k-means 算法不僅容易理解，而且也容易用代碼實現(xiàn)。k-means 算法采用基于劃分的方法，簡單易行、效率高，現(xiàn)已廣泛應(yīng)用于大規(guī)模數(shù)據(jù)的聚類分析中，目前絕大多數(shù)聚類分析的研究均圍繞著該算法進(jìn)行擴(kuò)展和改進(jìn)。

1.1 算法原理

k-means 中的是指簇的個數(shù)，需預(yù)先指定。迭代時選擇簇內(nèi)樣本的均值向量作為簇的中心。k-means 聚類算法的核心思想是把若干數(shù)據(jù)對象劃分為個聚類，使每個聚類中的數(shù)據(jù)點到該聚類中心的平方和最小。算法的主要步驟如下：

從若干數(shù)據(jù)對象中任意選擇個對象作為初始聚類中心。

根據(jù)每個聚類對象的均值（中心對象），計算每個對象到這些中心對象的距離，并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分。

計算每個（有變化）聚類的平均值（中心對象）。

循環(huán)Step2、Step3，直到每個聚類不再發(fā)生變化為止。

1.2 算法優(yōu)缺點

k-means 算法的優(yōu)勢主要有：簡單、易于理解和實現(xiàn)，只需要計算點和簇中心之間的距離即可，所以運(yùn)算速度非?？?；收斂快，一般僅需5～10 次迭代即可；高效，時間復(fù)雜度為（**）。

對于k-means 算法存在的問題，可做分述如下：

（1）必須設(shè)置簇的數(shù)量（預(yù)先給定值）。由于是先驗給定的，但值卻往往難于確定，特別是對于大型數(shù)據(jù)集，在算法啟動前是無法精準(zhǔn)給出的。

（2）k-means 算法對初始選取的聚類中心點是敏感的，需要研發(fā)出初始隨機(jī)種子點啟動算法，且隨機(jī)種子點的選取至關(guān)重要。不同的隨機(jī)種子點得到的聚類結(jié)果完全不同。一般從隨機(jī)選擇的聚類中心開始執(zhí)行，可能會在算法的不同運(yùn)行過程中，產(chǎn)生不同的聚類結(jié)果，這也會導(dǎo)致結(jié)果無法復(fù)現(xiàn)且缺乏一致性。

（3）對噪點過于敏感。因為算法是基于均值的，但均值求取上有時也并不簡單。如：對于球形簇的分組效果較好，而對非球型簇，特別是不同尺寸、不同密度的簇分組效果卻欠佳。如果初始點選擇不當(dāng)，最終的分組效果就會存在很大的差異，如圖2 所示。

圖2 初始點選擇后的分組效果對比圖Fig.2 Comparison chart of grouping effect of initial points selection

1.3 改進(jìn)方法總述

針對k-means 算法存的問題，考慮到本文重點研究的學(xué)生成績數(shù)據(jù)庫的實際問題，在開展聚類分析過程中，本文將進(jìn)行適當(dāng)?shù)膬?yōu)化，以減少算法缺陷導(dǎo)致的不良結(jié)果。

研究中，需選取合適的值，就要用到先驗知識。常見的方法有拍腦袋法、肘部法則（Elbow Method）、間隔統(tǒng)計量（Gap Statistic）、輪廓系數(shù)（Silhouette Coefficient）、Canopy 算法等。比照這些方法，本文借鑒選用一種簡單且操作簡便、基于平方誤差的計算方法來確定值。

針對值需事先給定的問題，在沒有先驗經(jīng)驗的情況下，可采取幾種不同的值嘗試，分別計算平方誤差（值），找到“拐點”?；谄椒秸`差的計算公式為：

其中，為簇內(nèi)樣本數(shù)，為簇的中心。值越小，說明簇內(nèi)樣本距離越小，相似度越高。

研究得到的平方誤差曲線如圖3 所示。由圖3可知，當(dāng)5 時，聚類性能基本達(dá)到最優(yōu)效果；當(dāng)繼續(xù)增加時，性能并沒有明顯變化，則可將最終的聚類算法值選擇為5。

圖3 平方誤差曲線Fig.3 Square error curve

k-means 算法是初值敏感的，選擇不同的初始值可能導(dǎo)致不同的簇劃分規(guī)則。如k-means++算法就是針對K-means 聚類算法中隨機(jī)選取初始聚類中心的缺陷問題的改進(jìn)，這是一種基于數(shù)據(jù)分布選取初始聚類中心的算法，整體上與k-means 算法相差不大，同樣是采取迭代更新的思想。算法的主要改進(jìn)是在第一步選取個初始聚類中心時，不再是在整個數(shù)據(jù)集中隨機(jī)選取個數(shù)據(jù)對象作為初始聚類中心，而是遵循初始的聚類中心之間的距離應(yīng)盡可能遠(yuǎn)的原則，選取個初始聚類中心。

借鑒k-means++算法的一些思想，本文對于初始值的選取采用簡化的辦法。在選擇初始點時，可以選擇距離盡可能遠(yuǎn)的點；在預(yù)處理階段，對數(shù)據(jù)進(jìn)行歸一化處理時，可考慮剔除噪點。如果99%的學(xué)生成績在20～95 之間，只有1%的學(xué)生成績超過95或是低于20，則在做歸一化處理時，可選取99%學(xué)生中成績的最高分作為最大值，剩余1%的學(xué)生成績直接置為1 即可。

2 實驗結(jié)果驗證與分析

現(xiàn)行的以考試成績絕對分?jǐn)?shù)來衡量學(xué)生學(xué)習(xí)狀況的方法比較主觀，且評價方式過于單一。例如：成績在90 分以上為優(yōu)秀，成績在60 分以上為及格，低于60 分為不及格等。這樣的處理方法雖簡便易行，但存在一些不妥之處，如成績中有用信息未獲重視、成績絕對分值相差不大但劃分后相差很大、總體成績的動態(tài)分布情況不合理等現(xiàn)象出現(xiàn)，導(dǎo)致無法公正、合理、有效地評價學(xué)生成績。充分挖掘、且利用隱含在學(xué)生成績中的有用信息，并采取針對性的措施，如能從學(xué)生期中考試成績挖掘出一些預(yù)判性的有用信息，并采取積極有效措施，就有可能提高學(xué)生的期末考試成績。為此，通過上述聚類方法嘗試進(jìn)行相關(guān)成績分析很有必要。

為了實現(xiàn)系統(tǒng)的可視化，采用Java 與PHP 混合編程，借鑒經(jīng)典的k-means 聚類算法，優(yōu)化和改進(jìn)初始點及值的確定，并同時最大限度地保證系統(tǒng)的穩(wěn)定性。主要數(shù)據(jù)源來自北京超星學(xué)習(xí)通平臺中具體課程相關(guān)班級的部分科目期中考試成績，導(dǎo)出數(shù)據(jù)為Excel 表格形式，成績均為百分制。前期進(jìn)行數(shù)據(jù)清洗，主要去除一些無關(guān)或空白數(shù)據(jù)，如學(xué)生缺考將會置零并刪除，以免影響聚類結(jié)果。

2.1 聚類分析

基于聚類分析的成績劃分是將原有絕對成績劃分改為相對成績的劃分。每個簇組成一個成績?nèi)海總€簇中心的數(shù)據(jù)就是該成績?nèi)旱闹行某煽?。這些中心成績是學(xué)生成績等級劃分的參考標(biāo)準(zhǔn)之一，因此用于學(xué)生成績評價也更為準(zhǔn)確。通過聚類分析，將學(xué)生成績劃歸到各個簇中，簇的大小、形狀、中心值可以用來評價教學(xué)效果的好壞。

通常，聚類個數(shù)值要盡可能地接近所用的聚類變量的個數(shù)。如：5 個變量用于聚類分析，通常就會分為5 個類。類個數(shù)太多不利于對類的解釋；太少不利于分開，并降低了類的同質(zhì)性。比較可行的辦法是每次用不同類的個數(shù)來做實驗并對比所得結(jié)果，確定最理想的類個數(shù)。通過k-means算法聚類劃分學(xué)生成績數(shù)據(jù)，類的個數(shù)從1 到8，依次運(yùn)行一遍，計算類內(nèi)平方誤差和J（1，2，3，…，8），繪出J和值個數(shù)的曲線圖。在J值隨變化的曲線上，其拐點對應(yīng)的類別數(shù)基本接近于最優(yōu)聚類個數(shù)。文中繪制得到的值選取曲線如圖4 所示。由圖4 可見，J隨的增加而單調(diào)減少。當(dāng)值為68 時，J呈平緩狀態(tài)，因此可以認(rèn)為6 是比較合適的聚類個數(shù)。

圖4 k 值選取曲線圖Fig.4 k value selection curve

2.2 聚類結(jié)果評價

從學(xué)生成績數(shù)據(jù)庫中隨機(jī)選擇6 個學(xué)生的學(xué)習(xí)成績作為初始聚類中心，經(jīng)過k-means 聚類算法生成6 個類別，見表1。

表1 生成的最終聚類中心Tab.1 Generated final cluster centers

在學(xué)生成績評價中通過聚類分析發(fā)現(xiàn)，每一個類就是一個成績?nèi)?，處于每個類中心的數(shù)據(jù)就是該成績?nèi)旱闹行某煽儭＠纾旱? 類學(xué)生的計算機(jī)基礎(chǔ)成績隨中心值82.51 的變化與第6 類學(xué)生的大學(xué)英語成績隨中心值74.23 的變化如圖5 所示。由圖5 可以看出相近的成績都被劃分到了同一類，避免了采用傳統(tǒng)劃分方法可能出現(xiàn)“學(xué)生成績差別不大，劃分后結(jié)果可能相差很大”的情況。另外，每一科成績隨中心的變化就是相對于整體成績的分布情況。

圖5 學(xué)生成績隨聚類中心變化圖Fig.5 Changes in student grades with cluster centers

總之，該聚類分析不僅可以使學(xué)生清楚自己相對于整體成績的位置，還可以體現(xiàn)某類學(xué)生在某些學(xué)科的不足，從而提醒任課教師采取針對性措施。從表1 中所劃分的類的人數(shù)及中心成績可以看出，所有學(xué)生前三門基礎(chǔ)學(xué)科成績較低，尤其大學(xué)英語成績最低，而思政課程的成績就相對較高。同時也可以看出，每一類學(xué)生哪些學(xué)科成績相對偏低，從而制定有效改進(jìn)的解決辦法，提高學(xué)生期末考試的成績。比如第二類別英語成績最低的這一部分學(xué)生，可以反映給學(xué)校教務(wù)處適當(dāng)增加英語學(xué)科的課時，具體評價解釋見表2。

表2 聚類評價和解釋Tab.2 Cluster evaluation and interpretation

3 結(jié)束語

隨著人工智能技術(shù)在各類信息化領(lǐng)域中的不斷深入，學(xué)習(xí)過程中數(shù)據(jù)源的大量涌現(xiàn)，作為常見的無監(jiān)督學(xué)習(xí)的典型算法—k-means 聚類算法，對其在個性化學(xué)習(xí)系統(tǒng)中開展相關(guān)應(yīng)用研究有著廣闊的前景。本文從經(jīng)典的k-means 算法出發(fā)，探索并尋找一種效率更高、穩(wěn)定性更好的聚類分析方法，并在個性化學(xué)習(xí)系統(tǒng)中進(jìn)行實踐，取得了不錯的應(yīng)用效果，也為后續(xù)的進(jìn)一步研究提供了有益借鑒。