基于關(guān)聯(lián)規(guī)則的web文檔聚類(lèi)算法a

《基于關(guān)聯(lián)規(guī)則的web文檔聚類(lèi)算法a》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1000-9825/2002/13(03)0417-07?2002JournalofSoftware軟件學(xué)報(bào)Vol.13,No.3基于關(guān)聯(lián)規(guī)則的Web文檔聚類(lèi)算法?宋擒豹,沈鈞毅(西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,陜西西安710049)E-mail:qbsong@mail.xjtu.edu.cn;jyshen@mail.xjtu.edu.cnhttp://www.xjtu.edu.cn摘要:Web文檔聚類(lèi)可以有效地壓縮搜索空間,加快檢索速度,提高查詢(xún)精度.提出了一種Web文檔的聚類(lèi)算法.該算法首先采用向量空間模型VSM(vectorspacemodel)表示主題,根據(jù)主題表示文檔;再以文檔

2、為事務(wù),以主題為事務(wù)項(xiàng),將文檔和主題間的關(guān)系看作事務(wù)的形式,采用關(guān)聯(lián)規(guī)則挖掘算法發(fā)現(xiàn)主題頻集,相應(yīng)的文檔集即為初步文檔類(lèi);然后依據(jù)類(lèi)間距離和類(lèi)內(nèi)連接強(qiáng)度閾值合并、拆分類(lèi),最終實(shí)現(xiàn)文檔聚類(lèi).實(shí)驗(yàn)結(jié)果表明,該算法是有效的,能處理文檔類(lèi)間固有的重疊情況,具有一定的實(shí)用價(jià)值.關(guān)鍵詞:文檔聚類(lèi);關(guān)聯(lián)規(guī)則;Web挖掘;WWW中圖法分類(lèi)號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A隨著WWW的飛速發(fā)展,Internet上的資源和服務(wù)均呈現(xiàn)出爆炸性增長(zhǎng)的趨勢(shì).為了幫助人們有效地使用這些資源和服務(wù),陸續(xù)有一些功能強(qiáng)大的搜索引擎問(wèn)世了.這些搜索引擎在給人們帶來(lái)很大便利的同時(shí)也暴露出搜索結(jié)果不能很好地滿(mǎn)足用戶(hù)需求的問(wèn)題.Web

3、文檔聚類(lèi)技術(shù)可以縮減搜索空間,加快檢索速度,提高查詢(xún)精度,[1~6]因而受到了人們的廣泛關(guān)注.[5,6]Web文檔聚類(lèi)主要有基于概率和基于距離的兩類(lèi)方法.基于概率的方法以貝葉斯概率為理論基礎(chǔ),用概率的分布方式描述聚類(lèi)結(jié)果,可以處理類(lèi)間相互重疊的情況;缺點(diǎn)是當(dāng)特征空間維數(shù)較高或特征值間呈現(xiàn)出較[4]強(qiáng)的相關(guān)性時(shí),聚類(lèi)精度和效率均不能令人滿(mǎn)意.基于距離的方法,如K-均值和最近鄰等,都以傳統(tǒng)的特征向量表示文檔,再將文檔看作是向量空間中的一個(gè)點(diǎn),通過(guò)計(jì)算點(diǎn)之間的距離進(jìn)行聚類(lèi),比較形象直觀;缺點(diǎn)是特征向量必須經(jīng)過(guò)規(guī)范化處理以避免由于文檔長(zhǎng)度不同或各個(gè)文檔間關(guān)鍵詞出現(xiàn)的頻度各異而產(chǎn)生的畸變,特別是當(dāng)

4、數(shù)據(jù)維數(shù)較高時(shí),聚類(lèi)的質(zhì)量和算法的性能都明顯下降.[7]我們用主題表示文檔,將文檔和主題間的關(guān)系描述成事務(wù)的形式,根據(jù)臻于成熟的關(guān)聯(lián)規(guī)則挖掘算法初步劃分文檔類(lèi),然后依照類(lèi)間耦合度和類(lèi)的內(nèi)聚性進(jìn)行聚類(lèi)確認(rèn),有效地解決了上述方法中普遍存在的擴(kuò)展性問(wèn)題.1Web文檔的結(jié)構(gòu)化表示W(wǎng)eb文檔是一種半結(jié)構(gòu)化數(shù)據(jù),為便于檢索和查詢(xún),需要進(jìn)行結(jié)構(gòu)化處理.Web文檔表示就是抽取和描述其特征,并在此基礎(chǔ)上建立特征的結(jié)構(gòu)化描述的過(guò)程.在對(duì)Web文檔進(jìn)行結(jié)構(gòu)化表示的時(shí)候,我們首先用向量空間模型VSM(vectorspacemodel)表示每一個(gè)主題,并根據(jù)建立的主題特征向量和文檔內(nèi)容形成文檔的主題向量,再依此分

5、別計(jì)算給定文檔與這些主題間的關(guān)聯(lián)度,然后根據(jù)關(guān)聯(lián)度創(chuàng)建文檔-主題事務(wù)矩陣.最后,對(duì)文檔-主題事務(wù)矩陣中的行向量(即事務(wù))進(jìn)行規(guī)范化處?收稿日期:2000-04-04;修改日期:2000-08-28基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60173058);國(guó)家863青年基金資助項(xiàng)目(863-306-QN2000-5)作者簡(jiǎn)介:宋擒豹(1966－),男,陜西華縣人,博士,副教授,主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘,知識(shí)工程,計(jì)算機(jī)網(wǎng)絡(luò)安全;沈鈞毅(1939－),男,江蘇揚(yáng)州人,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)理論,數(shù)據(jù)挖掘,數(shù)據(jù)倉(cāng)庫(kù).418JournalofSoftware軟件學(xué)報(bào)2002,13(3

6、)理,將它轉(zhuǎn)換成單位向量,以使關(guān)聯(lián)度之間具有可比性.下面我們依次對(duì)上述Web文檔結(jié)構(gòu)化過(guò)程中用到的概念進(jìn)行具體定義和闡述.定義1.主題特征向量.設(shè)T是主題的集合,對(duì)于其中的每一個(gè)主題Ti∈T,我們用特征向量[()()()()]TT=k,w,k,w,...,k,w,...,k,wii,1i,1i,2i,2i,ji,ji,li,l表示.其中,ki,j代表主題Ti中的第j個(gè)關(guān)鍵字/短語(yǔ);wi,j為第j個(gè)關(guān)鍵字/短語(yǔ)ki,j對(duì)應(yīng)的權(quán)值,表示該關(guān)鍵字/短語(yǔ)在該主題中的重要程度,且∑wi,j=1,1≤j≤l;l=Ti,為主題Ti中關(guān)鍵字/短語(yǔ)的個(gè)數(shù),各個(gè)主題的l依實(shí)際情況而定,可以不同.用VSM定義

7、主題特征向量,代表主題的關(guān)鍵字/短語(yǔ)及其重要性可以根據(jù)具體情況來(lái)設(shè)定,各個(gè)主題的關(guān)鍵字個(gè)數(shù)也可以不同,這就充分兼顧了不同主題各自的具體情況,具有廣泛的適用性和較強(qiáng)的可維護(hù)性.定義2.文檔的主題向量.設(shè)D是文檔的集合,其中每一個(gè)文檔Dj∈D關(guān)于主題Ti的向量ToDj(Ti)表示文檔Dj對(duì)主題Ti的貢獻(xiàn),定義為[jjjj]T?ToD(T)=μ,μ,...,μ,...,μ,jii,1i,2i,ki,l??(2)j×wi,kμ=∪K∪D,?