基于關(guān)聯(lián)規(guī)則的網(wǎng)絡(luò)行為分析

劉宗成,張忠林,田苗鳳

(蘭州交通大學(xué) 電子與信息工程學(xué)院,甘肅 蘭州730070)

摘要網(wǎng)絡(luò)用戶訪問網(wǎng)站的過程中,產(chǎn)生了大量的用戶瀏覽網(wǎng)頁的相關(guān)記錄,隱含著用戶在上網(wǎng)過程中的行為習(xí)慣。但其中潛在的用戶信息難以發(fā)現(xiàn)。因此,急需有效的方法提取這些數(shù)據(jù)中的信息,數(shù)據(jù)挖掘應(yīng)用而生。其中,關(guān)聯(lián)規(guī)則技術(shù)是應(yīng)用廣泛的技術(shù)之一。文中利用Apriori算法對Web結(jié)構(gòu)數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘,所得到的規(guī)則反映出頁面之間的鏈接關(guān)系。分析挖掘結(jié)果可得到用戶訪問的行為規(guī)律,為相關(guān)網(wǎng)站的安全性和優(yōu)化改進提供有效的決策依據(jù)。

關(guān)鍵詞Apriori算法;網(wǎng)絡(luò)日志挖掘;關(guān)聯(lián)規(guī)則;行為分析

收稿日期:2015-03-09

基金項目:甘肅省科技支撐計劃基金資助項目(1104GKCA016)

作者簡介:劉宗成(1988—),男,碩士研究生。研究方向:數(shù)據(jù)挖掘。E-mail:liuzongcheng1234@163.com

doi:10.16180/j.cnki.issn1007-7820.2015.09.004

中圖分類號TP301.6

Analysis of Network Behaviors Based on Association Rules

LIU Zongcheng,ZHANG Zhonglin,TIAN Miaofeng

(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

AbstractThe large number of web browsing records contains the implicit behaviors of users on the Internet,which however is difficult to find.Therefore,effective methods for extracting the information from the data,or the data mining applications are in urgent need.Among them,the association rules technology is one of the widely used.This paper adopts the Apriori algorithm to analyze the Web structure data mining for association rules,and the resulting rules reflect the page link between the relationships.Analysis of the results reveals the pattern of user access behaviors,providing an effective decision-making basis for the security and improvement of websites.

KeywordsApriori algorithm;web log mining;association rules;behavior analysis

隨著網(wǎng)絡(luò)信息爆炸式的增長給人們帶來了諸多不便。全球每天約有數(shù)以百萬計的網(wǎng)頁誕生,有數(shù)億人次通過瀏覽器訪問各種網(wǎng)站、進行在線交易等活動,由此產(chǎn)生數(shù)以億計的數(shù)據(jù)[1]。但這些數(shù)據(jù)長期以來無法得到充分利用。因此,人們迫切需要一種有效的方法能從海量的網(wǎng)絡(luò)資源中獲取可用的信息或知識,因此,數(shù)據(jù)挖掘[2]應(yīng)運而生。具體而言,數(shù)據(jù)挖掘是通過一定的技術(shù),從海量的網(wǎng)絡(luò)數(shù)據(jù)中分析獲得有趣規(guī)則,發(fā)現(xiàn)隱含的有用知識的過程,是網(wǎng)絡(luò)信息中知識發(fā)現(xiàn)的重要方法。目前,網(wǎng)絡(luò)數(shù)據(jù)挖掘主要分為內(nèi)容挖掘、結(jié)構(gòu)挖掘和使用挖掘[3]。其沿用了Robot、全文檢索等網(wǎng)絡(luò)信息檢索中的優(yōu)秀成果,同時綜合運用了人工智能、模式識別、神經(jīng)網(wǎng)絡(luò)領(lǐng)域的各種技術(shù)[4]進行信息處理。為確保網(wǎng)絡(luò)信息的安全,現(xiàn)有的技術(shù),如防火墻、入侵檢測、身份認證等[5],是不能完全保證的。其主要原因是這些技術(shù)均側(cè)重于對已發(fā)生的攻擊行為做出響應(yīng),徹底解決這一問題的根本策略應(yīng)當(dāng)從網(wǎng)絡(luò)行為安全分析入手。

1網(wǎng)絡(luò)行為及其安全性

通過對用戶在上網(wǎng)過程中的一系列連續(xù)行為的處理,分析得出用戶網(wǎng)絡(luò)行為特征信息,可作為決策的一種數(shù)據(jù)支持。面對網(wǎng)絡(luò)安全問題日益嚴重的現(xiàn)實,國內(nèi)外眾多專家和學(xué)者堅持不懈,積極研究如何提高網(wǎng)絡(luò)安全性。一般,網(wǎng)絡(luò)入侵檢測[6]包括誤用檢測和異常檢測,誤用檢測主要是依據(jù)模式匹配原理來進行檢測的,正確率相對較高,但僅能檢測已知入侵類型進行。異常檢測主要依據(jù)特征比對原理進行檢測,其能檢測出未知的入侵類型,但誤檢率較高[7]。圖1是常用的網(wǎng)絡(luò)檢測模式。

圖1　常用的網(wǎng)絡(luò)檢測模式

后來出現(xiàn)的聚類分析、隱馬爾可夫、模式匹配等檢測方法,均是基于統(tǒng)計學(xué)或?qū)＜蚁到y(tǒng)的檢測,要求有較多的經(jīng)驗數(shù)據(jù),準確率有時偏低[8-10]。

