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