葉良艷

（安徽電子信息職業(yè)技術(shù)學(xué)院信息與智能工程系，安徽 蚌埠233000）

1 前 言

面對浩瀚的數(shù)據(jù)海洋，從海量數(shù)據(jù)中發(fā)現(xiàn)真正需要的信息，這個過程就是數(shù)據(jù)挖掘的過程。從挖掘?qū)ο髞矸?，WEB數(shù)據(jù)挖掘一般分為三類：WEB 日志挖掘、WEB 內(nèi)容挖掘、WEB 結(jié)構(gòu)挖掘［1，2］。其中web日志數(shù)據(jù)挖掘?qū)ο笫怯脩粼L問web日志記錄數(shù)據(jù)，通過挖掘技術(shù)挖掘出有效、潛在、可理解的規(guī)則模式。在web日志挖掘過程中，有很多無關(guān)、冗余數(shù)據(jù)影響到?jīng)Q策，粗糙集理論不需要先驗(yàn)知識就可以減少原來的數(shù)據(jù)量，且不影響原有知識表達(dá)信息，是最后生成決策規(guī)則、挖掘數(shù)據(jù)的有效模式。

粗糙集理論［3］是1982年由波蘭學(xué)者Z.Paw lak提出的，該理論可以有效地分析不一致、不完整、不精確等不完備的數(shù)據(jù)信息，另外可以對數(shù)據(jù)進(jìn)行運(yùn)算分析和推理，最終揭示潛在規(guī)律。其發(fā)現(xiàn)知識系統(tǒng)中具有代表性的軟件有：Rough Enough數(shù)據(jù)挖掘工具系統(tǒng)、ROSE 模塊化軟件系統(tǒng)、Rosetta數(shù)據(jù)分析工具包。

2 粗糙集基本定義

定義1 設(shè)一個知識信息S，S＝ ｛U，A，V，f｝，其中，U 為論域，A 為屬性的有限集，且A＝C∪D，C為條件屬性子集合，D 為決策屬性子集合，Vk是屬性k的域，即f：U×A→V，其中每個xi∈U，p∈A，則有f（xi，p）∈Vp。

定義2 假設(shè)xi，xj∈U，P?A 定義二元關(guān)系IND （P）稱為等價關(guān)系，當(dāng)且僅當(dāng)p（xi）＝p（xj）并對所有的p∈P成立，則稱xi、xj在信息表S中屬性集P是等價的。

定義5 在一個知識信息系統(tǒng)S中，設(shè)ψ為S的一個分類，通過約簡后其最小屬性子集與有同來屬性集擁有相同的分類質(zhì)量，即有R?P?Q，并且γR（ψ）＝γP（ψ），則稱為P屬性集的ψ約簡，記為REDUψ（P）。

約簡中的一般約簡算法主要就是一個迭代過程。假設(shè)判斷P 是否是C 相對于Q 的約簡，只需測試POSP（Q）＝POSC（Q）可滿足即可。一般約簡算法的思想［4－8］是：依次從表中刪除某個屬性，如果刪除該屬性后的信息表還可以清楚表達(dá)原來的信息系統(tǒng)，該操作繼續(xù)；若不能影響信息表達(dá)，則恢復(fù)為前一個表，接著下一個屬性，當(dāng)剩下屬性都不能刪除時即可，這就是一個約簡。

3 基于遺傳算法的約簡算法

遺傳算法描述如下：

步驟1 初始化群。將集合中的每個元素用二進(jìn)制符號來表示，且每個元素二進(jìn)制位的長度都固定。

步驟2 個體評價。用設(shè)置好的適應(yīng)度函數(shù)來評判每個個體的好壞，差的個體將被淘汰，優(yōu)秀的個體將被保留。

步驟3 選擇 （selection）。從群體中選擇出最適合環(huán)境的優(yōu)秀個體，繁殖下一代的父本。父本適應(yīng)度高低與被選擇作為繁殖的父本概率成正比。

步驟4 交叉、變異。交叉因繁殖下一代的父本發(fā)生了基因組合，變成新的個體，交叉概率Pc值常取0.25～0.75區(qū)間內(nèi)；變異是因父本中的某些基因發(fā)生了異向轉(zhuǎn)化，即0、1編碼變換，變異概率常取值為0.01～0.2。

基于遺傳方法的約簡算法，其時間復(fù)雜度為O （｜A｜｜U｜2），空間復(fù)雜度為O （｜U｜2）。

4 基于遺傳算法WEB日志挖掘

WEB日志挖掘過程是對收集數(shù)據(jù)源、將日志記錄文件導(dǎo)入到數(shù)據(jù)庫中、清洗原數(shù)據(jù)源、將清洗后的數(shù)據(jù)轉(zhuǎn)換挖掘格式數(shù)據(jù)等一系列預(yù)處理操作，然后將得到的數(shù)據(jù)利用粗糙集思想對預(yù)處理后的數(shù)據(jù)挖掘，并利用約簡算法對其進(jìn)行屬性約簡，最后從中提取決策規(guī)則，發(fā)現(xiàn)用戶訪問模式，找出用戶訪問網(wǎng)站的規(guī)律，了解用戶的興趣所在，為網(wǎng)站設(shè)計(jì)提供策劃。

