【摘要】：提出一種基于改進(jìn)后綴樹與交互聚類思想相結(jié)合的算法ISTC算法,通過改造傳統(tǒng)后綴樹結(jié)構(gòu)實現(xiàn)了對文檔標(biāo)題和摘要的層次化聚類,同時用交互聚類的方式替代了傳統(tǒng)的遞歸算法.ISTC算法具有語言無關(guān)性,不僅適用于基于單詞的西方文字,而且可以在不引入詞典分詞技術(shù)的情況下有效地處理基于單字的中文字符.在此算法基礎(chǔ)上,設(shè)計并實現(xiàn)了基于改進(jìn)后綴樹算法的交互聚類引擎,在不同的網(wǎng)絡(luò)環(huán)境下對其進(jìn)行了系統(tǒng)測試,并與其他元搜索引擎進(jìn)行了對比.實驗結(jié)果表明,使用改進(jìn)后綴樹算法進(jìn)行實時交互式聚類是可行的.
【圖文】：

類方法是以遞歸算法為基礎(chǔ)并有固定的聚類閾值,需要大量的時間和空間[5]. STC算法的優(yōu)點是利用短語不僅可以發(fā)現(xiàn)類,還可以描述類.后綴樹算法作為一種新的、增量式的線性時間運算方法,生成的數(shù)據(jù)結(jié)構(gòu)非常緊湊,節(jié)約了大量的存儲空間.文獻(xiàn)[6]給出了詳細(xì)的建樹過程.圖1為與字符串“ABDCABCD”對應(yīng)的后綴樹結(jié)構(gòu).圖1　后綴樹結(jié)構(gòu)Fig. 1　Structure of suffix tree由圖1可見,傳統(tǒng)的后綴樹結(jié)構(gòu)采用邊作為存儲單位,而在程序?qū)崿F(xiàn)中樹結(jié)構(gòu)仍是以節(jié)點形式存在,這種結(jié)構(gòu)沒有充分發(fā)揮節(jié)點的靈活性.同時,由于傳統(tǒng)后綴樹采用無序的插入方法,使建立后綴樹和讀取類標(biāo)識都必須進(jìn)行完全深度遍歷[7],當(dāng)數(shù)據(jù)量增大時,耗時會線性增加.中文以單個漢字為單位的建樹方法比英文以詞為單位占用時間和空間要大得多

層次化的后綴樹結(jié)構(gòu)是在傳統(tǒng)后綴樹的基礎(chǔ)上,將字符串Sn從邊上提取出放到葉節(jié)點上,每個節(jié)點作為一個存儲單元,同時引入排序方法插入節(jié)點,使建樹和讀樹的過程實現(xiàn)分層處理.當(dāng)一個節(jié)點不符合要求時,就不對它的子節(jié)點進(jìn)行深度遍歷,從而減少不必要的時間開支.節(jié)點結(jié)構(gòu)如圖2所示.圖2　節(jié)點的結(jié)構(gòu)Fig. 2　Structure of nodes節(jié)點標(biāo)簽用于存儲該節(jié)點存儲的字符串內(nèi)容;兄弟指針指向同一層中的下個節(jié)點;子節(jié)點指針指向該節(jié)點的第一個子節(jié)點,而第二個節(jié)點由第一個節(jié)點的兄弟指針鏈接;文檔索引標(biāo)簽是一個可變長的數(shù)組,用于存儲該節(jié)點的字符串短語在哪些結(jié)果文檔中存在.在層次化后綴樹結(jié)構(gòu)中,改進(jìn)了節(jié)點的同層次排序,在建樹過程中,每次從根節(jié)點出發(fā),當(dāng)在第一層找到新節(jié)點的排序位置在兩個現(xiàn)存節(jié)點間并且沒有相同部分時,將節(jié)點直接插入到兩節(jié)點之間.否則
【作者單位】： 吉林大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院;吉林大學(xué)通訊工程學(xué)院;
【基金】：吉林省科技發(fā)展計劃項目基金(批準(zhǔn)號:20070533)
【分類號】：TP311.13

