陳笑蓉，劉作國

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

文本聚類的重構(gòu)策略研究

陳笑蓉，劉作國

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

該文提出面向文本距離并獨(dú)立于聚類過程的聚類重構(gòu)策略。提出鄰近域的概念并闡述了鄰近域規(guī)則，設(shè)計(jì)了高斯加權(quán)鄰近域算法。利用高斯函數(shù)根據(jù)樣本與聚簇中心的距離為樣本賦權(quán)，計(jì)算聚簇間距。基于鄰近域權(quán)重對文本聚類的結(jié)果實(shí)施重構(gòu)。使用拆分算子拆分稀疏聚簇并調(diào)整異常樣本；使用合并算子合并相似聚簇。實(shí)驗(yàn)顯示聚簇重構(gòu)機(jī)制能夠有效地提高聚類的準(zhǔn)確率及召回率，增加聚簇密度，使得形成的聚類結(jié)果更加合理。

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

1 引言

文本聚類是信息處理領(lǐng)域的研究熱點(diǎn)。由于聚類之初難以獲得先驗(yàn)知識(shí)，對樣本空間分布情況做出的假設(shè)可能過于理想化，從而導(dǎo)致聚類結(jié)果偏離實(shí)際。此外，樣本規(guī)模的不斷擴(kuò)大可能致使原有聚類結(jié)果發(fā)生改變。例如，一篇關(guān)于釀酒工藝的文章，最初可能與其他科普知識(shí)同歸于科教類。隨著“舌尖上的中國”風(fēng)靡全國，各地飲食文化報(bào)道激增，這些文章可能被歸為飲食類。

雖然國內(nèi)外有一些文獻(xiàn)提出聚類重構(gòu)的概念，但主要是針對樣本空間描述或文本表示模型進(jìn)行重構(gòu)[1-2]，重構(gòu)的是聚類過程而非聚類結(jié)果。為提高聚類的準(zhǔn)確性和靈活性，本文引入一種針對聚類結(jié)果的重構(gòu)機(jī)制，對形成的聚簇進(jìn)行優(yōu)化。

2 相關(guān)工作

2.1 文本表示

重構(gòu)過程并非聚類過程，而是針對聚類結(jié)果進(jìn)行優(yōu)化，必須采用與聚類算法一致的文本表示模型及相似性度量。當(dāng)前主要有基于文本距離、基于密度、基于網(wǎng)格、基于語義的聚類模型，其中基于VSM的聚類模型是較為常見的。本文采用VSM模型進(jìn)行文本表示，以文本距離D(ti,tj)作為相似性度量實(shí)施聚類及重構(gòu)。

聚簇重構(gòu)的目標(biāo)是調(diào)整聚類結(jié)果中內(nèi)部松散或存在異常樣本的聚簇。重構(gòu)機(jī)制需要處理三類關(guān)系，即樣本與樣本的關(guān)系、樣本與聚簇的關(guān)系、聚簇與聚簇的關(guān)系[3]。

2.2 聚簇中心

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

定義1(聚簇中心)： 聚簇C的中心定義為其幾何中心，如式(1)所示。

(1)

式(1)中，聚簇中心K(C)的各維分量分別是各樣本對應(yīng)分量的向量均值。

定義2(聚簇密度)： 聚簇C的密度定義為式(2)。

(2)

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

2.3 簇間距離

評(píng)價(jià)聚簇間距離的算法包括最小距離算法(SingleLink)、最大距離算法(CompleteLink)、平均距離算法(AverageLink)、重心距離算法(GravityLink)等。最小距離算法及最大距離算法只使用一對樣本點(diǎn)進(jìn)行計(jì)算，對噪聲較為敏感。平均距離算法及重心距離算法雖然抗噪能力較強(qiáng)，但缺乏單調(diào)性[4]。

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

定義3(簇間距離)： 樣本x在聚簇C中的高斯權(quán)重為式(3)。

(3)

樣本x與聚簇C的距離為式(4)。

(4)

聚簇Ci與Cj的距離為式(5)。

(5)

為便于計(jì)算，式(3)取

3 聚簇重構(gòu)規(guī)則

3.1 鄰近域規(guī)則

聚簇重構(gòu)機(jī)制根據(jù)聚簇的密度及各樣本的距離調(diào)整聚簇，聚簇形狀可能影響重構(gòu)機(jī)制對聚簇密度的計(jì)算以及對聚簇中心的判定，導(dǎo)致產(chǎn)生不正確的重構(gòu)結(jié)果[5]。如圖1中所示。

圖1 聚簇形狀對重構(gòu)機(jī)制的影響

聚類算法形成的聚簇時(shí)常不是規(guī)則的球形，甚至是凹形。圖1中樣本x應(yīng)當(dāng)屬于聚簇a，但由于兩個(gè)聚簇并非規(guī)則的球形，聚簇中心距d1>d2，重構(gòu)機(jī)制錯(cuò)誤地將x劃分入聚簇b。

