劉作國(guó)，陳笑蓉

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025)

?

高斯加權(quán)的重構(gòu)性K-NN算法研究

劉作國(guó)，陳笑蓉

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025)

該文提出基于高斯加權(quán)距離以及聚類(lèi)重構(gòu)機(jī)制的K-NN文本聚類(lèi)算法。文章提出K-NN近鄰域的概念，通過(guò)高斯加權(quán)的近鄰域算法實(shí)施K-NN聚類(lèi)。利用高斯函數(shù)根據(jù)樣本與聚類(lèi)中心的距離為樣本賦權(quán)，計(jì)算聚類(lèi)距離。基于近鄰域權(quán)重和聚類(lèi)密度對(duì)形成的聚類(lèi)實(shí)施重構(gòu)，實(shí)現(xiàn)聚類(lèi)數(shù)目的自適應(yīng)調(diào)整。使用拆分算子拆分稀疏聚類(lèi)并調(diào)整異常樣本；使用合并算子合并相似聚類(lèi)。實(shí)驗(yàn)顯示聚類(lèi)重構(gòu)機(jī)制能夠有效地提高聚類(lèi)的準(zhǔn)確率及召回率，增加聚類(lèi)密度，使得形成的聚類(lèi)結(jié)果更加合理。

文本聚類(lèi)；K-NN算法；高斯加權(quán)；近鄰域規(guī)則；聚類(lèi)重構(gòu)

1 引言

K-NN聚類(lèi)算法簡(jiǎn)潔實(shí)用，是一類(lèi)常見(jiàn)的文本聚類(lèi)算法。K-NN算法選定樣本子集形成初始聚類(lèi)分布，根據(jù)初始分布將測(cè)試樣本劃入最近聚類(lèi)。K-NN算法初始聚類(lèi)的選擇直接影響聚類(lèi)結(jié)果，聚類(lèi)過(guò)程缺少對(duì)結(jié)果的檢測(cè)和調(diào)整機(jī)制，難以實(shí)現(xiàn)聚類(lèi)數(shù)目的自適應(yīng)變更[1]。

本文主要針對(duì)K-NN算法的距離判定策略和聚類(lèi)重構(gòu)機(jī)制進(jìn)行了研究，通過(guò)高斯加權(quán)算法實(shí)施距離度量，判定樣本歸屬。采用聚類(lèi)重構(gòu)機(jī)制對(duì)不合理聚類(lèi)實(shí)施拆分及合并，實(shí)現(xiàn)聚類(lèi)數(shù)目的自適應(yīng)調(diào)整，同時(shí)保證形成的聚類(lèi)更加緊密合理。

2 相關(guān)工作

2.1 文本表示

本文主要采用向量空間模型VSM進(jìn)行文本描述，文本t表示為式(1)。

(1)

同時(shí)采用歐式距離描述文本a,b之間的關(guān)系，如式(2)所示。

(2)

2.2 聚類(lèi)密度

本文使用幾何中心來(lái)定義聚類(lèi)的中心，并通過(guò)聚類(lèi)密度描述聚類(lèi)內(nèi)樣本的相關(guān)性。

定義1(聚類(lèi)中心) 聚類(lèi)C的中心定義為其幾何中心:

(3)

定義2(聚類(lèi)密度) 聚類(lèi)C的密度定義為式(4)。

(4)

聚類(lèi)內(nèi)部樣本與聚類(lèi)中心越接近，聚類(lèi)密度就越高，重構(gòu)的必要性就越小。優(yōu)先選擇密度較低的聚類(lèi)實(shí)施重構(gòu)可以提高聚類(lèi)效率。

2.3 簇間距離

文獻(xiàn)[2]認(rèn)為樣本的空間分布具有正態(tài)分布的性質(zhì)，靠近聚類(lèi)中心的樣本權(quán)重較高，對(duì)聚類(lèi)間距的影響較大。本文參考其思想，設(shè)計(jì)了一種高斯加權(quán)算法來(lái)計(jì)算聚類(lèi)間距，使算法向聚類(lèi)中心的高密度區(qū)域靠近。

定義3(簇間距離) 樣本x相對(duì)于聚類(lèi)C的高斯權(quán)重為:

(5)

