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