通常的解決方案是構(gòu)建標(biāo)準(zhǔn)坐標(biāo)系進(jìn)行空間變換，選擇具有一定區(qū)分度的方向構(gòu)建新的坐標(biāo)系，根據(jù)固有簇的特性重新定義距離標(biāo)度，使得各聚簇在新坐標(biāo)系下更接近球形[6-7]。

坐標(biāo)系的空間變換較繁瑣，可能影響樣本距離的計(jì)算，使得聚類結(jié)果失真。由于聚簇形狀主要影響異常樣本的調(diào)整，本文設(shè)計(jì)一種鄰近域(NearestDomain)算法處理不規(guī)則聚簇中的異常樣本。

規(guī)則1(單向原則)： 若a是b的最鄰近對象，b未必是a的最鄰近對象。

單向原則使樣本a可能進(jìn)入到鄰近對象b所屬聚簇，同時(shí)確保a不影響b與所屬聚簇的關(guān)系。即b不會(huì)由于a的“吸引”而背離其所屬聚簇。

規(guī)則2(就近原則)： 設(shè)樣本x的最鄰近樣本為a，x只有兩種可能的聚類歸屬： (1)x與a同屬一個(gè)聚簇；(2)x獨(dú)自形成聚簇。

就近原則限定了異常樣本的移動(dòng)范圍，如果x與最鄰近樣本a不屬于同一聚簇， 則x不可能與其他任何聚簇相關(guān)，它只能獨(dú)立形成聚簇。

就近原則的缺陷在于只考慮一個(gè)最鄰近的樣本點(diǎn)。如圖2中，樣本x最鄰近樣本為y，但其他鄰近樣本大部分屬于聚簇a，因此不應(yīng)當(dāng)將x從聚簇a中劃出。

圖2 就近性原則的缺陷

文獻(xiàn)[8]提出一種IMP_CBC聚類算法，選定多個(gè)聚簇核心，刪除沖突的核心并逐漸合并核心外的樣本。本文提出一種類似的鄰近域算法，解決就近原則的缺陷。

(6)

式(6)稱為x在Ci上的d鄰近域權(quán)重。

3.2 鄰近域算法

根據(jù)鄰近域規(guī)則，設(shè)計(jì)鄰近域算法如下。

Step1 確定聚簇C的候選異常樣本集；

Step4 調(diào)整異常樣本，若D(x,K(Ck))≤D(x,K(C))，則x∈Ck；否則x獨(dú)立形成聚簇；

Step5 更新聚簇中心并依次處理C中所有異常樣本；

Step6 依次處理所有密度低于閾值的聚簇；

設(shè)樣本規(guī)模為n，鄰近域算法平均計(jì)算復(fù)雜度T(n)=O(n×logn)。

3.3 鄰近域的半徑選擇

鄰近域半徑直接影響鄰近域算法的性能。半徑過小導(dǎo)致鄰近域內(nèi)樣本點(diǎn)數(shù)量不足，半徑過大(超過聚簇中心)則將涵蓋聚簇中心另一側(cè)的樣本點(diǎn)，使得算法產(chǎn)生錯(cuò)誤的結(jié)果。

設(shè)樣本x的最鄰近聚簇為CN，最鄰近樣本為tN，對鄰近域半徑d的基本要求是D(x,tN)≤d≤D(x,CN)，可以考慮取式(7)，

(7)

或式(8)。

(8)

本文取d=D(x,CN)進(jìn)行實(shí)驗(yàn)。

4 文本重構(gòu)機(jī)制

4.1 重構(gòu)策略

聚簇重構(gòu)需要考慮以下情形：

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

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

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

(1)類問題采用鄰近域算法處理；(2)～(3)兩類問題分別采用拆分算子和合并算子進(jìn)行處理。聚簇過于稀疏不利于判斷聚簇間距，會(huì)影響聚簇合并，因此聚簇重構(gòu)應(yīng)當(dāng)先拆分后合并，并優(yōu)先處理密度低的聚簇[9]。重構(gòu)機(jī)制總體過程如下。

Step1 獲取聚類結(jié)果；

Step2 計(jì)算聚簇中心及密度；

Step3 采用鄰近域算法處理異常樣本；

Step4 采用拆分算子處理稀疏聚簇；

Step5 采用合并算子處理相似聚簇；

Step6 更新重構(gòu)結(jié)果并實(shí)施迭代。

4.2 拆分算子

本文參照文獻(xiàn)[10]闡述的聚類改進(jìn)策略，設(shè)置密度閾值來限定拆分算子的作用范圍，聚簇拆分的算法如下。

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

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

Step3 尋找t最近聚簇Cj;

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

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

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

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

4.3 合并算子

聚簇合并的算法如下。

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

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

Step3 尋找Ci最近聚簇Cj;

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

Step5Cu中刪除已處理聚簇；

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

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

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

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

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

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

5.1 實(shí)驗(yàn)策略