樣本x與聚類(lèi)C的距離為:

(6)

聚類(lèi)Ci與Cj的距離為:

(7)

為便于計(jì)算，式(5)取μ=K(C),σ=1。

3 加權(quán)K-NN聚類(lèi)算法

K-NN聚類(lèi)是一類(lèi)常用的文本處理算法。算法的思想是: 如果一個(gè)樣本S的K個(gè)最近鄰更靠近聚類(lèi)C，就將S劃分入聚類(lèi)C。

K-NN聚類(lèi)思想建立在理想假設(shè)下，要求初始狀態(tài)的聚類(lèi)劃分合理，并且已經(jīng)形成的每個(gè)聚類(lèi)內(nèi)部聯(lián)系緊密。但實(shí)際情況往往并非如此，即便初始聚類(lèi)劃分是理想的，隨著大量樣本不斷加入聚類(lèi)，聚類(lèi)內(nèi)部的關(guān)聯(lián)性可能降低，導(dǎo)致形成的聚類(lèi)偏離理想狀態(tài)[3-4]。

3.1 鄰近域

假設(shè)K-NN聚類(lèi)算法取K=3，圖1中待測(cè)樣本x(以圓形表示)被劃分入聚類(lèi)b(以三角形表示)。但實(shí)際上聚類(lèi)b密度較低，b類(lèi)樣本之間距離較大，兩個(gè)相近樣本距離聚類(lèi)b中心較遠(yuǎn)，因此樣本x距離聚類(lèi)a(以方形表示)比較近。出現(xiàn)以上問(wèn)題的原因在于K-NN聚類(lèi)沒(méi)有考慮兩個(gè)聚類(lèi)中的樣本對(duì)待測(cè)樣本x的影響力，換而言之沒(méi)有考慮兩個(gè)聚類(lèi)中各個(gè)樣本的權(quán)重。

圖1 近鄰域權(quán)重的意義

文獻(xiàn)[5]提出一種文本的權(quán)重量化思想，指出文本分布越密集的樣本空間區(qū)域?qū)垲?lèi)劃分的影響越高。文獻(xiàn)[6-7]提出距離聚類(lèi)中心越近的樣本對(duì)聚類(lèi)的表征能力越強(qiáng)，因此權(quán)重也越高。

借鑒經(jīng)典的K-NN聚類(lèi)思想，本文提出加權(quán)近鄰域的概念來(lái)處理待測(cè)樣本的劃分問(wèn)題，并且認(rèn)為越靠近聚類(lèi)中心的樣本對(duì)聚類(lèi)的影響力越高，樣本權(quán)重也越大[8]。

定義4(近鄰域) 與樣本x距離小于d的全部樣本構(gòu)成x的d近鄰域，記為式(8)。

(8)

其中d稱(chēng)為近鄰域的半徑。

定義5(近鄰域權(quán)重): 樣本x的d近鄰域?yàn)镈omain(x,d)，聚類(lèi)Ci與Domain(x,d)交集為Si=Domain(x,d)∩Ci，則:

(9)

稱(chēng)為x在Ci上的d近鄰域權(quán)重，在不引起混淆的情況下簡(jiǎn)稱(chēng)為x的權(quán)重。

3.2 近鄰域規(guī)則

選取近鄰域半徑d內(nèi)的K個(gè)(d為確定值，K為不確定數(shù)目)相鄰對(duì)象進(jìn)行聚類(lèi)判定。采用近鄰域規(guī)則判定待測(cè)樣本x的類(lèi)別劃分: 樣本劃分入K個(gè)鄰近對(duì)象最接近的聚類(lèi)。其中d為樣本S到最近的聚類(lèi)的距離。

3.3 聚類(lèi)重構(gòu)

為解決初始聚類(lèi)對(duì)聚類(lèi)結(jié)果的影響，采取聚類(lèi)重構(gòu)策略對(duì)獲得的聚類(lèi)實(shí)施重構(gòu)。

聚類(lèi)重構(gòu)機(jī)制根據(jù)聚類(lèi)的密度及各樣本的距離拆分稀疏的聚類(lèi)，合并相近聚類(lèi)從而實(shí)現(xiàn)聚類(lèi)的數(shù)目及空間分布的自適應(yīng)調(diào)整。重構(gòu)機(jī)制需要考慮以下情形:

