一種基于改進(jìn)型Chameleon算法的宿舍分配方法

顧唐杰，秦 波，蔣小菲

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

0 引 言

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

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

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

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

1 算法理論分析

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

1.1 Chameleon算法

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

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

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

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

相對互連度和相對互連度的乘積，即：

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

1.2 改進(jìn)稀疏化

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

1.2.1 利用KD樹減少總體聚類時間

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

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

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

1.2.2 加權(quán)近鄰圖

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

公式如下：

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

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

含個數(shù)據(jù)點的數(shù)據(jù)集｛，，…，x｝

加權(quán)近鄰圖

1：Int中數(shù)據(jù)點的個數(shù)

2：For（1；；）

3： For（1；；）

4：（，）（，）；

//計算兩點近鄰度

5： End for

6：End for

7：If（（，）05）then

8： do∈（），∈（）

9：End if

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

11：σ＝Γ（）∩（）

計算兩點間的權(quán)值

12：End If

13：__（，，σ）

1.3 改進(jìn)圖劃分

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

raph

多連接子簇

1：whiledo

2： For∈（）do

3： Ifisthen

4：_（）

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

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

5：__

（，，）

6： End If

7： End for

8：End while

9：__（，，）

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

11：Forin（）do

12： Ifisthen

13：__（，，

）建立多連接簇

14： End If

15：End for

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

1.4 合并階段

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

1.4.1 共享最近鄰相似度

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

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

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

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

1.4.2 第一截斷法

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

合并圖

合并圖的最優(yōu)截斷高度

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實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

個簇的聚類

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

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

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

將樹狀圖帶入算法3中，利用第一截斷法求出聚類簇數(shù)。

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

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

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

3 實驗數(shù)據(jù)分析

3.1 KSNN-Chameleon評估

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

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

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

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

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

圖5 KSNN-Chameleon算法對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ù)據(jù)來源

實驗測試采用的硬件環(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。語言為Matlab、JAVA。

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

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

圖6 對不同數(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)點聚類情況。

3.4 通過KSNN-Chameleon宿舍分配

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

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

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

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

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

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

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

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

4 結(jié)束語

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