【共引文獻(xiàn)】

相關(guān)期刊論文 前4條

1 陳次白,林磊;動態(tài)專家評估排序技術(shù)[J];情報雜志;2005年04期

2 陳晶;元搜索引擎實現(xiàn)技術(shù)[J];情報雜志;2005年05期

3 劉麗;元搜索引擎結(jié)果顯示方式研究[J];情報雜志;2005年06期

4 王敏,楊炳儒;基于主題的個性化元搜索引擎的設(shè)計與實現(xiàn)[J];情報雜志;2005年07期

相關(guān)博士學(xué)位論文 前1條

1 劉煒;智能元搜索引擎中個性化模式庫的研究[D];太原理工大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 鮑宗泛;廣域網(wǎng)數(shù)據(jù)庫查詢系統(tǒng)的研究與開發(fā)[D];浙江大學(xué);2004年

2 呂傳宇;答疑系統(tǒng)中專題式智能型元搜索引擎的研究[D];重慶大學(xué);2004年

3 洪穎;面向化工領(lǐng)域的智能元搜索引擎系統(tǒng)的研究與設(shè)計[D];北京化工大學(xué);2004年

4 杭月芹;基于文檔查詢信息的檢索系統(tǒng)研究與實現(xiàn)[D];揚州大學(xué);2005年

5 楊才峰;基于自動分類的元搜索引擎的研究與應(yīng)用[D];華北電力大學(xué)（河北）;2005年

6 樊康新;基于服務(wù)器端的個性化元搜索引擎的研究與設(shè)計[D];蘇州大學(xué);2005年

7 魏振達(dá);基于服務(wù)的元搜索引擎研究[D];南華大學(xué);2006年

8 尹西杰;基于智能Agent的Web個性化信息檢索系統(tǒng)[D];山東大學(xué);2006年

9 李信利;基于信息類別的元搜索引擎研究[D];山東大學(xué);2006年

10 霍長青;個性化元搜索引擎研究與設(shè)計[D];山東科技大學(xué);2006年

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 曾本勝，，廉玉忠，李世取;后綴樹的平均高度[J];運籌與管理;1996年04期

2 王繼成,潘金貴,張福炎;Web文本挖掘技術(shù)研究[J];計算機(jī)研究與發(fā)展;2000年05期

3 周水庚,關(guān)佶紅,胡運發(fā);基于文檔實例的中文信息檢索[J];計算機(jī)工程與應(yīng)用;2000年10期

4 鄧英,李明;Web數(shù)據(jù)挖掘技術(shù)及工具研究[J];計算機(jī)工程與應(yīng)用;2001年20期

5 李睿,李明;Web數(shù)據(jù)挖掘技術(shù)探討[J];甘肅科技;2001年03期

6 姜寧,史忠植;文本聚類中的貝葉斯后驗?zāi)Ｐ瓦x擇方法[J];計算機(jī)研究與發(fā)展;2002年05期

7 林鴻飛,楊元生;用戶興趣模型的表示和更新機(jī)制[J];計算機(jī)研究與發(fā)展;2002年07期

8 姜寧,宮秀軍,史忠植;高維特征空間中文本聚類研究[J];計算機(jī)工程與應(yīng)用;2002年10期

9 鄭毅,吳斌,史忠植;基于概念空間的文本檢索系統(tǒng)[J];計算機(jī)工程與應(yīng)用;2002年12期

10 李家福,陸建江,張亞非;模糊聚類算法在漢語文本聚類中的應(yīng)用[J];計算機(jī)工程;2002年04期

相關(guān)會議論文 前9條

1 張寶艷;王慶輝;;中文文本聚類的研究與實現(xiàn)[A];第一屆學(xué)生計算語言學(xué)研討會論文集[C];2002年

2 張剛;周昭濤;王斌;;基于主題的分布式信息檢索研究[A];NCIRCS2004第一屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會議論文集[C];2004年

