基于web-logmining的web文檔聚類a

《基于web-logmining的web文檔聚類a》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、1000-9825/2002/13(01)0099-06?2002JournalofSoftware軟件學報Vol.13,No.1基于Web-LogMining的Web文檔聚類?1,21,234蘇中,馬少平,楊強,張宏江1(清華大學計算機科學與技術系,北京100084);2(清華大學智能技術與系統(tǒng)國家重點實驗室,北京100084);3(SimonFraser大學,加拿大);4(微軟中國研究院,北京100080)E-mail:suzhong_bj@hotmail.comhttp://www.tsinghua.edu.cn摘要:速度和效果是聚類算法面臨的兩大問題.DBSCAN(density

2、basedspatialclusteringofapplicationswithnoise)是典型的基于密度的一種聚類方法,對于大型數(shù)據(jù)庫的聚類實驗顯示了它在速度上的優(yōu)越性.提出了一種基于密度的遞歸聚類算法(recursivedensitybasedclusteringalgorithm,簡稱RDBC),此算法可以智能地、動態(tài)地修改其密度參數(shù).RDBC是基于DBSCAN的一種改進算法,其運算復雜度和DBSCAN相同.通過在Web文檔上的聚類實驗,結果表明,RDBC不但保留了DBSCAN高速度的優(yōu)點,而且聚類效果大大優(yōu)于DBSCAN.關鍵詞:數(shù)據(jù)庫;聚類;Webmining;數(shù)據(jù)挖掘中圖法

3、分類號:TP311文獻標識碼:A數(shù)據(jù)挖掘就是試圖在大型數(shù)據(jù)庫中發(fā)現(xiàn)隱含模式的過程.聚類算法是數(shù)據(jù)挖掘中的一個重要的分析工具.作為統(tǒng)計分析的一個分支,聚類分析在過去的40多年中得到了深入的研究,并廣泛運用于許多應用領域.對于數(shù)據(jù)挖掘的任務,聚類分析的誘人之處是有可能在不需要知道任何數(shù)據(jù)的層次信息的前提下,從數(shù)據(jù)中發(fā)現(xiàn)層次或類的關系.然而,在數(shù)據(jù)挖掘和機器學習中運用的聚類分析并沒有得到非常成功的運用.其原因就是在大規(guī)模數(shù)據(jù)庫中,通常算法的速度和效果不能令人滿意.[1][2~4]現(xiàn)在已有許多聚類算法,例如K-means,HAC(hierarchicalagglomerativeclusteri

4、ng),CLANRNS[5](clusteringlargeapplicationsbasedonrandomizedsearch)等,這些方法都是面向小數(shù)據(jù)集合的,不太適合數(shù)據(jù)挖掘所面對的大型數(shù)據(jù)庫.[6]DBSCAN(densitybasedspatialclusteringofapplicationswithnoise)是一種通過對局部密度分析,將相鄰點聚集在一起的聚類算法.在整個算法進行過程中,它只對數(shù)據(jù)庫進行一次掃描.如果DBMS對相鄰點的查詢效率很高(DBMS的查詢效率目前已經(jīng)完全滿足這一條件),DBSCAN的效率將非常令人滿意.它是當前面向大數(shù)據(jù)集聚類算法中最快的一種.然而

5、,由于算法本身在整個聚類過程中使用固定的參數(shù)(這將在下一節(jié)中討論),使得對于真實環(huán)境數(shù)據(jù)集的聚類,往往其聚類的效果不好.其主要原因是,由于其定義的密度的傳遞性質,往往將絕大多數(shù)的數(shù)據(jù)點都聚集在非常少的幾類中(通常是一類).在本文中,我們提出了一種基于密度的遞歸聚類算法RDBC(recursivedensitybasedclusteringalgorithm).此算法可以智能地、動態(tài)地修改其密度參數(shù).RDBC是基于DBSCAN的一種改進算法.算法的基本思想是,我們并?收稿日期:2000-04-03;修改日期:2000-07-20基金項目:國家重點基礎研究發(fā)展規(guī)劃973資助項目(G19980

6、30509)作者簡介:蘇中(1976－),男,上海人,博士生,主要研究領域為基于內容圖像檢索,模式識別,網(wǎng)絡數(shù)據(jù)挖掘;馬少平(1961－),男,河北唐山人,博士,教授,博士生導師,主要研究領域為模式識別,信息檢索,網(wǎng)絡數(shù)據(jù)挖掘;楊強(1961－),男,北京人,博士,教授,主要研究領域為機器學習,數(shù)據(jù)挖掘,知識系統(tǒng);張宏江(1960－),男,黑龍江哈爾濱人,博士,研究員,主要研究領域為視頻和圖像內容分析與檢索,計算機視覺,信息系統(tǒng).100JournalofSoftware軟件學報2002,13(1)不對原始數(shù)據(jù)集進行聚類,而是通過從數(shù)據(jù)集合中抽取高密度點生成新的數(shù)據(jù)集合,并修改密度參數(shù),反

7、復進行這一過程,直到生成的數(shù)據(jù)集合可以很容易地被聚類為止,然后以此結果為基礎,再將其他點逐層地吸附到各個類中.RDBC的運算復雜度和DBSCAN相同.通過對Web文檔數(shù)據(jù)的聚類實驗,結果表明,RDBC不但保留了DBSCAN高速度的優(yōu)點,而且聚類效果大大優(yōu)于DBSCAN.本文第1節(jié)給出了一些相關工作.第2節(jié)描述了RDBC算法.第3節(jié)講述了運用Web日志文件進行文檔聚類的方法.第4節(jié)是實驗描述.第5節(jié)是總結.1相關工作基于密度的聚類方法