基于用戶訪問(wèn)模式的數(shù)據(jù)挖掘技術(shù)在大型圖書網(wǎng)站中應(yīng)用的研究

王宇杰，喬聰

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 系統(tǒng)數(shù)據(jù)結(jié)構(gòu)

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

這樣，我們?cè)谟涗浻脩舻狞c(diǎn)擊行為時(shí)，所需要記錄的數(shù)據(jù)量就非常小。顧客點(diǎn)擊出版物詳細(xì)信息的行為記錄表和簡(jiǎn)單查詢記錄表的結(jié)構(gòu)分別如表1所示。

表1 數(shù)據(jù)記錄表結(jié)構(gòu)

用戶賬號(hào)（user_id）和出版物標(biāo)準(zhǔn)號(hào)（bzh）分別用來(lái)唯一地定位用戶和出版物信息。

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

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

來(lái)源頁(yè)面（referer）里面包含著用戶點(diǎn)擊此出版物詳細(xì)信息鏈接的所在的頁(yè)面信息，它可能指向這么幾個(gè)地方：網(wǎng)站首頁(yè)，簡(jiǎn)單查詢結(jié)果頁(yè)面，高級(jí)查詢結(jié)果頁(yè)面，出版物推介頁(yè)面等。這一字段主要用來(lái)統(tǒng)計(jì)和挖掘用戶瀏覽網(wǎng)頁(yè)的習(xí)慣?？梢宰⒁獾剑脩舻拿恳淮尾樵冃袨楹兔恳淮螢g覽出版物詳細(xì)信息的行為都會(huì)作為一條單獨(dú)的記錄保存下來(lái)。

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

表2 項(xiàng)集關(guān)聯(lián)規(guī)則知識(shí)表

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

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

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

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

1.5 應(yīng)用挖掘算法

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

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

圖1 數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)圖

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

1.6 規(guī)則生成

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

● 對(duì)于每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的所有非空子集。

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

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

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

1.7 關(guān)聯(lián)規(guī)則知識(shí)的應(yīng)用

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

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

2 小結(jié)

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

[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] 鄭秀麗,王樂(lè)寧,陳中柱.基于數(shù)據(jù)挖掘技術(shù)的電子商務(wù)客戶潛力開發(fā)方案.計(jì)算機(jī)工程與應(yīng)用,2002-05,194-195.

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

[4] 陸麗娜,楊怡玲,管旭東,魏恒義.Web日志挖掘中的數(shù)據(jù)預(yù)處理的研究.計(jì)算機(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] 寇育敬,王春花,黃厚寬.約束關(guān)聯(lián)規(guī)則的增量式維護(hù)算法.計(jì)算機(jī)研究與發(fā)展.2001-08,38(8),947-951.

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