1) 異常樣本調(diào)整。若聚類(lèi)內(nèi)少數(shù)樣本與簇內(nèi)其他樣本聯(lián)系較弱，應(yīng)當(dāng)將這些“另類(lèi)”樣本調(diào)整到其他聚類(lèi)中；

2) 稀疏聚類(lèi)拆分。若聚類(lèi)密度過(guò)低，說(shuō)明簇內(nèi)樣本分布稀疏，應(yīng)當(dāng)將稀疏聚類(lèi)拆分為多個(gè)密集聚類(lèi)；

3) 相似聚類(lèi)合并。若多個(gè)聚類(lèi)聯(lián)系緊密，考慮將它們合并為一個(gè)聚類(lèi)，合并后可能需要考慮1)、2)類(lèi)問(wèn)題。

1)類(lèi)問(wèn)題采用近鄰域算法處理；2)、3)兩類(lèi)問(wèn)題分別采用拆分算子和合并算子進(jìn)行處理。聚類(lèi)過(guò)于稀疏不利于判斷聚類(lèi)間距，會(huì)影響聚類(lèi)合并，因此聚類(lèi)重構(gòu)應(yīng)當(dāng)先拆分后合并，并優(yōu)先處理密度低的聚類(lèi)[9]。本文參照文獻(xiàn)[10]闡述的聚類(lèi)改進(jìn)策略，設(shè)置密度閾值來(lái)限定拆分算子的作用范圍，聚類(lèi)拆分的算法如下:

聚類(lèi)拆分算法

Step1 在密度低于閾值的聚類(lèi)中選擇密度最低的聚類(lèi)Ci;

Step2 獲取簇內(nèi)任意未處理成員t;

Step3 尋找t最近聚類(lèi)Cj;

Step4 若Ci=Cj轉(zhuǎn)Step6，否則繼續(xù):

① 若exp[-D(t,Cj)]≥Den(Cj)，t歸入Cj;

② 若exp[-D(t,Cj)]

Step5 更新聚類(lèi)中心及聚類(lèi)密度；

Step6 迭代處理聚類(lèi)Ci內(nèi)所有樣本。

算法Step4中，樣本t最近聚類(lèi)為Cj，若exp[-D(t,Cj)]≥Den(Cj)，說(shuō)明t比Cj中大多數(shù)樣本都更接近聚類(lèi)中心，允許將t歸入Cj;反之說(shuō)明t距離Cj中心較遠(yuǎn)，進(jìn)而斷定沒(méi)有與t相近的聚類(lèi)，需要新建聚類(lèi)來(lái)容納樣本t。

設(shè)樣本規(guī)模為n，理論上拆分算子完成所有計(jì)算的平均復(fù)雜度為O(n2)，由于聚類(lèi)中心、聚類(lèi)密度、高斯權(quán)重等復(fù)雜計(jì)算在聚類(lèi)過(guò)程中已經(jīng)完成，拆分算子實(shí)際時(shí)間開(kāi)銷(xiāo)為O(n×logn)。

聚類(lèi)合并的算法如下:

聚類(lèi)合并算法

Step1 整個(gè)聚類(lèi)集添加到未處理聚類(lèi)集合Cu;

Step2 獲取任意未處理聚類(lèi)Ci;

Step3 尋找Ci最近聚類(lèi)Cj;

Step4 分析Ci與Cj關(guān)系:

若exp[-D(Ci,Cj)]≥Den(Ci)或exp[-D(Ci,Cj)]≥Den(Cj)，合并聚類(lèi)Ci與Cj，更新聚類(lèi)中心及密度，將新聚類(lèi)添加到Cu。否則不予以合并；

Step5Cu中刪除已處理聚類(lèi)；

Step6 迭代處理Cu中所有聚類(lèi)。

算法Step4中，若exp[-D(Ci,Cj)]大于等于Ci或Cj任意一個(gè)的聚類(lèi)密度，說(shuō)明兩個(gè)聚類(lèi)存在較大交集，二者具有包含或較大的重疊關(guān)系，考慮將兩個(gè)聚類(lèi)合并。合并產(chǎn)生的新聚類(lèi)仍作為未處理聚類(lèi)參與迭代過(guò)程。

