顧唐杰，秦 波，蔣小菲

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴陽(yáng) 550025）

0 引 言

當(dāng)代年輕人擁有多樣化的性格，這也將導(dǎo)致部分學(xué)生在人際交往過(guò)程中會(huì)出現(xiàn)各種各樣的問題，在這些問題中室友往往擔(dān)任著非常重要的角色。良好的宿舍氛圍不但促進(jìn)了學(xué)習(xí)進(jìn)步，也提高了學(xué)生的生活質(zhì)量，為大學(xué)生心理健康起到正面積極作用。然而近幾年關(guān)于同寢室犯罪的報(bào)道卻已開始映入眼簾，拋開極端情況不談，在普通宿舍中也不時(shí)會(huì)出現(xiàn)因室友性格不同而導(dǎo)致的宿舍“小團(tuán)體”現(xiàn)象或校園霸凌問題。根據(jù)新華網(wǎng)一項(xiàng)針對(duì)大學(xué)生舍友關(guān)系的調(diào)查顯示，42.28%的學(xué)生與舍友曾經(jīng)發(fā)生矛盾；與舍友發(fā)生矛盾時(shí)，僅有47.81%的學(xué)生會(huì)選擇“積極溝通”。顯然對(duì)于部分學(xué)生的矛盾很難通過(guò)教育、引導(dǎo)途徑化解。

在此背景下智能宿舍分配方法孕育而生，2016年，上海大學(xué)的高校公寓“私人定制”計(jì)劃采用了網(wǎng)上選室友計(jì)劃。而在國(guó)外，學(xué)生也可以通過(guò)網(wǎng)絡(luò)選擇室友。為進(jìn)一步滿足學(xué)生宿舍需求，本文通過(guò)調(diào)研學(xué)生共性，對(duì)學(xué)生中性格習(xí)性相近或互補(bǔ)的學(xué)生進(jìn)行聚類，并對(duì)Chameleon算法做出改進(jìn)得到一種全新算法。

Chameleon算法是由CURE和ROCK算法演變而來(lái)，兼顧了接近度和內(nèi)部互聯(lián)度，在二維數(shù)據(jù)的聚類中取得了非常好的效果。目前，Chameleon算法也在不斷的發(fā)展中出現(xiàn)過(guò)比較典型的改進(jìn)。例如龍真真等人提出了M-Chameleon算法，改進(jìn)后不但減少了聚類過(guò)程中所需的參數(shù)，并能更加客觀地反映聚類情況。宮峰勛等人的《基于DPC算法與模塊密度的改進(jìn)Chameleon算法》中，在傳統(tǒng)算法的基礎(chǔ)上于圖劃分階段利用密度峰值算法使稀疏圖的劃分更為準(zhǔn)確，并在后續(xù)聚類過(guò)程中采用集群數(shù)據(jù)點(diǎn)相似性的函數(shù)獲得最終的聚類結(jié)果。

結(jié)合以上算法優(yōu)點(diǎn)，本文通過(guò)對(duì)Chameleon算法改進(jìn)得到KSNN-Chameleon算法。KSNNChameleon算法在針對(duì)學(xué)生宿舍分配問題時(shí)，能夠通過(guò)學(xué)生之間共性的差異進(jìn)行智能宿舍分配。在查閱相關(guān)資料和社會(huì)調(diào)查后，本文按照學(xué)生的興趣愛好、月生活水平、學(xué)習(xí)習(xí)慣、作息時(shí)間、嗜好等，對(duì)每一位學(xué)生的特點(diǎn)進(jìn)行劃分并通過(guò)Matlab軟件進(jìn)行分析推測(cè)出適合每一位學(xué)生的室友。

1 算法理論分析

本算法是在Chameleon算法的基礎(chǔ)上進(jìn)行改進(jìn)和提煉的新型KSNN-Chameleon算法。本節(jié)將介紹KSNN-Chameleon算法的理論依據(jù)，以及對(duì)傳統(tǒng)算法中各個(gè)階段的改進(jìn)。

