粒子群優(yōu)化算法在Web內(nèi)容挖掘中的應(yīng)用與研究

李智勇

（青海大學(xué)現(xiàn)代教育技術(shù)中心，西寧810016）

0 引言

Web數(shù)據(jù)挖掘的定義是：從Web文本和Web活動(dòng)中抽取用戶感興趣的、潛在的、有用模式和隱藏的信息。Web文本挖掘常用的領(lǐng)域有分類、聚類、關(guān)聯(lián)分析、Web主題發(fā)現(xiàn)與跟蹤、預(yù)測分析、提取規(guī)則發(fā)現(xiàn)、Web內(nèi)容變化規(guī)律檢測、用戶模型、頻繁子結(jié)構(gòu)發(fā)現(xiàn)、站點(diǎn)數(shù)據(jù)模式挖掘、數(shù)據(jù)集成等。

聚類算法取決于數(shù)據(jù)的類型、聚類的目的和應(yīng)用，而粒子群聚類算法是基于粒子群定理實(shí)現(xiàn)的，同時(shí)研究表明簡單的粒子群聚類算法在準(zhǔn)確率和速度上和決策樹、神經(jīng)元算法是可以相媲美的。

1 粒子群優(yōu)化算法（PSO）

在生物群體中個(gè)體間的競爭與合作等生物行為能產(chǎn)生的群體辨別能力，往往針對(duì)某些特定的問題可提供高效的解決方法。

PSO中粒子作為基本的組成單位，一個(gè)粒子代表解空間的一個(gè)候選解。設(shè)解向量為d維變量，則當(dāng)算法迭代次數(shù)為t時(shí)，第i個(gè)粒子xi（t）可表示為Xi（t）=[xi1（t），xi2（t），xi3（t），…xid（t）]。其中xik（t）表示第i個(gè)粒子在第k維解空間中的位置，即第i個(gè)候選解中的第k個(gè)待優(yōu)化的變量。粒子種群（population）由n個(gè)粒子組成，代表n個(gè)候選解。經(jīng)過t次迭代產(chǎn)生的種群：pop（t）=[x1（t），x2（t），x3（t），…，xi（t），…，xn（t）]。其中：xi（t）為種群中的第i個(gè)粒子。它表示粒子在一次迭代中位置的變化即粒子在解空間的位移，Vi（t）=[vi1（t），vi2（t），vi3（t），…，vik（t），…，vid（t）]。其中：vik（t）為第i個(gè)粒子在解空間第k維的速度。適應(yīng)度（fitness）函數(shù)。它由優(yōu)化目標(biāo)決定，用于評(píng)價(jià)粒子的性能即解的優(yōu)劣，從而指導(dǎo)粒子群體的搜索過程。算法迭代停止時(shí)適應(yīng)度最優(yōu)的粒子即為優(yōu)化搜索的最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個(gè)“極值”，即個(gè)體極值pBest和全局極值gBest來更新自己。在找到這兩個(gè)最優(yōu)值后，粒子根據(jù)如下公式（1）、（2）來更新自己的速度和位置：

粒子群算法的基本步驟為：①種群初始化，隨機(jī)給定種群的初始位置和初始速度。②粒子評(píng)價(jià)，對(duì)種群中的每一個(gè)個(gè)體計(jì)算其適應(yīng)值（fitness value）。③根據(jù)適應(yīng)值更新粒子的個(gè)體極值和種群的全局極值。④更新種群，根據(jù)迭代公式對(duì)每個(gè)粒子的位置和速度進(jìn)行更新。⑤如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟②。

2 粒子群算法在Web內(nèi)容挖掘中的應(yīng)用研究

