駱紹燁

(莆田學(xué)院信息工程學(xué)院,福建莆田351100)

一種基于用戶興趣的STC改進(jìn)算法

駱紹燁

(莆田學(xué)院信息工程學(xué)院,福建莆田351100)

作為一種常用的在線文檔聚類算法,STC算法聚類結(jié)果在用戶個(gè)性化方面存在不足。改進(jìn)后的算法結(jié)合用戶興趣模型,通過增加基類選擇因子和改善基類合并規(guī)則來進(jìn)行改進(jìn),實(shí)現(xiàn)基于用戶興趣特征的個(gè)性聚類效果。實(shí)驗(yàn)表明,改進(jìn)后的算法具有較好的準(zhǔn)確性和效率。

STC算法;用戶興趣模型;文本聚類

在浩大復(fù)雜的互聯(lián)網(wǎng)中,各種資源信息充斥其間,搜索已成為不可或缺的最重要的網(wǎng)絡(luò)應(yīng)用之一。根據(jù)CNNIC的最新統(tǒng)計(jì),搜索引擎的網(wǎng)民使用率達(dá)到了80.3%,僅次于即時(shí)通信排在了所有的網(wǎng)絡(luò)應(yīng)用中的第2位[1]。然而,搜索引擎僅只是對(duì)結(jié)果按照一定規(guī)則進(jìn)行排序,用戶一般只看搜索結(jié)果的前幾條記錄,無法全面了解搜索結(jié)果,而聚類技術(shù)則可以解決這一問題。

傳統(tǒng)的文本聚類主要是對(duì)一個(gè)或若干個(gè)文檔集進(jìn)行離線的聚類分析,文檔數(shù)量格式等相對(duì)固定。而在網(wǎng)頁數(shù)據(jù)聚類分析時(shí),網(wǎng)頁的內(nèi)容和格式等相對(duì)繁雜,并且要求在線完成聚類分析。目前, STC算法是WEB挖掘中使用最廣泛的在線聚類分析算法之一。

1 經(jīng)典STC算法

后綴樹(Suffix tree)起源于Weiner在1973年提出的一種數(shù)據(jù)結(jié)構(gòu)[2],主要用于字符串處理,能快速高效地解決字符串匹配和查詢問題。后綴樹的構(gòu)造方法較多,比較常用的是Okkonen’s算法[3]。該算法具有較好的時(shí)間性和空間性,且容易理解。其基本思想是:假設(shè)T[0..i-1]的后綴樹已經(jīng)建好了,那么在T[0..i-1]的每個(gè)后綴T[0..i-1], T[1..i-1],..T[j..i-1],..T[i-1..i-1],””(空字符串)的后面加上字符T[i]就可以得到T[0..i]的后綴樹[4]。

運(yùn)用該算法,構(gòu)造一個(gè)具有m個(gè)詞的字符串S的后綴樹的偽代碼實(shí)現(xiàn)如下:

廣義后綴樹是將后綴樹中的單一字符串推廣到多個(gè)字符的字符串,并對(duì)新字符串運(yùn)用后綴樹構(gòu)造方法進(jìn)行構(gòu)造。搜索結(jié)果聚類是將處理過的搜索引擎檢索到的文檔或網(wǎng)頁看成一個(gè)很長的字符串,對(duì)該字符串構(gòu)建廣義后綴樹,選取后綴樹中出現(xiàn)的相同的短語作為基類,然后進(jìn)行合并運(yùn)算。具體步驟如下:

1)文檔預(yù)處理:首先清除文檔中一些無關(guān)的內(nèi)容,包括網(wǎng)頁標(biāo)簽、標(biāo)點(diǎn)符號(hào)、空格等。如果是英文文檔,需要進(jìn)行詞干提取,而中文文檔則需要進(jìn)行中文分詞處理[5]。

2)構(gòu)造廣義后綴樹:將處理過后的文檔運(yùn)用后綴樹構(gòu)造方法構(gòu)造相應(yīng)的廣義后綴樹。

3)選擇基類:節(jié)點(diǎn)N的權(quán)值Score(N),其值由公式(1)來確定:

