基于粒子群優(yōu)化算法的Web挖掘技術(shù)的研究

摘要：Web是目前最大的信息系統(tǒng)。Web挖掘就從Web文檔和Web活動(dòng)中發(fā)現(xiàn)和抽取用戶感興趣的、潛在的、有用模式和隱藏的知識(shí)。本文介紹了有關(guān)web挖掘的任務(wù)和存在問題，同時(shí)介紹了PSO算法以及各種改進(jìn)措施。

關(guān)鍵詞：Web；挖掘；PSO

隨著Internet的迅速發(fā)展，World Wide Web已深入到社會(huì)生活的方方面面。Web可以說是目前最大的信息系統(tǒng)，其數(shù)據(jù)具有海量、多樣、異構(gòu)、動(dòng)態(tài)變化等特性。人們使用Web，一般有如下需求[1]：

獲取相關(guān)信息或服務(wù)；

從Web信息中發(fā)現(xiàn)新的知識(shí)；

提供個(gè)性化服務(wù)：不同的用戶對(duì)信息、服務(wù)有不同的要求。

為了解決上述問題，人們迫切需要能自動(dòng)地從Web上發(fā)現(xiàn)、抽取和過慮信息的工具，由此產(chǎn)生了Web挖掘。

Web挖掘就是從Web文檔和Web活動(dòng)中發(fā)現(xiàn)和抽取潛在的、用戶感興趣的有用模式和隱藏的知識(shí)[2]。

1.Web挖掘

WEB挖掘可以認(rèn)為包括以下四個(gè)子任務(wù)[3，4]：資源發(fā)現(xiàn)、信息選擇和預(yù)處理、概括和泛化、分析。

資源發(fā)現(xiàn)是一個(gè)從Web上的聯(lián)機(jī)資源中檢索數(shù)據(jù)的過程。信息選擇和預(yù)處理是一個(gè)信息轉(zhuǎn)變的過程。它可以是除去停用詞，詞干處理，發(fā)現(xiàn)訓(xùn)練集中的短語，以及得到關(guān)系或邏輯表示等。概括過程是應(yīng)用數(shù)據(jù)采掘技術(shù)獲得知識(shí)。最后的分析是對(duì)采掘結(jié)果的驗(yàn)證和解釋，在此過程中應(yīng)該發(fā)揮人的作用。

Web文本信息的特征獲取是指自動(dòng)地從Web文本信息中抽取出代表其內(nèi)容主題的特征詞條形成特征矢量來表示W(wǎng)eb文本。它影響到下一步Web文本分類的質(zhì)量。文本挖掘問題的一個(gè)主要難點(diǎn)是特征矢量的維數(shù)過高，對(duì)于大多數(shù)學(xué)習(xí)算法來說都難以承受。目前已有多種方法被用于特征抽取，比如文檔頻次門限方法、信息增益方法、χ2分布方法、互信息熵方法、基于奇異值分解的潛在語義索引方法（LSI）以及基于遺傳算法的特征提取算法等。

聚類技術(shù)是對(duì)符合某一訪問規(guī)律特征的用戶進(jìn)行用戶特征挖掘。Web使用挖掘中存在兩種類型的聚類：使用聚類(用戶聚類)和頁(yè)面聚類。根據(jù)聚類的結(jié)果聚類方法可分為層次聚類與非層次聚類。在不同的方法中，人們研究了獲得較高的計(jì)算效率的問題。

在Web使用挖掘過程中，對(duì)用戶、Web頁(yè)面等Web對(duì)象進(jìn)行聚類時(shí)，存在明顯的模糊性，模糊聚類也因此成為目前Web聚類分析研究的主流。

2.Web挖掘中存在的問題

Web數(shù)據(jù)挖掘[5]與傳統(tǒng)數(shù)據(jù)挖掘不同，Web頁(yè)面的結(jié)構(gòu)比一般文本文件復(fù)雜很多，它可以支持多種媒體的表達(dá)。人們最初是希望通過Web來實(shí)現(xiàn)世界各種信息的互通，在這個(gè)平臺(tái)上自然希望任何的信息都可以表達(dá)了。因此也造成了互聯(lián)網(wǎng)數(shù)據(jù)的復(fù)雜性這個(gè)特點(diǎn)。而在互聯(lián)網(wǎng)上文檔一般是分布的，異構(gòu)的，無結(jié)構(gòu)或者半結(jié)構(gòu)的。許多新技術(shù)的產(chǎn)生為解決這個(gè)難題提供了一條可行的道路，如XML技術(shù)。還有，互聯(lián)網(wǎng)上的數(shù)據(jù)動(dòng)態(tài)性極強(qiáng)，頁(yè)面本身的內(nèi)容和相關(guān)的鏈接經(jīng)常更新。而互聯(lián)網(wǎng)面對(duì)的客戶也各不相同，這些都造成了用戶行為模式分析的困難度。

現(xiàn)行Web挖掘方法很多，解決Web信息應(yīng)用部分問題，但存在一定的不足，如：由于用戶查詢固有的主觀性、不精確性和不確定性，大多數(shù)Web檢索系統(tǒng)僅用一個(gè)簡(jiǎn)單的檢索模型，側(cè)重于檢索效率，忽視了檢索的準(zhǔn)確性。不能進(jìn)行軟決策，現(xiàn)有查詢是基于“硬拋棄”法，而且取決于查詢與檢索出文檔的相關(guān)性，但相關(guān)性只是文檔的部分屬性，不是很分明的界限。頁(yè)面分級(jí)還不全面，還沒有考慮各種參數(shù)的權(quán)重，如點(diǎn)擊位置、相鄰性和頻率等，分級(jí)還很少考慮用戶的特點(diǎn)。

