Web信息聚類分析與算法研究

楊冰

摘 要 Web信息聚類分析是這些年來新興的方向，盡管是新的概念，但是使用傳統(tǒng)的聚類算法就可以取得很好的效果。文章對(duì)web信息聚類分析與算法進(jìn)行了探討，研究認(rèn)為，web信息聚類首先要經(jīng)過預(yù)處理，將復(fù)雜多樣的web信息轉(zhuǎn)化為簡潔統(tǒng)一的形式，便于算法處理。在算法的選擇上使用經(jīng)典的K-means或凝聚層次聚類能夠達(dá)到很高的精度，若能將算法進(jìn)一步優(yōu)化，其聚類結(jié)果會(huì)更加準(zhǔn)確。

關(guān)鍵詞 數(shù)據(jù)挖掘；聚類分析；web信息；大數(shù)據(jù)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-7597（2014）06-0053-01

伴隨著信息技術(shù)水平的高速發(fā)展，因特網(wǎng)蘊(yùn)含的信息量越來越大，互聯(lián)網(wǎng)已經(jīng)成為信息傳播的主流平臺(tái)。與此同時(shí)，由數(shù)據(jù)量過大引起的問題開始凸現(xiàn)出來，人們淹沒在數(shù)以億計(jì)的web頁面中而難以快速制定合適的決策。即使是通過搜索引擎有的放矢的搜索，得到的往往也是無序的結(jié)果，難以令人滿意。如何在海量的web數(shù)據(jù)中產(chǎn)生層次結(jié)構(gòu)，讓信息分門別類地展示在用戶面前，從而令用戶提取自己需要的信息成為一個(gè)亟待解決的熱門問題。

1 數(shù)據(jù)挖掘技術(shù)與聚類分析概述

1）數(shù)據(jù)挖掘概述。簡而言之，數(shù)據(jù)挖掘是用于將海量的原始數(shù)據(jù)轉(zhuǎn)化為簡潔直觀的信息的一種技術(shù)。它結(jié)合了傳統(tǒng)數(shù)據(jù)分析方法和大數(shù)據(jù)處理算法的優(yōu)點(diǎn)，可以進(jìn)行聚類分析、分類預(yù)測、關(guān)聯(lián)規(guī)則分析等工作。一般步驟包括預(yù)處理、數(shù)據(jù)挖掘、后處理。能夠用于處理各種高維和海量的數(shù)據(jù)。高維海量正是web信息所具有的兩個(gè)特點(diǎn)，故而數(shù)據(jù)挖掘技術(shù)對(duì)于web信息處理具有良好效果。

2）聚類分析概述。聚類分析是數(shù)據(jù)挖掘中的方法之一，它可以將數(shù)據(jù)自動(dòng)劃分為有聯(lián)系的組或者簇，而且使得同一組中對(duì)象間的相似度最大化，不同組中對(duì)象間的相似度極小化，換言之，一個(gè)簇就是由彼此相似的一組對(duì)象所構(gòu)成的集合，不同簇中的對(duì)象通常不相似或相似度很低。

聚類又可被稱作非監(jiān)督分類 ，它與監(jiān)督分類的區(qū)別在于監(jiān)督分類的類標(biāo)號(hào)已知，通過已知類標(biāo)號(hào)的訓(xùn)練集建立模型并預(yù)測新數(shù)據(jù)對(duì)象的類標(biāo)號(hào)，而聚類則不需要事先知道訓(xùn)練集的類標(biāo)號(hào)，在聚類過程中會(huì)自動(dòng)導(dǎo)出類標(biāo)號(hào)。

2 聚類分析算法

常用的聚類算法包括基于原型的、劃分的K-means算法、基于圖和原型的凝聚層次聚類算法、基于密度的DBSCAN算法。

1）K-means。K-means聚類算法以距離值的平均值對(duì)聚類成員進(jìn)行分配。如果一個(gè)對(duì)象屬于一個(gè)類，則該數(shù)據(jù)一定比較靠近類的中心，距離可以通過使用歐幾里得距離進(jìn)行度量。算法的基本步驟是：首先選取K個(gè)初始質(zhì)心，K由用戶自行指定，代表的是最終得到的簇的個(gè)數(shù)。每個(gè)點(diǎn)根據(jù)距離大小分配到離自己最近的質(zhì)心所在的簇中。然后根據(jù)每個(gè)簇內(nèi)點(diǎn)的分布情況重新計(jì)算質(zhì)心，指派每個(gè)簇新的質(zhì)心。重復(fù)上述兩個(gè)步驟直到質(zhì)心不再改變?yōu)橹埂?/p>

K-means聚類算法原理簡單，對(duì)于很多數(shù)據(jù)類型都具有良好效果。但是它無法處理非球形簇和密度不均勻的簇