式中,|N|表示節(jié)點(diǎn)N所包含的文檔數(shù)目,候選基類的|N|值應(yīng)至少等于2,即最少包含兩個(gè)文檔才有資格作為候選基類,|P|代表節(jié)點(diǎn)N所包含的詞語數(shù),當(dāng)|P|小于7時(shí),f(|P|)是一個(gè)線性函數(shù),大于等于7時(shí),則是一個(gè)固定的常數(shù)[6]。將計(jì)算出的各個(gè)節(jié)點(diǎn)權(quán)值進(jìn)行排序,選擇權(quán)值最大的前幾個(gè)短語作為候選基類。

4)基類合并:對(duì)所有的基類短語進(jìn)行相似度比較,對(duì)于基類短語Na和Nb,如果

和

則兩個(gè)基類可以合并。其中|Na|,|Nb|分別表示基類Na和Nb的總文檔數(shù),|Na∩Nb|表示兩個(gè)基類的相同文檔的數(shù)目[7]。

廣義后綴樹的聚類方法相對(duì)其他一些聚類算法具有許多優(yōu)點(diǎn):算法的空間復(fù)雜度不高,不似向量空間模型需要占用大量的空間用于表示高度稀疏的文本向量矩陣;廣義后綴樹算法使用短語作為基類,保存了一定語義結(jié)構(gòu),有益于提高文本語義的聚類效果;算法相對(duì)簡單,可以適應(yīng)在線聚類搜索引擎的需要。

2 算法的不足和研究現(xiàn)狀

經(jīng)典的STC算法主要是針對(duì)廣義搜索的聚類,忽略了用戶的個(gè)性化需求。不同的用戶搜索的需求各異。同樣搜索“籃球”,不同的人感興趣的話題就不一樣,有的感興趣的話題集中在籃球聯(lián)賽、“NBA”等籃球比賽上,而有的可能感興趣的是籃球本身的材質(zhì)、價(jià)格等。在聚類的過程中加入用戶興趣因素能有效提高聚類的準(zhǔn)確性,更好地滿足用戶的需求。目前,針對(duì)STC聚類算法的研究主要通過改進(jìn)聚類的各個(gè)階段來實(shí)現(xiàn)算法的優(yōu)化。而預(yù)處理階段和后綴樹構(gòu)造階段與用戶興趣關(guān)系不大,因而主要通過改進(jìn)基類選擇和基類合并兩個(gè)階段來改進(jìn)算法,提高聚類效果。

在確定基類階段,經(jīng)典STC算法僅是根據(jù)節(jié)點(diǎn)所包含共同文檔的數(shù)目和短語所含詞語數(shù)來確定候選基類權(quán)值,而沒有考慮用戶的搜索傾向。如果選擇出來的基類短語與用戶興趣差異很大或不相關(guān),該次聚類結(jié)果也大打折扣。如何在基類短語中融入用戶興趣,已有研究主要通過加入詞頻權(quán)重因子來提高準(zhǔn)確性[2,8-9]。然而,詞頻權(quán)重因子雖可以看作用戶的興趣度,但用戶的興趣來源不應(yīng)僅依靠詞頻確定。因此,劉德山在權(quán)重公式中還加入了查詢詞得分系數(shù)[10],將包含查詢詞的基類權(quán)重?cái)U(kuò)大100倍,使其盡可能地包含查詢詞,在減少偏差的同時(shí)也限制了基類的選擇范圍。

在基類合并方面,經(jīng)典STC算法考慮的是基類所含文檔的相似度,如果共同文檔在兩個(gè)基類中占有率都超過一半,則對(duì)兩個(gè)基類合并。在這樣的規(guī)則下,大多數(shù)情況下是合理的,但并不全面。有些基類具有很高的單方共同文檔率(即共同文檔占其中一方的比例),但由于兩者文檔數(shù)懸殊,無法滿足規(guī)則。針對(duì)這一問題,林慶等人將合并條件擴(kuò)展到具有文檔包含關(guān)系的兩個(gè)基類[11],即如果一個(gè)基類的覆蓋文檔是另一基類的組成部分,則合并兩個(gè)基類,避免同時(shí)出現(xiàn)具有包含關(guān)系的聚類。但這一附加規(guī)則仍然無法處理那些不具有包含關(guān)系而單方共同文檔率很高的基類。同時(shí),傳統(tǒng)的STC聚類合并僅基于共同文檔率,忽略了基類內(nèi)容間的關(guān)系。肖坤通過比較文檔的感興趣程度與聚類的質(zhì)心來衡量相關(guān)度[12],雖引入了用戶興趣,但忽視了用戶興趣主題的多樣性,文檔基類的用戶感興趣程度類似并不代表興趣主題是相關(guān)的。