任何原始數(shù)據(jù)在計(jì)算機(jī)中都必須采用特定的數(shù)學(xué)模型來表示，文本數(shù)據(jù)當(dāng)然也不例外。HTML語言描述的Web頁面由普通文本和HTML標(biāo)記構(gòu)成。并且各個(gè)標(biāo)記的級(jí)別是不一樣的，標(biāo)記的分布也有一定的規(guī)律，在使用習(xí)慣上也存在著差異。這些都是網(wǎng)頁解析和內(nèi)容提取可以利用的重要特征[3]。對(duì)于Web文檔預(yù)處理，主要由以下幾個(gè)步驟來完成：①解析HTML文擋，取出Web文檔中的噪音；②Web文本分詞；③剔除Web文檔中的停用詞；④特征選擇；⑤生成向量空間模型，以用于進(jìn)一步的Web文本聚類或其他文本挖掘工作。

在向量空間模型中，文本空間是由一組正交詞條向量所組成的向量空間，每個(gè)文本表示為其中的一個(gè)范化特征向量

其中ti表示詞條項(xiàng)，可以為詞，也可以為詞組，Wi（d）表示對(duì)應(yīng)分量的權(quán)值。而特征項(xiàng)可以取字、詞或短語，文本聚類算法也一般采用詞作為特征項(xiàng)表示文本。這樣這些正交詞條向量就組成了一個(gè)文本向量空間，每個(gè)文本都可映射為此向量空間的一個(gè)向量：

文本集合D中，di表示文本集合中的第i篇文本，ti代表文本集合中的一個(gè)特征項(xiàng)；t（fti，d）i表示特征項(xiàng)頻率，定義為特征ti項(xiàng)出現(xiàn)在文本di中的次數(shù)；d（ft）i表示文本頻率，定義為在文本集合D中出現(xiàn)過特征項(xiàng)ti的文本數(shù)；表示文本集合D中所有文本的總數(shù)；w（di，t）i表示特征項(xiàng)ti在文本di中的權(quán)重值，TFIDF權(quán)重則利用了各特征項(xiàng)在文本di中出現(xiàn)的局部特征項(xiàng)頻數(shù)t（fdi，t）i，與在文本集合D中出現(xiàn)過的全局文本頻數(shù)d（ft）i，進(jìn)行綜合加權(quán)。標(biāo)準(zhǔn)的TFIDF計(jì)算形式如下[4]：

本文的聚類方法使用的是向量空間模型。用文本中出現(xiàn)的詞語來表示文本特征，必須以特征獨(dú)立性假定為前提，也就是認(rèn)為構(gòu)成文本的各個(gè)詞之間是相互獨(dú)立的。從語料庫中選出包括醫(yī)療、軍事、體育、交通4類文章樣本，每類30篇，共計(jì)120篇文章。

使用RostNat采集器，在全網(wǎng)中采集相關(guān)信息，將采集到的文檔分別聚類保存，將其分離為單個(gè)文檔。每個(gè)文檔都表示為向量空間模型D,然后對(duì)其進(jìn)行分詞，進(jìn)行詞條化。進(jìn)一步對(duì)分詞進(jìn)行處理，得到TDIDF權(quán)重值。將120篇文章作為文檔文本集合D，集合中得每個(gè)文本di中的每個(gè)特征項(xiàng)目都有其自身的TFIDF權(quán)重值，顯而易見的是若用所有的分詞的權(quán)重值來表示該文本di，則di的維數(shù)隨文本詞匯的多少而確定。

為了使粒子保持運(yùn)動(dòng)慣性，使其有擴(kuò)展搜索空間的趨勢，以此探索新的區(qū)域。對(duì)基本粒子群算法的改進(jìn)，即對(duì)速度更新方程加慣性權(quán)重w

當(dāng)種群大小很小的時(shí)候，陷入局部最優(yōu)解的可能性很大；然而，群體過大將導(dǎo)致計(jì)算時(shí)間大幅增加。并且當(dāng)群體數(shù)目增長至一定水平時(shí)，再增長將不再有顯著的作用，本文設(shè)定種群大小為120。