（1）數(shù)據(jù)收集

本次挖掘的數(shù)據(jù)收集安徽電子信息職業(yè)技術(shù)學(xué)院一天的日志數(shù)據(jù)，web日志Log記錄數(shù)約為111 950萬條，web日志文件的大小約為18.8 M，為了便于日志數(shù)據(jù)處理，將日志導(dǎo)入到Access數(shù)據(jù)庫中。

（2）數(shù)據(jù)清洗

將web日志中與本次挖掘目的無關(guān)的數(shù)據(jù)刪除。1）框架、腳本或圖片、音頻等文件：①刪除一些圖片文件.Jpg、.gif、.bmp、.png；②刪除一些腳本文件.Css、.js；③刪除一些框架文件：top.html、left.html、right.html、buttom.html；④刪除一些音頻文件.wma、.rm、wmf、wmv；⑤刪除其它文件.doc、.xls、.rar、.ppt。2）刪除用戶請求方法是post的記錄。3）有空缺值需要記錄，可通過人工填寫補(bǔ)充其值、用平均值代替或者用可能性比較大的數(shù)值代替。因本系統(tǒng)的數(shù)據(jù)中記錄有空缺值較少，所以對此采用忽略的方法。4）刪除服務(wù)器狀態(tài)碼 （c＿status）中以3、4或者5開頭的信息。

通過上述數(shù)據(jù)清洗操作后，數(shù)據(jù)表log中只剩下20 031條記錄。

（3）清洗冗余數(shù)據(jù)

日志記錄的二維表可示為一個S信息系統(tǒng)。該二維表可看成是一個信息系統(tǒng)S＝ （U，A，V，f），其中U 是論域即用戶集合，A 是全部屬性的有限集合，A＝C∪D，C＝ ｛a1，a2……an｝，ai表示第i個條件屬性，在本二維表中，屬性為C＝ ｛a1，a2，a3……a14｝＝ ｛date，time，s－ip，s－sitename，csmethodcs－uri－query，cs－uri－stem，s－port，c－ip，cs－username，cs （User－Agent），sc－substatus，sc－status，sc－win32－status｝，D 為決策屬性。U／C＝U／ （C－Ci），其中Ci為不必要的若干屬性集合。C－Ci＝｛a2，a7，a8，a10，a11｝＝ ｛time，c－ip，cs－uri－stem，cs－uri－query，cs｝，其中通過c－ip，cs可以確定訪問的用戶，即論域。cs－uri－stem，cs－uri－query可以確定條件屬性。

上面得到的訪問信息表通過粗糙集處理工具軟件rosetta來處理決策表，在處理決策表之前一般可通過rosetta軟件消除缺省值并離散化，本系統(tǒng)的訪問信息表已經(jīng)離散化且沒有缺省值，所以可以將acess數(shù)據(jù)庫中的訪問信息表直接導(dǎo)入到rosetta，并進(jìn)行屬性約簡，提取規(guī)則。

5 結(jié)果分析

通過一般屬性約簡算法所得結(jié)果是 ｛index，dzx，zhaojiu，rjxy，economy，office，xxx，jsj，xsc｝。用戶訪問大部分部門，沒有特別的規(guī)則?；谶z傳算法約簡算法推導(dǎo)結(jié)果是 ｛index，zhaojiu｝。表示大部分用戶都訪問學(xué)校網(wǎng)站首頁和 “招生辦”部門。

兩個約簡算法所得結(jié)果截然不同，基于遺傳算法約簡算法所得結(jié)果更優(yōu)，7月正是高考考生填報志愿表的時間段，考生訪問學(xué)校網(wǎng)站主頁是為了了解該校的概況、歷史等信息；訪問 “招生辦”部門網(wǎng)站主要想了解該校錄取情況咨詢相關(guān)信息 （該校 “招生辦”部門提供了網(wǎng)上互動模塊）。

［1］Han J W，Kamber M.Data mining：concepts and techniques［M］.San Francisco：Morgan Kaufmann，2001.

［2］韓家煒，孟小峰，王靜，等.Web挖掘研究［J］.計(jì)算機(jī)研究與發(fā)展，2001，38（04）：405－414.

［3］Pawlak Z.Rough sets［J］.Inform Sci，1982，11：341－356.

［4］Miao D Q，Wang J.Information ＆dash.Based algorithm for reduction of knowledge［J］.IEEE Intern Conf Intell，1997，2（02）：1155－1158.

［5］Zhao K，Wang J.A reduction Algorithm Meeting Users’requirements［J］.Comput Sci Technol，2002，17（05）：578－593.

［6］苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法［J］.計(jì)算機(jī)研究與發(fā)展，1999，36（06）：681－684.

［7］代建華，李元香.一種基于粗糙集的決策系統(tǒng)屬性約簡算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2003，24（03）：523－526.

［8］王國胤，于洪，楊大春.基于條件信息熵的決策表約簡［J］.計(jì)算機(jī)學(xué)報，2002，25（07）：113－118.