WEB日志挖掘技術(shù)研究與應(yīng)用

WEB日志挖掘技術(shù)研究與應(yīng)用WEB日志挖掘技術(shù)研究與應(yīng)用/WEB日志挖掘技術(shù)研究與應(yīng)用第五章，原來是關(guān)聯(lián)規(guī)則，現(xiàn)在要改成聚類的方式，算法為第四章的改進(jìn)的蟻群算法。原來的功能圖太寬跨界了，圖不可以超過文檔的內(nèi)容部分。第一章,主要是研究現(xiàn)狀及分析進(jìn)行修改,其他的文字表述做相應(yīng)修改查重率差不多達(dá)到10％引言隨著Web日志技術(shù)的急劇增長(zhǎng)和快速普及,以及在電子商務(wù)和信息共享等方面的廣泛應(yīng)用,用戶可以用很低的成本從網(wǎng)絡(luò)上獲得信息，Internet已成為最豐富的信息來源地，為了更好地對(duì)這些大量、無序的網(wǎng)頁信息進(jìn)行排序和檢索，需要提升搜索引擎對(duì)網(wǎng)絡(luò)信息的處理和組織能力,因此在這樣的形勢(shì)下，產(chǎn)生了Web日志挖掘(Web日志Mining）［1］技術(shù)，目的在于從Web日志的組織結(jié)構(gòu)和鏈接關(guān)系中發(fā)掘出有用的模式和規(guī)律，該技術(shù)無疑成為數(shù)據(jù)挖掘中的熱點(diǎn)，包括自然規(guī)則計(jì)算方法、神經(jīng)網(wǎng)絡(luò)、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)為主等人工智能相關(guān)技術(shù)。隨著Internet/WWW的全球互通互連,從中取得的數(shù)據(jù)量難以計(jì)算，所以當(dāng)處理這些數(shù)據(jù)并且從Web日志的服務(wù)中抽取信息時(shí)需要采用Web日志挖掘技術(shù).Web日志挖掘需要從非結(jié)構(gòu)化、半結(jié)構(gòu)化或動(dòng)態(tài)易混淆的數(shù)據(jù)中,抽取潛在的、易用的信息和模式的過程.根據(jù)Web日志數(shù)據(jù)類別的不同，可以將Web日志挖掘分為以下三類：Web日志內(nèi)容挖掘、結(jié)構(gòu)挖掘和使用挖掘.這三類挖掘分別作用于網(wǎng)頁信息站點(diǎn)中的內(nèi)容、結(jié)構(gòu)和使用信息,并且已經(jīng)在發(fā)現(xiàn)用戶訪問模式、反競(jìng)爭(zhēng)情報(bào)活動(dòng)、建立數(shù)據(jù)倉(cāng)庫等很多方面得到了應(yīng)用。課題背景及研究意義隨著萬維網(wǎng)的迅速發(fā)展以及良好的發(fā)展趨勢(shì)，尤其是電子商務(wù)的蓬勃發(fā)展為網(wǎng)絡(luò)應(yīng)用提供了強(qiáng)大的支撐。然而處理Web日志上海量的數(shù)據(jù)量，需要一種能高效快捷地從Web日志頁面中獲取信息的工具,由此搜索引擎產(chǎn)生了。現(xiàn)有的搜索引擎技術(shù)在很大程度上方便了人們對(duì)信息的檢索,不過仍然存在一些不足之處，比如搜索精度不高、覆蓋率有限等問題，無法更好地發(fā)現(xiàn)Web日志上潛在、隱藏的知識(shí).將傳統(tǒng)的數(shù)據(jù)挖掘同Web日志相融合,從而發(fā)展出了Web日志挖掘，該技術(shù)就傳統(tǒng)的數(shù)據(jù)挖掘來看存在較多優(yōu)勢(shì).傳統(tǒng)數(shù)據(jù)挖掘技術(shù)只是對(duì)數(shù)據(jù)結(jié)構(gòu)中結(jié)構(gòu)化的數(shù)據(jù)進(jìn)行挖掘，通過數(shù)據(jù)間的存儲(chǔ)結(jié)構(gòu)不同來發(fā)現(xiàn)知識(shí)，而Web日志挖掘是針對(duì)半結(jié)構(gòu)化、雜亂、動(dòng)態(tài)的數(shù)據(jù)進(jìn)行挖掘，由于Web日志頁面內(nèi)容的復(fù)雜程度遠(yuǎn)超過普通文本的樣式結(jié)果，所以導(dǎo)致了Web日志挖掘技術(shù)無法直接傳承傳統(tǒng)的數(shù)據(jù)庫挖掘模型和技術(shù)。這就讓挖掘的前提需要將傳統(tǒng)數(shù)據(jù)挖掘技術(shù)及Web日志挖掘相結(jié)合，融合各自的優(yōu)點(diǎn)，使整個(gè)數(shù)據(jù)挖掘系統(tǒng)同數(shù)據(jù)庫能更緊密的結(jié)合在一起。由于要對(duì)數(shù)據(jù)進(jìn)行組織和整合，這就需要一個(gè)完整的Web日志挖掘體系，才能分析并得出自己需要的信息。因此進(jìn)行挖掘之前需要找到相關(guān)的Web日志文檔.各Web日志信息之間有著密切的關(guān)系,從中找到正確的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，利用自動(dòng)化搜索的方法實(shí)現(xiàn)對(duì)Web日志上信息結(jié)構(gòu)排序和內(nèi)容的抽取，避免了各算法之間使用的重復(fù)性.蟻群算法是一種模擬進(jìn)化的算法，它是借鑒螞蟻在尋找食物過程中會(huì)自動(dòng)搜尋最短路徑而衍生出來的。該算法具有優(yōu)良的分布式計(jì)算、正反饋性等特點(diǎn)，特別是在解決組合最優(yōu)的問題上已經(jīng)吸引了很多中外學(xué)者的關(guān)注。它也是繼遺傳算法、人工神經(jīng)網(wǎng)絡(luò)算法后又一個(gè)得到大家認(rèn)可的研究性課題。研究現(xiàn)狀及分析Web日志挖掘無論在國(guó)內(nèi)還是國(guó)外都是通過挖掘服務(wù)器存儲(chǔ)的Web日志，進(jìn)而發(fā)現(xiàn)用戶訪問Web站點(diǎn)的訪問模式。根據(jù)對(duì)Web日志數(shù)據(jù)源處理方法的不同，Web日志挖掘可以分為以下兩類:第一類是將Web日志記錄中的數(shù)據(jù)進(jìn)行轉(zhuǎn)換，然后傳遞進(jìn)傳統(tǒng)的關(guān)系表中，再用常規(guī)的算法對(duì)關(guān)系表中的數(shù)據(jù)進(jìn)行挖掘。第二類是在對(duì)Web日志記錄的數(shù)據(jù)進(jìn)行挖掘之前對(duì)數(shù)據(jù)先進(jìn)行數(shù)據(jù)預(yù)處理操作.國(guó)外對(duì)Web日志挖掘的研究基本上可以從1996年算起,比較突出的有：1996年學(xué)者M(jìn)。S。Chen、H。Mannila、T.Yan提出了可以將數(shù)據(jù)挖掘方法用于Web研究領(lǐng)域。Mannila和Chen在研究過程中都假設(shè)去掉了圖形文件、聲音文件以后的Web服務(wù)器日志如實(shí)地反映了用戶在網(wǎng)站中訪問的情況。Mannila[2］把用戶訪問頁面當(dāng)作事件,從網(wǎng)站訪問日志中試著尋找用戶訪問網(wǎng)站的周期。ChenREF_Ref435648169\r\＊MERGEFORMAT[3]提出了最大向前參引路徑,并提出用這種方法把用戶的Session分解成為一個(gè)個(gè)訪問事務(wù),然后就可以在事務(wù)基礎(chǔ)上，挖掘用戶訪問的模式。T.Yan研究了如何動(dòng)態(tài)地根據(jù)將用戶進(jìn)行分類,并根據(jù)同類用戶訪問頁面的情況提供推薦頁面。1997年，PerKowitz[4]等人在人機(jī)界面研究領(lǐng)域提出了AdaPtiveWebSite的概念,主要研究的是如何以歷史訪問為依據(jù)，使服務(wù)器提供的頁面可以自動(dòng)或者半自動(dòng)化地調(diào)整.1998年Han把Web服務(wù)器訪問日志集成到數(shù)據(jù)立方體結(jié)構(gòu)（Datacubestructure)中，這樣就可以對(duì)訪問日志用傳統(tǒng)的在線數(shù)據(jù)分析處理過程（oLAP)來處理日志數(shù)據(jù)了REF_Ref435648229\r[5］.國(guó)內(nèi)互聯(lián)網(wǎng)是從1997年開始迅速蓬勃的發(fā)展起來的。直到1999年，國(guó)內(nèi)互聯(lián)網(wǎng)用戶達(dá)到一定數(shù)量以后，國(guó)內(nèi)學(xué)者才開始關(guān)注Web數(shù)據(jù)挖掘,相比國(guó)外起步較晚。國(guó)內(nèi)的學(xué)者在基于Web日志挖掘的個(gè)性化服務(wù)方面主要側(cè)重于理論研究，比較突出的有:沈鈞毅［6]等人提出以Web站點(diǎn)的URL為行，以UserID為列，建立URLes-UserID關(guān)聯(lián)矩陣，元素值為用戶的訪問次數(shù)。然后，對(duì)列向量進(jìn)行相似性分析得到相關(guān)Web頁面；對(duì)相關(guān)頁面進(jìn)行進(jìn)一步處理，便可以發(fā)現(xiàn)頻繁訪問路徑。王紅俠[7］等人采用基于事務(wù)的方法,研究Web日志挖掘預(yù)處理及用戶訪問序列模式挖掘方法，提出了一種基于BitlnaP序列模式進(jìn)行用戶瀏覽模式識(shí)別的Web日志挖掘方法。吳俊杰［8]等人采用Web站點(diǎn)的訪問日志進(jìn)行事務(wù)識(shí)別后，根據(jù)群體用戶對(duì)Web站點(diǎn)的訪問順序進(jìn)行路徑聚類，最終的聚類結(jié)果反映出全體用戶的訪問興趣。吳躍進(jìn)認(rèn)為，能夠成為Web用戶聚類算法評(píng)價(jià)因素的參數(shù)有且僅有三個(gè),分別是點(diǎn)擊次數(shù)、訪問時(shí)間和訪問路徑;并在此基礎(chǔ)上利用Kruskal算法衍生出了K—Bacer算法,根據(jù)訪問頻繁路徑對(duì)用戶進(jìn)行聚類REF_Ref404608443\r［9]。吳躍進(jìn)將所有用戶的訪問序列生成無向圖，通過K—Bacer算法找出其中的頻繁路徑.K-Bacer算法是利用Kruskal算法的思想去產(chǎn)生最小生成樹，溯其根源是貪心算法.算法的時(shí)間復(fù)雜度依賴于排序算法，同時(shí)對(duì)所有用戶生成同一個(gè)無向圖,隨著用戶量的增加，其可維護(hù)性和可擴(kuò)展性大大降低。（1)Web日志挖掘聚類和分類技術(shù)聚類是從Web日志的訪問數(shù)據(jù)中分析并整合出來具有相似特征事務(wù)的技術(shù)。Web日志使用挖掘中分為：頁面聚類和使用聚類。頁面聚類是通過搜索引擎在Web日志上找到具有相關(guān)內(nèi)容的頁面組，這更方便于用戶在上網(wǎng)時(shí)能更容易地獲得想要的信息。使用聚類就是將具有相似瀏覽模式的用戶分為一組，這樣形成了若干組，并對(duì)其量化,從中得到對(duì)用戶有用的規(guī)則，當(dāng)前該技術(shù)常應(yīng)用于電子商務(wù)和一些個(gè)性化服務(wù)上。這兩種聚類方法就是通過搜索引擎分析用戶查詢或訪問網(wǎng)頁信息時(shí)產(chǎn)生的歷史記錄所形成的HTML，來向用戶提供超鏈接.分類是對(duì)新添加的數(shù)據(jù)進(jìn)行分類并將一個(gè)對(duì)象分到事先定義好的類中，根據(jù)用戶群的特征來挖掘出用戶群的訪問特征.在Web日志挖掘中，分類可以通過訪問用戶信息而得到的一些用戶特征,這需要抽取并選擇出最好地描述這組特定用戶的特征，并根據(jù)這些特征對(duì)用戶進(jìn)行分類。常使用監(jiān)督歸納學(xué)習(xí)算法來進(jìn)行分類，如決策樹、K-鄰近分類法和支持向量機(jī)、機(jī)器學(xué)習(xí)法、貝葉斯分類方法等。（2）蟻群算法蟻群算法，現(xiàn)在被稱為蟻群優(yōu)化（ACO,AntColonyOptimization)是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法，它源于社會(huì)昆蟲的群體活動(dòng)所表現(xiàn)出來令人驚訝的行為，也這對(duì)日后研究蟻群行為提供全新的領(lǐng)域.ACO技術(shù)是一種基于群體智能的算法,它源于自然解決問題的思想，并在求解組合優(yōu)化類問題上有明顯的優(yōu)越性.MarcoDorigo在1991年他的論文中首先提出了螞蟻系統(tǒng)(AS）,通過正反饋、分布式協(xié)作來尋找最優(yōu)路徑。并且常用于解決二次指派、多維背包、Job-shop調(diào)度等問題上。AS優(yōu)化算法采用了分布式計(jì)算方法，具有多代理性和較強(qiáng)的魯棒性等特點(diǎn)，且該算法已被大量應(yīng)用于機(jī)器人協(xié)作問題求解、電力、通信、數(shù)據(jù)分析等領(lǐng)域。蟻群算法是學(xué)者受到螞蟻覓食的啟發(fā)而發(fā)現(xiàn)的，螞蟻總能找到巢穴及食物源之間的最短路徑.經(jīng)研究發(fā)現(xiàn)，螞蟻群體協(xié)作功能是通過遺留在來往路徑上的信息素(Pheromone)來進(jìn)行信息通訊并形成正反饋。假設(shè)螞蟻?zhàn)邇蓷l不同的路徑來尋找食物，剛開始的時(shí)候走兩條路的螞蟻一樣多，并且在搜索過程中釋放出一定量的信息素，當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)后返回，短路徑的螞蟻來回一次時(shí)間就短且重復(fù)頻率快，因而在同一時(shí)間內(nèi)走過該路徑的螞蟻數(shù)目就多，灑下的信息素也就多，自然就有更多的螞蟻會(huì)吸引過來,這樣慢慢當(dāng)螞蟻數(shù)量不斷增加時(shí)（同樣信息素濃度也增加)，最短的路徑就近似被發(fā)現(xiàn)了。螞蟻系統(tǒng)具有搜索最優(yōu)的能力，得利于其同分布式計(jì)算和正反饋機(jī)制相結(jié)合的特點(diǎn)，使其具有較強(qiáng)的并行性和魯棒性，但也同樣存在一些缺陷,如搜索停滯以及搜索結(jié)果局部最優(yōu)等問題。針對(duì)該系統(tǒng)存在的不足，很多中外學(xué)者提出了許多改進(jìn)的蟻群算法，這些優(yōu)化算法在解決局部搜索最優(yōu)問題以及搜索停滯問題上有很大的提升。在當(dāng)前研究形勢(shì)下，蟻群算法已經(jīng)成為中外學(xué)者廣泛關(guān)注的熱點(diǎn)問題。論文組織結(jié)構(gòu)論文中較系統(tǒng)地分析和論述了Web日志挖掘中的各項(xiàng)技術(shù)。在此理論基礎(chǔ)上，引入了改進(jìn)的蟻群算法，并將其成功應(yīng)用于Web日志挖掘的聚類和分類上。論文的整體構(gòu)架如下：第一章緒論介紹了本課題的研究背景，主要內(nèi)容和論文的組織結(jié)構(gòu)第二章基于蟻群算法的Web日志挖掘理論介紹了Web日志挖掘理論，在論述了Web日志挖掘過程的基礎(chǔ)上，詳細(xì)地分析了Web日志挖掘中聚類和分類技術(shù)。然后分析了蟻群算法及幾種改進(jìn)的蟻群算法的思想。最后，對(duì)現(xiàn)有算法應(yīng)用于Web日志挖掘技術(shù)上存在的問題做了詳細(xì)地論述。第三章Web日志挖掘的預(yù)處理技術(shù)對(duì)Web日志挖掘中的關(guān)鍵技術(shù)，即Web日志挖掘預(yù)處理技術(shù)進(jìn)行了全面的分析和總結(jié)。第四章基本蟻群算法及其改進(jìn)對(duì)蟻群算法基本原理以傳統(tǒng)日志挖掘算法原理進(jìn)行了分析，并對(duì)基本蟻群算法進(jìn)行了改進(jìn)，通過仿真來說明基本蟻群算法的原理。第五章Web日志數(shù)據(jù)挖掘系統(tǒng)的實(shí)現(xiàn)以中名老中醫(yī)臨床經(jīng)驗(yàn)、學(xué)術(shù)思想傳承研究中的Web日志數(shù)據(jù)為例，基于改進(jìn)的蟻群算法設(shè)計(jì)了一套Web日志數(shù)據(jù)挖掘系統(tǒng)，并對(duì)系統(tǒng)進(jìn)行了評(píng)價(jià)和分析，為改善中醫(yī)系統(tǒng)網(wǎng)站提出了優(yōu)化建議。第六章總結(jié)及展望總結(jié)了本文的研究工作，提出進(jìn)一步研究的方向。基于蟻群算法的Web日志挖掘概念Web日志挖掘隨著信息技術(shù)的普及和應(yīng)用,各個(gè)領(lǐng)域產(chǎn)生了大量的數(shù)據(jù),這些數(shù)據(jù)被獲取、存儲(chǔ)下來,其中蘊(yùn)含著豐富的信息。人們持續(xù)不斷地探索處理這些數(shù)據(jù)的方法，以期最大程度地從中挖掘有用的信息，面對(duì)如潮水般不斷增加的數(shù)據(jù),人們不再滿足于數(shù)據(jù)的查詢和統(tǒng)計(jì)分析，而是期望從數(shù)據(jù)中提取信息或者知識(shí)為決策服務(wù)。數(shù)據(jù)挖掘技術(shù)突破了數(shù)據(jù)分析技術(shù)的種種局限，它結(jié)合統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫、機(jī)器學(xué)習(xí)等技術(shù)解決從數(shù)據(jù)中發(fā)現(xiàn)新的信息,輔助決策這一難題，是正在飛速發(fā)展的前沿學(xué)科。一些大型企業(yè)對(duì)數(shù)據(jù)挖掘產(chǎn)品和工具的使用都超過20年,并已產(chǎn)生了期望的效應(yīng).此外，數(shù)據(jù)挖掘產(chǎn)品和工具在金融、商業(yè)、電信、醫(yī)學(xué)等多個(gè)領(lǐng)域也得到廣泛推廣應(yīng)用。在數(shù)據(jù)庫技術(shù)飛速發(fā)展的同時(shí)，人工智能領(lǐng)域的一個(gè)分支—--—機(jī)器學(xué)習(xí)的研究也取得了很大的進(jìn)展.自20世紀(jì)50年代開始機(jī)器學(xué)習(xí)的研究以來，在不同時(shí)期的研究途徑和研究目的也不盡相同.一般大致可以分為三個(gè)階段，其研究?jī)?nèi)容則分別為：神經(jīng)模型和決策理論、概念符號(hào)獲取及知識(shí)加強(qiáng)和論域?qū)Ｓ脤W(xué)習(xí)。根據(jù)人類學(xué)習(xí)的不同模式人們提出了很多機(jī)器學(xué)習(xí)方法,如：實(shí)例學(xué)習(xí)、觀察和發(fā)現(xiàn)學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和遺傳算法等。其中某些常用且較成熟的算法已經(jīng)被人們用于實(shí)際的應(yīng)用系統(tǒng)及智能計(jì)算機(jī)的設(shè)計(jì)和實(shí)現(xiàn)中.正是由于數(shù)據(jù)庫技術(shù)和機(jī)器學(xué)習(xí)技術(shù)的發(fā)展,也是為了滿足人們實(shí)際工作的需要，數(shù)據(jù)挖掘（DataMining)技術(shù)逐漸發(fā)展了起來。Web日志挖掘是一項(xiàng)綜合技術(shù),是數(shù)據(jù)挖掘在Web日志上的應(yīng)用，涉及有信息學(xué)、數(shù)據(jù)挖掘、機(jī)器語言學(xué)、Web日志技術(shù)等多個(gè)領(lǐng)域。它是利用數(shù)據(jù)挖掘技術(shù)從Web日志相關(guān)的行為和資源中挖掘出新穎的、有效的、潛在有用、用戶易理解的模式和信息的過程。Web日志數(shù)據(jù)挖掘的基本原理過程如圖2。1所示。網(wǎng)站結(jié)構(gòu)、內(nèi)容網(wǎng)站結(jié)構(gòu)、內(nèi)容目標(biāo)數(shù)據(jù)集經(jīng)預(yù)處理的數(shù)據(jù)模式、規(guī)則、統(tǒng)計(jì)結(jié)果有趣的模式預(yù)處理模式發(fā)現(xiàn)模式分析圖2.1Web日志數(shù)據(jù)挖掘原理圖Web日志挖掘分類及架構(gòu)模型根據(jù)挖掘的對(duì)象不同，我們將其分類三類:Web日志內(nèi)容挖掘、Web日志結(jié)構(gòu)挖掘和Web日志使用挖掘。（1）Web日志內(nèi)容挖掘:又可分為Web日志頁面挖掘和查詢結(jié)果歸納；內(nèi)容挖掘主要是指從Web日志文檔的內(nèi)容或其描述中提取知識(shí)以及對(duì)搜索中發(fā)現(xiàn)的有用信息進(jìn)行分析的過程。(2）Web日志結(jié)構(gòu)挖掘：是指通過對(duì)Web日志站點(diǎn)中超鏈接結(jié)構(gòu)進(jìn)行分析、變形和歸納，并對(duì)Web日志頁面進(jìn)行分類,最終得到有用的結(jié)果。常用的算法有PageRank算法和HITS算法等，挖掘的對(duì)象包括Web日志的結(jié)構(gòu)、頁面的結(jié)構(gòu)以及Web日志文檔自身的結(jié)構(gòu);(3)Web日志使用挖掘:通過分析Web日志服務(wù)器的日志文件，以發(fā)現(xiàn)用戶訪問頁面的模式,如用戶訪問模式分析、個(gè)性化分析、分類和聚類。方便為站點(diǎn)管理員提供各種利于Web日志站點(diǎn)改進(jìn)的信息，并將訪問記錄數(shù)據(jù)傳給數(shù)據(jù)關(guān)系表中來實(shí)現(xiàn)對(duì)關(guān)系表數(shù)據(jù)的挖掘。Web日志挖掘過程2。1。2.1Web日志內(nèi)容挖掘的基本過程Web日志內(nèi)容挖掘的基本過程包括文本分析、文本解釋、文檔分類、文檔可視化，它目的在于挖掘出基于用戶需求的Web日志文本和多媒體信息,并對(duì)Web日志數(shù)據(jù)進(jìn)行多樣查詢，提取其中無結(jié)構(gòu)的動(dòng)態(tài)文本進(jìn)行集成、建模，最終實(shí)現(xiàn)知識(shí)發(fā)現(xiàn)。Web日志內(nèi)容挖掘可以分為兩類[10]:資源查找方法和數(shù)據(jù)庫方法。2.1。2。2Web日志使用挖掘的基本過程數(shù)據(jù)挖掘的流程可以分為明確問題、數(shù)據(jù)收集和數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘以及結(jié)果解釋和評(píng)估，如圖2-2所示。圖2-2數(shù)據(jù)挖掘的主要過程明確問題數(shù)據(jù)挖掘的首要工作是研究發(fā)現(xiàn)何種知識(shí)，即明確問題.在此過程中，數(shù)據(jù)挖掘人員必須和領(lǐng)域?qū)＜颐芮袇f(xié)作，一方面明確實(shí)際工作對(duì)數(shù)據(jù)挖掘的要求；另一方面通過對(duì)各種學(xué)習(xí)算法的對(duì)比進(jìn)而確定可用的學(xué)習(xí)算法。比如,數(shù)據(jù)分析員面對(duì)客戶的流失問題，需要利用數(shù)據(jù)分析找出原因,并且找出解決問題的辦法.數(shù)據(jù)收集和預(yù)處理數(shù)據(jù)收集和預(yù)處理階段一般要完成三項(xiàng)工作：數(shù)據(jù)選取、數(shù)據(jù)預(yù)處理和數(shù)據(jù)變換.數(shù)據(jù)選取就是確定操作對(duì)象,即目標(biāo)數(shù)據(jù)，一般是從原始數(shù)據(jù)庫中抽取的組數(shù)據(jù)。數(shù)據(jù)預(yù)處理一般包括消除噪音、推導(dǎo)計(jì)算缺失值數(shù)據(jù)、消除重復(fù)記錄、完成數(shù)據(jù)類型轉(zhuǎn)換（如把連續(xù)值數(shù)據(jù)轉(zhuǎn)換為離散型的數(shù)據(jù),以便用于符號(hào)歸納，或是把離散型的轉(zhuǎn)換為連續(xù)值型的,以便用于神經(jīng)網(wǎng)絡(luò)）等內(nèi)容。當(dāng)數(shù)據(jù)挖掘的對(duì)象是數(shù)據(jù)倉(cāng)庫時(shí),一般來說，數(shù)據(jù)預(yù)處理已經(jīng)在生成數(shù)據(jù)倉(cāng)庫時(shí)完成了。數(shù)據(jù)變換的主要目的是消減數(shù)據(jù)維數(shù),即從初始特征中找出真正有用的特征，以減少數(shù)據(jù)挖掘時(shí)要考慮的特征或變量個(gè)數(shù)。在進(jìn)行數(shù)據(jù)挖掘技術(shù)的分析之前,我們還有許多準(zhǔn)備工作要完成，通常有80%的時(shí)間和精力花費(fèi)在數(shù)據(jù)預(yù)處理階段。數(shù)據(jù)挖掘通常有以下三種訪問數(shù)據(jù)的途徑：從數(shù)據(jù)倉(cāng)庫中訪問數(shù)據(jù)。從關(guān)系數(shù)據(jù)庫中訪問數(shù)據(jù)。從簡(jiǎn)單文件或電子表格中訪問數(shù)據(jù)。數(shù)據(jù)挖掘在將數(shù)據(jù)提交給數(shù)據(jù)挖掘工具前，我們要根據(jù)具體情況考慮下列問題:學(xué)習(xí)應(yīng)該是有監(jiān)督的還是有無監(jiān)督的；在組合的數(shù)據(jù)中，哪些實(shí)例將用于建立模型，哪些實(shí)例將用于檢驗(yàn)?zāi)Ｐ?；從可用的屬性清單中選擇哪些屬性;數(shù)據(jù)挖掘工具需要使用者制定單個(gè)或多個(gè)學(xué)習(xí)參數(shù)，什么樣的參數(shù)設(shè)置可以最好的表示數(shù)據(jù)，從而用于建立模型.根據(jù)所需解決問題的類型，確定數(shù)據(jù)挖據(jù)的任務(wù),例如分類、聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)或序列模式發(fā)現(xiàn)等。確定了挖掘任務(wù)后，就要決定使用什么樣的算法。選擇算法時(shí)要考慮兩個(gè)因素：一是不同的數(shù)據(jù)有不同的特點(diǎn),因此需要用及之相關(guān)的算法來挖掘；二是用戶或?qū)嶋H運(yùn)行系統(tǒng)的要求,例如有的用戶可能希望獲取容易理解的描述型知識(shí)（采用規(guī)則表示的挖掘方法顯然要好于神經(jīng)網(wǎng)絡(luò)之類的方法），有的用戶則只是希望獲取預(yù)測(cè)準(zhǔn)確度盡可能高的預(yù)測(cè)型知識(shí)，而并不在意獲取的知識(shí)是否易于理解.結(jié)果解釋和評(píng)估數(shù)據(jù)挖掘質(zhì)量的好壞有兩個(gè)影響要素:一是所采用數(shù)據(jù)挖掘技術(shù)的有效性；二是用于挖掘的數(shù)據(jù)的質(zhì)量和數(shù)量(數(shù)據(jù)量的大?。?。若選擇了錯(cuò)誤的數(shù)據(jù)或不恰當(dāng)?shù)膶傩?，或?qū)?shù)據(jù)進(jìn)行了不適當(dāng)?shù)霓D(zhuǎn)換,則挖掘不出好的結(jié)果.對(duì)于數(shù)據(jù)挖掘出來的模式，要進(jìn)行評(píng)估，刪除冗余或無關(guān)的模式。如果模式不滿足要求，需要重復(fù)先前的過程，例如重新選取數(shù)據(jù)、采用新的數(shù)據(jù)變換方法、設(shè)定新的參數(shù)值改變算法等,甚至重新開始.數(shù)據(jù)挖掘過程是一個(gè)不斷反饋的過程。另外，要對(duì)發(fā)現(xiàn)的模式進(jìn)行可視化，把結(jié)果轉(zhuǎn)換為容易理解的表示形式，以使得發(fā)現(xiàn)的知識(shí)更易于理解，例如，把分類決策樹轉(zhuǎn)換為“if…else…”規(guī)則.Web日志使用挖掘是對(duì)網(wǎng)絡(luò)日志進(jìn)行挖掘，從用戶訪問Web日志時(shí)留下的訪問記錄中挖掘出潛在的、有用信息的過程。其目的在于要發(fā)現(xiàn)用戶留下的瀏覽模式和有用信息，這有利于開發(fā)Web日志的最大經(jīng)濟(jì)潛力，按照其分類規(guī)則，將Web日志使用挖掘分為數(shù)據(jù)預(yù)處理、模式識(shí)別和模式分析三個(gè)階段，如圖2.3所示：WebWeb站點(diǎn)文件日志文件用戶會(huì)話文件挖掘和模式感興趣的規(guī)則和模式預(yù)處理挖掘模式分析圖2。3Web日志使用挖掘過程（1）數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理階段是把從Web日志日志文件數(shù)據(jù)中獲得的使用信息、內(nèi)容信息和結(jié)構(gòu)信息轉(zhuǎn)換成數(shù)據(jù)抽象，并將符合用戶模式實(shí)現(xiàn)的數(shù)據(jù)從Web日志日志文件數(shù)據(jù)源中發(fā)掘出來，對(duì)該類型的用戶會(huì)話（事務(wù)數(shù)據(jù)庫）應(yīng)用挖掘算法，最終得到潛在的知識(shí)和有價(jià)值的模式的過程。數(shù)據(jù)預(yù)處理主要對(duì)日志文件進(jìn)行數(shù)據(jù)收集、抽取、清洗、用戶會(huì)話識(shí)別、事務(wù)模式分析等處理［11]。（2)模式識(shí)別識(shí)別的困難是由本地緩存和代理服務(wù)器造成的，當(dāng)完成對(duì)用戶事務(wù)的數(shù)據(jù)清理之后，開始執(zhí)行模式訪問階段,目的在于使用Web日志挖掘技術(shù)發(fā)掘隱藏在數(shù)據(jù)背后的模式和規(guī)律，常用技術(shù)有：統(tǒng)計(jì)分析、關(guān)聯(lián)規(guī)則發(fā)掘、生成序列模式、聚類和分類、依賴關(guān)系的建模。(3)模式分析由于挖掘出來的模式復(fù)雜且數(shù)量較大，需過濾掉在挖掘階段得到的那些沒有用的規(guī)則或模式,把有用的規(guī)則和模式轉(zhuǎn)換為知識(shí)，這就要通過一些工具來輔助用戶的理解。因此，近年來一些分析技術(shù)和工具的開發(fā)成為了Web日志使用挖掘研究的一個(gè)新熱點(diǎn).Web日志挖掘技術(shù)2。1.3。1聚類(1)基于模糊聚類算法的Web日志頁面聚類模糊集理論是Zadeh于1965年提出的，其定義如下:設(shè)為論域,若集合R是其上的一個(gè)模糊集,則有.是模糊集R的隸屬函數(shù)，為的隸屬度。在兩個(gè)模糊集A及B上的運(yùn)算有：應(yīng)用模糊算法進(jìn)行Web日志頁面聚類時(shí),主要就是構(gòu)造頁面間的模糊相似矩陣。定義Web日志訪問用戶集合,某一站點(diǎn)所有URL集合中可用用戶訪問情況表示為：,其中，，n表示用戶數(shù)量。此時(shí)可建立頁面間的模糊相似矩陣,矩陣中的元素值為：，因該矩陣為對(duì)稱矩陣,所以在計(jì)算相似度時(shí)只取一半數(shù)據(jù)，以給定的閾值構(gòu)造相似類。由于模糊矩陣不滿足傳遞性，故只能得到含有公共元素的相似類而非等價(jià)類.具體而言：對(duì)于每一個(gè),根據(jù)給定的閾值構(gòu)造相似類會(huì)具有相同的元素。如，；即。此時(shí)將具有公共元素的相似類歸并得到對(duì)應(yīng)的等價(jià)類即為Web日志頁面聚類的結(jié)果.將用戶Ci用瀏覽子圖的URL序列表示為:。建立客戶相似矩陣：按頁面聚類相同方法即可進(jìn)行用戶聚類。。2。1.3.2分類1.基于頁面文本及超文本結(jié)構(gòu)信息的Web日志頁面綜合分類因?yàn)榛赪eb日志頁面文本和超文本結(jié)構(gòu)信息的Web日志頁面分類方法各有其特色，所以可將兩者相結(jié)合提高分類結(jié)果.如文獻(xiàn)提出的二者取其最大值的方法,但該方法效果不是太明顯。而范炎等提出的利用貝葉斯方法將基于頁面文本和超文本結(jié)構(gòu)信息的分類視為兩個(gè)相互獨(dú)立的因素結(jié)合起來進(jìn)行綜合分類,即：考慮到超文本結(jié)構(gòu)分類中利用的單詞遠(yuǎn)遠(yuǎn)少于頁面文本分類，需要對(duì)不同方法分類結(jié)果加以預(yù)處理。其中n是D中出現(xiàn)的不同單詞數(shù),即根據(jù)n值不同分別為不同的分類結(jié)果賦予不同的權(quán)重。實(shí)驗(yàn)表明在基于貝葉斯方法的分類中，綜合分類的結(jié)果好于文本分類和超文本結(jié)構(gòu)分類單獨(dú)分類時(shí)5％以上，就正確率而言綜合分類好于前者6.75％,較后者提高5。79%。2.基于頁面文本的分類方法（1）基于貝葉斯方法的頁面分類。在頁面分類的諸多算法中貝葉斯分類方法的前提是：文本特征之間是相互獨(dú)立的.貝葉斯方法及閾值大小來對(duì)文本數(shù)據(jù)進(jìn)行劃分：其中指C類文檔第i個(gè)特征,是從C類文本中得到特征詞的概率，n值d中詞的個(gè)數(shù),m是系統(tǒng)詞典的大小,若所得的閾值大于預(yù)先設(shè)定得值，則認(rèn)為文本d屬于C類，否則不是.從概率大小來研究，貝葉斯分類方法可描述為：設(shè)文檔d的文檔向量的分量為相應(yīng)的特征詞在該文檔中出現(xiàn)的頻度，則d屬于C類文檔的概率公式為:(2。7）是在C類文檔中出現(xiàn)的條件概率的拉普拉斯概率估計(jì)，是C類文檔中特征詞出現(xiàn)的頻率，是d類文檔中特征詞出現(xiàn)的頻度，是文檔中所包含的不同特征的總數(shù)目。（2）基于文檔相似性的文檔分類?；谖臋n相似性的文檔分類方法并無貝葉斯方法所需的前提假設(shè)。使用文檔表示矩陣間的夾角余弦值來表示它們之間的相似程度(2。6)：Web日志挖掘算法的關(guān)鍵問題(1）Rank算法Rank算法是Web日志超鏈接結(jié)構(gòu)分析中最成功的代表之一，是評(píng)價(jià)網(wǎng)頁權(quán)威性的一種重要工具。搜索引擎Google就是利用該算法和anthortext標(biāo)記、詞頻統(tǒng)計(jì)等因素相結(jié)合的方法來檢索出的大量結(jié)果進(jìn)行相關(guān)度排序，將最權(quán)威的網(wǎng)頁盡量排在前面。Rank的基本思想：設(shè)頁面i的鏈入集合為｛T1，T2，…，Tn｝，即{T1，…,Tn｝中的每一個(gè)頁面都鏈接到頁面i，C（i）為頁面i的鏈出頁面數(shù)，則頁面i的等級(jí)值PR(i)可以通過以下兩步計(jì)算得出：（1)以概率e隨機(jī)取Web日志上任一頁面。（2)以概率1—e隨機(jī)取當(dāng)前頁面任一鏈出頁面.PR（i）=1—e+e＊(PR（T1)/C（T1)+…+PR(Tn)/C（Tn）)(2.7）存在問題：PageRank是對(duì)Web日志整體分析，通過模擬在Web日志上的隨機(jī)游動(dòng)對(duì)每一個(gè)網(wǎng)頁計(jì)算其PageRank值。因此該算法是獨(dú)立于用戶查詢的,可以對(duì)用戶要求產(chǎn)生快速的響應(yīng)。HITS算法是對(duì)Web日志的局部分析,是根據(jù)特定的查詢產(chǎn)生不同的根集,然后計(jì)算網(wǎng)頁的anthority值和Hub值，該算法是依賴于用戶查詢的,實(shí)時(shí)性差。（2)HITS算法1999年Kleinberg提出了HITS（HypertextInducedTopicSearch)算法。HITS算法的內(nèi)容如下:將查詢q提交給普通的基于相似度的搜索引擎，搜索引擎返回很多頁面，從中取前n個(gè)頁面作為根集(Rootset）,用s表示。通過向s中加入被s引用的頁面和引用s的頁面將s擴(kuò)展成一個(gè)更大的集合T,作為基本集(Baseset)。首先，為基本集中的每一個(gè)頁面賦予一個(gè)非負(fù)的權(quán)威權(quán)重ap和非負(fù)的Hub權(quán)重hp，并將所有的a和h值初始為同一個(gè)常數(shù)。Hub及權(quán)威的權(quán)重可按如下公式進(jìn)行迭代計(jì)算：存在問題：HITS算法存在“主題漂移”的現(xiàn)象，如用戶在查詢“量子物理學(xué)"時(shí)，由于算法中需要對(duì)初次檢索結(jié)果的根集擴(kuò)充成基集,最終的檢索結(jié)果中會(huì)包含大量的有關(guān)“物理學(xué)”的站點(diǎn)。因此HITS適合及寬主題的查詢，而PageRank則較好地克服了“主題漂移”的現(xiàn)象。蟻群算法蟻群算法是一種模擬螞蟻群體智能行為在圖中尋找優(yōu)化路徑的仿生類優(yōu)化算法,它由MarcoDorigo在92年提出，其思想來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，當(dāng)一只螞蟻找到食物后，會(huì)在其走過的路上釋放一種揮發(fā)性分泌物Pheromone（信息素，信息素濃度的大小表征路徑的遠(yuǎn)近），螞蟻在搜尋過程中能夠感知信息素的存在和強(qiáng)度，并吸引其他螞蟻過來,通過這種方式形成了信息素軌跡。蟻群算法分析為了便于理解,通常引入蟻群算法求解平面上某個(gè)城市的TSP問題來說明蟻群算法的模型。由于TSP是典型的組合優(yōu)化難題，常常用來驗(yàn)證某一算法的有效性.1.TSP問題的描述給定n個(gè)城市的集合｛1，2,…,n}及城市之間環(huán)游的花費(fèi)Cij（1in，1jn,ij)。TSP問題是要找到一條經(jīng)過每個(gè)城市一次且回到起點(diǎn)的最小花費(fèi)的環(huán)路。若將每個(gè)頂點(diǎn)看成是圖上的節(jié)點(diǎn)，花費(fèi)Cij為連接頂點(diǎn)Vi、Vj邊上的權(quán)，則TSP問題就是在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全圖上找到一條花費(fèi)最小的Hamilton回路.2。蟻群算法的描述假設(shè)將m只螞蟻放入到給定的n個(gè)城市中，那么每一只螞蟻每一步的行動(dòng)將符合下列規(guī)律：根據(jù)路徑上的信息素濃度，以相應(yīng)的概率來選取下一個(gè)城市；不再選取自己本次循環(huán)已經(jīng)經(jīng)過的城市為下一個(gè)城市；當(dāng)完成一步（從一個(gè)城市到達(dá)另一個(gè)城市）或者一個(gè)循環(huán)（完成對(duì)所有n個(gè)城市的訪問）后,更新所有路徑上的殘留信息濃度。螞蟻在選擇下一個(gè)城市的依據(jù)主要是兩點(diǎn):（1)(t)-—-t時(shí)刻連接城市i和j的路徑上殘留信息的濃度,即由算法本身提供的信息；(2)——-由城市i轉(zhuǎn)移到城市j的啟發(fā)信息，該啟發(fā)信息是由要解決的問題給出的，由一定的算法實(shí)現(xiàn).在TSP問題中一般取=1/Cij。那么,t時(shí)刻位于城市i的螞蟻k選擇城市j為目標(biāo)城市的概率為：也即，螞蟻選中某一個(gè)城市的可能性是問題本身所提供的啟發(fā)信息及從螞蟻目前所在城市到目標(biāo)城市路徑上殘留信息量的函數(shù)。為了避免殘留信息過多引起的殘留信息淹沒啟發(fā)信息的問題，在每一只螞蟻完成對(duì)所有n個(gè)城市的訪問后（也即一個(gè)循環(huán)結(jié)束后），必須對(duì)殘留信息進(jìn)行更新處理，模仿人類記憶的特點(diǎn)，對(duì)舊的信息進(jìn)行削弱.同時(shí)，必須將最新的螞蟻訪問路徑的信息加入。這樣得到 式中：殘留信息的保留部分，1—表示在時(shí)段t到(t+1）內(nèi)殘留信息被削弱的部分，為了防止信息的無限累積,的取值范圍必須在0到1之間； —--第k個(gè)螞蟻在時(shí)段t到(t+1)內(nèi)，在i到j(luò)的路徑上留下的殘留信息濃度. M.Dorigo介紹了的3種不同的實(shí)現(xiàn)方法，分別稱為ant_cycle，ant_density,ant_quantity算法。對(duì)于前一種算法:式中：Q是一個(gè)常量，用來表示螞蟻完成一次完整的路徑搜索后，所釋放的信息素總量：Lk表示螞蟻k在本次循環(huán)中所選擇路徑的總花費(fèi)，它等于第k個(gè)螞蟻經(jīng)過的各段路徑上所需的花費(fèi)Cij的總和.蟻群算法的關(guān)鍵問題（1)搜索時(shí)間較長(zhǎng)計(jì)算的復(fù)雜度主要體現(xiàn)在構(gòu)造模型的過程中，隨著問題規(guī)模的增大，算法消耗的時(shí)間也隨之增加,通過這些參數(shù)信息交換能夠向著最優(yōu)路徑進(jìn)化，但是當(dāng)群體規(guī)模較大時(shí)，很難在短時(shí)間內(nèi)找出一條較好的路徑。通過正反饋機(jī)制，使得較優(yōu)路徑上的信息量逐漸增加，需要在很長(zhǎng)的一段時(shí)間后，才能使較優(yōu)路徑上的信息量明顯高于其他路徑.目前這方面的研究開始逐步走向深入.（2）運(yùn)行效率及全局收斂針對(duì)蟻群算法運(yùn)行效率低下這一問題，曾先后提出了帶精英策略的螞蟻系統(tǒng)（ASelist）和基于優(yōu)化排序的螞蟻系統(tǒng)(ASrank）。雖然它們?cè)谶\(yùn)行效率方面取得一定的進(jìn)展,但是同樣也付出了容易收斂于局部最優(yōu)解的代價(jià)。在它們之后，MMAS以及ACS針對(duì)上述問題進(jìn)行了改進(jìn)，擴(kuò)展了蟻群的搜索空間,但是它們?cè)谛史矫嫱瑯右哺冻隽舜鷥r(jià)。目前的研究是將注意力集中到將蟻群算法及其他智能仿生算法相結(jié)合。本章小結(jié)首先介紹了Web日志挖掘的理論知識(shí)，包括分類、架構(gòu)模型等.詳細(xì)地論述了Web日志挖掘技術(shù)中的聚類和分類技術(shù)以及指出現(xiàn)階段存在的關(guān)鍵問題。然后，對(duì)蟻群算法進(jìn)行分析，系統(tǒng)地提出了當(dāng)前蟻群算法研究熱點(diǎn)問題.Web日志挖掘的預(yù)處理技術(shù)聚類是將復(fù)雜的事物分門別類,并對(duì)陌生繁亂的事物進(jìn)行歸類總結(jié)，相同類別的事物采取類似的處理方法，這樣就能大大提高事物的處理效率，通過自動(dòng)聚類能夠識(shí)別對(duì)象空間中不同密度空間的區(qū)域,從而發(fā)現(xiàn)全局分布模式，并結(jié)合蟻群算法的正反饋、魯棒性、分布式計(jì)算等優(yōu)點(diǎn),對(duì)聚類模型進(jìn)行設(shè)計(jì)。聚類模型分析聚類分析在Web日志挖掘中是一個(gè)很重要的技術(shù)。聚類分析可以增強(qiáng)對(duì)象集的可理解性,并發(fā)現(xiàn)對(duì)象集中數(shù)據(jù)間共同的結(jié)構(gòu)和聯(lián)系，保持其有效性.即按照一定的規(guī)律和需求,將一些特殊分散的對(duì)象按照其相似性進(jìn)行分類,并使得對(duì)象點(diǎn)的集合分成若干類，且每個(gè)類中的對(duì)象點(diǎn)最大程度地相似,各個(gè)類之間的對(duì)象點(diǎn)最大程度地不同。在聚類分析過程中沒有涉及關(guān)于分類方面的知識(shí),只是依靠對(duì)象點(diǎn)間的相似度作為劃分類的依據(jù)，因此聚類分析是一種觀察式學(xué)習(xí)，是利用數(shù)學(xué)方法研究和處理所給定對(duì)象的分類,其多元的統(tǒng)計(jì)分析方法是統(tǒng)計(jì)模式識(shí)別中非監(jiān)督模式識(shí)別的重要分支.為了描述對(duì)象樣本間的距離，特引入特征變量類型和相似性度量這2個(gè)概念。(1)特征變量類型為了描述一個(gè)對(duì)象樣本，我們通常會(huì)對(duì)對(duì)象進(jìn)行特征抽象化，使用多個(gè)特征指標(biāo)變量來給予每個(gè)對(duì)象一個(gè)特征向量.特征指標(biāo)變量可以分為：間隔標(biāo)度變量、二次變量、序數(shù)變量，處理不同類型的特征指標(biāo)變量則采取不同的策略.對(duì)于間隔標(biāo)度變量是使用連續(xù)的實(shí)數(shù)來表示的數(shù)量信息，一個(gè)樣本點(diǎn)可以看作是多維空間中的一點(diǎn)，通過一些特殊的運(yùn)算來求解各個(gè)樣本在空間上的距離。對(duì)于二元變量，用兩種狀態(tài)（0或1)來表示樣本屬性,1表示變量出現(xiàn)，0表示變量不出現(xiàn)，該變量特征也可以用來分類變量尺度，標(biāo)記多狀態(tài).對(duì)于序數(shù)變量，它類似于分類變量,不用于分類變量的是，其狀態(tài)時(shí)無序關(guān)系的，而分類的狀態(tài)是有序的。對(duì)于這兩種特征變量我們不能定義合適的數(shù)學(xué)運(yùn)算，需要通過特殊變換后才能進(jìn)行對(duì)象相似度計(jì)算.(2)相似性度量為了更好地描述對(duì)象集中的單個(gè)樣本，需要樣本類型中的特征指標(biāo)變量提供度量值，同樣為了描述樣本間的相似特性，也需要定義能合理地衡量樣本間相似程度,從而合理地進(jìn)行聚類的度量，以便把相似的樣本歸為一類，非相似的樣本歸為不同的類。常用刻畫樣本間的相似性函數(shù)有2種，分別是：相似系數(shù)函數(shù)、距離函數(shù).相似系數(shù)函數(shù)是用來描述樣本點(diǎn)特征性質(zhì)之間的相似程度,當(dāng)相似系數(shù)值越接近0時(shí)，說明兩個(gè)對(duì)象樣本越不相似,當(dāng)相反相似系數(shù)值越接近1，則說明兩個(gè)對(duì)象越相似,這才可以將它們歸為一類。距離函數(shù)指的是對(duì)象樣本間的距離，對(duì)于含有N個(gè)屬性的樣本對(duì)象來說，我們可以將每個(gè)樣本點(diǎn)看作是N維空間中的一個(gè)點(diǎn)，然后使用某種距離來表示樣本對(duì)象點(diǎn)之間的相似性，對(duì)象樣本點(diǎn)越相似，則樣本點(diǎn)之間的距離越小，可以將它們歸為一類；對(duì)象樣本點(diǎn)差異越大，則兩者間的距離越大，就不能歸為一類。聚類模型設(shè)計(jì)聚類首先要做的是對(duì)樣本對(duì)象的特征抽取，它所處理的對(duì)象是樣本數(shù)據(jù)集，由于實(shí)際應(yīng)用中的樣本數(shù)據(jù)對(duì)象一般都有多種特征,要具體選取哪種特征才可以正確地描述樣本對(duì)象的本質(zhì)和結(jié)構(gòu)對(duì)于聚類分析來說至關(guān)重要。特征抽取的結(jié)果是輸出一個(gè)矩陣，每一行對(duì)應(yīng)的是一個(gè)樣本對(duì)象，而每一列對(duì)應(yīng)的是一個(gè)特征變量。特征的抽取是另一個(gè)重要步驟,對(duì)后續(xù)的分析和決策有直接的影響。如果抽取的特征變量只是樣本對(duì)象中不重要的屬性，對(duì)這些無關(guān)緊要的屬性進(jìn)行聚類分析出的結(jié)果肯定也達(dá)不到預(yù)期的效果，因?yàn)楫?dāng)使用錯(cuò)誤的特征屬性來解釋對(duì)象時(shí)，容易扭曲樣本對(duì)象，再對(duì)這樣的樣本對(duì)象進(jìn)行的聚類分析,即便是用最好的聚類算法來對(duì)其處理，結(jié)果也是不正確的.總結(jié)蟻群算法和聚類分析的特點(diǎn)，引入了一種改進(jìn)的蟻群算法(ImprovedAntColonyAlgorithm，IACA)。并將其運(yùn)用到Web日志的用戶聚類上，聚類模型如下:1.初始化設(shè)定設(shè)有M個(gè)模式樣本、K個(gè)模式分類，N是表示為幾個(gè)樣本對(duì)象；初始狀態(tài)將M個(gè)樣本隨機(jī)分配到N個(gè)聚類中心，K表示分類出K個(gè)等級(jí)，每個(gè)模式樣本是一個(gè)D維向量，定義模式樣本。設(shè)聚類中心為，則目標(biāo)函數(shù)表示為：2。信息素更新計(jì)算螞蟻的各自初始聚類中心（第k個(gè)螞蟻將模式樣本i分配到第j個(gè)聚類中心)和初始目標(biāo)函數(shù)，初始化各螞蟻的樣本到各聚類中心的信息素濃度，信息素濃度更新公式為：其中是信息素增量，是信息素強(qiáng)度的持久性系數(shù)（算法中1-表示信息素?fù)]發(fā)度）.初始化，螞蟻將初始化，螞蟻將M個(gè)樣本隨機(jī)分配到K個(gè)聚類中心計(jì)算螞蟻的各自初始聚類中心和初始目標(biāo)函數(shù)初始化各螞蟻的樣本到各聚類中心的信息素濃度M只螞蟻到N個(gè)樣本進(jìn)行K個(gè)模式分類更新并調(diào)整信息素，計(jì)算出新的聚類中心，計(jì)算目標(biāo)函數(shù)搜索次數(shù)h=h+1h>=L?選取，輸出分類結(jié)果算法結(jié)束否否是是圖3。1流程圖3。聚類中心的計(jì)算方法對(duì)于聚類中心的計(jì)算方法，我們選擇了K均值算法[54]來計(jì)算每個(gè)聚類中心。4.有關(guān)參數(shù)的選擇由于算法參數(shù)的選擇會(huì)對(duì)蟻群算法的性能產(chǎn)生較大的影響。從螞蟻搜索最短路徑的原理出發(fā)，我們定義了一些參數(shù)：種群數(shù)N、常數(shù)Q、絕對(duì)感覺閾值CST和差別感覺閾值A(chǔ)ST以及信息素?fù)]發(fā)度1-等等.螞蟻數(shù)量N決定蟻群算法的循環(huán)次數(shù)呈線性變化。當(dāng)螞蟻數(shù)量過大時(shí),搜索的全局性和穩(wěn)定性有所提高,但是算法的收斂速度變慢。蟻群搜索過程中信息素?fù)]發(fā)度1-的大小關(guān)系到蟻群算法運(yùn)行過程中的收斂速度和全局搜索能力:當(dāng)1—過小時(shí)，搜索過的路徑被選擇的概率降低，雖然算法全局搜索能力和隨機(jī)性能有所提高,但是收斂速度卻下降;當(dāng)1—過大時(shí)，表示搜索過的路徑被再次選擇的概率增加，影響算法的全局搜索能力；所以對(duì)信息素?fù)]發(fā)度的選擇,需要平衡算法的收斂速度和全局搜索能力。另外,AST和CST的取值也很重要，取值不恰當(dāng)容易使解陷入局部收斂，算法需要在穩(wěn)定性和求解速度上取得平衡。Web日志預(yù)處理相關(guān)技術(shù)在對(duì)Web日志進(jìn)行挖掘之前，有一個(gè)很重要的數(shù)據(jù)處理過程，稱之為Web日志預(yù)處理，也就是對(duì)Web日志數(shù)據(jù)進(jìn)行過濾、清洗以及重新組合的過程。我們都知道服務(wù)器端的Web日志中記錄了用戶訪問網(wǎng)站的各種信息，但是這些信息中有些數(shù)據(jù)是自動(dòng)產(chǎn)生,而有些信息可能并不是我們需要研究的，這些都屬于無用的，所以我們應(yīng)該對(duì)其進(jìn)行數(shù)據(jù)預(yù)處理。而Web日志預(yù)處理技術(shù)主要包括有以下五個(gè)階段：（1）數(shù)據(jù)清理；（2）用戶識(shí)別;（3)會(huì)話識(shí)別； (4）路徑補(bǔ)充；(5)事物識(shí)別。服務(wù)器產(chǎn)生的Web日志文件是Web日志挖掘中數(shù)據(jù)預(yù)處理所要研究的對(duì)象。在這些日志文件中存在許多對(duì)研究沒有任何意義的數(shù)據(jù)，所以直接用這些文件將會(huì)導(dǎo)致研究出的結(jié)果有偏差或出錯(cuò)等問題。所以，Web日志數(shù)據(jù)預(yù)處理過程是Web日志挖掘的第一個(gè)階段，也是非常重要的階段.這個(gè)階段會(huì)對(duì)Web服務(wù)器日志或者代理日志進(jìn)行數(shù)據(jù)清洗、數(shù)據(jù)規(guī)范化和數(shù)據(jù)集成等操作,最終把原始的日志數(shù)據(jù)通過一系列操作,處理成便于進(jìn)行挖掘算法的數(shù)據(jù)。不同的Web日志文件中記錄的數(shù)據(jù)也會(huì)相應(yīng)的有各自的數(shù)據(jù)特點(diǎn)，是不一樣的，因?yàn)槊總€(gè)服務(wù)器設(shè)置的參數(shù)不一樣，但是有一些基本的信息是無論任何服務(wù)器都應(yīng)該有記錄的。如表3—1所示。表3-1Web訪問日志記錄的主要信息屬性日志的說明日期以及時(shí)間用戶請(qǐng)求頁面的日期以及具體的時(shí)間用戶IP地址客戶端主機(jī)的IP地址或者DNS入口用戶名服務(wù)器IP地址客戶端的用戶名服務(wù)器的IP地址服務(wù)器端口服務(wù)器端口號(hào)方法用戶請(qǐng)求數(shù)據(jù)的方法URL查詢用戶將要進(jìn)行的查詢協(xié)議狀態(tài)返回http的狀態(tài)的標(biāo)識(shí)發(fā)送的字節(jié)數(shù)服務(wù)器發(fā)送數(shù)據(jù)的字節(jié)數(shù)接受的字節(jié)數(shù)客戶端收到數(shù)據(jù)的字節(jié)數(shù)用戶代理服務(wù)的提供者Web日志數(shù)據(jù)預(yù)處理的過程Web日志數(shù)據(jù)預(yù)處理主要任務(wù)是，把輸入數(shù)據(jù)為Web服務(wù)器日志或其他的日志記錄文件轉(zhuǎn)化為可以進(jìn)行挖掘的用戶會(huì)話文件以及事務(wù)數(shù)據(jù)庫，而處理數(shù)據(jù)的結(jié)果將直接影響Web日志挖掘質(zhì)量的好壞。一般來說，Web日志數(shù)據(jù)的預(yù)處理過程由以下五個(gè)階段構(gòu)成，分別是數(shù)據(jù)清理、用戶識(shí)別、會(huì)話識(shí)別、路徑補(bǔ)充以及事物識(shí)別.如圖3-2所示.接下來針對(duì)這五個(gè)階段來詳細(xì)的進(jìn)行下介紹。圖3-2Web日志數(shù)據(jù)預(yù)處理的過程數(shù)據(jù)清理Web服務(wù)器日志文件中有很多及研究沒有任何意義的“臟數(shù)據(jù)”，數(shù)據(jù)清理這個(gè)操作就是把“臟數(shù)據(jù)"進(jìn)行“清洗”的過程.首先把從服務(wù)器取出來的Web日志記錄進(jìn)行合并,然后將其存進(jìn)對(duì)應(yīng)的數(shù)據(jù)字段中，因?yàn)閃eb日志文件一般只有html文件才會(huì)跟用戶會(huì)話相關(guān)，所以在這一過程中一般都要根據(jù)實(shí)際情況去掉日志中的圖像文件以及其他不相關(guān)的文件。比如圖像文件的后綴有g(shù)if,jpg，jpeg等等，除圖像文件之外還有一些js、css、swf等文件根據(jù)具體情況也進(jìn)行相應(yīng)的刪除。除此之外,以cgi為后綴的一些腳本文件也應(yīng)該被剔除掉。清理流程如圖3-3所示。開始開始N日志清理完成日志數(shù)據(jù)中是否有記錄N日志清理完成日志數(shù)據(jù)中是否有記錄從日志數(shù)據(jù)庫中讀取一條記錄YY從日志數(shù)據(jù)庫中讀取一條記錄YYN請(qǐng)求url的后綴是否為.gif、N請(qǐng)求url的后綴是否為.gif、.jpg等格式N從日志數(shù)據(jù)庫中刪除記錄狀態(tài)碼是否以2開頭狀態(tài)碼是否以2開頭Y將該記錄添加到表中將該記錄添加到表中圖3-3數(shù)據(jù)清理流程圖縱向縮減（也稱行縮減）為了讓W(xué)eb日志文件的數(shù)據(jù)能夠更加可靠，更加適應(yīng)挖掘的需要，對(duì)Web日志文件中無用信息進(jìn)行刪除是必需的一個(gè)過程。根據(jù)具體的挖掘研究,可以對(duì)Web日志文件的清洗任務(wù)進(jìn)行以下三個(gè)方面縱向縮減：1)URL擴(kuò)展名：在Web日志數(shù)據(jù)中，像一些以gif、jpg、css、cgi為后綴的文件通常被認(rèn)為是及日志挖掘沒有關(guān)聯(lián)的,應(yīng)該將這些文件剔除掉,因?yàn)橹挥衕tml格式的文件說明及用戶會(huì)話相關(guān)。當(dāng)然，凡是也有例外，如果要研究的網(wǎng)站是圖片網(wǎng)站,那想要對(duì)網(wǎng)站的流量進(jìn)行分析的話，這些格式的文件就要根據(jù)具體情況進(jìn)行相應(yīng)保存了。2）動(dòng)作：用戶訪問網(wǎng)站的方式通常有g(shù)et和post兩種,post動(dòng)作一般是需要過濾掉的，因?yàn)閜ost方式一般是用戶提交表單數(shù)據(jù)時(shí)使用，而get動(dòng)作是用戶進(jìn)行請(qǐng)求頁面的，一般要保留。3）狀態(tài)碼:狀態(tài)碼表示用戶請(qǐng)求頁面的結(jié)果，主要分以下幾種情況：第一種，以2開頭狀態(tài)碼表示頁面請(qǐng)求成功，比如200代表服務(wù)器成功返回頁面，202代表服務(wù)器已經(jīng)接受請(qǐng)求，但還沒有處理，206代表服務(wù)器成功處理了get請(qǐng)求；第二種，以3開頭的狀態(tài)碼表示重定向,比如301代表請(qǐng)求的頁面已經(jīng)永久移動(dòng)到新位置，304代表自從上次請(qǐng)求后，請(qǐng)求的網(wǎng)頁沒有修改過;第三種：以4開頭的狀態(tài)碼表示請(qǐng)求可能出錯(cuò)，比如400代表（錯(cuò)誤提示）服務(wù)器不理解請(qǐng)求的語法，401代表(未授權(quán)）請(qǐng)求要求身份驗(yàn)證，403代表（禁止）服務(wù)器拒絕請(qǐng)求，404代表(未找到）服務(wù)器找不到請(qǐng)求的網(wǎng)頁；第五種：以5開頭的狀態(tài)碼表示服務(wù)器錯(cuò)誤，比如500代表因服務(wù)器內(nèi)部錯(cuò)誤而無法完成請(qǐng)求，502表示網(wǎng)關(guān)錯(cuò)誤。由此，在進(jìn)行數(shù)據(jù)清洗過程中應(yīng)該把以4和5開頭的信息刪除。橫向縮減(也稱列縮減）當(dāng)使用數(shù)據(jù)挖掘的算法對(duì)數(shù)據(jù)進(jìn)行挖掘的時(shí)候,很多web日志中的屬性是非必需的,所以僅僅只考慮縱向縮減來減少日志文件是遠(yuǎn)遠(yuǎn)不夠的。比如，對(duì)用戶信息進(jìn)行聚類分析時(shí)只需要使用用戶的ip地址、用戶請(qǐng)求訪問的url、用戶訪問的時(shí)間、用戶使用的代理等屬性就可以；而分析web站點(diǎn)的流量時(shí)，只需要使用用戶請(qǐng)求url用戶訪問時(shí)間等屬性。這種縮減日志記錄中屬性的方法就是橫向縮減，也叫列縮減。及縱向縮減不同，橫向縮減不會(huì)縮減日志文件的行數(shù),而只會(huì)減少屬性列。用戶識(shí)別用戶就是指通過一個(gè)瀏覽器訪問一個(gè)或幾個(gè)服務(wù)器的個(gè)體。我們?cè)趯?shí)際中唯一確定一個(gè)用戶是非常困難的，因?yàn)橛蟹阑饓?、高速緩存、代理服?wù)器等進(jìn)行阻礙。辨別一個(gè)用戶可以有用戶IP和Cookie標(biāo)識(shí)兩種方法。Cookie是站點(diǎn)根據(jù)瀏覽器寫入本地的唯一的一個(gè)標(biāo)識(shí),當(dāng)用戶再通過url請(qǐng)求服務(wù)器時(shí)，請(qǐng)求中就會(huì)加上這個(gè)標(biāo)識(shí)，然后返回給服務(wù)器，這樣就可以識(shí)別用戶了。不過這種情況也有缺點(diǎn)，那就是當(dāng)若干個(gè)用戶使用同一個(gè)電腦的時(shí)候，一旦有用戶刪除Cookie,那么下一次登陸服務(wù)器就會(huì)被當(dāng)做第一次登陸。當(dāng)然也有可能因?yàn)殡[私不會(huì)被寫到Cookie中，所以，有的時(shí)候要把代理、服務(wù)器日志、參引頁面等綜合考慮才能確定一個(gè)用戶。圖3-4簡(jiǎn)單的Web站點(diǎn)因?yàn)楸镜卮矸?wù)器和高速緩存機(jī)制的存在,極有可能會(huì)使用戶在網(wǎng)站上的瀏覽情況歪曲，這就可能會(huì)導(dǎo)致我們漏掉了重要的訪問內(nèi)容，從而不能比較精確地描述用戶瀏覽網(wǎng)頁的情況。因?yàn)楦鱾€(gè)網(wǎng)站都有后退鍵，這就導(dǎo)致一個(gè)訪問記錄只列出了一次，而實(shí)際是很有可能被多個(gè)用戶參考了很多次。針對(duì)該問題目前主要有以下三種解決方法：關(guān)閉高速緩存、利用Cookie以及利用用戶注冊(cè)。但這三個(gè)方法都存在問題，首先，用戶是可以隨意刪除Cookie的。其次，高速緩存是為了提高網(wǎng)站加載的速度，關(guān)閉高速緩存之后也是可以再次打開的。最后,用戶的注冊(cè)涉及到了個(gè)人隱私，而且是自發(fā)的,所以很多用戶注冊(cè)的信息是不真實(shí)的。高速緩存問題的解決方法可以采用站點(diǎn)拓?fù)鋵W(xué)的知識(shí)或利用參考日志和時(shí)間信息來判斷遺失的參考.表3-2列出了目前用于用戶識(shí)別的幾種方法。表3—2中的方法多多少少也有一些不足之處，目前在Web日志挖掘中，對(duì)如何準(zhǔn)確識(shí)別用戶而又不涉及用戶的隱私的問題的研究已經(jīng)成為熱門的研究。本文只對(duì)用戶識(shí)別作簡(jiǎn)單介紹，不進(jìn)行深入的研究。表3-2用于用戶識(shí)別的方法方法IP地址和代理嵌入會(huì)話ID用戶注冊(cè)軟件代理Cookie描述假定每個(gè)IP地址和一個(gè)用戶代理組合表示一個(gè)用戶利用動(dòng)態(tài)網(wǎng)頁將ID插入每個(gè)鏈接用戶顯示的登錄網(wǎng)站當(dāng)程序調(diào)入瀏覽器后可以發(fā)回使用數(shù)據(jù)在用戶端保存一個(gè)唯一的用戶標(biāo)識(shí)隱私程度低低中中中/高中優(yōu)點(diǎn)可用性好，不需要另外的技術(shù)和信息簡(jiǎn)單可行，獨(dú)立于IP地址可以精確的跟蹤每一個(gè)注冊(cè)用戶可以跟蹤重復(fù)訪問可以精確跟蹤用戶訪問一個(gè)站點(diǎn)的信息缺點(diǎn)不能保證用戶的唯一性，一個(gè)IP多個(gè)用戶代理的情況無法處理沒有重復(fù)的訪問概念，需要完全動(dòng)態(tài)網(wǎng)頁無法跟蹤大量的非注冊(cè)用戶用戶可以禁止該軟件用戶可以中止使用cookie，可用性不高會(huì)話識(shí)別一個(gè)會(huì)話就是指用戶在一次訪問過程中所訪問的Web頁面的序列。會(huì)話識(shí)別的目的是將每個(gè)用戶的訪問信息劃分成若干個(gè)獨(dú)立的會(huì)話進(jìn)程，最簡(jiǎn)單的方法是采用超時(shí)估計(jì)的辦法，即當(dāng)對(duì)頁面之間的請(qǐng)求時(shí)間間隔超出所給定值時(shí),即可以認(rèn)為用戶已經(jīng)開始了一次新的會(huì)話。JPitkow的實(shí)驗(yàn)證明：比較合理的時(shí)間長(zhǎng)度應(yīng)該是25。5分鐘，通常使用30分鐘作為一個(gè)用戶點(diǎn)擊流會(huì)話的時(shí)間長(zhǎng)度。會(huì)話識(shí)別的流程圖如圖3-5所示。開始開始讀出表中一個(gè)用戶放的日志記錄讀出表中一個(gè)用戶放的日志記錄判斷判斷url是否超時(shí)NNYY在用戶會(huì)話表里插入新的用戶會(huì)話在用戶會(huì)話表里插入新的用戶會(huì)話Y判斷是否有訪問記錄未處理Y判斷是否有訪問記錄未處理NN結(jié)束結(jié)束圖3-5會(huì)話識(shí)別流程圖路徑補(bǔ)充由于本地緩存和代理服務(wù)器緩存的存在，使得服務(wù)器的日志會(huì)遺漏一些重要的頁面請(qǐng)求。路徑補(bǔ)充的任務(wù)就是將這些遺漏的請(qǐng)求補(bǔ)充到用戶會(huì)話當(dāng)中，解決的方法類似于用戶識(shí)別中采用的方法。如果當(dāng)前請(qǐng)求的頁面及用戶上一次請(qǐng)求的頁面之間沒有超文本鏈接，那么用戶很可能使用了瀏覽器上的“后退”按鈕調(diào)用緩存在本機(jī)中的頁面。檢查引用日志確定當(dāng)前請(qǐng)求來自哪一個(gè)頁面，如果在用戶的歷史訪問記錄上有多個(gè)頁面都包含當(dāng)前請(qǐng)求頁面的鏈接,則將請(qǐng)求時(shí)間最接近當(dāng)前請(qǐng)求頁面的頁面作為當(dāng)前請(qǐng)求的來源。若引用日志不完整，可以使用站點(diǎn)的拓?fù)浣Y(jié)構(gòu)代替。通過這種方法將遺漏的頁面請(qǐng)求添加到用戶的會(huì)話文件中。經(jīng)過以上幾個(gè)過程的數(shù)據(jù)預(yù)處理，就形成了事務(wù)數(shù)據(jù)庫,這個(gè)數(shù)據(jù)庫是下一階段數(shù)據(jù)挖掘的基礎(chǔ)。路徑補(bǔ)充流程圖如圖3—6所示。讀取一個(gè)用戶的會(huì)話序列開始讀取一個(gè)用戶的會(huì)話序列開始判斷當(dāng)前頁是否可從上一頁直接訪問判斷當(dāng)前頁是否可從上一頁直接訪問YYNN將該頁面加到用戶會(huì)話列表中結(jié)合將該頁面加到用戶會(huì)話列表中結(jié)合inter結(jié)構(gòu)將訪問路徑補(bǔ)充完整Y判斷用戶會(huì)話中有無未處理的會(huì)話序列Y判斷用戶會(huì)話中有無未處理的會(huì)話序列NN結(jié)束結(jié)束圖3—6路徑補(bǔ)充流程圖事務(wù)識(shí)別用戶會(huì)話是Web日志挖掘中唯一具有自然事務(wù)特征的元素,但對(duì)數(shù)據(jù)挖掘來說，還有些粗糙不夠精確,需要把會(huì)話進(jìn)一步分成具有一定語義的事務(wù),這兒只是借用了“事務(wù)”的叫法，也稱作情景識(shí)別（EpisodeIdentification)。常用的事務(wù)分割方法有:引用長(zhǎng)度（ReferenceLength）、最大向前路徑（MaximalForwardPath）、時(shí)間窗口（TimeWindow）等，事務(wù)識(shí)別(TransactionIdentification）的方法在資料上有詳細(xì)的說明。事務(wù)識(shí)別的流程圖如圖3—7所示。Flag=1Flag=1判斷當(dāng)前訪問頁面是否是前一個(gè)頁面的直接后繼判斷當(dāng)前訪問頁面是否是前一個(gè)頁面的直接后繼NYNYYFlag=0？YFlag=0？Flag=0？NYNYFlag=0，開始新的事務(wù)將當(dāng)前及第一頁面加到新事務(wù)中，F(xiàn)lag=0，開始新的事務(wù)將當(dāng)前及第一頁面加到新事務(wù)中，flag=1將當(dāng)前及第一頁面加到新事務(wù)中所有頁面是否已處理完？讀出用戶會(huì)話表的用戶訪問序列開始所有頁面是否已處理完？讀出用戶會(huì)話表的用戶訪問序列開始NN結(jié)束結(jié)束圖3-7事務(wù)識(shí)別流程圖本章小結(jié)本章介紹數(shù)據(jù)挖掘的預(yù)處理的相關(guān)理論，然后詳細(xì)闡述了Web日志挖掘前期工作--數(shù)據(jù)預(yù)處理的整個(gè)過程，主要包括數(shù)據(jù)清理、用戶識(shí)別、會(huì)話識(shí)別、路徑補(bǔ)充和事務(wù)識(shí)別五個(gè)部分。應(yīng)用于Web日志挖掘的改進(jìn)蟻群算法設(shè)計(jì)下面介紹基本蟻群算法及其典型的改進(jìn)算法和對(duì)基本蟻群算法進(jìn)行了改進(jìn)及計(jì)算機(jī)仿真。蟻群算法在Web日志挖掘中的應(yīng)用分析隨著互聯(lián)網(wǎng)用戶的不斷增加，Web服務(wù)器上保存大量的網(wǎng)絡(luò)日志數(shù)據(jù)，網(wǎng)絡(luò)日志數(shù)據(jù)中隱藏著用戶瀏覽模式信息，Web日志挖掘幫助用戶快速找到用戶瀏覽服務(wù)器資源的興趣路徑序列。一個(gè)Web站點(diǎn)模型可通過一個(gè)二元節(jié)點(diǎn)圖（N，E）進(jìn)行描述，其中E表示W(wǎng)eb頁頁之間的超鏈接集合，N表示W(wǎng)eb頁頁的集合，具體如圖4。1所示：圖4。1簡(jiǎn)單Web站點(diǎn)模型從圖4.1可知，當(dāng)用戶進(jìn)行網(wǎng)站瀏覽時(shí)，事先不知道那一條路徑達(dá)到用戶感興趣頁面(節(jié)點(diǎn))最優(yōu)，可以通過Web日志挖掘技術(shù)找出一條用戶達(dá)到目標(biāo)的最優(yōu)節(jié)點(diǎn)序列，即最短路徑。因此通常情況下，用戶瀏覽行為具有如下特點(diǎn):(1)盲目性及從眾性，例如新聞的點(diǎn)擊排行等,一般都根據(jù)歷史瀏覽人數(shù)較多路徑進(jìn)行瀏覽。（2）到達(dá)用戶尋找目標(biāo)的路徑越短,那么被瀏覽效率越高，瀏覽的頻率增加越快，不然，用戶煩瑣操作會(huì)失去該類用戶。對(duì)上述用戶瀏覽行為分析可知，其及自然界螞蟻覓食十分相似。大量研究表明，螞蟻可以通過相互協(xié)作和信息交流找到一條食物源和蟻巢之間的最短路徑。螞蟻覓食時(shí)，原本盲目行走的孤立螞蟻可以通過以前螞蟻在路徑上留下信息素進(jìn)行搜索，同時(shí)對(duì)該路徑上信息素加強(qiáng)，形成一種正反饋機(jī)制,使該路徑被螞蟻選擇概率越來越大,由于路徑信息素不斷的發(fā)揮，時(shí)間較長(zhǎng)的路徑保留的信息素相對(duì)較少，這樣螞蟻?zhàn)罱K找到一條最優(yōu)路徑。螞蟻群體的路徑尋優(yōu)機(jī)制如圖4。2所示，在圖4.2中，其中，CD為一障礙物,螞蟻通過由B或E繞過障礙物進(jìn)行覓食。圖4。2螞蟻群體的路徑尋找機(jī)制比較圖4.1和圖4.2可知,Web日志挖掘及蟻群覓食本質(zhì)極相似，因此采用蟻群算法對(duì)Web日志挖掘問題進(jìn)行求解是可行的。傳統(tǒng)日志數(shù)據(jù)挖掘算法本小節(jié)將介紹傳統(tǒng)的web日志挖掘算法及蟻群算法。Apriori算法在對(duì)Web日志進(jìn)行挖掘的各種算法中，比較傳統(tǒng)的是Apriori頻繁項(xiàng)集算法，這是一種挖掘關(guān)聯(lián)規(guī)則的算法，在很多領(lǐng)域中都有應(yīng)用，例如在網(wǎng)絡(luò)安全問題中可以用來檢測(cè)各項(xiàng)事件和攻擊的關(guān)聯(lián)，從而預(yù)測(cè)下一個(gè)攻擊行為；在商業(yè)中可以對(duì)消費(fèi)者的大數(shù)據(jù)進(jìn)行分析，對(duì)消費(fèi)者的購(gòu)買行為進(jìn)行統(tǒng)計(jì)并預(yù)測(cè).從機(jī)制上說,Apriori是一種廣度優(yōu)先搜索算法，由頻繁k—1項(xiàng)集產(chǎn)生候選頻繁k項(xiàng)集，當(dāng)候選頻繁k項(xiàng)集的支持度超過聞值時(shí),則選取為頻繁k項(xiàng)集.Apriori算法則建立在頻繁一項(xiàng)集開始，算法終止的條件是不能產(chǎn)生更多項(xiàng)數(shù)的頻繁項(xiàng)集時(shí)。而在這個(gè)算法中，通過2個(gè)階段來生成頻繁項(xiàng)集：第一階段是候選頻繁項(xiàng)集的建立階段，第二階段是計(jì)算項(xiàng)集支持度階段.在候選頻繁項(xiàng)集產(chǎn)生階段中，由已知的頻繁k—1項(xiàng)集中獲得候選頻繁k項(xiàng)集。在計(jì)算支持度階段中，通過遍歷數(shù)據(jù)集對(duì)每個(gè)候選頻繁項(xiàng)集進(jìn)行支持度計(jì)數(shù).對(duì)支持度大于閉值的候選頻繁項(xiàng)集選為頻繁k項(xiàng)集.頻繁項(xiàng)集通過計(jì)算生成后，可以使用頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則，這些規(guī)則可以進(jìn)一步在日常的應(yīng)用中應(yīng)用于各種預(yù)測(cè)分析，例如網(wǎng)絡(luò)中反映的用戶的習(xí)慣預(yù)測(cè).此外,在對(duì)于處理較小的數(shù)據(jù)集時(shí)，Apriori算法擁有很好的表現(xiàn)，不過其缺點(diǎn)會(huì)在數(shù)據(jù)集中項(xiàng)數(shù)多時(shí)表現(xiàn)，即算法效率較低。造成這種短板的原因是Apriori算法中為了產(chǎn)生一個(gè)頻繁k項(xiàng)集｛x1,x2,……xk｝，需要先生成2k—2個(gè)頻繁的子集。當(dāng)頻繁k項(xiàng)集的項(xiàng)數(shù)k很大時(shí),子集的數(shù)量變得很多，頻繁項(xiàng)集樹的節(jié)點(diǎn)數(shù)也將變多。因此，計(jì)算機(jī)將會(huì)反復(fù)的對(duì)數(shù)據(jù)集合進(jìn)行遍歷，從而生成頻繁項(xiàng)集，而對(duì)頻繁項(xiàng)集樹進(jìn)行保存也會(huì)占用大量緩存空間，影響整個(gè)算法效率。蟻群系統(tǒng)算法蟻群算法在Web日志挖掘中的應(yīng)用也是非常廣泛的,它本身有仿生學(xué)的機(jī)制,又包含了路徑概率選擇及信息的正負(fù)反饋，即如果一條路徑被幾乎全部的螞蟻所選擇行走，則該路徑為最佳路徑.這種思路在很多數(shù)據(jù)控制領(lǐng)域應(yīng)用廣泛。其具體機(jī)理為：假設(shè)用戶對(duì)Web網(wǎng)頁的游覽記錄如下：S=｛（n1，n4,n8)，(n1，n4），（n1，n4，n7），(n1，n3，n7），（n1，n3,n6），（n1，n3，n7)，（n1，n3,n6)，（n1，n2，n5，n3,n7），（n1，n2，n5),(n6，n7)）根據(jù)圖4.1可知，蟻群算法的Web日志管理模型如圖4。3所示：圖4.3蟻群系統(tǒng)在Web日志挖掘中的應(yīng)用模型在對(duì)一個(gè)網(wǎng)頁或者網(wǎng)站進(jìn)行瀏覽時(shí)，用戶對(duì)網(wǎng)頁的閱讀頻率和閱讀時(shí)長(zhǎng)可以體現(xiàn)出對(duì)此網(wǎng)站的興趣，當(dāng)用戶對(duì)內(nèi)容有興趣時(shí)，會(huì)表現(xiàn)在閱讀時(shí)間增長(zhǎng)，閱讀頁面增多，因此采用蟻群算法進(jìn)行日志挖掘時(shí)，會(huì)考慮采用定義用戶的瀏覽序列并建立一條路徑，而將瀏覽序列作為支持度，成為整個(gè)算法的啟發(fā)式信息，并對(duì)用戶的瀏覽興趣進(jìn)行描述.一種改進(jìn)的適用于Web日志挖掘的蟻群算如同前面所介紹，在初始階段，每只螞蟻分配到一個(gè)空的解集合，所有的信息素初始化為一個(gè)相同的值,隨著迭代過程的進(jìn)行，信息素值將依賴于產(chǎn)生的解的質(zhì)量得以更新。下面結(jié)合一個(gè)具體問題來詳細(xì)分析如何調(diào)整蟻群算法求解聚類問題,蟻群聚類算法采用的硬件/軟件環(huán)境分別為：CPU2。4GHz內(nèi)存256M硬盤容量80G安裝的是MicrosoftwindowsXP（ServicePack2)操作系統(tǒng)開發(fā)平臺(tái)MATLAB7。0。下面結(jié)合一個(gè)具體問題來詳細(xì)分析如何調(diào)整蟻群算法求解聚類問題，數(shù)據(jù)集見表4-1。表4-1為包含10個(gè)樣本的數(shù)據(jù)集,每個(gè)樣本有4個(gè)屬性，設(shè)置10只螞蟻欲將樣本劃分為3類。表4-110個(gè)樣本劃分為3類的聚類問題的數(shù)據(jù)集序號(hào)123415。43。71。50.224.83。41。60.234。83。01。40。144.33。01.10。155.84。01.20。20.475。43。91。30。485.13.51。40.395.73。81.70。3105。13。81.50.3下面本文介紹具體的迭代過程,為了便于描述，用t（本次取值1000）來表示迭代的次數(shù)。每只人工螞蟻依賴于第t次迭代提供的信息來實(shí)現(xiàn)分類。表4-2中列出本次迭代中最好解S1繼承的信息素矩陣。表4-2S1解的t次迭代后的信息素矩陣 序號(hào)12311.66440。680161.220721。64460。119691.664431.30270.011.664441。38150。011。664451。21521。66440。5011460.110021。66441。094971。66441.56421.283281。66440。010.7107191。14661。66440.11904101.66440.011.2349τ11=1.6644，τ12=0.68016,τ13=1。2207為第1個(gè)樣本對(duì)應(yīng)及每一個(gè)類的信息素值。這組數(shù)據(jù)表明，由于τ11的值較大，第1個(gè)樣本將以較大的概率歸于第1類。事實(shí)上，每只螞蟻按照以前介紹過的隨機(jī)加確定方法來選擇第i個(gè)樣本將所屬的類.在此，結(jié)合聚類問題再次加以敘述.方法如下：（i)以預(yù)先定義好的幾率q0（0<q0〈1，q0=0.9），選擇及樣本間具有最大信息素的類為樣本要?dú)w屬的類。（ii）以（1-q0）的幾率根據(jù)轉(zhuǎn)換概率隨機(jī)選擇樣本要?jiǎng)澐值念?由人工螞蟻遍歷所有的樣本構(gòu)建出的候選解的質(zhì)量是由特定的聚類問題的目標(biāo)函數(shù)值來決定的.下面表4-3為螞蟻數(shù)目為10的蟻群聚類算法(排好了順序)的結(jié)果：表4-3為螞蟻數(shù)目為10的蟻群聚類算法(排好了順序）的結(jié)果序號(hào)12345678910F113332211213。0041213332211213.0041313332211213。0041413332211213.0041513332211213。0041613332211213.0041713332211113。0275811332211213.0568933332211213。62261013131211213。9488本文還將實(shí)驗(yàn)的最優(yōu)解結(jié)果使用Matlab實(shí)現(xiàn)了2維和3維圖，使得結(jié)果顯示更加直觀明了，如圖4—4和圖4—5所示。圖4—42維效果圖4-53維效果本文還將實(shí)驗(yàn)的最優(yōu)解結(jié)果的分類值使用Excel保存了，如圖4—3。圖4—6結(jié)果輸出自動(dòng)保存到Excel中為提高算法中螞蟻找到的近似解的效率，很多改進(jìn)的蟻群算法都加入了局部搜索,特別是當(dāng)問題域的啟發(fā)信息不易獲得時(shí)，加入局部搜索可以幫助找到更好的解。目前，局部搜索對(duì)所有解都實(shí)行，也可以只對(duì)部分解實(shí)行,本文只對(duì)當(dāng)前可行解實(shí)行局部搜索.在局部搜索前，把所有的解按照目標(biāo)函數(shù)值進(jìn)行升序排列.本文將對(duì)具有高的目標(biāo)函數(shù)值的頭兩個(gè)解進(jìn)行局部搜索操作。局部搜索操作有很多種,這里選擇交換操作.方法如下：預(yù)先產(chǎn)生一個(gè)（0,1）間的隨機(jī)數(shù)pls,以pls=0.01為例.對(duì)表4-3中具有最高目標(biāo)函數(shù)值的解集S10進(jìn)行交換.為解集中的每個(gè)樣本產(chǎn)生隨機(jī)0.56367，0。35746,0。77456，0.46634，0。00139，0。54636，0.25635，0。35646，0。46324，0.14663。只有第五個(gè)樣本的隨機(jī)值小于pls,所以這個(gè)樣本要被分到其他類當(dāng)中.選擇類中心及這個(gè)樣本的距離最短的類為第5個(gè)樣本要去的類。第5個(gè)樣本原來在第二個(gè)類中，那么就要在另兩個(gè)類中選取，經(jīng)過計(jì)算將第5個(gè)樣本重新分到第三類中去。繼而對(duì)解集S9也進(jìn)行交換操作.對(duì)于通過交換而產(chǎn)生的新的解集要重新計(jì)算其目標(biāo)函數(shù)值，及原解集的目標(biāo)函數(shù)值比較，擇優(yōu)。執(zhí)行過局部搜索之后，要對(duì)信息素值進(jìn)行更新。信息素更新公式采用螞蟻系統(tǒng)中的公式:其中，τij（t)及τij（t+1）為樣本i及類j在t及t+1時(shí)間的信息素濃度。為螞蟻k所找到的最小目標(biāo)函數(shù)值.Q為一參數(shù)值.ρ為信息素蒸發(fā)參數(shù)，0〈ρ<1.至此，一次迭代結(jié)束.改進(jìn)后蟻群聚類算法流程改進(jìn)的蟻群聚類算法的主要步驟敘述如下:步驟1：初始化，包括螞蟻數(shù)目R、類的個(gè)數(shù)K、轉(zhuǎn)換規(guī)則參數(shù)q0、局部搜索閾值等。步驟2：所有人工螞蟻根據(jù)上一次的信息構(gòu)建解集，計(jì)算各類中心。步驟3：在產(chǎn)生的解集找到要交換樣本的Sk實(shí)施局部搜索操作.步驟4：更新信息素值。步驟5:如果沒有達(dá)到迭代次數(shù)預(yù)定值并且沒有穩(wěn)定解，則轉(zhuǎn)步驟2，否則輸出最優(yōu)的分類解集。算法基本流程如圖4-7。圖4—7蟻群算法流程圖當(dāng)然，迄今為止蟻群算法已經(jīng)有了很多的變型或改進(jìn)算法，但基于蟻群算法(ACA）尋找問題近似解的思想及實(shí)現(xiàn)優(yōu)化過程的機(jī)制還是沒有改變。由上圖可見，蟻群算法區(qū)別于其他傳統(tǒng)優(yōu)化算法,因?yàn)樗哂幸韵?個(gè)特點(diǎn)：(1）模擬了一種大自然真實(shí)存在的現(xiàn)象，并建立模型;（2）不可確定性；(3）總是表現(xiàn)出一種并行性,不是在系統(tǒng)中強(qiáng)行加入，而是算法本身隱含具有的。仿真實(shí)驗(yàn)對(duì)比分析在4。2小節(jié)中本文詳細(xì)介紹了基本蟻群算法的原理等，在本小節(jié)中將通過計(jì)算機(jī)仿真來理解基本蟻群算法的原理，并將作出的路徑圖和最終結(jié)果自動(dòng)保存到文本文檔(.txt)及Excel（.xls)中。仿真環(huán)境及數(shù)據(jù)為了詳細(xì)對(duì)比出兩種不同算法（改進(jìn)前及改進(jìn)后）算法優(yōu)劣，本文實(shí)驗(yàn)采用同一種實(shí)驗(yàn)數(shù)據(jù):樣例網(wǎng)站則名老中醫(yī)系統(tǒng)的日志數(shù)據(jù)，實(shí)驗(yàn)數(shù)據(jù)中紀(jì)錄數(shù)共8136條,經(jīng)過對(duì)這些日志數(shù)據(jù)的預(yù)處理,可以獲取到能夠用于傳統(tǒng)蟻群算法及增加局部搜索算法后的蟻群算法條件的數(shù)據(jù)。蟻群算法在實(shí)際問題的求解過程當(dāng)中往往具有較高的效率，盡管在不同程度上取得了一定的效果,但是仍然存在著一些不足之處，主要表現(xiàn)在：1）如果一些參數(shù)α、β、ρ、m、Q設(shè)置不合理，那么就會(huì)導(dǎo)致迭代速度非常慢，并且結(jié)果誤差較大;2)從蟻群算法本身來講，其計(jì)算量非常大，相應(yīng)的計(jì)算周期比較長(zhǎng);3）蟻群算法可以通過選取不同的路線來獲得最優(yōu)解，在具體循環(huán)次數(shù)的條件下，還可以根據(jù)不同的實(shí)際問題來對(duì)圖像的內(nèi)容進(jìn)行優(yōu)化處理，根據(jù)處理的結(jié)果來找到相應(yīng)的最優(yōu)解，這樣就能夠保證計(jì)算效率不會(huì)受到影響.從目前來看，蟻群算法的參數(shù)設(shè)置以及屬性方面的研究仍然存在著較多的難點(diǎn),其研究進(jìn)度仍然只是停留在實(shí)驗(yàn)階段，尚未大規(guī)模投入到實(shí)際應(yīng)用當(dāng)中。M。Dorigo等人結(jié)合具體的實(shí)驗(yàn)類型和數(shù)據(jù)來對(duì)蟻群算法的基本屬性進(jìn)行了全面性的分析和研究。所以本實(shí)驗(yàn)中重要參數(shù)設(shè)置如下:信息素濃度影響力參數(shù)α：所有算法α設(shè)為1.0.啟發(fā)式信息影響力參數(shù)β:所有算法β設(shè)為5。0。信息素蒸發(fā)系數(shù)ρ(（1-ρ）表示信息素的持久性系數(shù)）:所有算法ρ設(shè)為0。5(1—ρ即為0。5）。螞蟻數(shù)目m：本文將m設(shè)為問題規(guī)模n的2/5即m=n＊2/5在算法開始時(shí)螞蟻隨機(jī)分布在各個(gè)城市上.(n為其中TSP問題中后面的數(shù)字，如:ATT48.TSP中48即為n值）。TSP問題：本文使用ATT48。TSP的TSP問題。對(duì)比實(shí)驗(yàn)用4。2傳統(tǒng)蟻群算法及4。3改進(jìn)后蟻群算法的條件進(jìn)行計(jì)算機(jī)仿真，為了有效的、科學(xué)的對(duì)算法有效性進(jìn)行評(píng)價(jià)，采用準(zhǔn)確度作為模型的評(píng)價(jià)標(biāo)準(zhǔn)。準(zhǔn)確度定義如下：Precision=R/（R+W)*100%其中，R表示正確的結(jié)果，W表示錯(cuò)誤結(jié)果。設(shè)定θ為網(wǎng)頁之間的轉(zhuǎn)移概率的閾值，當(dāng)轉(zhuǎn)移概率大于該θ的路徑即為用戶感興趣路徑。若感興趣路徑閾值θ的值較低，那么不相關(guān)的網(wǎng)頁被推薦。大量實(shí)驗(yàn)表明，θ=0。5最好，因此本文的θ值為0.5,本文改進(jìn)后的蟻群算法及對(duì)比的傳統(tǒng)蟻群算法對(duì)于不同的事務(wù)長(zhǎng)度,用戶感興頁面進(jìn)行日志挖掘后預(yù)測(cè)的準(zhǔn)確度如表4。4所示：表4.4挖掘準(zhǔn)確度對(duì)比事務(wù)長(zhǎng)度本文改進(jìn)后蟻群算法傳統(tǒng)的蟻群算法36556473625826968781783798868598989圖4。8兩種算法的預(yù)測(cè)準(zhǔn)確度（藍(lán)色為改進(jìn)后，紅色為傳統(tǒng)算法）根據(jù)圖4.8可知,相對(duì)于傳統(tǒng)蟻群算法，本文設(shè)計(jì)的改進(jìn)后的蟻群算法的日志挖掘準(zhǔn)確度更高，能更加有效地跟蹤用戶的興趣變化，主要由于蟻群算法采用信息素機(jī)制實(shí)現(xiàn)正負(fù)反饋機(jī)制.對(duì)比結(jié)果表明，基于蟻群算法的Web網(wǎng)站日志挖掘模型可以很好挖掘用戶的興趣路徑,螞蟻之間的協(xié)作作用改善了用戶瀏覽頁面預(yù)測(cè)的準(zhǔn)確度，動(dòng)態(tài)跟蹤用戶瀏覽行為.另外，本文選取另外的網(wǎng)頁頁面?zhèn)€數(shù)分別為50、100、200的網(wǎng)站,對(duì)其網(wǎng)站日志采用本文的日志獲取方法進(jìn)行了提取，然后根據(jù)大小將其劃分為四個(gè)測(cè)試用命，大小分別為1M，2M,3M，4M,并繼續(xù)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，使之符合本文算法及傳統(tǒng)蟻群算法條件，然后考察其CPU執(zhí)行時(shí)間。實(shí)驗(yàn)結(jié)果為傳統(tǒng)蟻群算法的CPU時(shí)間大于本文算法的CPU時(shí)間；而且隨著測(cè)試用例的日志數(shù)量的增加，本文改進(jìn)后的算法執(zhí)行時(shí)間增加速率較慢，對(duì)傳統(tǒng)蟻群算法的執(zhí)行時(shí)間增加的幅度相對(duì)較大；缺點(diǎn)為本文算法對(duì)于網(wǎng)站上的鏈接數(shù)目敏感，如果網(wǎng)站上的URL數(shù)目增多，本文算法的執(zhí)行時(shí)間延長(zhǎng)，而傳統(tǒng)蟻群算法執(zhí)行時(shí)間及URL個(gè)數(shù)無關(guān)。最后,本文也評(píng)測(cè)了網(wǎng)站服務(wù)器的性能受用戶行為獲取機(jī)制的影響。本文統(tǒng)計(jì)了50次在用戶行為獲取機(jī)制加載前后，用戶計(jì)算機(jī)瀏覽器中載入網(wǎng)站頁面所需的時(shí)間,加載時(shí)間的平均增量為140毫秒，用戶基本的上網(wǎng)行為不會(huì)受到影響。本節(jié)將改進(jìn)后的蟻群算法引入到Web日志挖掘建模中，通過蟻群算法的正負(fù)反饋機(jī)制和路徑概率選擇機(jī)制快速找到用戶目標(biāo)網(wǎng)頁，仿真實(shí)驗(yàn)結(jié)果對(duì)比表明,改進(jìn)后的蟻群算法提高了網(wǎng)頁日志挖掘中的預(yù)測(cè)精度，更能反映出用戶的瀏覽興趣及意圖。改進(jìn)后的蟻群聚類算法應(yīng)用場(chǎng)景實(shí)驗(yàn)上節(jié)利用蟻群聚類算法對(duì)人工數(shù)據(jù)進(jìn)行了分析，現(xiàn)在本文會(huì)利用該算法對(duì)2005年中國(guó)24所高校綜合實(shí)力進(jìn)行分類，同時(shí)來驗(yàn)證蟻群聚類算法的實(shí)際應(yīng)用效果。下面是2005年中國(guó)24所高校綜合實(shí)力數(shù)據(jù)集，見表4-5，表4.5主要表示的是24個(gè)樣本集合,每個(gè)樣本集合都有其獨(dú)特的屬性，通過設(shè)置10只螞蟻來對(duì)下列3個(gè)樣本進(jìn)行分析，迭代次數(shù)1000次。表4-52005年中國(guó)24所高校綜合實(shí)力數(shù)據(jù)表：指標(biāo)序號(hào)