慣性權(quán)重w描述了粒子上一代速度對(duì)當(dāng)前速度的影響。w值較大，全局尋優(yōu)能力強(qiáng)，局部尋優(yōu)能力弱，反之，則局部尋優(yōu)能力強(qiáng)，而全局尋優(yōu)能力減弱。目前，采用較多的慣性權(quán)值是線性遞減權(quán)值（linearly decreasing weight，簡稱LDW）策略，即

其中，Tmax為最大進(jìn)化代數(shù)，wint為初始慣性權(quán)值，wend為進(jìn)化至最大代數(shù)時(shí)的慣性權(quán)值。典型取值wint=0.9，wend=0.4。慣性權(quán)值w的引入使PSO算法的性能到了很大提高。每代粒子的適應(yīng)度函數(shù)

來更新下一代數(shù)據(jù)的。其中pi表示屬于某個(gè)類的樣本數(shù)量，Nc表示類別的數(shù)量，mij則表示屬于第i個(gè)類的第j個(gè)樣本。

為了使文檔可視化，表示為2維空間中可見的數(shù)據(jù)。必須為文檔進(jìn)行降維處理。本論文中所采用的降維方式為主成成分分析（PCA）方式，假設(shè)樣本X1，X2，…，XN（Xi∈Rn，i=1，2，…N），則樣本集所估計(jì)的協(xié)方差矩陣為：

事實(shí)上，這一組最佳投影軸應(yīng)取Σ的d個(gè)最大特征值所對(duì)應(yīng)的標(biāo)準(zhǔn)特征向量。將所有的30維數(shù)據(jù)通過PCA變換后得到2維數(shù)據(jù)。通過試驗(yàn)得知第一主成分和第二主成分的積累貢獻(xiàn)率達(dá)到80%以上，所以本文取前兩維作為聚類可視化的X維和Y維。對(duì)二維數(shù)據(jù)表示得的文檔集合進(jìn)行PSO，可以看到聚類的效果。

3 小結(jié)

本章通過對(duì)Web的內(nèi)容挖掘的模型實(shí)現(xiàn)，實(shí)現(xiàn)對(duì)采集到的文檔分別聚類保存。Web內(nèi)容挖掘首先要獲取內(nèi)容，通過HML的文檔樹分析采用Map/Reduce進(jìn)行原始數(shù)據(jù)清理，然后通過Hive對(duì)數(shù)據(jù)分析構(gòu)建粒子群聚類模型，實(shí)現(xiàn)對(duì)樣本數(shù)據(jù)的挖掘生成粒子群模型。使用RostNat采集數(shù)據(jù)，將采集到的文檔分別聚類保存，將其分離為單個(gè)文檔。生成的每個(gè)文檔都表示為向量空間模型D，然后對(duì)其進(jìn)行分詞，詞條化，根據(jù)特征進(jìn)一步對(duì)分詞進(jìn)行處理，得到TDIDF權(quán)重值。通過實(shí)驗(yàn)仿真，提出參數(shù)修改方案，對(duì)PSO聚類效果進(jìn)行實(shí)現(xiàn)，對(duì)于文本聚類的穩(wěn)定性和收斂性的得到了較好的聚類效果。但對(duì)于其收斂性還沒有得到徹底解決，對(duì)整個(gè)算法進(jìn)行優(yōu)化，提高了數(shù)據(jù)挖掘的效率。

[1]林士敏，田鳳占.粒子群網(wǎng)絡(luò)的建造及其在數(shù)據(jù)采掘中的應(yīng)用[J].清華大學(xué)學(xué)報(bào)，2001，41（1）：49-52.

[2]張學(xué)明，施法中.分布式并行Web數(shù)據(jù)挖掘系統(tǒng)的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2002，4（1）：198-200.

[3]于滿泉，陳鐵睿，徐洪波.基于分塊的網(wǎng)頁信息解析器的研究與設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用，2005，25（4）：974-976.

[4]陳博.WEB文本情感分類中關(guān)鍵問題的研究[D].2008：49-53.