理論上合并算子復(fù)雜度為O(n2)，實(shí)際為O(n×logn)。

重構(gòu)機(jī)制示例 假設(shè)樣本空間共包括三類(lèi)16個(gè)文本，用三種圖形各代表一類(lèi)文本。初始狀態(tài)文本集被分為四類(lèi)，星形表示各聚類(lèi)幾何中心，箭頭指向文本的最近聚類(lèi)。理想狀態(tài)重構(gòu)過(guò)程如圖2所示。

圖2 聚類(lèi)重構(gòu)示例

經(jīng)過(guò)聚類(lèi)重構(gòu)，稀疏聚類(lèi)得到優(yōu)化，初始狀態(tài)對(duì)聚類(lèi)結(jié)果的影響也被削弱。聚類(lèi)的拆分及合并使得聚類(lèi)數(shù)目動(dòng)態(tài)調(diào)整，無(wú)需用戶干預(yù)，更符合聚類(lèi)處理的實(shí)際應(yīng)用需求。

4 實(shí)驗(yàn)分析

本文從復(fù)旦大學(xué)中文語(yǔ)料庫(kù)分別隨機(jī)選取500和1 000個(gè)樣本進(jìn)行聚類(lèi)實(shí)驗(yàn)。采用K-NN算法和加權(quán)重構(gòu)K-NN模型分別進(jìn)行聚類(lèi)。統(tǒng)計(jì)各類(lèi)別的準(zhǔn)確率、召回率、F-Score值并計(jì)算獲得的聚類(lèi)密度。

實(shí)驗(yàn)結(jié)果顯示近鄰域算法和聚類(lèi)重構(gòu)機(jī)制對(duì)文本聚類(lèi)的處理是有效的。經(jīng)過(guò)重構(gòu)處理后各類(lèi)文本準(zhǔn)確率、召回率均有顯著提升，聚類(lèi)密度有所提高，說(shuō)明重構(gòu)之后聚類(lèi)內(nèi)部樣本關(guān)聯(lián)性更強(qiáng)。

表1 500樣本K-NN聚類(lèi)及加權(quán)重構(gòu)K-NN結(jié)果對(duì)比

表2 1 000樣本K-NN聚類(lèi)及加權(quán)重構(gòu)結(jié)果K-NN對(duì)比

從表1及表2可見(jiàn)，藝術(shù)類(lèi)準(zhǔn)確率、召回率及聚類(lèi)密度較低，這是由于語(yǔ)料庫(kù)對(duì)文本的人工標(biāo)注不夠細(xì)致。語(yǔ)料庫(kù)藝術(shù)類(lèi)包括音樂(lè)、書(shū)畫(huà)、舞蹈、美學(xué)等多個(gè)領(lǐng)域的文章，雖然這些領(lǐng)域都屬于“藝術(shù)”范疇，但文本的詞匯特征相差甚遠(yuǎn)。通過(guò)聚類(lèi)重構(gòu)，“藝術(shù)”類(lèi)被劃分為四個(gè)子類(lèi)，如表3所示，每個(gè)子類(lèi)密度仍然是可接受的。

表3 “藝術(shù)”子類(lèi)

表1與表2的對(duì)比結(jié)果顯示，不同樣本規(guī)模下準(zhǔn)確率、召回率有一定差別，但重構(gòu)后聚類(lèi)密度卻相差無(wú)幾，這說(shuō)明聚類(lèi)算法對(duì)樣本規(guī)模是敏感的，但重構(gòu)機(jī)制不受到樣本規(guī)模的影響。

5 總結(jié)

本文提出一種高斯加權(quán)的K-NN文本聚類(lèi)算法。采用高斯函數(shù)對(duì)初始聚類(lèi)中各個(gè)樣本的影響力進(jìn)行評(píng)估。文章引入聚類(lèi)重構(gòu)機(jī)制調(diào)整稀疏聚類(lèi)，能夠有效提高聚類(lèi)密度并實(shí)現(xiàn)聚類(lèi)數(shù)目的自適應(yīng)調(diào)整。實(shí)驗(yàn)表明，重構(gòu)機(jī)制不受到樣本規(guī)模和初始劃分的影響，能夠有效地提高聚類(lèi)精度，保證聚類(lèi)的緊密性，其算法時(shí)間開(kāi)銷(xiāo)在可接受范圍。