1.1 Chameleon算法

聚類分析中的層次分析法可以籠統(tǒng)地分為：由整體分裂的方法和由多點(diǎn)凝聚的方法。這取決于層次分解當(dāng)中分解的順序，而Chameleon算法采用動(dòng)態(tài)建模的方式進(jìn)行聚類。Chameleon算法流程如圖1所示。由圖1可知，首先需要對(duì)數(shù)據(jù)項(xiàng)進(jìn)行稀疏化，然后通過(guò)相關(guān)的圖劃分算法對(duì)稀疏圖進(jìn)行劃分，從而形成多個(gè)相對(duì)連接性較高的初始子簇。最后使用凝聚層次聚類技術(shù)，重復(fù)合并相似性高的簇。即Chameleon算法是先對(duì)整體進(jìn)行分裂，又采用凝聚的方法進(jìn)行二次聚類的聚類算法。Chameleon算法最大的優(yōu)點(diǎn)在于，既考慮了每個(gè)簇的相對(duì)互連度( C，C)，又考慮到簇的相對(duì)鄰近度( C，C)，通過(guò)二者相結(jié)合的相似度函數(shù)計(jì)算數(shù)據(jù)點(diǎn)之間的距離。

圖1 Chameleon算法流程Fig.1 Chameleon algorithm flow chart

定義1 相對(duì)互連度( C，C)2個(gè)簇C和C之間的絕對(duì)互連度關(guān)于C和C的內(nèi)部互連度的規(guī)范化，即：

定義2 相對(duì)鄰近度( C，C)2個(gè)簇C和C之間的絕對(duì)接近度關(guān)于C和C的內(nèi)部接近度的規(guī)范化，公式如下：

相對(duì)互連度和相對(duì)互連度的乘積，即：

其中，是指定參數(shù)，設(shè)定兩值的權(quán)重。例如，當(dāng)1，代表2個(gè)度量標(biāo)準(zhǔn)權(quán)重相同；如果1，則Chameleon更偏重于相對(duì)接近度；反之，當(dāng)1時(shí)，則偏重相對(duì)近鄰度。

1.2 改進(jìn)稀疏化

Chameleon算法的第一個(gè)階段（稀疏化過(guò)程）是通過(guò)K最近鄰法求出數(shù)據(jù)點(diǎn)的K最近鄰圖的過(guò)程，得到的K近鄰圖被稱為數(shù)據(jù)集的稀疏圖。此方法計(jì)算數(shù)據(jù)點(diǎn)關(guān)系時(shí)采用的是歐式距離法，對(duì)于偏重于距離分析的Q型聚類問題，這種方式可以有效地將數(shù)據(jù)點(diǎn)進(jìn)行分類。然而，當(dāng)遇到利用數(shù)據(jù)相關(guān)程度進(jìn)行聚類的R型聚類問題時(shí)，這種聚類方法的適用性就會(huì)有所下降。因此，為了更好地利用稀疏圖進(jìn)行圖劃分，KSNN-Chameleon算法在稀疏化得到K近鄰圖后，將K近鄰圖轉(zhuǎn)換為加權(quán)近鄰圖。

1.2.1 利用KD樹減少總體聚類時(shí)間

由于本算法需要對(duì)K近鄰圖進(jìn)行轉(zhuǎn)換，聚類時(shí)間也隨之增加。KSNN-Chameleon在K近鄰算法的基礎(chǔ)上利用KD-tree原理對(duì)其進(jìn)行改進(jìn)，大大減少了聚類所需要的時(shí)間。

根據(jù)目標(biāo)點(diǎn)的距離度量，在輸入數(shù)據(jù)集中找出與最近的個(gè)點(diǎn)，涵蓋著個(gè)點(diǎn)的領(lǐng)域，記為N（），若N（）中某一個(gè)簇類C的出現(xiàn)的次數(shù)最多，則判定目標(biāo)點(diǎn)也屬于C。

