王宇杰，喬聰

0 引言

數(shù)據(jù)挖掘是為了幫助用戶處理大量存在的數(shù)據(jù)，發(fā)現(xiàn)其后隱含的規(guī)律性，同時將其模型化，完成輔助決策的作用。

數(shù)據(jù)挖掘技術分支很多，其中，基于用戶訪問模式的挖掘（也稱 Web日志挖掘或使用記錄的挖掘）是用于發(fā)現(xiàn)用戶行為及潛在顧客的信息，該種數(shù)據(jù)的挖掘有助于合理建造網(wǎng)站，幫助更好地組織設計網(wǎng)站主頁；幫助改善市場營銷決策，有助于商家制定促銷策略。所以，對于一個企業(yè)網(wǎng)站的建設來說，用戶訪問模式的挖掘有重要的意義。

本文結合一個大型圖書網(wǎng)站的建設，來研究基于用戶訪問模式的數(shù)據(jù)挖掘技術在大型網(wǎng)站中的應用。

1 基于用戶訪問模式的數(shù)據(jù)挖掘在大型圖書網(wǎng)站中的實現(xiàn)

1.1 用戶訪問模式（Web使用記錄）挖掘的基本流程

由于Web包含了豐富和動態(tài)的超鏈接信息，以及Web頁面的訪問和使用信息，這為數(shù)據(jù)挖掘提供了豐富的資源。我們可以將Web挖掘一般地定義為：從與WWW相關的資源和行為中抽取感興趣的、有用的模式和隱含信息。一般Web挖掘可分為3類：Web內(nèi)容挖掘 (Web content mining)、Web結構挖掘 (Web structure mining)和Web使用記錄的挖掘(Web usage mining)。Web使用記錄挖掘的主要目標是Web的訪問記錄中抽取感興趣的模式。WWW中的每個服務器都保留了訪問日志 (Web access log)，記錄了關于用戶訪問和交互的信息。分析這些數(shù)據(jù)可以幫助理解用戶的行為，從而改進站點的結構，或為用戶提供個性化的服務。

在模式發(fā)現(xiàn)中，首先要解決的問題就是數(shù)據(jù)的預處理，它主要包括如下兩個部分：①數(shù)據(jù)清理 (data cleaning)，包括無關記錄的剔除、判斷是否有重要的訪問沒有被記錄、用戶的識別等問題；②事務識別 (transaction identification)，是指將頁面訪問序列劃分為代表Web事務或用戶會話的邏輯單元。在對事務進行了劃分后，就可以根據(jù)具體的分析需求選擇訪問模式發(fā)現(xiàn)的技術，如路徑分析、關聯(lián)規(guī)則挖掘、時序模式以及聚類和分類技術。路徑分析(path analysis)可以用來發(fā)現(xiàn) Web站點中最經(jīng)常被訪問的路徑，從而可以調(diào)整站點的結構。在 Web使用記錄挖掘的環(huán)境下，關聯(lián)規(guī)則挖掘的目標是發(fā)現(xiàn)用戶對站點各頁面的訪問之間的關系，這對于電子商務是非常有用的。

對 Web日志進行分析和挖掘要經(jīng)過一系列的數(shù)據(jù)準備工作和建模工作。一個基本的流程如下：

（1）要對Web日志進行清洗、過濾和轉換，從中抽取感興趣的數(shù)據(jù)；

（2）URL、動作、資源的類型、資源的大小、請求的時間、在資源上停留的時間、請求者的Internet域名、用戶、服務器狀態(tài)作為Data Cube的維變量，將對模塊、頁面和文件請求次數(shù)、來自不同Internet域請求次數(shù)、事件、會話、帶寬、錯誤次數(shù)、不同瀏覽器種類、用戶所在組織作為度量變量建立Data Cub；

（3）利用數(shù)據(jù)挖掘技術 (如特征、分類、關聯(lián)、預測、時間序列分析、趨勢分析) 進行 Web流量分析、典型的事件序列和用戶行為模式分析、事務分析，可以回答成分和特色在什么上下文中被使用，什么是典型的事件序列；在用戶中是否有共同的行為模式，是什么；不同用戶群在使用和行為上有什么差異；用戶的行為是否隨時間變化，怎么變化等問題。

通過分析Web存取日志能幫助理解用戶的行為和Web結構，因此，可以改進Web頁面的設計和Web應用程序，發(fā)現(xiàn)潛在的電子商務客戶。Web Log數(shù)據(jù)挖掘提供了深層次的報告，像時間序列分析、相關、分類等。通過使用這類Web Log文件，可以進行一些研究工作，如系統(tǒng)性能分析，通過Web緩存改進系統(tǒng)設計、Web頁面預取、Web頁面交換 (swapping)；認識 Web信息訪問的本質；理解用戶的反映和動機。有些研究提出了可適應站點 (adaptive site)的概念，即可以通過用戶訪問模式的學習改進其自身的 Web站點。