3 基于用戶興趣的改進(jìn)STC算法

針對(duì)現(xiàn)有算法的不足,文中充分研究用戶的興趣在聚類過程中的表達(dá),改進(jìn)算法的基類選擇和基類合并階段,使聚類檢索更好的體現(xiàn)用戶的個(gè)性要求,實(shí)現(xiàn)更切合用戶需求的聚類效果。

在聚類選擇中加入用戶興趣,首先必須確定用戶需求。用戶興趣的表示方法有多種,這里選擇常用的向量空間模型來表示。

定義1:用戶的興趣模型I通過一系列興趣節(jié)點(diǎn)Ik來表示,Ik∈I,對(duì)于每個(gè)Ik,均有二元組(sk,wk)表示,sk表示的是用戶感興趣的特征詞,wk表示sk所對(duì)應(yīng)的特征詞權(quán)重。其數(shù)學(xué)描述如下:

I={(s1,w1),(s2,w2),(s3,w3),…,(sn,wn)}(2)式中,n是興趣模型特征詞的總數(shù),wn通過IR領(lǐng)域中文本處理運(yùn)用最為廣泛的詞頻——反文檔頻率算法來確定[13]。將用戶興趣加入到基類短語的權(quán)值計(jì)算中,將基類權(quán)值計(jì)算修改為

式中,wi表示候選基類短語中第i詞在用戶興趣模型中的權(quán)重,ni表示基類短語中第i詞在文檔中的頻率。修改后的公式中增加了用戶興趣因子,避免了某些與用戶興趣密切相關(guān)的短語因包含的文檔數(shù)較少而落選。已有研究中用戶興趣通常只由短語中各詞在興趣模型中的權(quán)重決定,沒有考慮到該詞在覆蓋文檔中的出現(xiàn)頻率。用戶興趣詞出現(xiàn)頻率更高的文檔,用戶感興趣的可能性自然更高,加入詞頻能更好地體現(xiàn)用戶的興趣。

在基類選擇時(shí),個(gè)別基類短語節(jié)點(diǎn)包含了大量的文檔,可能超過了所有文檔數(shù)的一半,甚至接近總文檔數(shù),此類短語節(jié)點(diǎn)計(jì)算出的基類權(quán)值也必然很大。但正因?yàn)榇祟惞?jié)點(diǎn)代表性太廣泛,將導(dǎo)致聚類結(jié)果沒有區(qū)分度,即大部分文檔都集中在一個(gè)分類中,失去了聚類的意義。因此,在計(jì)算基類權(quán)值之前應(yīng)對(duì)候選基類節(jié)點(diǎn)進(jìn)行篩選,篩去包含文檔數(shù)過多的節(jié)點(diǎn),通常建議節(jié)點(diǎn)的文檔包含比(文檔包含比=節(jié)點(diǎn)文檔數(shù)/總文檔數(shù))不超過30%[6]。

3.2 改進(jìn)的基類合并算法

在基類合并過程中,為了避免一些基類的“子類”或者“近似子類”因文檔數(shù)量差異過大而無法合并,在原有合并規(guī)則的基礎(chǔ)上增加一條新的規(guī)則來處理這一情況。

小學(xué)數(shù)學(xué)課程標(biāo)準(zhǔn)對(duì)于數(shù)學(xué)教育至關(guān)重要，制定標(biāo)準(zhǔn)必須非常謹(jǐn)慎.課標(biāo)的制定絕非產(chǎn)品設(shè)計(jì)，可以為所欲為；而是嚴(yán)肅的科學(xué)研究，去尋求和確定建構(gòu)學(xué)生知識(shí)大廈的正確途徑.由于課標(biāo)不當(dāng)，幾代美國人已經(jīng)在數(shù)學(xué)上遭遇了滑鐵盧；在加拿大，“數(shù)學(xué)恐懼癥”也在大幅蔓延.希望數(shù)以百萬計(jì)的孩子不再被當(dāng)作試驗(yàn)品，重蹈覆轍.