是一種對(duì)K維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)樹形樹狀結(jié)構(gòu)進(jìn)行快速檢索。是空間二分樹的一種特殊情況。

1.2.2 加權(quán)近鄰圖

傳統(tǒng)K近鄰圖僅僅只能體現(xiàn)出數(shù)據(jù)點(diǎn)之間的位置關(guān)系和距離關(guān)系，而面對(duì)R型聚類問題時(shí)，利用歐式距離描述數(shù)據(jù)點(diǎn)之間的位置關(guān)系是不太準(zhǔn)確的。為更好地解決R型聚類中，稀疏圖依賴距離的問題，本文將得到的稀疏圖，通過(guò)近鄰度權(quán)重的方式進(jìn)行改良從而得到加權(quán)近鄰圖。利用加權(quán)近鄰圖進(jìn)行圖劃分可以更有效地避免R型聚類問題中依賴距離因素的問題。

公式如下：

其中，是分簇個(gè)數(shù)，a是點(diǎn)和被分為同一個(gè)簇的次數(shù)。若（，）≥05，則和為彼此的近鄰點(diǎn)。

交集個(gè)數(shù)表明，若兩者越相似，則所擁有的共同近鄰點(diǎn)就越多，權(quán)重越大。根據(jù)以上定義得到算法1，用以得到加權(quán)近鄰圖。

含個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集｛，，…，x｝

加權(quán)近鄰圖

1：Int中數(shù)據(jù)點(diǎn)的個(gè)數(shù)

2：For（1；；）

3： For（1；；）

4：（，）（，）；

//計(jì)算兩點(diǎn)近鄰度

5： End for

6：End for

7：If（（，）05）then

8： do∈（），∈（）

9：End if

10：If（∈（）‖∈（））then

11：σ＝Γ（）∩（）

計(jì)算兩點(diǎn)間的權(quán)值

12：End If

13：__（，，σ）

1.3 改進(jìn)圖劃分

Chameleon算法的第二階段在得到稀疏圖后會(huì)直接采用hMetis劃分算法對(duì)獲得的稀疏矩陣進(jìn)行圖劃分。hMetis是一種多層次的分割方法，在處理粗糙圖形信息上具有良好的效果并且聚類的時(shí)間更短。但考慮到hMetis算法不開放源代碼，并且hMetis算法是一種采用最小可能性切割邊緣進(jìn)行圖劃分的方法，有時(shí)會(huì)產(chǎn)生距離很遠(yuǎn)卻聚為一類的問題，所以在處理一些信息時(shí)達(dá)不到理想的聚類效果。為了更好地實(shí)現(xiàn)圖劃分，KSNN-Chameleon算法采用flood-fill法結(jié)合遞歸二分法，代替原有的hMetis算法，對(duì)得到的加權(quán)近鄰圖進(jìn)行圖劃分。詳情見算法2。

raph

多連接子簇

1：whiledo

2： For∈（）do

3： Ifisthen

4：_（）

綜合能源系統(tǒng)是能源互聯(lián)網(wǎng)的物理載體,主要著眼于解決能源系統(tǒng)自身面臨的問題和發(fā)展需求,其研究不過(guò)分強(qiáng)調(diào)何種能源占主導(dǎo)地位。

//創(chuàng)建新空間存放數(shù)據(jù)點(diǎn)

5：__

（，，）

6： End If

7： End for

8：End while

9：__（，，）

10：（，）標(biāo)記簇中的點(diǎn)

11：Forin（）do

12： Ifisthen

13：__（，，

）建立多連接簇

14： End If

15：End for

給區(qū)域內(nèi)某一個(gè)點(diǎn)上色，并對(duì)所有相鄰的點(diǎn)依次涂上的顏色，不斷填充此區(qū)域，直到區(qū)域內(nèi)的所有點(diǎn)都附上顏色。