網(wǎng)絡(luò)行為分析[11]也是一個數(shù)據(jù)挖掘的過程,是對網(wǎng)絡(luò)行為異常的分析,但側(cè)重點在于網(wǎng)絡(luò)用戶特征分析。網(wǎng)絡(luò)行為分析盡可能將網(wǎng)絡(luò)中不同節(jié)點存儲的數(shù)據(jù)盡量融合起來進行綜合分析,以便觀察和發(fā)現(xiàn)網(wǎng)絡(luò)內(nèi)部的具體情況,主要目的在于挖掘網(wǎng)絡(luò)中潛在的關(guān)鍵性的能夠反映網(wǎng)絡(luò)行為的信息,文獻[12～13]分別從網(wǎng)絡(luò)訪問控制和網(wǎng)絡(luò)行為模擬方面對網(wǎng)絡(luò)行為分析進行了探討。

2網(wǎng)絡(luò)日志挖掘過程

由于互聯(lián)網(wǎng)用戶的持續(xù)激增,Web服務(wù)器中的日志數(shù)據(jù)也隨之呈指數(shù)性增長。這些Web日志數(shù)據(jù)當(dāng)中隱含著非常重要的數(shù)據(jù)資源之間的關(guān)聯(lián)信息。Web日志的挖掘過程,一般分為4個階段:原始數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘及對挖掘出的結(jié)果進行評估分析[1]。

原始數(shù)據(jù)的采集指對記錄的用戶訪問信息數(shù)據(jù)有針對性地進行收集,即收集存儲于服務(wù)器上的Web日志內(nèi)容中所需的數(shù)據(jù)項。

數(shù)據(jù)預(yù)處理是一個復(fù)雜的過程,包括數(shù)據(jù)清理、轉(zhuǎn)換和規(guī)約等一系列過程,是進行挖掘的基礎(chǔ)。

數(shù)據(jù)挖掘是在上述過程處理結(jié)果的基礎(chǔ)上進行的,應(yīng)用挖掘技術(shù),例如關(guān)聯(lián)規(guī)則技術(shù),找出潛在的規(guī)則,模式等。

結(jié)果評估分析指根據(jù)實際對挖掘結(jié)果進行分析、解釋,并利用它們做出決策,指導(dǎo)實踐。

3關(guān)聯(lián)規(guī)則算法

關(guān)聯(lián)規(guī)則[14]算法是數(shù)據(jù)挖掘中的重要算法之一。數(shù)據(jù)挖掘是一種從海量數(shù)據(jù)中挖掘潛在知識的方法,關(guān)聯(lián)規(guī)則描述了同一事物中不同屬性之間的關(guān)聯(lián)關(guān)系和依賴關(guān)系。關(guān)聯(lián)規(guī)則挖掘步驟可分為兩個子步驟:找出所有頻繁項集、由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則。其中,找出所有頻繁項集的效率對關(guān)聯(lián)規(guī)則挖掘的整體效率起到關(guān)鍵作用。Apriori算法是一種成熟的,經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法,其采用迭代法挖掘頻繁項集,過程主要分為兩步:連接步和剪枝步[15]。

Apriori算法描述如下:

假設(shè)D為事務(wù)數(shù)據(jù)庫,Ck為候選項集,Lk為頻繁項集,min_support為設(shè)定的最小支持度。

算法:Apriori。

輸入:D;min_support。

輸出:Lk。

(1)L1=find_frequent_1_itemsets(D);

(2)for (k=2;Lk-1≠Φ;k++) {

(3)Ck=apriori_gen(Lk-1,min_support);//由頻繁k-1項集生成候選k項集

(4)for each transactiont∈D

(5)Ct=subset(Ck,t);//構(gòu)造t的候選子集

(6)for each candidatec∈Ct

(7)c.count++;

(8)}

(10)}

(11)returnL=∪kLk;

其中,函數(shù)apriori_gen(k-1)利用頻繁k-項集生成候選項集,算法描述如下:

1)for each itemsetl1∈Lk-1

