浦慧忠

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

0 引言

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

研究可知，聚類就是將一個(gè)數(shù)據(jù)集劃分為若干組或類的過程。通過對(duì)數(shù)據(jù)進(jìn)行分組（目的），若組內(nèi)的相似性越大、組間的差距越大，聚類效果就越好（評(píng)價(jià)標(biāo)準(zhǔn)）。而聚類分析就是致力于發(fā)現(xiàn)這些數(shù)據(jù)對(duì)象之間的關(guān)系，期寄在相似的基礎(chǔ)上收集數(shù)據(jù)來分類。聚類大多是應(yīng)用在數(shù)據(jù)挖掘、數(shù)據(jù)分析領(lǐng)域，并屬于機(jī)器學(xué)習(xí)中非監(jiān)督學(xué)習(xí)的范疇。目前，已經(jīng)比較成功地解決了低維數(shù)據(jù)的聚類問題。但由于實(shí)際應(yīng)用中存在數(shù)據(jù)的復(fù)雜性，特別是面對(duì)高維數(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é)果對(duì)比）。聚類效果的好壞主要取決于2 個(gè)因素：一是衡量距離的方法（distance measurement），二是聚類算法（algorithm）的選擇。聚類分析的核心是選擇合適的聚類算法，目前許多聚類算法在小于200 個(gè)數(shù)據(jù)對(duì)象的情況下成效明顯，但對(duì)于一個(gè)大規(guī)模數(shù)據(jù)庫，將導(dǎo)致結(jié)果有很大的偏差。因此，亟需研發(fā)出一個(gè)具有高度可伸縮性的聚類算法。迄今為止，高維聚類分析已成為一個(gè)重要研究方向，同時(shí)也是聚類技術(shù)的難點(diǎn)。

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

1 k-means 算法

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

1.1 算法原理

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

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

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

計(jì)算每個(gè)（有變化）聚類的平均值（中心對(duì)象）。

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

1.2 算法優(yōu)缺點(diǎn)

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

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

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

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

（3）對(duì)噪點(diǎn)過于敏感。因?yàn)樗惴ㄊ腔诰档模登笕∩嫌袝r(shí)也并不簡單。如：對(duì)于球形簇的分組效果較好，而對(duì)非球型簇，特別是不同尺寸、不同密度的簇分組效果卻欠佳。如果初始點(diǎn)選擇不當(dāng)，最終的分組效果就會(huì)存在很大的差異，如圖2 所示。

圖2 初始點(diǎn)選擇后的分組效果對(duì)比圖Fig.2 Comparison chart of grouping effect of initial points selection

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果驗(yàn)證與分析

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

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

2.1 聚類分析

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

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

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

2.2 聚類結(jié)果評(píng)價(jià)

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

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

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

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

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

表2 聚類評(píng)價(jià)和解釋Tab.2 Cluster evaluation and interpretation

3 結(jié)束語

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