1.4 合并階段

本算法在Chameleon聚類的第三個(gè)階段合并時(shí)主要針對(duì)2個(gè)部分進(jìn)行改良。一方面?zhèn)鹘y(tǒng)算法在針對(duì)二維數(shù)據(jù)集時(shí)，采用的相似性度量函數(shù)可以有效地將圖劃分后的各個(gè)數(shù)據(jù)簇進(jìn)行分析和合并，但是在面對(duì)三維以上的數(shù)據(jù)集時(shí)，其聚類效果會(huì)隨著維度的升高而下降。為了在高維R型聚類問題中，得到更加精準(zhǔn)的聚類簇，KSNN-Chameleon算法采用共享最近鄰相似度的方法進(jìn)行改進(jìn)，從而避免高維情況下的維數(shù)災(zāi)難。另一方面，傳統(tǒng)算法中需要反復(fù)計(jì)算目標(biāo)數(shù)據(jù)集的最優(yōu)聚類個(gè)數(shù)，這一過(guò)程消耗大量的時(shí)間，而KSNN-Chameleon算法采用第一截?cái)喾ǖ姆绞?，?duì)該過(guò)程進(jìn)行簡(jiǎn)化，可得到數(shù)據(jù)集聚類的最佳簇?cái)?shù)。

1.4.1 共享最近鄰相似度

為了解決高維度問題，本文引入共享最近鄰相似度代替?zhèn)鹘y(tǒng)相似性度量，由于共享最近鄰相似性度量在空間中主要反映的是點(diǎn)的局部結(jié)構(gòu)，因此對(duì)空間的維度并不敏感，所以可作為一種相對(duì)合適的度量方法。共享最近鄰相似度可以理解為：對(duì)于2個(gè)不同的數(shù)據(jù)點(diǎn)而言，如果彼此的相似點(diǎn)中，存在著大量重合的部分，那么即可判定這2個(gè)數(shù)據(jù)點(diǎn)也相似。如圖2所示，點(diǎn)和都有8個(gè)最近鄰居，其中有4個(gè)點(diǎn)是和都共有的，稱為共享鄰居，所以，點(diǎn)和點(diǎn)之間的最近鄰相似度為4。

圖2 共享鄰居展示圖Fig.2 Shared nearest neighbour diagram

在數(shù)據(jù)集中存在任意2點(diǎn)和，將點(diǎn)的個(gè)近鄰集合設(shè)為（），同理將的集合設(shè)為（），則點(diǎn)和的的公共鄰居集，定義如下：

對(duì)于數(shù)據(jù)集的任意數(shù)據(jù)點(diǎn)和，其共享最近鄰相似度可定義為：

1.4.2 第一截?cái)喾?/p>

為了更有效地合并子簇并減少獲取數(shù)據(jù)的時(shí)間，在子簇合并的過(guò)程中使用“第一截?cái)喾ā?。該方法的原理是：通過(guò)2個(gè)簇合并的位置視為“第一個(gè)大躍變”，此時(shí)2個(gè)簇理論上最不相似，因此只需找到第一個(gè)大躍變位置，如此就能找到最適合的分簇?？蓪⒑喜⒑蟮膶蛹?jí)視為自下而上的樹狀圖，將樹狀圖從中間劃分為上、下兩個(gè)部分，不斷切割直至找到第一大躍變點(diǎn)作為合并圖的最優(yōu)截?cái)鄶?shù)據(jù)，該數(shù)據(jù)即為數(shù)據(jù)集的最優(yōu)分簇，具體代碼詳見算法3。

合并圖

合并圖的最優(yōu)截?cái)喔叨?/p>

1： Procedure（，）

2：_（）

3：（）

4：while0 do

5：_（*）

6： If

7： return

8： else

9：

10： End if

11：End while

12：_（）

13：（）

14：For alldo∈

15：

16： Ifthen

17：

18：