2）凝聚層次聚類。凝聚的層次聚類采取的是自底向上的方法，首先將每個(gè)對(duì)象單獨(dú)作為一個(gè)簇，然后每一步都按照某種標(biāo)準(zhǔn)合并最近的兩個(gè)簇，直到所有的對(duì)象都在一個(gè)簇中，或者達(dá)到某個(gè)終結(jié)條件。比起K-means算法，層次聚類算法最大的優(yōu)勢就是不需要事先指定簇的個(gè)數(shù)，簇的個(gè)數(shù)是根據(jù)對(duì)象的分布情況動(dòng)態(tài)生成的，這樣使得簇的個(gè)數(shù)更加靈活，最終的結(jié)果也具有說服力。

層次聚類盡管更加靈活，但是時(shí)間復(fù)雜度和空間復(fù)雜度都很高，故而不太適合處理數(shù)據(jù)量太大的數(shù)據(jù)集。

3）DBSCAN。DBSCAN是一種有效的基于密度的聚類算法，假定聚類對(duì)象是點(diǎn)，根據(jù)點(diǎn)集密度的大小，我們可以將點(diǎn)分為三類：稠密區(qū)域內(nèi)的點(diǎn)是核心點(diǎn)；稠密區(qū)域邊上的點(diǎn)是邊界點(diǎn)；稀疏區(qū)域內(nèi)的點(diǎn)是噪聲點(diǎn)。在這三種點(diǎn)的定義的基礎(chǔ)上我們可以對(duì)算法作如下描述：任意兩個(gè)核心點(diǎn)的距離若在給定的范圍之內(nèi)，則二者屬于同一個(gè)簇；任意與核心點(diǎn)距離足夠近的邊界點(diǎn)和該核心點(diǎn)屬于同一個(gè)簇；噪聲點(diǎn)不屬于任何簇，在聚類過程中被丟棄。

DBSCAN比K-means的抗噪能力強(qiáng)，它可以處理任意形狀和大小的簇（包括K-means不能處理的球形簇）。但是對(duì)于密度不均勻的簇DBSCAN效果也不能令人滿意。

3 Web信息聚類過程

1）數(shù)據(jù)預(yù)處理?；ヂ?lián)網(wǎng)上的web頁面格式各種各樣，無法直接用于聚類，首先必須對(duì)它們進(jìn)行預(yù)處理，構(gòu)建特征向量。預(yù)處理的過程一般包括分詞、特征降維、相似度計(jì)算等。分詞是為了構(gòu)建特征集，但是容易導(dǎo)致維度過高，影響聚類效果。此時(shí)需要進(jìn)行特征降維，選取原始特征集的子集進(jìn)行聚類，這樣不僅能夠提高算法運(yùn)行速度，還可以提高聚類精度。經(jīng)過預(yù)處理之后，web頁面信息量得到簡化，同時(shí)改善了頁面表示效果，提高了頁面間的區(qū)分度，更有利于聚類。

2）聚類。選用合適的聚類方法如K-means或凝聚層次聚類，利用第一步構(gòu)建的特征向量進(jìn)行聚類。頁面之間的距離可以通過余弦相似度進(jìn)行度量。聚類的結(jié)果具有層次結(jié)構(gòu)，比如，如果原始網(wǎng)頁集合是關(guān)于電影的網(wǎng)頁，那么聚類之后會(huì)把這些網(wǎng)頁分別歸類。影評(píng)類網(wǎng)頁屬于一類，電影視頻網(wǎng)頁屬于一類，影星介紹屬于一類。這些類均可以進(jìn)一步細(xì)分，最終達(dá)到用戶想要的效果。

4 總結(jié)

綜上所述，在21世紀(jì)的今天，計(jì)算機(jī)信息技術(shù)更新速度加快。特別是最近幾年，針對(duì)web信息處理的研究越來越火熱，由于web信息的復(fù)雜性，簡單的聚類算法效果也許并不理想。另外，由于網(wǎng)絡(luò)信息資源的迅速膨脹，網(wǎng)絡(luò)文本規(guī)模也越來越大，對(duì)于聚類算法在空間復(fù)雜度上的要求也越來越高。而以上三種聚類算法都有各自的優(yōu)缺點(diǎn)，因此，如何進(jìn)一步優(yōu)化聚類算法，降低算法的時(shí)間和空間代價(jià)，提高算法對(duì)于不同數(shù)據(jù)集的適應(yīng)能力，提升算法的抗噪性，最終提高對(duì)web信息的聚類效果還需要進(jìn)行更加深入的分析研究。

參考文獻(xiàn)

[1]Tan，Pang-Ning， Michael Steinbach， and Vipin Kumar.數(shù)據(jù)挖掘?qū)д摚?006.

[2]張樹魁.網(wǎng)絡(luò)文本信息聚類算法研究與應(yīng)用[D].北京：北京交通大學(xué)，2009.

[3]邱韜奮.基于聚類算法的Web信息抽取技術(shù)研究[D].暨南大學(xué)，2011.

[4]張世博，周義明.一種優(yōu)化初始化中心的k均值web信息聚類算法[J].北京石油化工學(xué)院學(xué)報(bào)，2012：55-58.

[5]孫學(xué)剛，陳群秀，馬亮.基于主題的Web文檔聚類研究[J].中文信息學(xué)報(bào)，2003：21-26.endprint