基于密度的改進(jìn)K-Means文本聚類(lèi)算法研究.pdf

1、伴隨著信息技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)的不斷發(fā)展,每天有數(shù)億的分布式信息被人們所共享。如何在這些海量的、異構(gòu)的信息資源中快速而有效的檢索出需要的信息成為人們?nèi)找骊P(guān)注的問(wèn)題。知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘技術(shù)是解決這一問(wèn)題的最新課題。文本聚類(lèi)是文本發(fā)現(xiàn)和文本挖掘的最重要、最基本的功能之一,近年來(lái)文本聚類(lèi)算法的研究取得了長(zhǎng)足的發(fā)展和一系列的研究成果。
　　目前常用的文本聚類(lèi)算法有五類(lèi):基于劃分的聚類(lèi)算法,如最常用的 K-means算法;基于層次的聚類(lèi)算法;基

2、于密度的聚類(lèi)算法,如 DBSCAN算法;基于網(wǎng)格的聚類(lèi)算法和基于模型的聚類(lèi)算法
　　K-means算法是文本聚類(lèi)算法中的最經(jīng)典的基于劃分的算法之一。其主要思想是隨機(jī)選擇 K個(gè)初始中心點(diǎn),將每個(gè)簇中心用該簇中數(shù)據(jù)的均值表示。這種算法具有時(shí)間復(fù)雜度低,實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn),對(duì)處理大數(shù)據(jù)集的可伸縮性較好。但是該算法也有比較明顯的缺點(diǎn):首先該算法的聚類(lèi)效果對(duì)聚類(lèi)初始中心的選擇和設(shè)置過(guò)于敏感,極易導(dǎo)致聚類(lèi)結(jié)果隨之波動(dòng);其次是需要提前給定 K值固定

3、聚類(lèi)個(gè)數(shù);另外該算法在運(yùn)行中容易陷入局部最優(yōu)解。
　　本文對(duì)傳統(tǒng)的 K-means算法加以改進(jìn),主要有兩個(gè)方面的。首先基于距離和統(tǒng)計(jì)的思想對(duì)數(shù)據(jù)集中的孤立點(diǎn)進(jìn)行了檢測(cè),先將數(shù)據(jù)點(diǎn)之間按最近距離升序排列,計(jì)算出所有數(shù)據(jù)點(diǎn)最近鄰距離最大的幾個(gè)數(shù)據(jù)點(diǎn)的最近鄰距離差,以最大的距離差對(duì)應(yīng)的距離值為半徑對(duì)數(shù)據(jù)點(diǎn)的密度進(jìn)行統(tǒng)計(jì),將密度小于密度閾值的數(shù)據(jù)點(diǎn)進(jìn)行統(tǒng)計(jì)學(xué)標(biāo)準(zhǔn)化值的檢測(cè),從而判斷出數(shù)據(jù)集的強(qiáng)孤立點(diǎn)和部分弱孤立點(diǎn)并進(jìn)行處理。
　　其

4、次提出一種可變步長(zhǎng)的初始中心點(diǎn)選取算法。先將最近最小距離的數(shù)據(jù)點(diǎn)的平均距離計(jì)算出來(lái),以此建立可變步長(zhǎng)的半徑空間,數(shù)據(jù)點(diǎn)的從小到大在半徑空間中選取半徑,對(duì)半徑密度值進(jìn)行計(jì)算,最終將半徑密度最大最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為初始聚類(lèi)中心點(diǎn)進(jìn)行輸出。
　　最后將基于距離和統(tǒng)計(jì)的孤立點(diǎn)檢測(cè)算法和基于可變步長(zhǎng)的初始中心選取算法結(jié)合到傳統(tǒng)的 K-Means聚類(lèi)算法中,產(chǎn)生了基于密度的改進(jìn) K-Means文本聚類(lèi)算法。該算法通過(guò)對(duì)孤立點(diǎn)的檢測(cè)和處理能避免傳統(tǒng)