2)for each itemsetl2∈Lk-1

3)ifl1[1]=l2[1]∩l1[2]=l2[2]∩…∩l1[k-1]=l2[k-1]

then {

4)c=l1×l2;//連接

5)if has_infrequent_subset(c,Lk-1) then

6)deletec;//剪枝

7)else addctoCk;

8)}

9)returnCk;

函數(shù)has_infrequent_subset()實現(xiàn)了候選k-項集的剪枝,即刪除k-項集中非頻繁項(k-1)-項子集。其算法描述如下:

(1)for eachk-1 subsetsofc

(2)if nots∈Lk-1then

(3)return TRUE;

(4)return FALSE;

關(guān)聯(lián)規(guī)則算法是從事務(wù)數(shù)據(jù)庫中存儲的大量數(shù)據(jù)集合之間發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系,用于幫助人們進行各種決策。文獻[16]中介紹了不同的數(shù)據(jù)挖掘方法在網(wǎng)絡(luò)安全中的應(yīng)用,文獻[17]利用數(shù)學(xué)模糊邏輯與關(guān)聯(lián)規(guī)則相結(jié)合的方法檢測異常。

4實例

在網(wǎng)絡(luò)行為分析中,Web日志是重要的數(shù)據(jù)來源之一。因此,本文以某Web日志文件記錄作為數(shù)據(jù)源,數(shù)據(jù)處理之后,運用Apriori算法進行關(guān)聯(lián)規(guī)則挖掘分析,從而獲得有關(guān)用戶行為的信息。表1記錄了日志文件中一些典型的內(nèi)容。

表1　部分日志文件內(nèi)容

在對Web日志文件中的數(shù)據(jù)進行挖掘之前,先要進行必要的數(shù)據(jù)預(yù)處理過程。數(shù)據(jù)預(yù)處理是對原始數(shù)據(jù)進行清理、過濾和標準化,將數(shù)據(jù)轉(zhuǎn)化為需要的抽象類型,為下一步進行數(shù)據(jù)挖掘做好準備。在本文中,數(shù)據(jù)預(yù)處理時,選擇用戶會話級的數(shù)據(jù),會話是指同一用戶在某一次瀏覽網(wǎng)頁過程中請求顯示一個網(wǎng)頁序列的過程。

為了方便分析,簡化分析過程,在數(shù)據(jù)預(yù)處理之后,選取5個會話,并只保留相同類型的數(shù)據(jù)作為數(shù)據(jù)挖掘的對象。如表2所示,將IP分別以數(shù)字1到5代表,表示有5次會話,將URL分別以字母A～Z代表,表示訪問頁面地址的集合。在這5次會話中訪問的頁面地址是{A,B,C,D,E,F}。

表2　數(shù)據(jù)預(yù)處理結(jié)

根據(jù)表2,生成事務(wù)數(shù)據(jù)庫表3,其中每個事務(wù)項(TID)包含一個地址項集。現(xiàn)假設(shè)最小支持度計數(shù)為2,即min_supp=2(這里所示為絕對支持度,因使用支持度計數(shù),對應(yīng)的相對支持度為2/6=33.3%)。

表3　事務(wù)數(shù)據(jù)庫

利用表3的數(shù)據(jù)和Apriori算法挖掘頻繁項集,挖掘到的頻繁項集是{B,D,F}。根據(jù)挖掘出的所有的頻繁項集,產(chǎn)生相應(yīng)的關(guān)聯(lián)規(guī)則。

給定用戶最小置信度(min_conf)為70%,由頻繁項集產(chǎn)生的關(guān)聯(lián)規(guī)則是:

(1)B→D,c=3/4=75%(c代表該規(guī)則的置信度,下同)。

(2)D→B,c=3/3=100%。

(3)(B,F)→D,c=2/2=100%。

(4)(D,F)→B,c=2/2=100%。

上述關(guān)聯(lián)規(guī)則反映了網(wǎng)頁地址間的關(guān)聯(lián)關(guān)系。因此,可根據(jù)得到的4條規(guī)則分析用戶訪問網(wǎng)頁的行為。例如:

規(guī)則1B→D,c=3/4=75%,意味著用戶在一次會話中訪問了頁面B之后,有75%的可能會去訪問頁面D。

規(guī)則3(B,F)→D,c=2/2=100%,反映出用戶在一次會話中訪問了頁面B,F之后,有100% 的可能會去訪問頁面D,即肯定訪問頁面D。依據(jù)挖掘結(jié)果,發(fā)現(xiàn)用戶的網(wǎng)絡(luò)行為特征,分析用戶網(wǎng)絡(luò)行為的安全性。有針對性地優(yōu)化網(wǎng)站鏈接、提高服務(wù),使用戶用較短的時間訪問所需的頁面。