為處理Web數(shù)據(jù)特征，克服目前現(xiàn)有的Web挖掘方法的局限，軟計(jì)算方法是一個(gè)很好的方法。軟計(jì)算是一組協(xié)同的方法，它提供一種處理現(xiàn)實(shí)中模糊狀態(tài)信息靈活處理能力。它們的目標(biāo)是通過探索不精確、不確定、近似推理和局部正確的最大可能限度，達(dá)到易理解的、健壯的和低代價(jià)的解決方案，類似人的決策過程。軟計(jì)算技術(shù)包括模糊邏輯(fuzzy logic，F(xiàn)L)、粗糙集(rough set，RS)、人工神經(jīng)網(wǎng)絡(luò)(artificial neural network，ANN)和遺傳算法(genetic algorithm，GA)[ 5-8]。

現(xiàn)有的Web文檔特征抽取算法文章證明這些特征抽取方法都有一些局限。傳統(tǒng)的聚類分析把每個(gè)待辨識(shí)的對(duì)象嚴(yán)格地劃分到某個(gè)類中，各個(gè)類別的界限是分明的。然而現(xiàn)實(shí)世界存在著大量的界限劃分不嚴(yán)格的聚類問題。即問題具有一定的模糊性，如在區(qū)分“優(yōu)”和“良”等級(jí)時(shí)，就需要模糊劃分。在Web使用挖掘過程中，對(duì)用戶、Web頁(yè)面等Web對(duì)象進(jìn)行聚類時(shí)，存在明顯的模糊性，模糊聚類也因此逐漸成為Web聚類分析研究的主流。

3.粒子群優(yōu)化算法

粒子群優(yōu)化(Particle Swarm Optimization， PSO)算法[1]是Kennedy和Eberhart受人工生命研究結(jié)果的啟發(fā)、通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機(jī)搜索算法，與其他進(jìn)化算法一樣，也是基于“種群”和“進(jìn)化”的概念，通過個(gè)體間的協(xié)作與競(jìng)爭(zhēng)，實(shí)現(xiàn)復(fù)雜空間最優(yōu)解的搜索；同時(shí)，PSO又不像其他進(jìn)化算法那樣對(duì)個(gè)體進(jìn)行交叉、變異、選擇等進(jìn)化算子操作，而是將群體(swarm)中的個(gè)體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子(particle)，每個(gè)粒子以一定的速度在解空間運(yùn)動(dòng)，并向自身歷史最佳位置pbest和鄰域歷史最佳位置gbest聚集，實(shí)現(xiàn)對(duì)候選解的進(jìn)化。PSO算法具有很好的生物社會(huì)背景而易理解、參數(shù)少而易實(shí)現(xiàn)，對(duì)非線性、多峰問題均具有較強(qiáng)的全局搜索能力，在科學(xué)研究與工程實(shí)踐中得到了廣泛關(guān)注[3-8] 。

由于PSO 中粒子向自身歷史最佳位置和鄰域或群體歷史最佳位置聚集，形成粒子種群的快速趨同效應(yīng)，容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象。同時(shí)，PSO的性能也依賴于算法參數(shù)。為了克服上述不足，國(guó)內(nèi)外學(xué)者相繼提出了各種改進(jìn)措施。主要有粒子群初始化、鄰域拓?fù)洹?shù)選擇和混合策略四類。

4.結(jié)論

由此可見，由于Web信息的獨(dú)特性，和傳統(tǒng)的數(shù)據(jù)挖掘相比，Web挖掘還有很多需要解決的難題需要我們針對(duì)實(shí)際應(yīng)用加以解決。

參考文獻(xiàn)：

[1]吉林大學(xué)博士學(xué)位論文 Web挖掘中若干問題的研究 許建潮 2005.6.10.

[2]Raymond Kosala，Hendrik Blockeel， Web Mining Research: A Survey， SIGKDD Explorations，2(1)，pages 1-15，July 2000.

[3]中國(guó)科學(xué)院博士學(xué)位論文 WEB信息檢索與分類中的數(shù)據(jù)采掘研究 李曉黎 2001.5.21.

[4]周龍鑲，陽小華．基于用戶訪問模式的WWW瀏覽路徑優(yōu)化[J]．軟件學(xué)報(bào)，2001，12(6)，846～850.

[5]Jianhan Zhu，Jun Hong，John G Hughes．Using Markov Models for Web Site Link Prediction．In：Proceedings ofthe thirteenth ACM conference on Hypertext and hypermedia．Maryland(USA)，2002，169~170.

[6]浙江大學(xué)博士畢業(yè)論文 Web訪問信息挖掘若干關(guān)鍵技術(shù)的研究 余軼軍 2006.4.1.

[7]S.Mitra，S.K.Pal，P.Mitra.Data mining in soft computing framework:A survey.IEEE Transactions on Neural Networks，2001，13:3~14.

[8]劉清.Rough集及Rough推理，北京:科學(xué)出版社，2003.