蟻群算法在Web挖掘聚類系統(tǒng)的設(shè)計與實現(xiàn)

基于蟻群算法的Web挖掘聚類系統(tǒng)的設(shè)計與實現(xiàn)摘要本文在研究現(xiàn)有Web挖掘中聚類技術(shù)的基礎(chǔ)上，將一種改進的蟻群聚類算法應(yīng)用于Web挖掘聚類系統(tǒng)中；并引入一種改進的蟻群算法應(yīng)用于Web使用挖掘的用戶事務(wù)聚類中。實驗結(jié)果表明：與傳統(tǒng)的聚類算法相比，基于螞蟻的聚類算法在Web挖掘中具有一定的優(yōu)勢。本文首先針對Web挖掘的過程進行概述，然后詳細地分析了Web挖掘中聚類和分類技術(shù)存在的優(yōu)缺點。深入討論了幾種改進的蟻群算法，在分析了現(xiàn)有算法應(yīng)用于Web挖掘技術(shù)上的不足之后，提出一種改進后的聚類算法并應(yīng)用于Web挖掘聚類系統(tǒng)中，重新定義構(gòu)造螞蟻的方式、相似度和行為，通過仿真實驗來對比傳統(tǒng)的算法，來證明改進的算法對于Web聚類挖掘的適用性。最后，引入了一種改進的蟻群算法(ImprovedAntColonyAlgorithm,IACA),結(jié)合其聚類分析模型并對算法進行實現(xiàn)，將其應(yīng)用到Web使用挖掘的聚類模型上。通過實驗仿真，該聚類算法在聚類過程中，很好地解決了算法中停滯的問題，并且在全局優(yōu)化方面表現(xiàn)出較好的性能。關(guān)鍵詞：Web挖掘；蟻群算法；Web內(nèi)容挖掘；Web使用挖掘；聚類ABSTRACTBasedonthestudyofexistingWebminingtheclusteringtechnologybasedonanimprovedantclusteringalgorithmwasappliedtoclassWebminingclusteringsystem;AndintroducingakindofimprovedantcolonyalgorithmisappliedtoWebusemininguseraffairsinclustering.Theexperimentalresultsshowthat:withthetraditionalclusteringalgorithm,basedontheantclusteringalgorithminWebmininghascertainadvantage.FirstlyWebminingprocessaresummarizedinthispaper,andthenanalyzedindetailintheWebminingtheclusteringandclassificationtechnologyandtheadvantagesanddisadvantagesoftheexisting.Furtherdiscussedseveralimprovedantcolonyalgorithm,theanalysisoftheexistingalgorithmappliedinWebminingtechnologyaftershortcomings,thispaperputsforwardaimprovedclusteringalgorithmandappliedinWebminingclustersystem,redefinestructureant'sway,thesimilarityandthebehavior,throughthesimulationexperimentstocomparedwiththetraditionalalgorithm,toprovethattheimprovedalgorithmforWebclusteringminingapplicability.Finally,weintroduceakindofImprovedAntColonyAlgorithm(ImprovedAntColonyAlgorithm,IACA),combinedwithitsclusteringanalysismodelandtheAlgorithmrealization,itsapplicationtoWebuseminingclusteringmodel.Throughtheexperimentalsimulation,thisclusteringalgorithmintheclusteringprocess,providesgoodsolutionalgorithmstagnationproblems,andintheaspectsofglobaloptimizationshowsgoodperformance.Keywords:WebMining;AntColonyAlgorithm;WebContentMining;WebUsageMining；Clustering同濟大學碩/博士學位論文蟻群算法在Web挖掘聚類模型的設(shè)計與實現(xiàn)____________________________________________________________同濟大學碩士學位論文摘要第二章基于蟻群算法的Web挖掘理論2.1Web挖掘Web挖掘是一項綜合技術(shù)，是數(shù)據(jù)挖掘在Web上的應(yīng)用，涉及有信息學、數(shù)據(jù)挖掘、機器語言學、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)容目標數(shù)據(jù)集經(jīng)預(yù)處理的數(shù)據(jù)模式、規(guī)則、統(tǒng)計結(jié)果有趣的模式預(yù)處理模式發(fā)現(xiàn)模式分析圖2.1Web數(shù)據(jù)挖掘原理圖2.1.1Web挖掘分類及架構(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)的有用信息進行分析的過程。(2)Web結(jié)構(gòu)挖掘：是指通過對Web站點中超鏈接結(jié)構(gòu)進行分析、變形和歸納，并對Web頁面進行分類，最終得到有用的結(jié)果。常用的算法有PageRank算法和HITS算法等，挖掘的對象包括Web的結(jié)構(gòu)、頁面的結(jié)構(gòu)以及Web文檔自身的結(jié)構(gòu)；(3)Web使用挖掘：通過分析Web服務(wù)器的日志文件，以發(fā)現(xiàn)用戶訪問頁面的模式，如用戶訪問模式分析、個性化分析、分類和聚類。方便為站點管理員提供各種利于Web站點改進的信息，并將訪問記錄數(shù)據(jù)傳給數(shù)據(jù)關(guān)系表中來實現(xiàn)對關(guān)系表數(shù)據(jù)的挖掘。2.1.2Web挖掘過程Web內(nèi)容挖掘的基本過程Web內(nèi)容挖掘的基本過程包括文本分析、文本解釋、文檔分類、文檔可視化，它目的在于挖掘出基于用戶需求的Web文本和多媒體信息，并對Web數(shù)據(jù)進行多樣查詢，提取其中無結(jié)構(gòu)的動態(tài)文本進行集成、建模，最終實現(xiàn)知識發(fā)現(xiàn)。Web內(nèi)容挖掘可以分為兩類[10]：資源查找方法和數(shù)據(jù)庫方法。Web使用挖掘的基本過程Web使用挖掘是對網(wǎng)絡(luò)日志進行挖掘，從用戶訪問Web時留下的訪問記錄中挖掘出潛在的、有用信息的過程。其目的在于要發(fā)現(xiàn)用戶留下的瀏覽模式和有用信息，這有利于開發(fā)Web的最大經(jīng)濟潛力，按照其分類規(guī)則，將Web使用挖掘分為數(shù)據(jù)預(yù)處理、模式識別和模式分析三個階段，如圖2.2所示：Web站點文件Web站點文件日志文件用戶會話文件挖掘和模式感興趣的規(guī)則和模式預(yù)處理挖掘模式分析圖2.2Web使用挖掘過程(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ù)處理主要對日志文件進行數(shù)據(jù)收集、抽取、清洗、用戶會話識別、事務(wù)模式分析等處理[11]。(2)模式識別識別的困難是由本地緩存和代理服務(wù)器造成的，當完成對用戶事務(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使用挖掘研究的一個新熱點。2.1.3Web挖掘技術(shù)聚類(1)基于模糊聚類算法的Web頁面聚類[13]模糊集理論是Zadeh于1965年提出的，其定義如下：設(shè)為論域，若集合R是其上的一個模糊集，則有。是模糊集R的隸屬函數(shù)，為的隸屬度。在兩個模糊集A與B上的運算有：應(yīng)用模糊算法進行Web頁面聚類時，主要就是構(gòu)造頁面間的模糊相似矩陣。定義Web訪問用戶集合，某一站點所有URL集合中可用用戶訪問情況表示為：，其中，，n表示用戶數(shù)量。此時可建立頁面間的模糊相似矩陣，矩陣中的元素值為：，因該矩陣為對稱矩陣，所以在計算相似度時只取一半數(shù)據(jù)，以給定的閾值構(gòu)造相似類。由于模糊矩陣不滿足傳遞性，故只能得到含有公共元素的相似類而非等價類。具體而言：對于每一個,根據(jù)給定的閾值構(gòu)造相似類會具有相同的元素。如，；即。此時將具有公共元素的相似類歸并得到對應(yīng)的等價類即為Web頁面聚類的結(jié)果。將用戶Ci用瀏覽子圖的URL序列表示為：。建立客戶相似矩陣：按頁面聚類相同方法即可進行用戶聚類。。分類1.基于頁面文本與超文本結(jié)構(gòu)信息的Web頁面綜合分類[16]因為基于Web頁面文本和超文本結(jié)構(gòu)信息的Web頁面分類方法各有其特色，所以可將兩者相結(jié)合提高分類結(jié)果。如文獻[15]提出的二者取其最大值的方法，但該方法效果不是太明顯。而范炎[16]等提出的利用貝葉斯方法將基于頁面文本和超文本結(jié)構(gòu)信息的分類視為兩個相互獨立的因素結(jié)合起來進行綜合分類，即：(2.3)考慮到超文本結(jié)構(gòu)分類中利用的單詞遠遠少于頁面文本分類，需要對不同方法分類結(jié)果加以預(yù)處理。(2.4)其中n是D中出現(xiàn)的不同單詞數(shù)，即根據(jù)n值不同分別為不同的分類結(jié)果賦予不同的權(quán)重。實驗表明在基于貝葉斯方法的分類中，綜合分類的結(jié)果好于文本分類和超文本結(jié)構(gòu)分類單獨分類時5%以上，就正確率而言綜合分類好于前者6.75%，較后者提高5.79%。2.基于頁面文本的分類方法[14](1)基于貝葉斯方法的頁面分類。在頁面分類的諸多算法中貝葉斯分類方法的前提是：文本特征之間是相互獨立的。貝葉斯方法與閾值大小來對文本數(shù)據(jù)進行劃分：(2.5)其中指C類文檔第i個特征，是從C類文本中得到特征詞的概率，n值d中詞的個數(shù)，m是系統(tǒng)詞典的大小，若所得的閾值大于預(yù)先設(shè)定得值，則認為文本d屬于C類，否則不是。從概率大小來研究，貝葉斯分類方法可描述為：設(shè)文檔d的文檔向量的分量為相應(yīng)的特征詞在該文檔中出現(xiàn)的頻度，則d屬于C類文檔的概率公式為：(2.6)(2.7)(2.7)是在C類文檔中出現(xiàn)的條件概率的拉普拉斯概率估計，是C類文檔中特征詞出現(xiàn)的頻率，是d類文檔中特征詞出現(xiàn)的頻度，是文檔中所包含的不同特征的總數(shù)目。(2)基于文檔相似性的文檔分類?；谖臋n相似性的文檔分類方法并無貝葉斯方法所需的前提假設(shè)。使用文檔表示矩陣間的夾角余弦值來表示它們之間的相似程度(2.8)：(2.8)2.1.4Web挖掘算法的關(guān)鍵問題(1)Rank算法[17]Rank算法是Web超鏈接結(jié)構(gòu)分析中最成功的代表之一，是評價網(wǎng)頁權(quán)威性的一種重要工具。搜索引擎Google就是利用該算法和anthortext標記、詞頻統(tǒng)計等因素相結(jié)合的方法來檢索出的大量結(jié)果進行相關(guān)度排序，將最權(quán)威的網(wǎng)頁盡量排在前面。Rank的基本思想：設(shè)頁面i的鏈入集合為{T1，T2,…，Tn}，即{T1，…，Tn}中的每一個頁面都鏈接到頁面i，C(i)為頁面i的鏈出頁面數(shù)，則頁面i的等級值PR(i)可以通過以下兩步計算得出：(1)以概率e隨機取Web上任一頁面。(2)以概率1-e隨機取當前頁面任一鏈出頁面。PR(i)=1-e+e*(PR(T1)/C(T1)+…+PR(Tn)/C(Tn))(2.9)存在問題：PageRank是對Web整體分析，通過模擬在Web上的隨機游動對每一個網(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擴展成一個更大的集合T，作為基本集(Baseset)。首先，為基本集中的每一個頁面賦予一個非負的權(quán)威權(quán)重ap和非負的Hub權(quán)重hp，并將所有的a和h值初始為同一個常數(shù)。Hub與權(quán)威的權(quán)重可按如下公式進行迭代計算：(2.10)(2.11)存在問題：HITS算法存在“主題漂移”的現(xiàn)象，如用戶在查詢“量子物理學”時，由于算法中需要對初次檢索結(jié)果的根集擴充成基集，最終的檢索結(jié)果中會包含大量的有關(guān)“物理學”的站點。因此HITS適合與寬主題的查詢，而PageRank則較好地克服了“主題漂移”的現(xiàn)象。2.2蟻群算法蟻群算法是一種模擬螞蟻群體智能行為在圖中尋找優(yōu)化路徑的仿生類優(yōu)化算法,它由MarcoDorigo在92年提出，其思想來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為,當一只螞蟻找到食物后，會在其走過的路上釋放一種揮發(fā)性分泌物Pheromone（信息素，信息素濃度的大小表征路徑的遠近）[5]，螞蟻在搜尋過程中能夠感知信息素的存在和強度，并吸引其他螞蟻過來，通過這種方式形成了信息素軌跡。2.2.1蟻群算法分析數(shù)學模型為了便于理解，通常引入蟻群算法求解平面上某個城市的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)過的城市為下一個城市；當完成一步（從一個城市到達另一個城市）或者一個循環(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為目標城市的概率為：(2.12)也即，螞蟻選中某一個城市的可能性是問題本身所提供的啟發(fā)信息與從螞蟻目前所在城市到目標城市路徑上殘留信息量的函數(shù)。為了避免殘留信息過多引起的殘留信息淹沒啟發(fā)信息的問題，在每一只螞蟻完成對所有n個城市的訪問后（也即一個循環(huán)結(jié)束后），必須對殘留信息進行更新處理，模仿人類記憶的特點，對舊的信息進行削弱。同時，必須將最新的螞蟻訪問路徑的信息加入。這樣得到(2.13) 式中：殘留信息的保留部分，1-表示在時段t到(t+1)內(nèi)殘留信息被削弱的部分，為了防止信息的無限累積，的取值范圍必須在0到1之間； 第k個螞蟻在時段t到(t+1)內(nèi)，在i到j(luò)的路徑上留下的殘留信息濃度。 在文獻[18]中,M.Dorigo介紹了的3種不同的實現(xiàn)方法，分別稱為ant_cycle,ant_density,ant_quantity算法。對于前一種算法：(2.14)式中：Q是一個常量，用來表示螞蟻完成一次完整的路徑搜索后，所釋放的信息素總量：Lk表示螞蟻k在本次循環(huán)中所選擇路徑的總花費，它等于第k個螞蟻經(jīng)過的各段路徑上所需的花費Cij的總和。2.2.2蟻群算法的改進幾種典型的改進蟻群優(yōu)化算法如下：1.天才螞蟻算法天才螞蟻算法[20]主要是針對AS算法進行改進而提出的一種算法。其調(diào)度策略如下：設(shè)定搜索中已有的最優(yōu)解為，調(diào)度問題解空間中存在不同類型的待優(yōu)化變量，在該路徑上修改信息素軌跡，以增強正反饋效果，修改公式為：(2.16)其中的定義方法和以前設(shè)定的相同，e為調(diào)整影響權(quán)重的參數(shù)，所以由下式給出：(2.17)2.最大最小蟻群算法最大最小蟻群算法是由Hoos和stutzle等人提出的，較傳統(tǒng)的蟻群算法有明顯改動。（1）基本蟻群算法中各路徑的信息量具有不確定性，為了避免這個缺陷，利用與蟻群算法運行過程相關(guān)的信息熵值表示選擇過程的不確定性，將所有路徑上的信息素濃度控制在一定的范圍內(nèi)，這樣就可以實現(xiàn)蟻群算法的自適應(yīng)調(diào)節(jié)。（2）所有路徑上信息素濃度在初始化時已被定義為數(shù)值的上限值，同樣設(shè)置一個較小的揮發(fā)系數(shù)，這樣可以在算法開始的時候探索更多的路徑。（3）當系統(tǒng)停滯或在一定時間內(nèi)系統(tǒng)沒有產(chǎn)生更好的解時，路徑上的信息素被重新初始化，修改信息素的方法如下：(2.18)(2.19)(2.20)其中Cbest是已知最優(yōu)路徑的長度，Cib是本次循環(huán)中找到的最優(yōu)路徑的長度，Hoos等人經(jīng)過試驗證明，在求解小規(guī)模的問題時，計算路徑上的信息素增量使用公式(2.20)，隨著問題規(guī)模的增加，公式(2.19)使用的頻率也增加。2.2.3蟻群算法的關(guān)鍵問題(1)搜索時間較長計算的復(fù)雜度主要體現(xiàn)在構(gòu)造模型的過程中，隨著問題規(guī)模的增大，算法消耗的時間也隨之增加，通過這些參數(shù)信息交換能夠向著最優(yōu)路徑進化，但是當群體規(guī)模較大時，很難在短時間內(nèi)找出一條較好的路徑。通過正反饋機制，使得較優(yōu)路徑上的信息量逐漸增加，需要在很長的一段時間后，才能使較優(yōu)路徑上的信息量明顯高于其他路徑。目前這方面的研究開始逐步走向深入[24]。(2)運行效率與全局收斂針對蟻群算法運行效率低下這一問題，曾先后提出了帶精英策略的螞蟻系統(tǒng)（ASelist）和基于優(yōu)化排序的螞蟻系統(tǒng)（ASrank）。雖然它們在運行效率方面取得一定的進展，但是同樣也付出了容易收斂于局部最優(yōu)解的代價。在它們之后，MMAS以及ACS針對上述問題進行了改進，擴展了蟻群的搜索空間，但是它們在效率方面同樣也付出了代價。目前的研究是將注意力集中到將蟻群算法與其他智能仿生算法相結(jié)合。2.3小結(jié)首先介紹了Web挖掘的理論知識，包括分類、架構(gòu)模型等。詳細地論述了Web挖掘技術(shù)中的聚類和分類技術(shù)以及指出現(xiàn)階段存在的關(guān)鍵問題。然后，對蟻群算法進行分析，介紹了幾種常用的改進算法，系統(tǒng)地提出了當前蟻群算法研究熱點問題。最后，對比幾種現(xiàn)有改進的算法在Web挖掘技術(shù)上的應(yīng)用，并給出了各自算法在應(yīng)用中存在的優(yōu)勢和不足。第三章聚類模型分析與設(shè)計第三章聚類模型分析與設(shè)計聚類是將復(fù)雜的事物分門別類，并對陌生繁亂的事物進行歸類總結(jié)，相同類別的事物采取類似的處理方法，這樣就能大大提高事物的處理效率，通過自動聚類能夠識別對象空間中不同密度空間的區(qū)域，從而發(fā)現(xiàn)全局分布模式，并結(jié)合蟻群算法的正反饋、魯棒性、分布式計算等優(yōu)點，對聚類模型進行設(shè)計。3.1聚類模型分析聚類分析在Web挖掘中是一個很重要的技術(shù)。聚類分析可以增強對象集的可理解性，并發(fā)現(xiàn)對象集中數(shù)據(jù)間共同的結(jié)構(gòu)和聯(lián)系，保持其有效性。即按照一定的規(guī)律和需求，將一些特殊分散的對象按照其相似性進行分類，并使得對象點的集合分成若干類，且每個類中的對象點最大程度地相似，各個類之間的對象點最大程度地不同。在聚類分析過程中沒有涉及關(guān)于分類方面的知識，只是依靠對象點間的相似度作為劃分類的依據(jù)，因此聚類分析是一種觀察式學習，是利用數(shù)學方法研究和處理所給定對象的分類，其多元的統(tǒng)計分析方法是統(tǒng)計模式識別中非監(jiān)督模式識別的重要分支。為了描述對象樣本間的距離，特引入特征變量類型和相似性度量這2個概念。(1)特征變量類型為了描述一個對象樣本，我們通常會對對象進行特征抽象化，使用多個特征指標變量來給予每個對象一個特征向量。特征指標變量可以分為：間隔標度變量、二次變量、序數(shù)變量，處理不同類型的特征指標變量則采取不同的策略。對于間隔標度變量是使用連續(xù)的實數(shù)來表示的數(shù)量信息，一個樣本點可以看作是多維空間中的一點，通過一些特殊的運算來求解各個樣本在空間上的距離。對于二元變量，用兩種狀態(tài)（0或1）來表示樣本屬性，1表示變量出現(xiàn)，0表示變量不出現(xiàn)，該變量特征也可以用來分類變量尺度，標記多狀態(tài)。對于序數(shù)變量，它類似于分類變量，不用于分類變量的是，其狀態(tài)時無序關(guān)系的，而分類的狀態(tài)是有序的。對于這兩種特征變量我們不能定義合適的數(shù)學運算，需要通過特殊變換后才能進行對象相似度計算。(2)相似性度量為了更好地描述對象集中的單個樣本，需要樣本類型中的特征指標變量提供度量值，同樣為了描述樣本間的相似特性，也需要定義能合理地衡量樣本間相似程度，從而合理地進行聚類的度量，以便把相似的樣本歸為一類，非相似的樣本歸為不同的類。常用刻畫樣本間的相似性函數(shù)有2種，分別是：相似系數(shù)函數(shù)、距離函數(shù)。相似系數(shù)函數(shù)是用來描述樣本點特征性質(zhì)之間的相似程度，當相似系數(shù)值越接近0時，說明兩個對象樣本越不相似，當相反相似系數(shù)值越接近1，則說明兩個對象越相似，這才可以將它們歸為一類。距離函數(shù)指的是對象樣本間的距離，對于含有N個屬性的樣本對象來說，我們可以將每個樣本點看作是N維空間中的一個點，然后使用某種距離來表示樣本對象點之間的相似性，對象樣本點越相似，則樣本點之間的距離越小，可以將它們歸為一類；對象樣本點差異越大，則兩者間的距離越大，就不能歸為一類。3.2聚類模型設(shè)計聚類首先要做的是對樣本對象的特征抽取，它所處理的對象是樣本數(shù)據(jù)集，由于實際應(yīng)用中的樣本數(shù)據(jù)對象一般都有多種特征，要具體選取哪種特征才可以正確地描述樣本對象的本質(zhì)和結(jié)構(gòu)對于聚類分析來說至關(guān)重要。特征抽取的結(jié)果是輸出一個矩陣，每一行對應(yīng)的是一個樣本對象，而每一列對應(yīng)的是一個特征變量。特征的抽取是另一個重要步驟，對后續(xù)的分析和決策有直接的影響。如果抽取的特征變量只是樣本對象中不重要的屬性，對這些無關(guān)緊要的屬性進行聚類分析出的結(jié)果肯定也達不到預(yù)期的效果，因為當使用錯誤的特征屬性來解釋對象時，容易扭曲樣本對象，再對這樣的樣本對象進行的聚類分析，即便是用最好的聚類算法來對其處理，結(jié)果也是不正確的?？偨Y(jié)蟻群算法和聚類分析的特點，引入了一種改進的蟻群算法(ImprovedAntColonyAlgorithm，IACA)。并將其運用到Web的用戶聚類上，聚類模型如下：1.初始化設(shè)定設(shè)有M個模式樣本、K個模式分類，N是表示為幾個樣本對象；初始狀態(tài)將M個樣本隨機分配到N個聚類中心，K表示分類出K個等級，每個模式樣本是一個D維向量，定義模式樣本。設(shè)聚類中心為，則目標函數(shù)表示為：(3.7)2.信息素更新計算螞蟻的各自初始聚類中心（第k個螞蟻將模式樣本i分配到第j個聚類中心）和初始目標函數(shù)，初始化各螞蟻的樣本到各聚類中心的信息素濃度，信息素濃度更新公式為：(3.8)其中是信息素增量,是信息素強度的持久性系數(shù)（算法中1-表示信息素揮發(fā)度）。初始化，螞蟻將M個樣本隨機分配到K個聚類中心初始化，螞蟻將M個樣本隨機分配到K個聚類中心計算螞蟻的各自初始聚類中心和初始目標函數(shù)初始化各螞蟻的樣本到各聚類中心的信息素濃度M只螞蟻到N個樣本進行K個模式分類更新并調(dià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ā)度1-等等。螞蟻數(shù)量N決定蟻群算法的循環(huán)次數(shù)呈線性變化。當螞蟻數(shù)量過大時,搜索的全局性和穩(wěn)定性有所提高，但是算法的收斂速度變慢。蟻群搜索過程中信息素揮發(fā)度1-的大小關(guān)系到蟻群算法運行過程中的收斂速度和全局搜索能力：當1-過小時，搜索過的路徑被選擇的概率降低，雖然算法全局搜索能力和隨機性能有所提高，但是收斂速度卻下降；當1-過大時，表示搜索過的路徑被再次選擇的概率增加，影響算法的全局搜索能力；所以對信息素揮發(fā)度的選擇，需要平衡算法的收斂速度和全局搜索能力。另外，AST和CST的取值也很重要，取值不恰當容易使解陷入局部收斂，算法需要在穩(wěn)定性和求解速度上取得平衡。3.3聚類算法源代碼設(shè)計部分不要用大篇幅偽碼，用流程圖更好些設(shè)計部分不要用大篇幅偽碼，用流程圖更好些算法采用vb語言實現(xiàn)，整個算法的偽代碼偽代碼和源碼是兩個概念如下：偽代碼和源碼是兩個概念DimhaveResult‘是否已經(jīng)搜索出結(jié)果的標志dimMinT‘目標函數(shù)的最小值DimAntNum‘最后分類結(jié)果的螞蟻序號Forak=1toM‘初始化Initialization(ak)'初始化螞蟻種群中每只螞蟻的各個樣本隨機分配到K個模式分類中的某個類別ClusterCenter(ak)‘計算初始時第ak只螞蟻的K個聚類中心Distance(ak,0)’計算初始時第ak只螞蟻的每個模式樣本到聚類中心的距離以及第ak只螞蟻的目標函數(shù)Ifak=1then‘目標函數(shù)最小值開始為初始值的最小值MinT=T(ak,0)ElseIfT(ak,0)<MinTthen‘找到所有螞蟻當中最小的目標函數(shù)值MinT=T(ak,0)EndifEndifAST=5*Q/MinT‘定義螞蟻的絕對感覺閾限NextInfomation(0)’初始化每只螞蟻在各條路徑上的信息素濃度CST=0.02*T(ak,0)‘定義螞蟻的差別感覺閾限‘螞蟻開始對N個樣本進行分類Forh=1toL ‘總共進行L次搜索Forak=1toM‘M只螞蟻分別聚類Clustering(ak)‘第ak只螞蟻根據(jù)(5)式對每個樣本進行聚類ClusterCenter(ak)‘計算第ak只螞蟻的K個聚類中心Distance(ak,h)’計算第ak只螞蟻的每個模式樣本到聚類中心距離以及第ak只螞蟻的目標函數(shù)Ifabs(T(ak,h)-T(ak,h-1))/T(ak,h-1)<ethenhaveResult=1‘存在滿足條件的結(jié)果ifT(ak,h)<MinTthenMinT=T(ak,h)‘尋找所有螞蟻中目標函數(shù)的最小值A(chǔ)ntNum=akEndifEndifNextInfomation(h)’第h次搜索完成后更新每只螞蟻在各條路徑上的信息素濃度IfhaveResult=1then‘表明螞蟻已經(jīng)搜索到了解Fori=1toN‘打印出每個樣本所屬的類別Forj=1toKIfS(AntNum,i,j)=1thenResponse.write“第”&i&“個樣本所屬類別為第”&j&“類；”&vbCRLFEndifNextnextExitfor‘算法結(jié)束EndifNext3.4小結(jié)本章總結(jié)了聚類技術(shù)在Web挖掘中的重要性，認真分析了聚類模型的幾種類型，并詳細地論述了基于蟻群算法的聚類模型設(shè)計。第四章蟻群算法在Web挖掘聚類上的實現(xiàn)第四章基于改進的蟻群算法在Web內(nèi)容挖掘聚類上的實現(xiàn)4.1基于改進的ACA的路由算法算法實現(xiàn)細節(jié)？改進原因與結(jié)果？算法實現(xiàn)細節(jié)？改進原因與結(jié)果？本算法的關(guān)鍵之處在于對蟻群算法中狀態(tài)轉(zhuǎn)移規(guī)則的啟發(fā)量的設(shè)置。在TSP問題中，啟發(fā)量的設(shè)置比較簡單，為距離的倒數(shù)，而在QoS路由選擇中，啟發(fā)量的設(shè)置就比較復(fù)雜，也比較重要，因為這直接決定了螞蟻尋路的規(guī)則。文中提出了一種新的啟發(fā)量的設(shè)置方法，即在n，b兩點之間的啟發(fā)量η(a，b)設(shè)置為|A*COST(a，b)+B*DEIAY(a，b)+B*NODEDELAY(b)+C*LOST(b)|的倒數(shù)，其中，COST(a,b)表示a和b兩點之間的費用，DELAY(a,b)表示a和b兩點之間的延時，NODEDELAY(b)表示b點的節(jié)點延時，LOST(b)表示節(jié)點b的分組丟失率。A，B，C均為常數(shù)，其賦值有兩個原則，一是調(diào)整各個約束條件之間的數(shù)量級，使其處于可比的狀態(tài)，二是可以適當加大需重點考慮的QoS值的系數(shù)，比如算法對延時比較敏感，則可加大B的賦值，使其比重加大，從上面的設(shè)置可以看出，當η(a，b)越大，則a和b兩點之間的費用、延時等就越小，符合QoS選路的原則。而在蟻群算法的信息素全局和局部更新規(guī)則中，△r均設(shè)為常數(shù)，經(jīng)過多次比較，在全局更新規(guī)則中，△r設(shè)為10，在局部更新規(guī)則中，△r設(shè)為1。蟻群算法中的β，p，q0等參數(shù)由免疫算法的抗體產(chǎn)生。4.2Web內(nèi)容挖掘聚類由于Web頁面中包含了很多文本、圖片、音頻、視頻等類型的信息。這些Web數(shù)據(jù)經(jīng)過數(shù)據(jù)清理、特征抽取等數(shù)據(jù)預(yù)處理后得到數(shù)據(jù)集，由于Web頁面中的內(nèi)容非常豐富，這樣增大了該算法的搜索空間，即系統(tǒng)接收的是一個特征向量矩陣，每一行代表的是一個樣本對象，根據(jù)上述得到的規(guī)則進行系統(tǒng)設(shè)計，這樣就可以大大提高算法的效率[36]。電子商務(wù)的快速增長已令商界和消費者雙方均面臨著新的形勢。由于激烈的競爭，客戶可以選擇從幾個備選方案挑選最合適的需求，同時商業(yè)社會也意識到需要具備聰明的營銷策略和關(guān)系管理。Web使用挖掘試圖發(fā)現(xiàn)有用的知識，并從次要數(shù)據(jù)中獲得用戶與Web的交互。Web使用挖掘已成為有效網(wǎng)站管理、創(chuàng)建自適應(yīng)網(wǎng)站、商業(yè)和服務(wù)支援，個性化，網(wǎng)絡(luò)交通流分析等等非常關(guān)鍵的功能。研究蟻群行為和他們的自組織能力能更系統(tǒng)地對感興趣的知識進行檢索/管理，因為它提供了模型分布式自適應(yīng)組織，這對困難的解決優(yōu)化、分類和分布控制等[17][18][16]起著非常重要的作用。本文中，我們提出的蟻群聚類算法來發(fā)現(xiàn)Web使用模式（數(shù)據(jù)集群）和一個線性基因編程方法來分析訪問者的瀏覽趨勢。實證結(jié)果清楚地表明，雖然對比改進的模糊聚類的[11]方法時，性能的精度并不高效，但是對比自組織地圖（為Web使用模式聚類），蟻群聚類的性能更優(yōu)。4.2.1數(shù)據(jù)清理由于Web數(shù)據(jù)具有異構(gòu)、動態(tài)等特性，海量的數(shù)據(jù)導(dǎo)致Web數(shù)據(jù)呈現(xiàn)雜亂、冗余等問題，這些有問題的數(shù)據(jù)時常會誤導(dǎo)聚類分析，給聚類結(jié)果帶來不利的影響，因此在進行挖掘之前必須對數(shù)據(jù)進行清理工作。舉例說明一下數(shù)據(jù)清理的過程，Web日志文件中歷史記錄如下：26—[06/Nov/2012:20:30:15+0800]”GET/2009/2009tdsh/home.htmHTTP/1.1”2002035從該條記錄可以看出，由IP為26的主機發(fā)出請求，且訪問Web的時間為2012年11月06日晚上8點30分15秒，+0800表示訪問的服務(wù)器位于第八區(qū)，訪問的方法為獲取”GET”，請求的內(nèi)容的是/2009/2009tdsh/home.htm，所用的協(xié)議為HTTP1.1，200表示請求成功，是服務(wù)器執(zhí)行該請求的結(jié)果標記代碼，2035表示瀏覽網(wǎng)頁請求的字節(jié)數(shù)大小。按照要求，進行數(shù)據(jù)清理的步驟如下：(1)首先對網(wǎng)頁的地址，如“GET/login?type=%id=%name=”的記錄進行刪除，因為這種記錄只應(yīng)用于頁面的刷新，對聚類沒有影響。(2)其次將頁面地址“GET/HTTP/1.1”的記錄刪除，因為這種記錄只是訪問頁面時使用的協(xié)議，對聚類沒有影響。(3)再將字節(jié)數(shù)為0的記錄刪除，因為這種記錄為用戶發(fā)起的請求且從頁面上未獲得任何信息，對聚類無影響。(4)再將網(wǎng)頁地址中后綴名為gif、jpg、mp3、mp4等的記錄刪除，因為這些圖形、音/視頻文件是用戶訪問頁面時自動下載的，不能反映用戶的興趣。根據(jù)以上步驟完成Web數(shù)據(jù)的清理后，接下去進行特征提取操作，從清理后的數(shù)據(jù)中提取出合適的特征向量，并對每一條記錄定義一個定量的描述，向Web挖掘聚類提供向量矩陣。4.2.2特征提取特征屬性的提取直接影響到用戶想通過聚類來獲取什么樣的信息，針對Web站點上用戶的訪問時間和瀏覽頁面記錄信息進行聚類，定義用戶的IP地址、訪問時間和訪問頁面URL三個屬性作為Web日志數(shù)據(jù)的特征屬性。特征屬性中用戶的IP、訪問時間以及頁面URL的表現(xiàn)形式為Web文本字符串，所以首先需要將其轉(zhuǎn)換為實數(shù)。然后當完成數(shù)據(jù)轉(zhuǎn)換并進行特征提取操作以后，抽象Web數(shù)據(jù)為一個數(shù)據(jù)矩陣，把這個數(shù)據(jù)矩陣作為源數(shù)據(jù)應(yīng)用于Web聚類系統(tǒng)。根據(jù)特征提取的思想獲得一些數(shù)據(jù)矩陣具有能使規(guī)則有效性得到最大提升，這樣的操作思想即為這個蟻群聚類算法得到的最優(yōu)規(guī)則?，F(xiàn)有的特征子集選取算法一般是構(gòu)造一個評價函數(shù)，對特征集中的每一個特征進行評估，然后根據(jù)其評估得分的大小對其進行排序，選取預(yù)定數(shù)目的最佳特征作為備用的特征子集。1、把文本表示成帶權(quán)重的信息的詞項向量，50年代就已經(jīng)提出了，這種思想正是向量空間模型的所在。2、在向量空間模型中，t1tn是N維的坐標系。w1(d)wn(d)為相應(yīng)的坐標值。因而文本d被看成N維空間中的一個規(guī)范化特征矢量，為了簡化可以不考慮tk在文本中的順序及相互關(guān)系。其中wk(d)為tk在文本D中的權(quán)重。計算方法為：TF乘以IDF，TermFrequency,InverseDocumentFrequency.1)詞頻：特征詞在文本中出現(xiàn)的頻率。2)倒排文檔頻率：特征詞在文本集中分布情況的量化。特征詞在文本集中出現(xiàn)的頻度。工式：lg(N/nk+0.01):其中N是文本總數(shù)，nk是出現(xiàn)該特征詞的文本數(shù)。3)歸一化因子：對文本向量的各個分量進行標準化，使得具有相同匹配特征數(shù)的文本，短文本比長的重要W(t,d)為詞t在文本d中的權(quán)重TF(t,d)為詞在文本d中的詞頻N為訓(xùn)練文本總數(shù)nk為訓(xùn)練文本集中出現(xiàn)t的文本數(shù)4)在計算權(quán)重前應(yīng)先去除停止詞。詞條與權(quán)重構(gòu)成特征向量。4.2.3相似度計算 會話是指用戶訪問web服務(wù)器的瀏覽行為，用會話相似度來衡量，亦即2次回話瀏覽行為的相似程度。如果2次會話瀏覽的網(wǎng)頁相同并且對多個網(wǎng)頁瀏覽的順序（瀏覽路徑）相同，那么這2次會話的瀏覽行為相同。任意兩次會話p和q的相似度的計算步驟為：（1）設(shè)網(wǎng)站上有效URL的總數(shù)為n，網(wǎng)站的每一URL指定一個唯一的數(shù)字j={1,2,3…,n}，用戶的任意一次網(wǎng)頁瀏覽行為用一個n維的布爾瀏覽向量T(p)表示，向量元素tj(p)定義為：（2）若已知會話p和會話q的網(wǎng)頁瀏覽向量分別為T(p)和T(q)，并完全忽略網(wǎng)站的分層組織，則兩次會話瀏覽網(wǎng)頁的相似度為：（3）若會話p和會話q的網(wǎng)頁瀏覽路徑分別是k，r個瀏覽頁排序而成，并分別用1,2,3….,k和1,2,3…,r進行編號，會話p和會話q的網(wǎng)頁瀏覽路徑差異用一個m維的布爾向量S(p,q)表示，取m=min{k,r}，且向量元素Sk(p,q)定義為：（4）會話p和會話q的瀏覽路徑相似度為：（5）會話p和會話q的瀏覽行為相似度為：相似度Comp(p,q)不僅衡量了任意2次會話p和會話q瀏覽多個網(wǎng)頁的相似程度而且衡量了會話p和會話q對這多個網(wǎng)頁的瀏覽順序的相似度，即衡量了這2次會話的瀏覽行為的相似程度。4.2.4瀏覽模式的挖掘方法我們把瀏覽行為比較類似的會話歸類為一種瀏覽模式。在對大量會話樣本的瀏覽行為計算彼此之間的相似度的基礎(chǔ)上，采用聚類分析方法進行歸類，從而挖掘出若干種瀏覽模式。我們采用基于密度聚類算法把瀏覽行為聚類，聚類算法的步驟為：計算會話p與會話q的距離函數(shù)D(p,q)：對會話樣本空間中的所有會話行為進行聚類，對樣本空間中的會話點p指定ε-鄰域為：該領(lǐng)域中的所有會話q的瀏覽行為被歸類為一種瀏覽模式p?？梢酝ㄟ^指定鄰域包含的會話點數(shù)|A,(q)|應(yīng)滿足最少點數(shù)MinPts來確定ε的值，即有，通過對會話樣本空間的聚類實驗，我們認為取MinPts=15或ε=0.55比較適宜。將鄰域A,(q)中的所有會話點從會話樣本空間中刪除。若樣本空間為空或者沒有任何點存在ε鄰域，則重復(fù)步驟（2）；否則，轉(zhuǎn)步驟（3）。會話樣本空間中還留下的會話點被確認為噪聲會話模式，即不屬于任何孤立的會話模式。4.3算法分析不要縮寫，文中提到的算法好幾個，在這里具體是哪個算法？不要縮寫，文中提到的算法好幾個，在這里具體是哪個算法？算法步驟如下：(1)隨機產(chǎn)生20條21位0l二進制編碼染色體作為初始抗體庫。(2)進行初始化，讀入網(wǎng)絡(luò)拓撲及QoS信息，產(chǎn)生包含20只螞蟻的蟻群。(3)從染色體庫中按順序取出一條染色體，產(chǎn)生相應(yīng)的螞蟻算法的參數(shù)，設(shè)置各邊信息量的初始值，采用蟻群算法開始尋找指定源節(jié)點和目的節(jié)點之間的最優(yōu)路由。當一只螞蟻成功地完成路由選擇后，判斷該路由是否滿足QoS約束條件，對這只螞蟻選擇的路由的各路徑上的信息素根據(jù)局部更新規(guī)則進行更新。(4)當20只螞蟻都完成尋徑后，對當前滿足Q。S約束的最優(yōu)路徑上的信息素按照全局信息素規(guī)則進行更新。如沒有，則說明沒找到滿足QoS的路由。(5)對該蟻群進行50次迭代尋徑，計算當前染色體的適應(yīng)度值。(6)對步驟(3)到(5)重復(fù)進行，直到2O條染色體全部使用過一遍。(7)對20條染色體的適應(yīng)度值進行排序、交叉、變異以及基于親和度的群體更新，產(chǎn)生新一代20條染色體，返回步驟(3)進行尋徑。循環(huán)若干次后算法結(jié)束。4.3.1算法實現(xiàn)根據(jù)改進后算法的原理，使用C++實現(xiàn)如下所示:double

