楊冰

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

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

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

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

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

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

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

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

2 聚類(lèi)分析算法

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

1）K-means。K-means聚類(lèi)算法以距離值的平均值對(duì)聚類(lèi)成員進(jìn)行分配。如果一個(gè)對(duì)象屬于一個(gè)類(lèi)，則該數(shù)據(jù)一定比較靠近類(lèi)的中心，距離可以通過(guò)使用歐幾里得距離進(jìn)行度量。算法的基本步驟是：首先選取K個(gè)初始質(zhì)心，K由用戶(hù)自行指定，代表的是最終得到的簇的個(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聚類(lèi)算法原理簡(jiǎn)單，對(duì)于很多數(shù)據(jù)類(lèi)型都具有良好效果。但是它無(wú)法處理非球形簇和密度不均勻的簇

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

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

3）DBSCAN。DBSCAN是一種有效的基于密度的聚類(lèi)算法，假定聚類(lèi)對(duì)象是點(diǎn)，根據(jù)點(diǎn)集密度的大小，我們可以將點(diǎn)分為三類(lèi)：稠密區(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)不屬于任何簇，在聚類(lèi)過(guò)程中被丟棄。

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

3 Web信息聚類(lèi)過(guò)程

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

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

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

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