該規(guī)則的數(shù)學(xué)描述:

或者

通過修改,新的合并規(guī)則能夠更好地解決基類包含問題,當(dāng)共同文檔數(shù)達(dá)到其中任一文檔數(shù)的80%以上時(shí),就認(rèn)為兩個(gè)基類具有包含關(guān)系或近似包含關(guān)系,可以將兩個(gè)基類合并。

現(xiàn)有的STC聚類合并大多是基于共同文檔率考慮的,很少涉及文檔的內(nèi)容聯(lián)系,僅有部分研究采用文檔用戶感興趣度來表達(dá)文檔間的內(nèi)容關(guān)系[12]。但興趣度接近只是表達(dá)用戶對(duì)文檔的感興趣程度是類似的,無法代表內(nèi)容之間的關(guān)聯(lián)。而文檔的主題是內(nèi)容的體現(xiàn),文檔主題的一致或類似也就表示文檔內(nèi)容具有一定的相似性,即文檔的主題相似性反映了兩者的內(nèi)容聯(lián)系。

基類文檔的主題雖然可以通過詞頻來確定,但這樣確定出的主題自由度過大,過于寬泛而不具針對(duì)性。引入用戶興趣模型來確定主題,可以通過用戶興趣模型中的權(quán)重來識(shí)別主題的重要性,避免確定出如“運(yùn)動(dòng)”、“商品”等過于寬泛的主題詞,而降低主題區(qū)分度。

定義2:對(duì)于基類B的用戶興趣主題T(B),通過一系列主題節(jié)點(diǎn)Tk來表示,Tk∈T(B),對(duì)于每個(gè)Tk,均由一個(gè)二元組(sk,ik)表示,sk表示的是用戶興趣主題的特征詞,ik表示sk在基類B中的興趣度。其數(shù)學(xué)描述如下:

其中 ik=nk*wk/nB

式中,nk表示特征詞在B中出現(xiàn)的次數(shù),wk為特征詞的權(quán)重,nB是基類文檔B的總詞數(shù)。

為了突出體現(xiàn)基類的用戶興趣主題,選取基類中興趣度最高的3個(gè)主題興趣節(jié)點(diǎn)作為基類B的主要興趣主題特征詞,記為T′(B),3個(gè)主要興趣主題特征詞構(gòu)成的集合為文檔的主要用戶興趣特征,記為S′(B)。

對(duì)于兩個(gè)基類,考慮到基類主題的相對(duì)廣泛性和不可確定性,共同文檔率仍然作為主要考慮因素。只有達(dá)到一定共同文檔率的兩個(gè)基類,才進(jìn)行必要的主題分析。如果它們的主要興趣特征詞的興趣度均超過一定閾值(記為δ),且3個(gè)主要興趣相同,則兩個(gè)基類合并。對(duì)特征詞興趣度的閾值要求既節(jié)省了時(shí)間,也避免了僅依靠主題相似的不確定性。

綜合以上,基類Na和Nb合并的前提是滿足以下條件之一:

和

或者

3)i′Na＞δAND i′Nb＞δAND S′(Na)=S′(Nb)

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

為了驗(yàn)證基于用戶興趣的改進(jìn)STC聚類算法,設(shè)計(jì)了原型系統(tǒng)進(jìn)行實(shí)驗(yàn)測試,對(duì)經(jīng)典STC算法和改進(jìn)后的算法進(jìn)行分析對(duì)比。實(shí)驗(yàn)數(shù)據(jù)通過微軟Bing API獲得,聚類方法在J2EE的平臺(tái)上實(shí)現(xiàn),運(yùn)行在酷睿i5、4 GB內(nèi)存的Windows XP計(jì)算機(jī)上。

