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

楊冰

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

關鍵詞 數據挖掘；聚類分析；web信息；大數據

中圖分類號：TP311 文獻標識碼：A 文章編號：1671-7597（2014）06-0053-01

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

1 數據挖掘技術與聚類分析概述

1）數據挖掘概述。簡而言之，數據挖掘是用于將海量的原始數據轉化為簡潔直觀的信息的一種技術。它結合了傳統數據分析方法和大數據處理算法的優點，可以進行聚類分析、分類預測、關聯規則分析等工作。一般步驟包括預處理、數據挖掘、后處理。能夠用于處理各種高維和海量的數據。高維海量正是web信息所具有的兩個特點，故而數據挖掘技術對于web信息處理具有良好效果。

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

聚類又可被稱作非監督分類 ，它與監督分類的區別在于監督分類的類標號已知，通過已知類標號的訓練集建立模型并預測新數據對象的類標號，而聚類則不需要事先知道訓練集的類標號，在聚類過程中會自動導出類標號。

2 聚類分析算法

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

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

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

2）凝聚層次聚類。凝聚的層次聚類采取的是自底向上的方法，首先將每個對象單獨作為一個簇，然后每一步都按照某種標準合并最近的兩個簇，直到所有的對象都在一個簇中，或者達到某個終結條件。比起K-means算法，層次聚類算法最大的優勢就是不需要事先指定簇的個數，簇的個數是根據對象的分布情況動態生成的，這樣使得簇的個數更加靈活，最終的結果也具有說服力。

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

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

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

3 Web信息聚類過程

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

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

4 總結

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

參考文獻

[1]Tan，Pang-Ning， Michael Steinbach， and Vipin Kumar.數據挖掘導論，2006.

[2]張樹魁.網絡文本信息聚類算法研究與應用[D].北京：北京交通大學，2009.

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

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

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