3 邱立坤;程葳;龍志yN;孫嬌華;;面向BBS的話題挖掘初探[A];全國第八屆計算語言學(xué)聯(lián)合學(xué)術(shù)會議（JSCL-2005）論文集[C];2005年

4 黎琳;;Web內(nèi)容挖掘在數(shù)字圖書館中的應(yīng)用[A];中國工程物理研究院第七屆電子技術(shù)青年學(xué)術(shù)交流會論文集[C];2005年

5 彭怡;;從數(shù)據(jù)挖掘文章聚類分析看其發(fā)展趨勢[A];現(xiàn)代工業(yè)工程與管理研討會會議論文集[C];2006年

6 朱強(qiáng)生;田英;周延泉;何華燦;;基于非負(fù)因子分析的模糊文本挖掘[A];2006通信理論與技術(shù)新進(jìn)展——第十一屆全國青年通信學(xué)術(shù)會議論文集[C];2006年

7 羅娜;左萬利;袁福宇;張靖波;張慧杰;;使用本體語義提高文本聚類(英文)[A];全國語域web與本體能研討會論文集[C];2006年

8 顏端武;李曉鵬;王磊;成曉;;文本聚類中基于本體的相似性測度(英文)[A];全國語域web與本體能研討會論文集[C];2006年

9 丁X;許侃;;基于文本聚類方法的我國科技管理研究領(lǐng)域的計量研究[A];第三屆科技政策與管理學(xué)術(shù)研討會暨第二屆科教發(fā)展戰(zhàn)略論壇論文匯編[C];2007年

相關(guān)重要報紙文章 前2條

1 王培森;從Web挖到競爭情報[N];中國計算機(jī)報;2003年

2 中國科學(xué)院計算技術(shù)研究所 王 斌;內(nèi)容為王[N];計算機(jī)世界;2004年

相關(guān)博士學(xué)位論文 前6條

1 戈鵬;敏捷化CAPP系統(tǒng)原理、關(guān)鍵技術(shù)與應(yīng)用實踐[D];四川大學(xué);2003年

2 何清;機(jī)器學(xué)習(xí)與文本挖掘若干算法研究[D];中國科學(xué)院研究生院（計算技術(shù)研究所）;2002年

3 梁作鵬;面向Web的XML檢索關(guān)鍵技術(shù)研究[D];東南大學(xué);2005年

4 熊云波;文本信息處理的若干關(guān)鍵技術(shù)研究[D];復(fù)旦大學(xué);2006年

5 劉向威;NLP技術(shù)在中文信息檢索中的應(yīng)用研究[D];天津大學(xué);2005年

6 何麗;基于Web挖掘的決策支持系統(tǒng)模型研究[D];天津大學(xué);2005年

相關(guān)碩士學(xué)位論文 前10條

1 易靖;基于信息粒度原理的文本分類方法的研究[D];北京工業(yè)大學(xué);2001年

2 蘇偉峰;基于概念的文本自動分類研究[D];廈門大學(xué);2002年

3 劉恒;程序中重復(fù)代碼的自動檢測[D];大連理工大學(xué);2003年

4 劉立平;一種中文文本聚類方法的研究[D];湘潭大學(xué);2003年

5 張俊艷;基于SVM有聚類指導(dǎo)的Web中文文本分類器的研究及其實現(xiàn)[D];福州大學(xué);2004年

6 馬國俊;潛在語義索引在中文文本聚類中的應(yīng)用研究[D];西安建筑科技大學(xué);2004年

7 谷波;基于粗集模型的聚類方法及其在文獻(xiàn)過濾系統(tǒng)中的應(yīng)用[D];山西大學(xué);2004年

8 李建祥;智能網(wǎng)頁推薦系統(tǒng)的相關(guān)技術(shù)研究[D];西南交通大學(xué);2004年

9 繆嘉嘉;數(shù)據(jù)倉庫的數(shù)據(jù)獲取關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2003年

10 袁磊;基于概率模型的文本聚類[D];吉林大學(xué);2005年

本文編號：2525626