19： Return

20： End If

21：End for

22：

23：Return

2 KSNN-Chameleon實(shí)現(xiàn)

KSNN-Chameleon算法與傳統(tǒng)算法均分為3個(gè)階段，傳統(tǒng)的Chameleon算法在針對(duì)二維Q型算法時(shí)，能夠得到良好的聚類效果。但其算法在面向如“宿舍分配”等多維R型聚類問題時(shí)，難以維持二維情況下的精準(zhǔn)聚類。因此本算法在傳統(tǒng)算法的各個(gè)階段都進(jìn)行了不同程度的改良，使得改良后的算法在面對(duì)高維度的R型聚類問題時(shí)也能取得良好的聚類效果。

2.1 構(gòu)建加權(quán)近鄰圖

KSNN-Chameleon算法以加權(quán)近鄰圖的方式代替原有的K近鄰圖作為數(shù)據(jù)集的稀疏圖。首先采用KD樹和K近鄰算法相結(jié)合的方式，獲取K近鄰圖，然后，根據(jù)公式（3）計(jì)算出每個(gè)點(diǎn)的相似度，再通過(guò)公式（4）和公式（5）計(jì)算出每個(gè)點(diǎn)近鄰點(diǎn)集，得到由近鄰點(diǎn)集構(gòu)造出的加權(quán)近鄰圖。具體步驟如下所示。

初始數(shù)據(jù)集，分類參數(shù)

加權(quán)近鄰圖（稀疏圖）

構(gòu)建KD樹，通過(guò)輸入?yún)?shù)對(duì)相似度矩陣進(jìn)行初始化。

從KD樹的樹根開始不斷遍歷，將所有數(shù)據(jù)劃分在不同的區(qū)域當(dāng)中。

根據(jù)數(shù)據(jù)集中的數(shù)據(jù)，利用定義3中的公式（3）算出每個(gè)點(diǎn)間的相似度，構(gòu)建相似度矩陣。

在KD樹的每個(gè)區(qū)域中取前個(gè)最相似的值分類更新相似度矩陣，得到K-最近鄰相似矩陣。

利用算法1，分別求出不同值時(shí)得到相似矩陣情況，根據(jù)定義6、7計(jì)算數(shù)據(jù)點(diǎn)間的近鄰權(quán)重，得到加權(quán)近鄰圖。

2.2 加權(quán)近鄰圖的劃分與合并

在KSNN-Chameleon算法的第二階段和第三階段中，對(duì)加權(quán)近鄰圖進(jìn)行圖劃分時(shí)，首先利用遞歸二分法和洪水覆蓋法（flood-fill）對(duì)稀疏圖進(jìn)行圖劃分如算法2所示，然后采用定義10中的公式（7）計(jì)算出共享相似度，對(duì)圖劃分后得到的子簇進(jìn)行自下而上的層次聚類，此時(shí)可以得到數(shù)據(jù)集的合并樹狀圖。此后采用算法3中的第一截跳法求出適合于數(shù)據(jù)集的最佳聚類數(shù)，反復(fù)合并劃分圖直到滿足最終簇?cái)?shù)完成聚類，具體步驟如下所示。

加權(quán)近鄰圖，聚類簇?cái)?shù)

個(gè)簇的聚類

將加權(quán)近鄰圖帶入算法2中，利用flood-fill方法對(duì)加權(quán)近鄰圖進(jìn)行圖劃分，得到分簇。

結(jié)合定義10中公式（7）求出各個(gè)子簇之間的共享相似度，推算子簇之間的相似關(guān)系。

通過(guò)共享相似度對(duì)數(shù)據(jù)集進(jìn)行自下而上的層次聚類，并將聚類結(jié)果視為樹狀圖。

將樹狀圖帶入算法3中，利用第一截?cái)喾ㄇ蟪鼍垲惔財(cái)?shù)。