1.2 大型圖書網(wǎng)站用戶使用模式挖掘系統(tǒng)簡介

用戶使用模式的挖掘是 Web使用記錄挖掘的一個重要組成部分。由于大型圖書網(wǎng)站是一個動態(tài)性極強的信息源，其信息不斷發(fā)生更新。出版物的信息越來越多，鏈接信息和訪問記錄也處于頻繁地更新之中。網(wǎng)站面對的是形形色色的用戶群體，大部分用戶面對由一兩個關鍵字搜索出來的幾十種出版物，不清楚哪一個是對自己有用的信息，極容易不知所措迷失方向，也極容易失去耐心。所以從大量的用戶點擊出版物的詳細信息行為中發(fā)現(xiàn)用戶使用模式，并不斷地更新這種知識，有非常重要的意義。

為了簡化數(shù)據(jù)的預處理過程，使挖掘出來的用戶使用模式更有針對性，我們從以下兩個方面對用戶的點擊行為進行了顯式記錄：①用戶進行簡單查詢的信息；②用戶查看出版物詳細信息的行為。對這兩方面的用戶行為記錄不斷地進行挖掘和更新挖掘，基本上可以滿足我們的初始目標。

在出版物查詢模塊的建設過程中，我們精心構建了用戶導航系統(tǒng)。導航系統(tǒng)主要向用戶提供如下服務：根據(jù)用戶以往所查詢的出版物種類，向用戶推薦一些新的出版物，這些出版物是通過挖掘其他廣大用戶的出版物查詢記錄而確定的，對用戶有很強的針對性和指導意義。

用戶提交了一次查詢以后，系統(tǒng)不僅會返回符合查詢條件的出版物信息，還會根據(jù)用戶提交的查詢內(nèi)容，搜索已經(jīng)挖掘出來的用戶行為模式關聯(lián)規(guī)則知識庫，得到與用戶此次查詢相關聯(lián)的查詢關鍵字，這些關鍵字經(jīng)過剪枝（去除用戶已經(jīng)查詢過的關鍵字）和排序（按支持數(shù)的多少排序）返回給用戶。同樣，當用戶點擊了某一出版物的詳細信息鏈接以后，系統(tǒng)不僅返回這一出版物的所有屬性，還返回與這一出版物相關聯(lián)的出版物的鏈接。用戶可以輕松地找到自己所希望查詢的出版物信息。

下面詳細地討論網(wǎng)站中數(shù)據(jù)挖掘的實現(xiàn)過程。

1.3 系統(tǒng)數(shù)據(jù)結構

數(shù)據(jù)庫中的出版物信息表包含有所有出版物的標準號、出版物名稱、類型、分類、學科所屬專業(yè)、適用專業(yè)、讀者層次、作者、定價、封面、目錄、內(nèi)容簡介、作者簡介、專家點評等等詳細信息，其中標準號是其主鍵，每一種出版物都有自己唯一的標準號。而在用戶管理模塊中，每個用戶都有自己詳細的注冊信息，包括賬號、姓名、性別、出生年月、職業(yè)、學歷、收入、地址、興趣愛好等等，還有一些用戶自己設定的個性化參數(shù)，如是否愿意接受網(wǎng)站提供的導航服務等，注冊賬號是其主鍵。

這樣，我們在記錄用戶的點擊行為時，所需要記錄的數(shù)據(jù)量就非常小。顧客點擊出版物詳細信息的行為記錄表和簡單查詢記錄表的結構分別如表1所示。

表1 數(shù)據(jù)記錄表結構

用戶賬號（user_id）和出版物標準號（bzh）分別用來唯一地定位用戶和出版物信息。

提交時間（rq）是一個 date類型，Oracle的這一 date類型數(shù)據(jù)中包含有用戶提交購物表單的準確日期和時間。

命中出版物條目數(shù)（shoot）字段里存放這一查詢條件下返回的出版物的數(shù)量。

來源頁面（referer）里面包含著用戶點擊此出版物詳細信息鏈接的所在的頁面信息，它可能指向這么幾個地方：網(wǎng)站首頁，簡單查詢結果頁面，高級查詢結果頁面，出版物推介頁面等。這一字段主要用來統(tǒng)計和挖掘用戶瀏覽網(wǎng)頁的習慣。可以注意到，用戶的每一次查詢行為和每一次瀏覽出版物詳細信息的行為都會作為一條單獨的記錄保存下來。