首先測試聚類的效果。測試時(shí),改進(jìn)的STC算法采用兩種不同的用戶興趣模型。兩種用戶興趣模型分別給予不同的特征詞,用戶興趣模型A的特征詞為“原理”、“課程”、“課件”、“教程”等傾向計(jì)算機(jī)專業(yè)學(xué)習(xí)的詞語,而用戶興趣模型B則選用“安卓”、“Apple”、“手機(jī)”、“移動(dòng)”等有關(guān)手機(jī)操作系統(tǒng)的詞語。表1是檢索詞為“操作系統(tǒng)”在檢索文檔數(shù)為500的情況下,不同算法或用戶興趣模型檢索聚類情況。

從表1可以看出,經(jīng)典STC算法形成的聚類標(biāo)簽數(shù)量更多一些,且相對(duì)比較雜,其中包含了檢索詞“操作系統(tǒng)”以及“軟件”、“系統(tǒng)”等較多寬泛的詞語,甚至出現(xiàn)了一些無顯著意義的聚類標(biāo)簽,如“網(wǎng)”、“64位”、“提供”等。而在改進(jìn)STC算法的兩個(gè)不同用戶興趣模型下,聚類標(biāo)簽中均沒有出現(xiàn)檢索詞,部分代表性差的標(biāo)簽也消失了。這是由于在改進(jìn)的算法下,文檔包含比過高的詞被剔除。同時(shí),通過在選擇基類時(shí)引入用戶興趣特征詞權(quán)重因子,改進(jìn)后的算法產(chǎn)生的聚類標(biāo)簽更多地包含了對(duì)應(yīng)用戶興趣模型中的特征詞。此外,經(jīng)典STC的聚類標(biāo)簽中有部分詞語有著包含關(guān)系,如“XP系統(tǒng)”和“XP系統(tǒng)下載”,改進(jìn)的算法通過合并單方重復(fù)率過高的文檔集避免了這樣的情況。

表1 聚類結(jié)果對(duì)比Tab.1 Clustering results

第2組實(shí)驗(yàn)測試算法的時(shí)間復(fù)雜度。從微軟Bing搜索的結(jié)果中分別選用不同數(shù)量的搜索結(jié)果文檔,運(yùn)用改進(jìn)前后的算法進(jìn)行測試。文檔數(shù)量分別選取100,200,300,400,500 5個(gè)層次,測試結(jié)果為5個(gè)不同檢索詞的平均聚類時(shí)間,其結(jié)果如圖1所示。

圖1 算法改進(jìn)前后聚類時(shí)間對(duì)比Fig.1 Clustering time about the algorithm s before and after im p rovem ent

從圖1中可以看出,改進(jìn)STC算法在相同文檔數(shù)量的情況下,所花費(fèi)的時(shí)間均要比經(jīng)典STC的長,這主要是由于改進(jìn)的算法基類合并時(shí)不但要對(duì)文檔重復(fù)度進(jìn)行判斷,還要對(duì)基類的興趣主題相似度進(jìn)行對(duì)比。但是每個(gè)基類的興趣特征詞的興趣度計(jì)算只需要遍歷基類文檔一次即可,基類數(shù)目通常也不會(huì)太多,所以增加的時(shí)間耗費(fèi)并不明顯。

5 結(jié) 語

通過分析原有的STC聚類算法,結(jié)合用戶興趣模型對(duì)算法基類選擇和基類合并階段進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法在基本保證算法時(shí)間效率的前提下,完善了經(jīng)典STC算法的部分缺陷,并具有更加貼近用戶需求的聚類效果。

[1]中國互聯(lián)網(wǎng)絡(luò)信息中心.第33次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[EB/OL].(2014-03-05).http://www.cnnic.net.cn/

hlwfzyj/hlwxzbg/hlwtjbg/201403/t20140305_46240.htm.

[2]馮冰潔,楊天奇.后綴樹聚類算法在元搜索引擎中的應(yīng)用[J].微計(jì)算機(jī)信息,2010,26(1):204-206.

FENG Bingjie,YANG Tianqi.Suffix tree clustering algorithm in themeta search engine[J].Microcomputer Information,2010,26 (1):204-206.(in Chinese)

[3]Ukkonen E.On-line construction of suffix tree[J].Algorithmica,1995,14(3):249-260.

[4]吳江寧,王治江.一種基于后綴樹的Web搜索結(jié)果聚類方法[J].情報(bào)學(xué)報(bào),2010,29(1):78-83.

