【文章內(nèi)容簡介】 于無法識別同一用戶的重復(fù)訪問，所以均將其作為不同的用戶來對待。另外為了實現(xiàn)上的簡易性，本文只是根據(jù)IP地址的不同來劃分不同的用戶。4 基于K均值算法的Web事務(wù)聚類分析數(shù)據(jù)挖掘領(lǐng)域中存在著多種聚類分析算法[12]。目前主要的聚類算法可以劃分為：劃分方法[7]、層次方法、基于密度的方法、基于網(wǎng)格的方法，和基于模型的方法。在眾多的算法當(dāng)中，屬于劃分方法的K均值算法是最為經(jīng)典，也是使用最廣泛的聚類分析算法之一。 K均值算法K均值算法（又稱K中心或C均值算法）接收一個輸入?yún)?shù)和個數(shù)據(jù)對象，并將這個數(shù)據(jù)對象劃分為個簇，使得簇內(nèi)數(shù)據(jù)對象的相似度盡可能高，而簇間數(shù)據(jù)對象的相似度盡可能低。簇和簇之間的相似度取決于簇的中心，即簇內(nèi)所有數(shù)據(jù)對象的均值[10][15]。K均值算法的工作流程如下：首先，在數(shù)據(jù)集中隨機地選擇個數(shù)據(jù)對象，由這個數(shù)據(jù)對象代表個簇的初始中心（或均值）。然后，根據(jù)數(shù)據(jù)對象到個簇中心的距離，將所有的數(shù)據(jù)對象分別分配至最近的簇中。此時重新計算個簇的均值。該過程不斷地迭代，直至某個指標(biāo)函數(shù)收斂為止。一般可以使用平方差指標(biāo)函數(shù)，即 ， （）其中是數(shù)據(jù)集中所有數(shù)據(jù)對象的平方差的和；是給定數(shù)據(jù)對象在空間中所對應(yīng)的點；是簇的均值（和均是多維的）。也就是說，對每個數(shù)據(jù)對象到其所屬簇中心的距離的平方求和。該指標(biāo)函數(shù)的收斂使得簇的內(nèi)部盡可能緊湊，而簇和簇之間盡可能相互隔離。 事務(wù)間的距離設(shè)每個數(shù)據(jù)對象都有個屬性，那么就可以用維空間中的一個點來代表一個數(shù)據(jù)對象，其中是數(shù)據(jù)對象的第個屬性值。兩個數(shù)據(jù)對象之間的距離則為這兩個點在維空間中的歐氏距離。即設(shè)兩個數(shù)據(jù)對象為和，則有 （）在Web事務(wù)聚類分析中，一個事務(wù)則是一個數(shù)據(jù)對象。數(shù)據(jù)對象的維數(shù)即是網(wǎng)站中URL地址的個數(shù)，對象在第維的值則是該事務(wù)訪問第個URL地址的次數(shù)。例如，假設(shè)網(wǎng)站共有4個URL地址A、B、C、D，分別對應(yīng)4維空間中的4維，那么事務(wù)所對應(yīng)的4維空間的點則為（3，1，0，1），事務(wù)所對應(yīng)的點為（1，1，1，0）。因此，事務(wù)和事務(wù)之間的距離為。5 基于蟻群算法的Web事務(wù)聚類分析近年來，一些學(xué)者開始運用群體智能(Swarm Intelligence)的思想來研究聚類問題。如蟻群、魚群、蜂群等，在沒有任何先驗知識的分布環(huán)境下，它們具有自組織、合作、通訊等特點。Denubourg等首次模擬幼蟻自動分類及蟻尸聚積現(xiàn)象，提出了聚類基本模型（Basic Model，BM）[16]。蟻群聚類算法不需要事先知道數(shù)據(jù)分區(qū)或簇的數(shù)目等先驗知識，并且螞蟻的隨機行為可以適應(yīng)各種變化的數(shù)據(jù)集而無需訓(xùn)練，得到的結(jié)果比K均值等需要先驗知識的聚類算法更為準(zhǔn)確合理。本文采用了[4]中的人工螞蟻聚類算法，并加以改進，對預(yù)處理后的Web日志數(shù)據(jù)進行聚類，得到了質(zhì)量良好的聚類結(jié)果。 蟻群算法對聚群而居的社會性昆蟲——如螞蟻和蜜蜂來說，單個的個體只能完成極其簡單的任務(wù)，但由這些簡單的個體所構(gòu)成的整個群體，卻表現(xiàn)出高度結(jié)構(gòu)化的社會組織，在很多情況下能夠完成遠遠超過單個個體能力的復(fù)雜任務(wù)。比如覓食行為則是蟻群一個重要而有趣的行為。在從食物源到蟻穴并返回的過程中，螞蟻能在其走過的路徑上分泌一種化學(xué)物質(zhì)Pheromone——信息素，并以此指導(dǎo)自己的運動方向，使螞蟻傾向于朝著該物質(zhì)強度高的方向移動，信息素的強度會隨著時間而減弱。受到自然界中真實蟻群集體行為的啟發(fā)，(Ant Colony Optimization，ACO)，并用該方法解決了一系列組合優(yōu)化問題。蟻群算法是一種新近發(fā)展的稱為群體智能(Swarm Intelligence)的人工智能的分支。群體智能的特點是最小智能但自治的個體，利用個體與個體，以及個體與環(huán)境的交互作用，實現(xiàn)完全分布式控制，并具有自組織、可擴展性、健壯性等特性。而將蟻群算法用于聚類分析的靈感，則是源于螞蟻堆積它們的尸體和分類它們的幼體。生物學(xué)家通過長期觀察發(fā)現(xiàn)，螞蟻通常構(gòu)筑一個固定場所的墓地，盡管螞蟻并不知道關(guān)于蟻群整體的任何指導(dǎo)性信息，但它可將死去的同伴安放在一個固定的區(qū)域，將分散在蟻穴內(nèi)各處的螞蟻尸體堆積起來。另外，觀察還發(fā)現(xiàn)，蟻群在安排不同蟻卵的位置時，會按照蟻卵大小不同而將其堆放在蟻穴周圍和中央的位置。受到蟻群聚類行為的啟發(fā)，Deneubourg J L提出了一種解釋蟻群聚類現(xiàn)象的基本模型[5]。隨著蟻群算法領(lǐng)域的研究進展，人們又提出了許多模仿蟻群聚類行為的聚類分析算法[16]。螞蟻算法在各個領(lǐng)域獲得的成效得到了越來越多研究者的關(guān)注。目前人們對蟻群算法的研究已經(jīng)由當(dāng)初單一的TSP領(lǐng)域滲透到了多個應(yīng)用領(lǐng)域，這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的勃勃生機，并已經(jīng)成為一種完全可與遺傳算法相媲美的仿生優(yōu)化算法。 事務(wù)間的相似度在討論事務(wù)之間的相似度之前，這里先給出子序列的定義。一個給定序列的子序列就是該給定序列中去掉零個或者多個元素所構(gòu)成的另一個序列。以形式化的方式來說，給定一個序列，另一個序列是的子序列，如果存在的一個嚴格遞增下標(biāo)序列，使得對所有的，有。例如，是的子序列，相應(yīng)的下標(biāo)序列為 [17][19]。設(shè)已識別出的兩個事務(wù)為 其中表示事務(wù)中所訪問的第個頁面，表示事務(wù)中所訪問的第個頁面，且。又設(shè)序列是序列中滿足如下的性質(zhì)的最長的子序列——即對來說，使得，其中。同理設(shè)是序列中滿足該性質(zhì)的最長的子序列——即對來說，使得，其中。由此可設(shè)事務(wù)與間的相似度函數(shù)為 （）例如，若，則有。相似度函數(shù)具有以下的性質(zhì)：（1）。（2）。（3）如果事務(wù)和事務(wù)中所訪問的頁面完全不一樣，則；若事務(wù)和事務(wù)都在訪問一樣的頁面，則。證明略。 基于人工螞蟻模型的聚類分析算法：圖 5. 1 基于人工螞蟻模型的聚類分析算法偽代碼下面給出算法各個部分的Java代碼實現(xiàn)。 人工螞蟻和巢，一只人工螞蟻代表一個事務(wù)，且由基因、標(biāo)簽和模板組成。因此可以構(gòu)造一個螞蟻類：class Ant { int id。 // 基因，即螞蟻標(biāo)識 int label = 0。 // 標(biāo)簽，代表螞蟻所屬的巢，初始值為0 double template。 // 模板，其值在0到1之間 int[] urlIdArray。 // 螞蟻對應(yīng)事務(wù)所訪問的URL序列}由于下面的實現(xiàn)會將所有的螞蟻存儲在數(shù)組中，因此Ant類的id域是可選的，下文將用數(shù)組索引來標(biāo)識螞蟻。一個蟻巢即是一個簇，其由蟻巢標(biāo)識和蟻巢大?。聪伋仓形浵伒臄?shù)目）組成：class Cluster { int id。 // 蟻巢標(biāo)識 int size。 // 蟻巢大小}這里Cluster類的id域是必須的，因為隨著螞蟻之間的不斷相遇，會有大量的新簇產(chǎn)生和舊簇消失，這樣所有的Cluster對象就必須存儲在動態(tài)的鏈表中，而不能存儲在靜態(tài)數(shù)組中。 相似度函數(shù)相似度函數(shù)以兩個螞蟻對象作為輸入，計算出這兩只螞蟻所對應(yīng)的事務(wù)之間的相似度：double similarity(Ant ant1, Ant ant2) { double percentage1 = 0。 for (int i = 0。 i 。 i++) { for (int j = 0。 j 。 j++) { if ([i] == [j]) { percentage1++。 break。 } } } percentage1 /= 。 double percentage2 = 0。 for (int i = 0。 i 。 i++) { for (int j = 0。 j 。 j++) { if ([i] == [j]) { percentage2++。 break。 } } } percentage2 /= 。 return percentage1 * percentage2。}6 試驗與分析本文采用北京電子科技學(xué)院Web服務(wù)器（）2007年10月14日至2007年10月21日一周的日志文件作為數(shù)據(jù)集。原始日志文件大小為99MB，包含了440600條記錄；經(jīng)過數(shù)據(jù)清洗后，剩余19812條記錄，從中識別出1635個會話。 基于蟻群算法的聚類分析結(jié)果由于本文目前沒有對于北京電子科技學(xué)院網(wǎng)站中事務(wù)群的先驗知識，因此先采用蟻群算法對經(jīng)過預(yù)處理的日志文件進行聚類分析。經(jīng)過基于蟻群算法的聚類分析后，從中發(fā)現(xiàn)了8個簇，789個孤立點。：簇2 包含272個會話訪問的主題 總訪問次數(shù)學(xué)院信息 (sid=2) 272簇1 包含193個會話訪問的主題 總訪問次數(shù)學(xué)院概況 (sid=3) 340招生就業(yè) (sid=7) 292學(xué)院信息 (sid=2) 209學(xué)生天地 (sid=9) 171研究生工作處 (sid=327) 110系部設(shè)置 (sid=158) 95人才培養(yǎng) (sid=5) 72機構(gòu)總覽 (sid=4) 39招生信息網(wǎng) (sid=265) 18專題 (sid=170) 17后勤服務(wù) (sid=14) 10重要文件 (sid=135) 7校友園地 (sid=273) 7專題 (sid=393) 6科學(xué)研究 (sid=12) 5教學(xué)與研究 (sid=284) 1簇3 包含110個會話訪問的主題 總訪問次數(shù)招生就業(yè) (sid=7) 110簇4 包含101個會話訪問的主題 總訪問次數(shù)學(xué)院概況 (sid=3) 101簇6 包含46個會話訪問的主題 總訪問次數(shù)系部設(shè)置 (sid=158) 46簇7 包含45個會話訪問的主題 總訪問次數(shù)研究生工作處 (sid=327) 45簇5 包含42個會話訪問的主題 總訪問次數(shù)學(xué)生天地 (sid=9) 126學(xué)院信息 (sid=2) 99招生就業(yè) (sid=7) 12專題 (sid=393) 10校友園地 (sid=273) 9網(wǎng)絡(luò)服務(wù) (sid=11) 6人才培養(yǎng) (sid=5) 4師德建設(shè) (sid=311) 4招生信息網(wǎng) (sid=265) 4學(xué)院概況 (sid=3) 4研究生工作處 (sid=327) 4科學(xué)研究 (sid=12) 2后勤服務(wù) (sid=14) 2簇8 包含37個會話訪問的