導航系統(tǒng)真正的核心是關聯(lián)規(guī)則知識表，它是用來存放經(jīng)過挖掘后產(chǎn)生的關聯(lián)規(guī)則知識的。由于關聯(lián)規(guī)則知識的多樣性，我們把表分成多個子表來管理，分別是1-項集的規(guī)則表、2-項集的規(guī)則表等等依次類推。例如2-項集的規(guī)則知識表結構如表2所示。分開存放可以提高檢索速度，節(jié)省數(shù)據(jù)空間。

表2 項集關聯(lián)規(guī)則知識表

bzh1，bzh2，和bzh分別是一個2 項集規(guī)則的三個元素，它們共同組成規(guī)則（bzh1∧bzh2）? bzh。conf字段里保存著這條規(guī)則的置信度。

1.4 數(shù)據(jù)預處理

一個大型交易數(shù)據(jù)庫中包含有很多信息，它可以是抽象的概括的，比如某種職業(yè)的用戶喜歡買某一類型的書（多層規(guī)則挖掘），也可以是具體的明細的，比如人們在買完某一本書之后又接著買了另外一本書（序列規(guī)則挖掘）。由于條件所限，我們只進行了單維布爾關聯(lián)規(guī)則的挖掘，也即所有用戶購買圖書出版物規(guī)則的挖掘。關系數(shù)據(jù)庫僅僅是將所有信息結構化保存，并不考慮現(xiàn)實中數(shù)據(jù)之間的邏輯聯(lián)系，所以在進行挖掘以前，必須根據(jù)挖掘的特性對數(shù)據(jù)進行預處理。

如前所述，用戶的點擊行為記錄中包含有四個字段，但要挖掘的只是出版物之間的關聯(lián)規(guī)則，并不考慮用戶本身的各種屬性及點擊的時間之間的關系等，所以真正用到的只是其中的標準號（bzh）字段。數(shù)據(jù)預處理的主要工作就是把同一用戶在一次登陸中提交的查詢或者點擊的出版物詳細信息鏈接整理成為一條新的記錄。判斷用戶是否是一次登陸的方法是，同一用戶ID的兩條記錄之間的時間差小于一個session的存活時間。具體方法是，在數(shù)據(jù)分析處理計算機上檢索用戶購買行為記錄表，把記錄表中的用戶賬號（user_id）和出版物標準號（bzh）或查詢關鍵字（keyword）按用戶賬號和提交時間（rq）排序后提取到數(shù)據(jù)分析計算機上來，然后把相同賬號的記錄時間差小于20分鐘的所有記錄分別作為一條新的事務記錄保存在一個文件中。這樣就形成了可在其上進行關聯(lián)挖掘的數(shù)據(jù)文件，其中每一個標準號就是這條事務中的一個項目。

1.5 應用挖掘算法

網(wǎng)站在最初運行一段時間后，數(shù)據(jù)挖掘系統(tǒng)要進行第一次基礎挖掘，基礎挖掘要用改進的Apriori算法進行，這樣不僅能得到數(shù)據(jù)的頻繁項集信息，也可以得到其負邊界信息。以后每經(jīng)過一段時間的運行，數(shù)據(jù)挖掘系統(tǒng)就要進行更新挖掘，更新挖掘算法使用增量式更新算法。應用這一算法，不僅能夠更新整個數(shù)據(jù)庫的關聯(lián)規(guī)則知識，還可以得到新增數(shù)據(jù)庫的關聯(lián)規(guī)則，這樣就可以為顧客提供全面精準的導航服務了。數(shù)據(jù)挖掘系統(tǒng)結構如圖1所示。

每一次更新挖掘時，對用戶行為記錄表進行挖掘前的預處理以后，都要將其中的記錄進行備份，并將原記錄表清空，以使下次處理的數(shù)據(jù)都是新的數(shù)據(jù)。而每次進行增量式更新挖掘后，就把新的事務數(shù)據(jù)庫并入原數(shù)據(jù)庫中，作為一個新的“原數(shù)據(jù)庫”以準備下一次挖掘。

圖1 數(shù)據(jù)挖掘系統(tǒng)結構圖

更新挖掘出來的整個數(shù)據(jù)庫的頻繁項集信息和新增數(shù)據(jù)庫的頻繁項集信息分別存放在不同的文件中，以備規(guī)則生成程序來檢驗它們的置信度情況，真正生成關聯(lián)規(guī)則知識。

1.6 規(guī)則生成