將得到的簇?cái)?shù)與聚類簇?cái)?shù)對(duì)比，若不同則返回Step 2；若相同，則此時(shí)的聚類結(jié)果即為最終的聚類結(jié)果。

結(jié)合KSNN-Chameleon算法三個(gè)階段所繪制的大致流程如圖3所示。

圖3 KSNN-Chameleon算法總流程Fig.3 Flow chart of KSNN-Chameleon algorithm

3 實(shí)驗(yàn)數(shù)據(jù)分析

3.1 KSNN-Chameleon評(píng)估

為驗(yàn)證KSNN-Chameleon算法的可行性，本文采用Matlab測(cè)試數(shù)據(jù)集中具有代表性的4個(gè)測(cè)試數(shù)據(jù)集、即Aggregation、Iris、Seeds、Wine數(shù)據(jù)集對(duì)改良算法進(jìn)行測(cè)試，并通過(guò)幾種聚類評(píng)估的基準(zhǔn)驗(yàn)證KSNN-Chameleon算法對(duì)于高維度的數(shù)據(jù)集具有良好的聚類效果。在與傳統(tǒng)算法進(jìn)行對(duì)比后得到的聚 類結(jié)果見表1。

表1 不同維度下2種算法聚類對(duì)比Tab.1 Clustering comparison of two algorithms in different dimensions

KSNN-Chameleon算法針對(duì)Aggregation二維數(shù)據(jù)集聚類后的結(jié)果如圖4所示，在面向二維數(shù)據(jù)集時(shí)，KSNN-Chameleon算法與傳統(tǒng)算法得出的結(jié)果圖基本一致。圖5為Iris（四維數(shù)據(jù)集）在三維空間中的展示圖，通過(guò)對(duì)比后證明在高維聚類的情況中，KSNN-Chameleon算法比傳統(tǒng)Chameleon算法的聚類更加完善，其中聚類精度平均提升了20.88%，聚類時(shí)間平均提升了2.73%。實(shí)驗(yàn)證明在面對(duì)R型高維度聚類問題時(shí)，KSNN-Chameleon算法仍然能具有較好的穩(wěn)定性與聚類精度。

本實(shí)驗(yàn)對(duì)289名在校學(xué)生進(jìn)行調(diào)研，并將數(shù)據(jù)整理為表，見表2。結(jié)合圖4、圖5和表2中數(shù)據(jù)可看出，對(duì)于二維數(shù)據(jù)集而言，KSNN-Chameleon算法的聚類精度沒有明顯地高于傳統(tǒng)Chameleon算法，僅僅是略高于傳統(tǒng)型。但當(dāng)數(shù)據(jù)集的維度變大時(shí)，傳統(tǒng)Chameleon算法的聚類效果明顯下降，而改進(jìn)型則有了顯著的提升，即KSNN-Chameleon算法更適用于高維度聚類。在對(duì)比二者所消耗的時(shí)間時(shí)，發(fā)現(xiàn)KSNN-Chameleon算法和Chameleon算法所消耗的時(shí)間幾乎沒有很大的差別。但在二維以上環(huán)境中，KSNN-Chameleon算法所消耗的時(shí)間還是略小于傳統(tǒng)算法的，這是由于在稀疏化階段，KSNNChameleon算法為了更好地適應(yīng)高維聚類，在傳統(tǒng)算法只使用K近鄰圖的基礎(chǔ)上，又對(duì)數(shù)據(jù)進(jìn)行了近鄰加權(quán)的操作，所以增加了時(shí)間的消耗。同時(shí)，該算法為了抵消這一部分操作帶來(lái)的時(shí)間影響，在K近鄰法中又增加了KD樹的概念，減少了部分內(nèi)存和時(shí)間的多余損耗，甚至在高維情況下還有一定的提升。

圖4 KSNN-Chameleon算法對(duì)Aggregation數(shù)據(jù)集聚類結(jié)果Fig.4 The clustering results of Aggregation dataset using the KSNN-Chameleon algorithm