本文在近鄰域的加權(quán)規(guī)則和距離度量方面還存在改進(jìn)和優(yōu)化的空間。更合理的近鄰域加權(quán)規(guī)則可以使得K-NN聚類(lèi)所獲得的聚類(lèi)更加合理，同時(shí)也有助于對(duì)稀疏聚類(lèi)的判定，減小聚類(lèi)重構(gòu)的代價(jià)。

[1] Hyeong-Il Kim and Jae-Woo Chang. K-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks[J]. Journal of Computer Science & Technology, 2013, 28(4): 585-596.

[2] 劉金嶺,馮萬(wàn)利,張亞紅.初始化簇類(lèi)中心和重構(gòu)標(biāo)度函數(shù)的文本聚類(lèi)[J].計(jì)算機(jī)應(yīng)用研究,2011,28(11): 4115-4117.

[3] 王燦田,孫玉寶,劉青山.基于稀疏重構(gòu)的超圖譜聚類(lèi)方法[J].計(jì)算機(jī)科學(xué),2014,41(2): 145-148,156.

[4] 曾依靈,許洪波,吳高巍,等.一種基于空間映射及尺度變換的聚類(lèi)框架[J].中文信息學(xué)報(bào),2010,24(3): 81-88.

[5] Amineh Amini, Teh Ying Wah, Mahmoud Reza Saybani, et al. A Study of Density-Grid based Clustering Algorithms on Data Streams[C]//Proceedings of the FSKD 2011. Shanghai China. 2011: 1652-1656.

[6] 陳建超,胡桂武,楊志華,等.基于全局性確定聚類(lèi)中心的文本聚類(lèi)[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(10): 147-150.

[7] 季鐸,王智超,蔡?hào)|風(fēng),等.基于全局性確定聚類(lèi)中心的文本聚類(lèi)[J].中文信息學(xué)報(bào),2008,22(3): 50-55.

[8] 王駿,王士同,鄧趙紅. 特征加權(quán)距離與軟子空間學(xué)習(xí)相結(jié)合的文本聚類(lèi)新方法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(8): 1655-1665.

[9] M Shahriar Hossain, Praveen Kumar Reddy Ojili, Cindy Grimm, etal. Scatter/Gather Clustering: Flexibly Incorporating User Feedback to Steer Clustering Results[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(12): 2829-2838.

[10] NishaM N, Mohanavalli S, Swathika R. Improving the quality of Clustering using Cluster Ensembles[C]//Proceedings of 2013 IEEE Conference on Information and Communication Technologies. 2013: 88-92.

Research on Gauss Weighed Reorganization K-NN

LIU Zuoguo, CHEN Xiaorong

(College of Computer Science & Technology Guizhou University, Guiyang,Guizhou 550025, China)

This paper presents a K-NN text clustering algorithm employing uses Gauss Weighed Distance and Cluster Reorganization Mechanism. The concept of Nearest Domain is proposed and Nearest Domain Rules are elaborated. Then Gauss Weighing Algorithm is designed to Quantification samples’ distance and weights. A text is weighed based on the distance from cluster center via Gauss function in order that distances of clusters can be calculated. Further, Cluster Reorganization Mechanism will make a self-adaption to the amount of clusters. Splitting operator separates sparse clusters and adjusts abnormal texts while consolidating operator combines similar ones. Clustering experiment shows that reorganization process effectively improves the accuracy and recall rate and makes result more reasonable by increasing the inner density of clusters.

text clustering; K-NN; Gauss weighing; nearest domain rule; cluster reorganization

劉作國(guó)(1987—),博士研究生,主要研究領(lǐng)域?yàn)橹形男畔⑻幚?。E-mail:412769371@qq.com陳笑蓉(1954—),教授,主要研究領(lǐng)域?yàn)橹形男畔⑻幚?。E-mail:xrchengz@163.com

1003-0077(2015)05-0112-05

2015-07-31 定稿日期： 2015-09-07

國(guó)家自然科學(xué)基金(61363028)

TP391

A