rnd(intlow,doubleuper)

{

doublep=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);return(p);

};

intrnd(intuper)

{

return(rand()%uper);

};classGInfo

{

public:

doublem_dDeltTrial[iCityCount][iCityCount];

doublem_dTrial[iCityCount][iCityCount];

doubledistance[iCityCount][iCityCount];

};

intant::ChooseNextCity()

{

//Updatetheprobabilityofpathselection

//selectapathfromtabu[m_iCityCount-1]tonext

inti;

intj=10000;

doubletemp=0;

intcurCity=tabu[m_iCityCount-1];

for(i=0;i<iCityCount;i++)

{

if((AllowedCity[i]==1))

{

temp+=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);

}

}

doublesel=0;

for(i=0;i<iCityCount;i++)

{

if((AllowedCity[i]==1))

{

prob[i]=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)/temp;

sel+=prob[i];

}

else

prob[i]=0;

}if(j==10000)

{

temp=-1;

for(i=0;i<iCityCount;i++)

{

if((AllowedCity[i]==1))

if(temp<pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha))

{

temp=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);

j=i;

}

}

}

returnj;}

voidant::UpdateResult()

{

//Updatethelengthoftour

inti;

for(i=0;i<iCityCount-1;i++)

m_dLength+=Map.distance[tabu[i]][tabu[i+1]];

m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]];

}

