基于ACO的Web使用挖掘方法研究.pdf

1、互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，實現(xiàn)了全球的資源共享和信息交換。然而互聯(lián)網(wǎng)上的信息量呈指數(shù)級速度增長所導(dǎo)致的“信息過載”和“信息迷航”問題已日益制約用戶高效地使用各種信息資源。網(wǎng)站通過提供Web個性化服務(wù)可以提高用戶的訪問效率和滿意度。實現(xiàn)Web個性化推薦所面臨的關(guān)鍵問題是需要對大量匿名用戶的行為模型進(jìn)行深層理解，傳統(tǒng)的個性化方法很難處理匿名用戶的情形，把Web使用挖掘用于Web個性化推薦是解決上述問題的有效途徑。作為Web數(shù)據(jù)挖掘的一個重要組成

2、部分，Web使用挖掘就是利用數(shù)據(jù)挖掘技術(shù)分析用戶訪問留下的日志文件，挖掘用戶瀏覽模式的過程。Web使用挖掘可用于理解用戶在網(wǎng)站的訪問行為，從而可以主動為用戶提供網(wǎng)站導(dǎo)航服務(wù)。蟻群算法(Ant Colony Optimization，簡稱ACO)作為群體智能算法的一個分支，是受真實蟻群覓食行為的啟發(fā)而逐步發(fā)展起來的一種模擬螞蟻群體智能行為的算法。由于其在求解復(fù)雜優(yōu)化問題方面的優(yōu)勢，在許多領(lǐng)域都得到了應(yīng)用。因此，將蟻群算法引入Web使用挖掘

3、、發(fā)現(xiàn)用戶的瀏覽模式、為用戶提供導(dǎo)航推薦服務(wù)，具有重要的理論意義和應(yīng)用價值。
　　 本文首先對蟻群算法的收斂性和Web使用數(shù)據(jù)的預(yù)處理進(jìn)行了研究，在此基礎(chǔ)上，分別將蟻群算法應(yīng)用于用戶導(dǎo)航模式和用戶聚類的挖掘。所做的主要工作及創(chuàng)新性研究成果如下：
　　 (1)在圖搜索螞蟻系統(tǒng)的收斂性分析基礎(chǔ)上，對基本蟻群算法進(jìn)行了改進(jìn)，并對這種改進(jìn)的蟻群算法構(gòu)造全局最優(yōu)解的概率等收斂性問題進(jìn)行了研究。首先對Dorigo Macro提出的基

4、本蟻群算法中的Ant Cycle模型作了三點改進(jìn)：其一是僅最優(yōu)秀螞蟻釋放信息素，即在第f步迭代結(jié)束之后，僅對前t步迭代中所找到的最優(yōu)解上的弧進(jìn)行信息素的加強，這樣就鼓勵螞蟻在至今發(fā)現(xiàn)的最好路徑的鄰近區(qū)域去搜索路徑，使螞蟻對解空間的探索更有方向性；其二是對殘留信息素數(shù)量進(jìn)行限幅控制。為了避免算法過早收斂于非全局最優(yōu)解，在算法的迭代過程中，對任意弧上的殘留信息素設(shè)定了下界；其三是信息素?fù)]發(fā)系數(shù)自適應(yīng)變化。通過揮發(fā)系數(shù)的自適應(yīng)變化使蟻群在算法

5、的前面階段增加搜索的隨機性，避免搜索過度集中，有利于搜尋更優(yōu)解；在算法的后期，減小隨機程度，增加收斂速度，使算法在已經(jīng)搜索到較優(yōu)解的情況下，逐漸收斂到全局最優(yōu)解。在此基礎(chǔ)上，對該算法的收斂性進(jìn)行了證明。在僅需滿足兩個基本假設(shè)條件的前提下，證明了算法能以接近于1的概率收斂于最優(yōu)解。實驗結(jié)果表明，與基本蟻群算法相比，本文算法的全局搜索能力與收斂速度都有所提高，是一種有效的算法。
　　 (2)在分析現(xiàn)有的Web使用數(shù)據(jù)預(yù)處理過程的基礎(chǔ)

6、上，對預(yù)處理中的一個關(guān)鍵問題--會話識別問題進(jìn)行了研究，并提出了一種基于自適應(yīng)時間閾值的會話識別方法。傳統(tǒng)的面向時間的方法只根據(jù)一個固定的時間閾值參數(shù)來識別會話的方法是具有局限性的，本文利用動態(tài)的時間閾值參數(shù)進(jìn)行會話識別，分析每個用戶的平均頁面訪問時間，并結(jié)合固定的時間閾值得到一個動態(tài)的自適應(yīng)時間閾值，從而實現(xiàn)會話訪問時間參數(shù)的個性化。實驗結(jié)果表明，通過該方法獲得的用戶會話能夠更加準(zhǔn)確地描述用戶的實際瀏覽行為，對模式發(fā)現(xiàn)階段能夠產(chǎn)生好的

7、影響，從而可以提高基于Web使用挖掘的用戶導(dǎo)航推薦結(jié)果的質(zhì)量。
　　 (3)基于螞蟻覓食行為與用戶瀏覽網(wǎng)頁行為的相似性，把Web用戶看成是人工的螞蟻，利用蟻群算法中的概念“外激素”來反映用戶的訪問興趣，提出了一個蟻群導(dǎo)航模型來挖掘用戶的興趣導(dǎo)航模式。首先考慮了頁面訪問次數(shù)、頁面訪問順序、網(wǎng)站結(jié)構(gòu)和頁面訪問時間等因素對用戶導(dǎo)航路徑模式挖掘的影響，其次，考慮了早期訪問者與現(xiàn)有訪問者對導(dǎo)航路徑模式發(fā)現(xiàn)的不同影響，提出了基于蟻群算法的群

8、體用戶導(dǎo)航模型，并應(yīng)用蟻群算法來發(fā)現(xiàn)用戶偏好的導(dǎo)航路徑模式。實驗結(jié)果表明，與傳統(tǒng)算法相比，蟻群算法應(yīng)用于用戶導(dǎo)航推薦的準(zhǔn)確性較高，說明蟻群算法揭示的是群體用戶的興趣路徑，更能反映用戶的瀏覽偏好。
　　 (4)將蟻群算法應(yīng)用于Web使用聚類挖掘領(lǐng)域，提出了一種蟻群算法與K-means算法相結(jié)合的方法對訪問網(wǎng)站的用戶進(jìn)行聚類。首先介紹了基于群體智能的蟻群聚類算法的四種模型，然后將基于蟻群覓食行為的蟻群算法引入Web使用聚類。蟻群算法

9、的一個重要特征是對初始過程不敏感，在滿足一定的條件下總是能收斂到全局最優(yōu)解，但是收斂速度較慢；與蟻群算法相對照，K-means聚類收斂速度較快，但很可能收斂到一個局部最優(yōu)解，并且由于初始聚類是隨機生成的，其結(jié)果受到初始過程的影響。本文提出一種將K-means算法嵌入到蟻群算法中的混合算法，充分利用蟻群算法的全局搜索能力和K-means算法的局部搜索能力，并將該算法應(yīng)用到Web用戶聚類問題的求解中，實驗結(jié)果表明該方法是有效的，與K-mea