以復(fù)旦大學(xué)中文語料庫進(jìn)行實(shí)驗(yàn)。采用K-means算法和SOM模型分別進(jìn)行聚類，對聚類結(jié)果實(shí)施重構(gòu)，以驗(yàn)證聚類重構(gòu)機(jī)制的有效性。單次實(shí)驗(yàn)流程如下。

Step1 從語料庫中隨機(jī)選擇十個(gè)類別，再從這十類中隨機(jī)抽取共計(jì)n個(gè)文本作為樣本集。要求每個(gè)類別至少有一個(gè)文本；

Step2 對文本進(jìn)行編號(hào)并由人工記錄所屬類別，以便作者分析實(shí)驗(yàn)結(jié)果；

Step3 實(shí)施文本聚類；

Step4 實(shí)施聚類重構(gòu)，進(jìn)行對比。

5.2 實(shí)驗(yàn)結(jié)果及分析

本節(jié)對文本聚類及聚類重構(gòu)的結(jié)果進(jìn)行對比分析。類別Ci的準(zhǔn)確率Pi、召回率Ci及F-score值定義如下。

定義7(準(zhǔn)確率、召回率、F值)：

Pi=正確分入Ci的文本數(shù)/Ci實(shí)際文本數(shù)；

Ri=正確分入Ci的文本數(shù)/Ci應(yīng)有文本數(shù)；

由于重構(gòu)機(jī)制對某些聚簇實(shí)施了拆分或合并，形成的聚簇與人工標(biāo)注結(jié)果不是一一對應(yīng)關(guān)系。本節(jié)采取子類分析策略統(tǒng)計(jì)準(zhǔn)確率及召回率。

以下采用K-means及SOM分別進(jìn)行聚類處理并實(shí)施重構(gòu)。實(shí)驗(yàn)結(jié)果如表1、2、3、4所示。

表1 500樣本K-means聚類及重構(gòu)結(jié)果對比

表2 1000樣本K-means聚類及重構(gòu)結(jié)果對比

續(xù)表

表3 500樣本SOM聚類及重構(gòu)結(jié)果對比

表4 1000樣本SOM聚類及重構(gòu)結(jié)果對比

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

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

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

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

6 總結(jié)

本文提出一種文本聚類結(jié)果的重構(gòu)機(jī)制，可適用于基于文本距離或文本相似度的聚類算法，對獲得的聚類結(jié)果實(shí)施優(yōu)化。文章探討了樣本分布特征及聚簇形狀對重構(gòu)機(jī)制的影響，采用鄰近域規(guī)則進(jìn)行聚簇優(yōu)化。實(shí)驗(yàn)表明，重構(gòu)機(jī)制在不影響聚類處理策略的前提下拆分或合并聚簇，能夠有效地提高聚類精度，保證聚簇的緊密性，其算法時(shí)間開銷在可接受范圍。

重構(gòu)機(jī)制所需的樣本距離、聚簇中心、聚簇密度等參數(shù)由聚類過程計(jì)算獲得，因此重構(gòu)機(jī)制對聚類過程有一定的依賴性，要求在進(jìn)行文本聚類的同時(shí)保存相關(guān)參數(shù)，增加了額外的空間開銷。利用XML等數(shù)據(jù)存儲(chǔ)格式可以高效地存取數(shù)據(jù)，有利于重構(gòu)算法執(zhí)行效率的提高及適用范圍的擴(kuò)展。

[1] MShahriar Hossain, Praveen Kumar Reddy Ojili, Cindy Grimm, et al. Scatter/Gather Clustering: Flexibly Incorporating User Feedback to Steer Clustering Results[J]. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 2012, 18(12): 2829-2838.

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

[3] Jinjiang Li, Hui Fan, Da Yuan, et al. Kernel Function Clustering Based on Ant Colony Algorithm[C]//Guo Maozu. ICNC 2008. Jinan， China. 2008: 645-649.

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

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

[6] Nisha M 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.

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

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

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

[10] 曾依靈,許洪波,吳高巍,等.一種基于語料庫特征的聚類算法[J].軟件學(xué)報(bào),2010,21(11): 2802-2813.

Research on Reorganization of Text Clustering Results

CHEN Xiaorong, LIU Zuoguo

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

This paper illustrates a distance oriented reorganization strategy in which clusters could be reorganized in independence from clustering process. The concept of Nearest Domain is proposed and Nearest Domain rules are elaborated. Then Gauss Weighing Algorithm is designed to re-wieght a text by the distance from cluster kernel. At last, Nearest Domain Weights will separates sparse clusters and adjusts abnormal texts while 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; cluster reorganization; nearest domain rule; Gauss weighing

陳笑蓉(1954—)，碩士，教授，主要研究領(lǐng)域?yàn)橹形男畔⑻幚怼?mail：xrchengz@163．com劉作國(1987—)，博士研究生，主要研究領(lǐng)域?yàn)橹形男畔⑻幚?。E?mail：412769371@qq．com

1003-0077(2016)02-0189-07

2013-12-11 定稿日期： 2014-05-15

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

TP391

A