FL15111702+WEB日志挖掘技術研究與應用

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