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

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

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

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

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

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

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

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

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

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