WU Jiangning,WANG Zhijiang.A clusteringmethod forWeb search results based on suffix tree[J].Journal of the China Society for Scientific,2010,29(1):78-83.(in Chinese)

[5]彭松行.基于描述優(yōu)先算法的Web搜索結(jié)果聚類系統(tǒng)研究[J].心智與計(jì)算,2010(4):250-257.

PENG Songhang.Research of Web search results clustering system based on description quality first algorithm[J].Mind and Computation,2010(4):250-257.(in Chinese)

[6]杜紅斌,夏克文,劉南平,等.一種改進(jìn)的基于廣義后綴樹的文本聚類算法[J].信息與控制,2009,38(3):331-336.

DU Hongbin,XIA Kewen,LIUNanping,etal.An improved text clustering algorithm ofgeneralized suffix tree[J].Information and Control,2009,38(3):331-336.(in Chinese)

[7]劉文婷,滕奇志.后綴樹聚類在專用搜索引擎中的應(yīng)用研究與改進(jìn)[J].成都信息工程學(xué)院學(xué)報(bào),2010,25(3):269-274.

LIUWenting,TENG Qizhi.The research and improvement of STC on dedicated search engine[J].Journal of Chengdu University of Information Technology,2010,25(3):269-274.(in Chinese)

[8]彭靜,翟英,馮爽.后綴樹算法在輿情聚類中的應(yīng)用[J].河北科技大學(xué)學(xué)報(bào),2012,33(1):65-68.

PENG Jing,ZHAIYing,FENG Shuang.Application of STC algorithm to internet public opinions clustering[J].Journal of Hebei University of Science and Technology,2012,33(1):65-68.(in Chinese)

[9]陽小蘭,錢程,趙海廷.一種基于Nutch的網(wǎng)頁聚類系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(5):118-122.

YANG Xiaolan,QIAN Cheng,ZHAO Haiting.Design and implementation on Web clustering system based on Nutch[J]. Computer Engineering and Applications,2011,47(5):118-122.(in Chinese)

[10]劉德山.一種改進(jìn)的基于后綴樹模型搜索結(jié)果聚類算法[J].計(jì)算機(jī)科學(xué),2011,38(11):148-152.

LIU Deshan.Improved search results clustering algorithm based on suffix treemodel[J].Computer Science,2011,38(11):148-152.(in Chinese)

[11]林慶,袁曉峰,吳旻.中文Web文檔聚類算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(20):4759-4761.

LIN Qing,YUAN Xiaofeng,WU Min.Research of one kind of Chinese web document clustering algorithm[J].Computer Engineering and Design,2009,30(20):4759-4761.(in Chinese)

[12]肖坤.面向用戶興趣的校園網(wǎng)聚類搜索引擎的研究與實(shí)現(xiàn)[D].長沙:國防科技大學(xué),2010.

[13]龔衛(wèi)華,楊良懷,金蓉,等.基于主題的用戶興趣域算法[J].通信學(xué)報(bào),2011,32(1):72-78.

GONGWeihua,YANG Lianghuai,JIN Rong,et al.Domain of interests clustering algorithm based on users′preferred topics[J]. Journal on Communications,2011,32(1):72-78.(in Chinese)

(責(zé)任編輯:楊 勇)

A New STC A lgorithm Based on User Interest

LUO Shaoye
(College of Information Engineering,Putian University,Putian 351100,China)

STC algorithm is an online document clustering algorithm commonly used.There are some deficiencies in users′personalization of the clustering results.The improved algorithm combined with the users′interest model can implement the characteristic clustering results by increasing the base class selection factor and improving the merge rules of the base class.The experiments show that the improved algorithm has better accuracy and efficiency.

STC algorithm,user interestmodel,text clustering

TP 391

A

1671-7147(2015)01-0085-05

2014-09-10;

2014-10-16。

福建省教育廳B類科技項(xiàng)目(JB12175);莆田市科技項(xiàng)目(2014G16);莆田學(xué)院教育教學(xué)改革研究項(xiàng)目(JG2012001)。

駱紹燁(1982—),男,福建莆田人,講師,工學(xué)碩士。主要從事WEB挖掘及WEB應(yīng)用研究。

Email:Lsy123@163.com