圖5 KSNN-Chameleon算法對(duì)Iris數(shù)據(jù)集聚類結(jié)果Fig.5 The clustering results of Iris dataset using the KSNNChameleon algorithm

表2 StuData信息Tab.2 StuData information

3.2 實(shí)驗(yàn)條件和數(shù)據(jù)來(lái)源

實(shí)驗(yàn)測(cè)試采用的硬件環(huán)境如下：CPU為i5-8300H，內(nèi)存為8 GB。運(yùn)行環(huán)境為Windows 10操作系統(tǒng)。軟件環(huán)境為IntelliJ IDEA 2020.3.4 x64、Matlab2020b。語(yǔ)言為Matlab、JAVA。

3.3 數(shù)據(jù)集稀疏化

以Matlab中的二維數(shù)據(jù)集Aggregation和學(xué)生調(diào)查的五維數(shù)據(jù)集StuData為例，將二維數(shù)據(jù)集Aggregation展示在二維平面中，StuData作為五維數(shù)據(jù)集將其中3個(gè)特征向量的數(shù)據(jù)抽取出來(lái)展示在三維坐標(biāo)系中。結(jié)合第1節(jié)中的稀疏化步驟，針對(duì)數(shù)據(jù)集Aggregation取值為10，然后通過(guò)傳統(tǒng)Chameleon算法以相似度計(jì)算得到的近鄰圖如圖6（a）所示，通過(guò)改進(jìn)型Chameleon算法得到的加權(quán)近鄰圖如圖6（b）所示，可以看出兩者在同樣的值和二維環(huán)境中得到的近鄰圖相似。按照同樣的步驟，在五維數(shù)據(jù)集StuData中取值為10后，通過(guò)傳統(tǒng)算法得到的近鄰圖如圖6（c）所示，而通過(guò)KSNNChameleon算法得到的加權(quán)近鄰圖如圖6（d）所示。

圖6 對(duì)不同數(shù)據(jù)集使用傳統(tǒng)算法和改進(jìn)算法稀疏化Fig.6 Using the traditional algorithm and the improved algorithm to sparsely process different data sets

由圖6可以看出在高維度情況下，KSNNChameleon算法的稀疏化結(jié)果更加精確，并且沒有出現(xiàn)遠(yuǎn)點(diǎn)聚類情況。

3.4 通過(guò)KSNN-Chameleon宿舍分配

本文通過(guò)問卷調(diào)查的形式訪問了289名在校學(xué)生的共7項(xiàng)意愿，從而整理得到了五維數(shù)據(jù)集StuData。在通過(guò)對(duì)每一項(xiàng)指標(biāo)詳盡的分配權(quán)重后，對(duì)其采用多種不同形式的聚類算法進(jìn)行聚類，模擬出宿舍分寢情況。采用聚類評(píng)估的方式，對(duì)這些聚類方法進(jìn)行評(píng)估，驗(yàn)證這些算法在面對(duì)高維聚類時(shí)的性能優(yōu)劣，對(duì)比結(jié)果見表3。

表3 采用不同算法對(duì)StuData進(jìn)行聚類Tab.3 Clustering StuData with different algorithms

由表3可看出，將KSNN-Chameleon算法與目前幾種主流聚類算法，包括：傳統(tǒng)Chameleon算法、M-Chameleon算法、K-means、CURE、DPC算法，進(jìn)行對(duì)比發(fā)現(xiàn)，針對(duì)五維數(shù)據(jù)集StuData和KSNNChameleon算法的聚類精度是最高的。對(duì)6種算法的值進(jìn)行對(duì)比后，發(fā)現(xiàn)KSNN-Chameleon算法除了略低于CURE算法外，值都高于其它算法。對(duì)測(cè)試數(shù)據(jù)集重疊程度進(jìn)行測(cè)量的值進(jìn)行比對(duì)后，發(fā)現(xiàn)KSNN-Chameleon算法依然擁有良好的表現(xiàn)，僅略低于DPC算法。在聚類時(shí)間上，由于KSNN-Chameleon算法在聚類過(guò)程中需要對(duì)稀疏圖進(jìn)行加權(quán)，所以運(yùn)行的時(shí)間也相對(duì)延長(zhǎng)了。對(duì)比傳統(tǒng)Chameleon算法，KSNN-Chameleon算法的聚類精度平均提升了0.165，值平均提升了0.205，值提升了0.181，在面對(duì)高維R型聚類問題時(shí)明顯更加穩(wěn)定，證明在高維環(huán)境中KSNN-Chameleon算法能夠進(jìn)行更有效的聚類。