5結(jié)束語

本文通過利用Web日志記錄,運用關(guān)聯(lián)規(guī)則算法中的Apriori算法對用戶的網(wǎng)絡(luò)行為進行分析,挖掘用戶的網(wǎng)絡(luò)行為特征,為優(yōu)化網(wǎng)絡(luò)服務(wù),提高網(wǎng)絡(luò)的安全性提供支持。

Apriori算法是數(shù)據(jù)挖掘中的經(jīng)典算法之一,能夠在海量數(shù)據(jù)中挖掘出關(guān)聯(lián)規(guī)則,在網(wǎng)絡(luò)行為挖掘中是比較適用的。但Apriori算法的效率較低,尤其當(dāng)數(shù)據(jù)集規(guī)模較大時。這主要表現(xiàn)在:(1)Apriori算法要多次掃描數(shù)據(jù)集。當(dāng)掃描海量數(shù)據(jù)時,該算法必定耗費大量時間,嚴重影響算法執(zhí)行效率。(2)Apriori算法在執(zhí)行過程中產(chǎn)生大量的中間項集。這勢必要有大量空間用以存儲這些中間項集,占用大量內(nèi)存,影響算法執(zhí)行效率。

基于上述缺陷,提出一種改進的Apriori算法,以提高效率,更好地運用于解決網(wǎng)絡(luò)行為挖掘中去,是今后的主要研究工作。

參考文獻

[1]馮凌,林杰,雷星暉.Web日志數(shù)據(jù)挖掘模型研究[J].計算機集成制造系統(tǒng),2005,11(8):1073-1074.

[2]金燕,張玉峰.網(wǎng)絡(luò)數(shù)據(jù)挖掘及其在面向Web的知識檢索中的應(yīng)用[J].現(xiàn)代圖書情報技術(shù),2003(6):55-57.

[3]吳小波,徐維祥.多支持度關(guān)聯(lián)規(guī)則在網(wǎng)絡(luò)使用挖掘中的應(yīng)用[J].計算機工程與應(yīng)用,2005(31):168-171.

[4]李村合.網(wǎng)絡(luò)信息挖掘技術(shù)及其應(yīng)用研究[J].情報科學(xué),2002(11):1212-1214.

[5]繆紅保,李衛(wèi).基于數(shù)據(jù)挖掘的用戶安全行為分析[J].計算機應(yīng)用研究,2005(2):105-107.

[6]楊宏宇,朱丹,謝豐,等.入侵異常檢測研究綜述[J].電子科技大學(xué)學(xué)報,2009,38(5):587-596.

[7]楊向榮,宋擒豹,沈均毅.基于行為模式挖掘技術(shù)的網(wǎng)絡(luò)入侵檢測[J].西安交通大學(xué)學(xué)報,2002,36(2):173-176.

[8]劉智國,張雅明,林立忠.基于粒子群LSSVM的網(wǎng)絡(luò)入侵檢測[J].計算機仿真,2010,27(11):136-140.

[9]郭亞周,高德遠.模糊聚類分析在入侵檢測系統(tǒng)中的應(yīng)用研究[J].沈陽理工大學(xué)學(xué)報,2005,24(4):26-28.

[10]趙俊忠.入侵檢測系統(tǒng)中檢測技術(shù)的研究[J].計算機工程與應(yīng)用,2005(2):11-13.

[11]江泓,何恩.行為分析技術(shù)及其在可信網(wǎng)絡(luò)中的應(yīng)用前景[J].信息安全與通信保密,2009(2):67-69.

[12]ZengBin,ZhangDafang,LiWenwei.Designandimple-mentationofanetworkbehavioranalysis-orientedIPnetworkmeasurementsystem[C].NZ:IEEEComputerSociety,2008:374-379.

[13]KimTaekyu.Ontology/dataengineeringbaseddistributedsimulationoverserviceorientedarchitecturefornetworkbe-havioranalysis[M].Arizona:UniversityofArizona,2008.

[14]王光宏,蔣平.數(shù)據(jù)挖掘綜述[J].同濟大學(xué)學(xué)報:自然科學(xué)版,2004,32(2):246-252.

[15]韓家煒,坎伯.數(shù)據(jù)挖掘:概念與技術(shù)[M].北京:機械工業(yè)出版社,2001.

[16]KimSeungwoo,ParkSanghyun,WonJungIm,etal.Privacypreservingdataminingofsequentialpatternsfornetworktrafficdata[J].InformationSciences:anInternationalJournal,2008,178(3):694-713.

[17]LuoJ,BridgesS.Miningfuzzyassociationrulesandfuzzyfrequencyepisodesforintrusiondetection[J].InternationalJournalofIntelligentSystems,2000,15(8):687-704.