voidant::move()

{

//theantmovetonexttownandaddtownIDtotabu.

intj;

j=ChooseNextCity();

addcity(j);

}

classproject

{

public:for(i=0;i<iAntCount;i++)

{

for(j=0;j<iCityCount-1;j++)

{

Map.m_dDeltTrial[ants[i].tabu[j]][ants[i].tabu[j+1]]+=Q/ants[i].m_dLength;

Map.m_dDeltTrial[ants[i].tabu[j+1]][ants[i].tabu[j]]+=Q/ants[i].m_dLength;

}

Map.m_dDeltTrial[ants[i].tabu[iCityCount-1]][ants[i].tabu[0]]+=Q/ants[i].m_dLength;

Map.m_dDeltTrial[ants[i].tabu[0]][ants[i].tabu[iCityCount-1]]+=Q/ants[i].m_dLength;

}

for(i=0;i<iCityCount;i++)

{

for(j=0;j<iCityCount;j++)

{

Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j]);

Map.m_dDeltTrial[i][j]=0;

}

}

voidproject::initmap()

{

inti;

intj;

for(i=0;i<iCityCount;i++)

for(j=0;j<iCityCount;j++)

{

Map.m_dTrial[i][j]=1;

Map.m_dDeltTrial[i][j]=0;

}

ifstreamin("eil51.tsp");

structcity

{

intnum;

intx;

int

y;

}cc[iCityCount];

for(inti=0;i<iCityCount;i++)

{

in>>cc[i].num>>cc[i].x>>cc[i].y;

besttour[i]=0;

}

intj;

for(i=0;i<iCityCount;i++)

for(j=0;j<iCityCount;j++)

{

{

Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2));

}

}4.3.2實驗環(huán)境軟件環(huán)境：Web挖掘聚類系統(tǒng)的開發(fā)環(huán)境：WindowsXP、C++編譯環(huán)境下完成。硬件環(huán)境：CPU：Intel酷睿雙核1.5GHz內(nèi)存：1GB硬盤：160GB顯卡：NVIDIAGeForce5600MGS4.3.3實驗結(jié)果最好有你的改進后算法和沒改進或者和其他算法的比較，目前比較對象過于單一，為什么選擇C5.0？這樣更有說服力最好有你的改進后算法和沒改進或者和其他算法的比較，目前比較對象過于單一，為什么選擇C5.0？這樣更有說服力仿真實驗的原始數(shù)據(jù)采用美國密歇根大學機器學習數(shù)據(jù)庫，選擇的是經(jīng)典聚類分析數(shù)據(jù)集，通過運行蟻群聚類算法，分析該算法在Web聚類上的結(jié)果，從中得到算法的性能參數(shù)，從而對該算法的性能和實用性進行分析，說明改進后的算法優(yōu)于先前算法。設(shè)定網(wǎng)站上有效URL的總數(shù)為7，網(wǎng)站的每一個URL指定一個唯一的數(shù)字{1,2,3,4,5,6,7}，其網(wǎng)頁組織結(jié)構(gòu)圖如圖所示。圖4.1流程圖現(xiàn)有三個用戶的一次網(wǎng)頁瀏覽行為的布爾瀏覽向量T(1)、T(2)和T(3)分別表示為（1,1,1,0,1,0,0）-1，（1,1,1,0,0,1,0）-1和（1,1,1,0,1,0,0）-1，則則類似可以得到D(1,2)、D(1,3)和D(2,3)均小于0.55，說明這三個用戶的訪問行為相似且可歸為同一個瀏覽模式。表4.1聚類系統(tǒng)實驗結(jié)果（聚類簇號）TestSetAccuracyRate(%)12345678910MeanRateSimplicityAnt_Miner376.270.272.479.268.577.279.873.771.473.874.24.8C5.074.670.173.669.672.377.276.477.670.472.673.313.1在這次仿真實驗中，結(jié)果證明了上述理論分析的正確性。通過大量反復(fù)的實驗比較，發(fā)現(xiàn)改進后的算法在迭代了15000次后，就已經(jīng)能達到或超越傳統(tǒng)的蟻群算法迭代1000000次的效果，傳統(tǒng)算法形成的聚類簇中，并不純正，在同一個聚類簇中含有不同分類的樣本對象。而改進的算法聚類簇比較純正，并采取了距離度量相結(jié)合的策略，提高了聚類的精度。從中可以看出，改進后的算法在大大減少迭代次數(shù)提高算法效率的同時，還在一定程度上改善了Web聚類挖掘效果。4.4小結(jié)本章主要介紹了基于蟻群算法的Web頁面分類模型[41]，并將其運用于Web內(nèi)容挖掘中。Ant_Miner3分類算法實質(zhì)上是一種序列覆蓋算法：蟻群搜索到一條規(guī)則，移去他覆蓋的樣例，再重復(fù)這一過程，從而得到共同覆蓋樣例的一組規(guī)則。由于Web文檔結(jié)構(gòu)的特殊性，在本實驗中，采用了文本預(yù)處理技術(shù)來對Web頁面進行消歧和抽取詞干。這樣，經(jīng)過處理后的文檔的屬性維度得到大大減小，算法的搜索空間也變的更小。經(jīng)采取10維的實驗交叉驗證，并采用標準的質(zhì)量評估預(yù)測分類規(guī)則質(zhì)量，并同傳統(tǒng)的分類算法C5.0就正確率和簡潔性進行了對比。結(jié)果顯示：在處理小數(shù)據(jù)量時，Ant_Miner3算法能夠發(fā)現(xiàn)更好的分類規(guī)則，以及得出更簡單的規(guī)則。第五章蟻群IACA算法在Web使用挖掘的聚類模型實現(xiàn)57第五章基于改進的蟻群算法在Web使用挖掘的聚類模型實現(xiàn)Web挖掘有其獨有的特性，比傳統(tǒng)的數(shù)據(jù)挖掘數(shù)據(jù)量大，數(shù)據(jù)結(jié)構(gòu)表現(xiàn)為無序、結(jié)構(gòu)復(fù)雜等特點。傳統(tǒng)的聚類算法要求用戶提供先驗信息（聚類類別或其他參數(shù)等），使得傳統(tǒng)聚類算法結(jié)果對輸入?yún)?shù)較為敏感，降低了算法的適用性。針對這一問題，引入一種新的解決方案，源于每個用戶在瀏覽Web時表現(xiàn)出來的特征不同。本文提出一種改進的蟻群聚類算法并應(yīng)用在Web使用挖掘的用戶聚類上，該蟻群聚類算法不需要用戶輸入先驗信息，改善了聚類結(jié)果并減輕了用戶負擔，實驗表明該算法在Web使用挖掘的聚類結(jié)果中更準確。5.1改進的蟻群算法(IACA)介紹由于傳統(tǒng)的蟻群聚類算法在實現(xiàn)時過度依賴輸入?yún)?shù)、搜索過程中停滯、以及算法的適用性不高等問題，本文引入一種改進的蟻群算法(ImprovedAntColonyAlgorithm,IACA)[42]，克服了傳統(tǒng)蟻群算法以上的缺點。它吸收了前人提出的具有感覺和知覺特性的蟻群算法[22]和具有隨機擾動的蟻群算法[19]的優(yōu)點，并結(jié)合了聚類分析的實際情況。其算法原理如下：(1)信息素更新：引入隨機擾動策略定義一個螞蟻種群M并讓M只螞蟻開始搜索，如果第m只螞蟻將第n個成員分類到第k類中，則在第m只螞蟻的第nk路徑上更新較大的信息素濃度，設(shè)置標志，其他螞蟻在nk路徑上的信息素濃度也受到第m只螞蟻的影響。由于螞蟻之間的相互影響，會產(chǎn)生一個影響程度，信息素濃度會隨著影響度的增加而增加。初始化每條路徑上的信息素濃度，每條路徑上的信息素濃度就會隨著螞蟻的不斷搜索而更新。當完成一次路徑搜索后，會對各螞蟻在其路徑上的信息素濃度進行更新，得到信息素增量公式為：(5.1)其中：Q表示正常數(shù)，=1時，表示第h次的時候，第k只螞蟻將第i個模式樣本分類到第j類，反之=0；(0<<1)表示其他螞蟻對螞蟻k的影響程度。表示第h次的時候，第k只螞蟻完成所有樣本分類以后，各樣本到各聚類中心的距離之和，由公式(3.2)計算。算法為了避免大量無效的搜索導(dǎo)致系統(tǒng)停滯的問題，提出隨機擾動策略，并引入可變的擾動因子，系統(tǒng)可跳出局部最優(yōu)。隨機擾動策略由公式(5.2)來表示，為了防止最優(yōu)的路徑被漏選。(5.2)其中，s表示對應(yīng)的城市，為擾動因子，P是(0,1)中均勻分布的隨機數(shù)。由公式得出：螞蟻在某次迭代過程中有多種選擇路徑，除了信息素濃度最大的那條路徑的選擇外，其他路徑都采用隨機選擇方式；而對信息素濃度最大的那條路徑選擇時，使用轉(zhuǎn)移的概率公式來選擇。該公式將螞蟻的隨機選擇和確定性選擇相結(jié)合，隨機選擇使計算轉(zhuǎn)移系數(shù)具有較強隨機性，確定性選擇使螞蟻得到轉(zhuǎn)移系數(shù)最大的路徑，結(jié)合二者的優(yōu)點，可使得IACA改進算法具有更好的全局搜素能力。 (2)螞蟻選擇路徑：引入螞蟻的自身感覺和知覺特性，螞蟻在選擇路徑的時候，需對三個閾值來進行比較，分別是：螞蟻的絕對感覺閾限AST、差別感覺閾限CST以及極限信息素濃度，將信息素濃度為分別與這三個閾值進行比較來確定路徑的選擇。由此得出則路徑選擇方式為：(5.3)5.2Web使用挖掘聚類模型用戶事務(wù)是指從Web用戶訪問訪問時留下的服務(wù)器日志、注冊信息以及沿某一方向的最大向前引用路徑中挖掘出的訪問模式。主要步驟如下：5.2.1Web事務(wù)識別定義首先我們采用基于支持度的濾波方法來實現(xiàn)，目的在于過濾掉不頻繁的用戶事務(wù)模式。在Web日志預(yù)處理階段，根據(jù)用戶的興趣度算法來計算每個用戶事務(wù)模式的支持度，設(shè)定一個門限值，提高了聚類結(jié)果的準確性。同時，改進了數(shù)據(jù)預(yù)處理過程，刪除了異常用戶訪問Web頁面的訪問記錄以及該用戶模式中包含的非頻繁用戶事務(wù)模式的URL。經(jīng)過用戶事務(wù)預(yù)處理，大量非頻繁的用戶事務(wù)模式被過濾掉且減少了用戶事務(wù)模式特征矢量的維數(shù)，減輕了數(shù)據(jù)挖掘的任務(wù)。用于聚類用戶事務(wù)集合，提高聚類結(jié)果的準確性。第二項預(yù)處理任務(wù)是Web事務(wù)識別。在對web訪問記錄進行挖掘之前，必須進行事務(wù)標識的工作。一次用戶會話(usersession)是指某個用戶對于一個web站點的一次訪問過程中所引用到的全部頁面，事務(wù)標識是將一次用戶會話分割成多個邏輯單元，事務(wù)和會話的區(qū)別在于事務(wù)的大小是可變的，從一個頁面到某個會話的全部頁面，決定于所定義的粒度;和通常的數(shù)據(jù)庫管理系統(tǒng)不同，這種粒度的定義是不明確的。5.2.2用戶瀏覽行為模型為了將用戶會話分解為有意義的事務(wù)，需要有一個潛在的模型支持它。用戶訪問訪問一個web頁面一般是出于如下兩種目的之一:一是為了導(dǎo)航目的，二是需要其內(nèi)容信息。我們分別稱之為相對于該用戶的導(dǎo)航頁面和內(nèi)容頁面。盡管通過web頁面中鏈接的數(shù)目或許可以容易地判定某些頁面的性質(zhì)，然而大多數(shù)頁面是無法通過該方法被清楚歸為某一類的。例如，一個僅包含了標題和一串鏈接列表的網(wǎng)頁可以認定是導(dǎo)航頁面，而一個既包含了文本信息又包含了鏈接的頁面則無法僅依據(jù)其自身信息就認定其是導(dǎo)航頁面還是內(nèi)容頁面，因為針對不同的用戶，它們的頁面性質(zhì)可能也隨之變化。根據(jù)導(dǎo)航頁面和內(nèi)容頁面的概念，我們可以給出事務(wù)的定義。事務(wù)的定義根據(jù)應(yīng)用的不同可分為兩種，通常對事務(wù)的定義是某個用戶在一個站點的一次訪問過程中，從一系列的導(dǎo)航頁面到內(nèi)容頁面的引用。對于此類導(dǎo)航一內(nèi)容事務(wù)的挖掘可以得到通向某個內(nèi)容頁面的常用路徑。另一個事務(wù)的定義是某個用戶在一個站點的一次訪問過程中，對所有內(nèi)容頁面的引用，即對一次用戶會話刪除了所有的導(dǎo)航頁面后產(chǎn)生的頁面序列;對于此類內(nèi)容事務(wù)的挖掘可以得到web站點上內(nèi)容頁面之間的聯(lián)系，這種聯(lián)系與這些內(nèi)容頁面之間的路徑信息無關(guān)。內(nèi)容事務(wù)的挖掘?qū)?yīng)于導(dǎo)航一內(nèi)容事務(wù)挖掘的事務(wù)間分析，但是因為它省略了導(dǎo)航信息，所以可以得到一些導(dǎo)航一內(nèi)容事務(wù)挖掘所得不到的用戶特性。無論何種事務(wù)定義，其關(guān)鍵問題在于如何才能夠動態(tài)確定一條服務(wù)器記錄是出于導(dǎo)航目的還是內(nèi)容瀏覽目的。5.2.3具體分析模型相似度將直接決定聚類的效果，因此在對用戶事務(wù)進行聚類之前，必須給出用戶事務(wù)相似性的定義。首先將用戶事務(wù)轉(zhuǎn)化成標稱數(shù)據(jù)。假設(shè)T為用戶事務(wù)模式集，m表示用戶事務(wù)模式數(shù)，每個用戶事務(wù)可表示成二進制向量的形式：，N是站點中有效的URL的總數(shù)，用戶的任意一次網(wǎng)頁瀏覽行為可用一個n維的布爾向量表示：(5.4)通過公式(5.4)將用戶事務(wù)數(shù)據(jù)轉(zhuǎn)化為標稱數(shù)據(jù)。假設(shè)某用戶事務(wù)訪問的頁面為A->B->D，網(wǎng)站的頁面向量為(A,B,C,D,E)，則可將用戶事務(wù)表示為(1,1,0,1,0)的標稱數(shù)據(jù)形式。由于每個用戶對Web站點都是通過其訪問興趣來訪問，因此形成了一種有序關(guān)系。當這兩個用戶事務(wù)對多個網(wǎng)頁瀏覽的順序相同、這幾個網(wǎng)頁的訪問類型相同，以及瀏覽網(wǎng)頁的數(shù)量相同。所以就瀏覽行為來看，兩個用戶事務(wù)行為相同，通過取二者的平均值來衡量這兩個用戶事務(wù)間的相似度。任意兩個用戶事務(wù)和的相似度計算步驟如下:(1)若已知用戶事務(wù)和的網(wǎng)頁瀏覽向量分別為和，用戶事務(wù)相似度計算采用公式(5.5)的余弦測度法來計算。(5.5)(2)若用戶事務(wù)和的網(wǎng)頁瀏覽路徑分別是由p、q個頁面排序而成，并分別用1,2,3,…,p和1,2,3,…,q進行編號，用戶事務(wù)和的網(wǎng)頁瀏覽路徑差異用一個m維的布爾向量表示，取，向量元素定義為：(5.6)其中k=1,2,3,…,m(3)計算用戶事務(wù)和的瀏覽路徑相似度：(5.7)(4)計算用戶事務(wù)和的瀏覽行為相似度：(5.8)相似度不僅衡量了任意兩個用戶事務(wù)和瀏覽多個網(wǎng)頁的相似程度，而且衡量了用戶事務(wù)和對這多個網(wǎng)頁的瀏覽順序的相似度，即衡量了這兩個用戶事務(wù)的瀏覽行為的相似度。為了提高該聚類算法的運算速度，在進行聚類之前，可首先計算所有用戶事務(wù)間的相似度，并把它們存儲在事務(wù)相似度矩陣R中,見公式(5.9)。(5.9)其中m表示用戶事務(wù)的個數(shù)，表示事務(wù)和的相似度。由于事務(wù)間的相似關(guān)系具有對稱和自反的性質(zhì)，因此有=，且。5.3算法分析5.3.1流程分析本文的算法原理是指在總結(jié)了蟻群算法和K-均值算法在實現(xiàn)優(yōu)化排列問題和聚類分析問題的基礎(chǔ)上，引入隨機擾動策略和螞蟻仿生學特性，從而提出的改進蟻群算法(IACA)，用于實現(xiàn)Web使用挖掘上用戶事務(wù)的聚類，并將該模型用算法來實現(xiàn)，具體流程如下：具體算法流程為：(1)給定一個精度以及總的搜索次數(shù)L。初始狀態(tài)，讓螞蟻種群中M只螞蟻的每一只都將N個模式樣本隨機分配各自的K個模式分類，根據(jù)分配結(jié)果并引入K均值算法[33]，計算螞蟻各自的初始聚類中心，然后根據(jù)公式(3.2)計算每個螞蟻的初始目標函數(shù)。并根據(jù)各自的隨機分配結(jié)果初始化各螞蟻的樣本到各聚類中心的信息素濃度，其中Q為一正常數(shù)，表示第k只螞蟻將第i個員工分類到第j類，否則。各個螞蟻的絕對感覺閾限，其中C為常數(shù)，根據(jù)前面的闡述，這里我們?nèi)＝5（表明感覺閾限是初始信息素濃度的5倍），差別感覺閾限。(2)螞蟻群中M只螞蟻分別對N個樣本進行K個模式分類，每只螞蟻的每次分配均按公式(5.3)將第i個樣本分配到第j類，待所有的樣本都已經(jīng)分配完成之后，下一只螞蟻按照同樣的方式對樣本進行分類。當所有的螞蟻都已經(jīng)分配完成后，則表明一個搜索周期完成。(3)一個搜索周期完成后，按公式(3.3)更新信息素濃度，并引入隨機擾動公式(5.2)調(diào)整的信息素濃度。(4)根據(jù)公式(3.2)計算每只螞蟻各自的目標函數(shù)更新并調(diào)整信息素,根據(jù)K均值算法計算出新的聚類中心，同時將已搜索次數(shù)h加1(h=h+1)。若在M只螞蟻中滿足，則選擇min()即最小的值并輸出分類結(jié)果，否則將搜索次數(shù)h與固定閾值L比較,如果已搜索次數(shù)h>=L，則輸出結(jié)果；如果已搜索次數(shù)h<L，則在步驟(4)聚類的基礎(chǔ)上轉(zhuǎn)步驟(2)繼續(xù)搜索更優(yōu)的解。5.3.2算法實現(xiàn)同第四章問題同第四章問題根據(jù)上述描述改進算法的原理，采用Matlab語言實現(xiàn)，算法的偽代碼如下：以下是具體代碼實現(xiàn)算法/*初始化樣本*/For樣本集中的每一個樣本對象alphado隨機將tao投影到二維網(wǎng)格空間中EndFor/*主循環(huán)迭代*/function[y,val]=QACSticloadatt48att48;最大循環(huán)次數(shù)MAXIT=300;城市個數(shù)NC=50;產(chǎn)生一個0到1之間的隨機數(shù)taotao=ones(50,50);rho=0.3;alpha=2;beta=3;IfPm>Prdo Ai隨機移動區(qū)域中沒有被樣本對象占用的網(wǎng)格EndIfQ=200;mant=30;iter=1;fori=1:NCforj=1:NCdistance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2);endendIf循環(huán)次數(shù)是50的倍數(shù)do計算第一種行為螞蟻的占所有螞蟻的比重bestroutebestroute=zeros(1,50);routelength=inf;EndIfforite=1:MAXITforka=1:mantdeltatao=zeros(50,50);[routek,lengthk]=travel(distance,tao,alpha,beta);iflengthk<routelengthbestroute=routek;endfori=1:NC-1deltatao(routek(i),routek(i+1))=deltatao(routek(i),routek(i+1))+Q/lengthk;enddeltatao(routek(50),1)=deltatao(routek(50),1)+Q/lengthk;endfori=1:NC-1 迭代次數(shù)i+1forj=i+1:NCifdeltatao(i,j)==0deltatao(i,j)=deltatao(j,i);endendendtao=(1-rho).*tao+deltatao;endy=bestroute;val=routelength;toc/*主循環(huán)迭代*/For所有的樣本對象doEndFor/*算法結(jié)束*/5.3.3實驗結(jié)果數(shù)據(jù)預(yù)處理：提取了新浪網(wǎng)的Web服務(wù)器站點的日志數(shù)據(jù)作為實驗數(shù)據(jù),在這些實驗數(shù)據(jù)中包含了2,713,124條數(shù)據(jù)記錄。進行數(shù)據(jù)清理后,還有141,361條數(shù)據(jù),其中包含985個不同的網(wǎng)頁。分別得出了23,685個用戶、35,452個會話、56,231個用戶事務(wù)。測試環(huán)境:Matlab實現(xiàn)算法。實驗條件為AMDAthlon(tm)x2250uProcessor，2G內(nèi)存，操作系統(tǒng)為Windows7。500個用戶事務(wù),200個URL，抽取其中30個用戶事務(wù)用來測試，見表5.1表5.1用戶事務(wù)表編號用戶事務(wù)編號用戶事務(wù)1p16,p20,p21,p25,p2316p23,p20,p16,p21,p372p28,p19,p2217p17,p48,p39,p593p19,p22,p2818p16,p20,p21,p23,p254p17,p48,p8019p45,p17,p395p17,p39,p5920p17,p39,p456p35,p36,p3721p36,p35,p347p15,p19,p20,p2222p35,p36,p378p16,p40,p5123p16,p38,p58,p789p41,p53,p1724p35,p37,p36,p17210p36,p34,p3525p29,p127,p9111p24,p45,p29,p7226p17,p48,p39,p4512p53,p17,p4127p48,p95,p13313p98,p128,p2928P20,p54,p56,p6514p19,p64,p5529p72,p45,p29,p6315p45,p29,p7230p54,p56,p65經(jīng)過改進算法聚類的結(jié)果為：{7,22,11,20,24}、{21,17,19,26,6}、{2,6,18,8,23}、{3,9,10,13}、{4,14,25}、{12,28,31}、{14,29,27}、{30}，聚類結(jié)果正確。在實驗過程中，同時對以下算法也進行了50次聚類實驗，并對聚類的結(jié)果進行比較，得出的實驗結(jié)果如下：表5.2算法對比表算法K-均值算法FCM基本蟻群算法IACA算法正確率85.4%87.6689.9%93.8%計算時間322s309s280s259s由表5.2可得出：IACA算法在Web的用戶聚類效果上，較其它算法，在正確率以及時間上都具有一定的優(yōu)勢。5.4小結(jié)傳統(tǒng)的聚類算法對于初始值的設(shè)定很敏感，初始值的設(shè)定直接影響最終結(jié)果，也導(dǎo)致了聚類結(jié)果會存在較大的差異，但是蟻群算法的聚類結(jié)果并不依賴于初始值的設(shè)定。從實驗結(jié)果可以看出，改進的IACA算法應(yīng)用在Web使用挖掘的用戶事務(wù)聚類上，聚類正確率以及算法消耗時間都有著明顯的優(yōu)勢，會比K-均值算法、FCM算法等性能更好，速度更快。第六章總結(jié)與展望第六章總結(jié)與展望6.1總結(jié)Web挖掘中的聚類是Web挖掘技術(shù)中最重要的部分，本文主要是在Web挖掘中的聚類分析方面進行的研究工作，從復(fù)雜模式中獲取知識并改善頁面間的關(guān)系，研究重點對現(xiàn)有的蟻群算法進行改進，是算法能具有更好的適用性。本文的主要工作及創(chuàng)新點：1.引入一種改進的蟻群算法(IACA),并將其引入到Web使用挖掘領(lǐng)域，應(yīng)用該算法進行Web用戶事務(wù)聚類，給出其聚類模型，并對算法進行仿真實驗。實驗表明，改進的算法在聚類的正確性和性能上都較其他的算法有著更好的