在對(duì)比多種算法后，本文采用KSNNChameleon算法對(duì)StuData的數(shù)據(jù)圖和聚類結(jié)果圖進(jìn)行分析，圖7為三維環(huán)境中展示數(shù)據(jù)集StuData的所有數(shù)據(jù)點(diǎn)，圖8為使用傳統(tǒng)Chameleon算法對(duì)數(shù)據(jù)進(jìn)行聚類后的結(jié)果圖。圖9為通過(guò)KSNNChameleon算法對(duì)數(shù)據(jù)集進(jìn)行聚類后的結(jié)果圖。通過(guò)圖8和圖9的對(duì)比可以看出，通過(guò)KSNNChameleon算法得到的聚類圖相較Chameleon聚類得到的結(jié)果聚類圖更加均勻，每個(gè)簇中的數(shù)據(jù)也更加平均和接近。證明KSNN-Chameleon算法對(duì)傳統(tǒng)算法的改良是有效的。

圖7 StuData三維環(huán)境中數(shù)據(jù)圖Fig.7 Data graph of StuData in 3D environment

圖8 StuData通過(guò)傳統(tǒng)Chameleon算法進(jìn)行聚類Fig.8 StuData clustering by traditional Chameleon algorithm

圖9 StuData通過(guò)KSNN-Chameleon算法進(jìn)行聚類Fig.9 StuData clustering by KSNN-Chameleon algorithm

研究針對(duì)StuData數(shù)據(jù)集中289名學(xué)生進(jìn)行聚類后，將每一簇的學(xué)生按照每4人一組模擬為一個(gè)宿舍，繪制成宿舍分配表發(fā)放到這289名學(xué)生手中，并再次對(duì)學(xué)生進(jìn)行調(diào)研回訪。在289名學(xué)生中有65.05%的學(xué)生愿意按照此宿舍分配表的方式進(jìn)行換寢，另外34.95%的學(xué)生認(rèn)為維持原有的宿舍分配也不錯(cuò)。

4 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)的Chameleon算法進(jìn)行改進(jìn)，提出基于加權(quán)近鄰法的KSNN-Chameleon算法，在針對(duì)R型高階聚類問題時(shí)能夠有著良好的聚類效果。算法首先在聚類的稀疏化階段采用了加權(quán)近鄰圖的方法，有效避免了在R型聚類中使用距離為參照標(biāo)準(zhǔn)的問題。然后用洪水覆蓋法（flood-fill）代替原有的hMetis算法，對(duì)加權(quán)近鄰圖的處理更加地細(xì)膩。最后利用共享近鄰相似度和第一截?cái)喾?，使得在高維環(huán)境中也能更好地將數(shù)據(jù)進(jìn)行聚類，而不出現(xiàn)分散的問題。分析可知，KSNN-Chameleon算法在聚類的準(zhǔn)確率和精度方面對(duì)比傳統(tǒng)算法均有所提高。KSNN-Chameleon算法對(duì)比傳統(tǒng)Chameleon算法的聚類精度提升了20.88%，聚類時(shí)間上則提升了2.73%，由此證明KSNN-Chameleon算法在面對(duì)高維R型聚類問題時(shí)更加穩(wěn)定。