劉作國，陳笑蓉

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

?

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

劉作國，陳笑蓉

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

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

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

1 引言

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

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

2 相關(guān)工作

2.1 文本表示

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

(1)

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

(2)

2.2 聚類密度

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

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

(3)

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

(4)

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

2.3 簇間距離

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

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

(5)

樣本x與聚類C的距離為:

(6)

聚類Ci與Cj的距離為:

(7)

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

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

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

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

3.1 鄰近域

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

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

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

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

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

(8)

其中d稱為近鄰域的半徑。

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

(9)

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

3.2 近鄰域規(guī)則

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

3.3 聚類重構(gòu)

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

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

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

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

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

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

聚類拆分算法

Step1 在密度低于閾值的聚類中選擇密度最低的聚類Ci;

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

Step3 尋找t最近聚類Cj;

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

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

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

Step5 更新聚類中心及聚類密度；

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

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

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

聚類合并的算法如下:

聚類合并算法

Step1 整個聚類集添加到未處理聚類集合Cu;

Step2 獲取任意未處理聚類Ci;

Step3 尋找Ci最近聚類Cj;

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

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

Step5Cu中刪除已處理聚類；

Step6 迭代處理Cu中所有聚類。

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

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

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

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

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

4 實驗分析

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

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

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

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

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

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

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

5 總結(jié)

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

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

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

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

[4] 曾依靈,許洪波,吳高巍,等.一種基于空間映射及尺度變換的聚類框架[J].中文信息學(xué)報,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] 陳建超,胡桂武,楊志華,等.基于全局性確定聚類中心的文本聚類[J].計算機(jī)工程與應(yīng)用,2011,47(10): 147-150.

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

[8] 王駿,王士同,鄧趙紅. 特征加權(quán)距離與軟子空間學(xué)習(xí)相結(jié)合的文本聚類新方法[J].計算機(jī)學(xué)報,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

劉作國(1987—),博士研究生,主要研究領(lǐng)域為中文信息處理。E-mail:412769371@qq.com陳笑蓉(1954—),教授,主要研究領(lǐng)域為中文信息處理。E-mail:xrchengz@163.com

1003-0077(2015)05-0112-05

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

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

TP391

A