由行為數(shù)據(jù)庫中的事務找出頻繁項集以后，由它們產(chǎn)生強關聯(lián)規(guī)則（既滿足最小支持度，又滿足最小置信度）的方法是直接了當?shù)?。對于置信度，可以用下式來表示，其中條件概率用項集支持度計數(shù)表示。

● 對于每個頻繁項集l，產(chǎn)生l的所有非空子集。

由于規(guī)則由頻繁項集產(chǎn)生，每個規(guī)則都自動滿足最小支持度。當運行算法產(chǎn)生頻繁項集后，新增數(shù)據(jù)的頻繁項集和整個數(shù)據(jù)庫的頻繁項集連同它們的支持度會分別存放在散列表中，使得它們可以快速被訪問。在規(guī)則形成階段，把新增數(shù)據(jù)庫中頻繁項集形成的規(guī)則和整個數(shù)據(jù)庫中頻繁項集形成的規(guī)則進行合并，既如果有相同的規(guī)則的，按它們中置信度大的那個作為最終置信度進行保存。

關聯(lián)規(guī)則可以是多個項集關聯(lián)一個項集，也可能是一個項集關聯(lián)多個項集，也可能是多個項集關聯(lián)多個項集。規(guī)則生成后，按照規(guī)則的條件項集數(shù)目分別保存入相關的關聯(lián)規(guī)則知識表中，一對多或者多對多的關聯(lián)規(guī)則分成多條規(guī)則存放在表中，每一個結果項目都可以作為一個獨立的規(guī)則來看待。

這樣，數(shù)據(jù)經(jīng)過預處理，挖掘頻繁項集，生成規(guī)則并寫入數(shù)據(jù)庫后，就可以作為知識對用戶的新查詢行為提供建議了。

1.7 關聯(lián)規(guī)則知識的應用

挖掘得到的關聯(lián)規(guī)則知識存放在關聯(lián)規(guī)則知識表中（如表3-2），在實際運用中，根據(jù)用戶本次登陸以來的提交的內(nèi)容從多到少依次搜索3-項集知識表、2-項集知識表和1-項集知識表。具體方法是，如果是首次提交，就只搜索1-項集知識表；如果是第二次提交，就把這兩次提交的內(nèi)容作為兩個條件先查詢2-項集知識表，然后再用第二次提交的內(nèi)容查詢1-項集知識表；第三次及以后查詢的方法同上。

把滿足關聯(lián)條件的條目所指向的書目標準號組合在一起，按照各個條目的置信度指數(shù)進行排序，然后按順序全部或者取前五個同用戶所要查詢的內(nèi)容一起返回給用戶，使用戶在得到自己想要查詢的內(nèi)容的同時，還可以得到與所提交的條件有關的其他書目的快捷的鏈接，從而方便了用戶的查詢過程。

2 小結

本文首先介紹了基于用戶訪問模式的數(shù)據(jù)挖掘對對大型系統(tǒng)的重要性，然后結合大型圖書網(wǎng)站的建設，詳細介紹了用戶訪問模式（Web使用記錄）挖掘的基本流程，接著詳細介紹了數(shù)據(jù)結構的設計，數(shù)據(jù)預處理，挖掘算法的應用，規(guī)則的生成等關鍵性的數(shù)據(jù)挖掘技術，最后介紹了產(chǎn)生的規(guī)則的應用。

[1] Park J S, Chen M S, and Yu P S. An Effective Hash-based Algorithm for Mining Association Rules.In Proc. 1995 ACM-SIGMOD Int.Conf. Managemeng of Data, San Jose,CA, May1995.

[2] 鄭秀麗,王樂寧,陳中柱.基于數(shù)據(jù)挖掘技術的電子商務客戶潛力開發(fā)方案.計算機工程與應用,2002-05,194-195.

[3] 韓家煒,孟小峰,王靜,李盛恩.Web挖掘研究.計算機研究與發(fā)展,2002-04,38(4),405-414.

[4] 陸麗娜,楊怡玲,管旭東,魏恒義.Web日志挖掘中的數(shù)據(jù)預處理的研究.計算機工程,2000-4,26(4),66-72.

[5] Tomasz Imielinski, Leonid Khachiyan,Amin Abdulghani.Cubegrades:Generalizing Association Rules. Data Mining and Knowledge Discovery, 6, 219-257, 2002.

[6] 寇育敬,王春花,黃厚寬.約束關聯(lián)規(guī)則的增量式維護算法.計算機研究與發(fā)展.2001-08,38(8),947-951.

[7] Jiawei Han, Micheline Kamber著.范明,孟小峰等譯:數(shù)據(jù)挖掘:概念與技術.機械工業(yè)出版社,2001.