基于Apriori關(guān)聯(lián)規(guī)則在信息無障礙網(wǎng)站的應(yīng)用

王 玉,張偉紅,劉 雨

(吉林大學 應(yīng)用技術(shù)學院,長春 130012)

0 引 言

信息無障礙是指無論健全人還是殘疾人、無論年輕人還是老年人都能從信息技術(shù)中獲益,任何人在任何情況下都能平等、方便、無障礙地獲取和利用信息。

目前國內(nèi)外的信息無障礙研究主要集中在相關(guān)的理論研究與技術(shù)研究。早在2002年就有學者對阿拉巴馬州政府網(wǎng)站進行了無障礙水平評價,結(jié)果顯示,無障礙水平雖有相當?shù)倪M步,但水平仍然偏低,進而提出通過標準推動聯(lián)邦一級公共部門實現(xiàn)信息無障礙。2006年Shadi[1]試圖通過建立語義網(wǎng)絡(luò)技術(shù)數(shù)據(jù)模型,對網(wǎng)頁進行自動化易讀性評價。Stuart[2]研究顯示,交互式語音瀏覽器能為弱視的用戶提供可訪問世界各地網(wǎng)頁的工具。Vicente[3]對網(wǎng)頁內(nèi)容易讀性指導方針W3C的WCAG進行分析,以方便殘疾人士使用瀏覽器獲取信息,并對網(wǎng)頁無障礙程度的評價工具進行了分析。我國在這方面的研究相對滯后。

通過實現(xiàn)信息無障礙,加大社會宣傳,促進政府、企業(yè)相關(guān)部門加大建設(shè)信息無障礙力度,可使更多的人群在信息社會中受益。通過實現(xiàn)網(wǎng)頁無障礙的相關(guān)新聞、最新政策的發(fā)布、信息無障礙行業(yè)標準技術(shù)發(fā)表等,提高政府、企業(yè)相關(guān)部門對信息無障礙的認識、呼吁全社會關(guān)心信息無障礙事業(yè),加速網(wǎng)站無障礙事業(yè)的發(fā)展。筆者旨在通過在Web日志數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則以指導信息無障礙網(wǎng)站的設(shè)計與開發(fā)。根據(jù)3次點擊原則及網(wǎng)站結(jié)構(gòu)設(shè)計的特點,針對大量用戶對網(wǎng)站頁面URL的訪問頻率等信息通過Apriori算法實現(xiàn)數(shù)據(jù)挖掘,以尋找用戶訪問頁面之間的關(guān)聯(lián)規(guī)則,優(yōu)化網(wǎng)站結(jié)構(gòu),實現(xiàn)網(wǎng)站信息無障礙化。

1 數(shù)據(jù)挖掘相關(guān)技術(shù)

數(shù)據(jù)挖掘是指從大量的、模糊的、不完全的、隨機的數(shù)據(jù)中提取隱含的,人們無法用肉眼發(fā)現(xiàn)的一些潛在的信息和知識的過程,數(shù)據(jù)挖掘技術(shù)已在社會各方面得到廣泛應(yīng)用[4,5]。數(shù)據(jù)挖掘是通過分析每個數(shù)據(jù),從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)。主要包含數(shù)據(jù)準備、規(guī)律尋找和規(guī)律表示3個步驟。數(shù)據(jù)準備是從相關(guān)的數(shù)據(jù)源中選取所需的數(shù)據(jù)并整合成用于數(shù)據(jù)挖掘的數(shù)據(jù)集； 規(guī)律尋找是用某種方法將數(shù)據(jù)集所含的規(guī)律找出來；規(guī)律表示是盡可能以用戶可理解的方將找出的規(guī)律表示出來。數(shù)據(jù)挖掘的任務(wù)可分為關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、數(shù)據(jù)聚類、分類知識發(fā)現(xiàn)、序列模式發(fā)現(xiàn)和趨勢預測等,典型數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)如圖1所示。

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

數(shù)據(jù)挖掘是在數(shù)據(jù)庫領(lǐng)域中占比較重要地位的領(lǐng)域,國內(nèi)外數(shù)據(jù)挖掘的發(fā)展趨勢及其研究方向主要有知識發(fā)現(xiàn)方法的研究及應(yīng)用。目前大部分有關(guān)數(shù)據(jù)挖掘的研究主要集中在數(shù)據(jù)挖掘的數(shù)據(jù)總結(jié)、分類、聚類和關(guān)聯(lián)規(guī)則等方面。關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘的核心內(nèi)容之一,近年來得到了很快的發(fā)展,并成為當今數(shù)據(jù)挖掘的熱點。

網(wǎng)站的數(shù)據(jù)挖掘主要是對Web日志的挖掘[6,7],Web日志如何產(chǎn)生這里不再進行詳細介紹。Web日志挖掘主要分為數(shù)據(jù)的預處理、數(shù)據(jù)發(fā)現(xiàn)、模式識別和模式分析5個步驟。在模式識別中,主要用了路徑分析和關(guān)聯(lián)規(guī)則兩種技術(shù)。

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

用戶訪問網(wǎng)站后,在Web日志中會產(chǎn)生一系列的數(shù)據(jù),這些數(shù)據(jù)不能完全被人們用到,如網(wǎng)站的結(jié)構(gòu)都會產(chǎn)生Web日志,還有一些圖片等無用的數(shù)據(jù)。數(shù)據(jù)預處理是對那些人們用不到的數(shù)據(jù),即被稱為“臟”數(shù)據(jù)進行處理[8]。這些處理主要用一些數(shù)據(jù)庫的操作語言實現(xiàn)的,把這些語言嵌套在實現(xiàn)數(shù)據(jù)挖掘的程序代碼中,在其進行數(shù)據(jù)挖掘前,由程序自動清理。數(shù)據(jù)預處理是個重要的過程,如果在這個過程對數(shù)據(jù)不能進行有效處理,將會影響到后面的操作,出現(xiàn)結(jié)果不準確等問題。

1.2 數(shù)據(jù)發(fā)現(xiàn)

數(shù)據(jù)發(fā)現(xiàn)主要是通過一些程序處理,把Web日志中對人們有用的數(shù)據(jù)存儲到事務(wù)數(shù)據(jù)庫中,以便以后對這些數(shù)據(jù)的應(yīng)用。這里把能用到的數(shù)據(jù)單獨放到一個容器,就可以對容器進行操作,提高了程序執(zhí)行的速度和效率。

1.3 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則最早是Agrawal等[9,10]于1993年提出的,假設(shè)I是項的集合,給定一個交易數(shù)據(jù)庫D,其中每個事務(wù)T是I的非空子集,即每個交易都與一個唯一的標識符TID(Transaction IDentity)對應(yīng)。設(shè)一個X項集,T中包含A。關(guān)聯(lián)規(guī)則是形如X?Y的蘊含式,在D中的支持度S是D中事務(wù)同時包含項集X、項集Y的百分比,即概率； 置信度c是包含X的事務(wù)中同時又包含Y的百分比,即條件概率。

同時滿足最小支持度閾值和最小置信度閾值的規(guī)則成為強規(guī)則,這些閾值是根據(jù)挖掘需要人為設(shè)定的。關(guān)聯(lián)規(guī)則的挖掘一般分為兩個步驟：1)找出所有頻繁項集,這些項集的支持度必須滿足用戶給定的最小支持度； 2)根據(jù)找出的頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則,這些規(guī)則必須滿足最小支持度和最小可信度。

支持度和置信度是描述關(guān)聯(lián)規(guī)則的兩個重要概念,前者用于衡量關(guān)聯(lián)規(guī)則在整個數(shù)據(jù)庫中的統(tǒng)計重要性,后者用于衡量關(guān)聯(lián)規(guī)則的可信程度。一般來說,只有支持度和置信度均較高的關(guān)聯(lián)規(guī)則才可能是用戶感興趣、有用的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的挖掘問題就是在事務(wù)數(shù)據(jù)庫D中找出具有用戶給定的最小支持度minsup和最小置信度minconf的關(guān)聯(lián)規(guī)則。若support(X?Y)≥minsup且confidence(X?Y)≥minconf,稱關(guān)聯(lián)規(guī)則X?Y為強規(guī)則。

2 基于改進的Apriori算法的Web日志挖掘過程

Apriori 算法是最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法之一,Apriori 算法使用頻繁項集性質(zhì)的先驗知識,是最有影響的挖掘布爾型關(guān)聯(lián)規(guī)則頻繁項集的算法[11]。Apriori算法基于Apriori性質(zhì)----頻繁項集的所有非空子集都必須是頻繁的,以壓縮搜索空間。筆者主要利用Apriori算法找出數(shù)據(jù)的關(guān)聯(lián)規(guī)則,通過關(guān)聯(lián)規(guī)則挖掘的實現(xiàn)找出事務(wù)數(shù)據(jù)之間的關(guān)系。

2.1 Apriori算法

Apriori算法查找頻繁項集的基本思想是：首先找出所有的頻繁集,這些項集出現(xiàn)的頻繁性至少和預定義的最小支持度一樣； 然后由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則,這些規(guī)則必須滿足最小支持度和最小可信度； 再由找到的頻繁項集產(chǎn)生期望的規(guī)則。一旦這些規(guī)則被生成,則只有大于用戶給定的最小可信度的規(guī)則才被保留。

Apriori算法在第1次迭代時,由I直接構(gòu)成候選I項目集的集合CI,若I={i1,i2,…,im},則CI={{i1},{i2},…,{im}}。Apriori算法在第k次迭代中,先根據(jù)上一次迭代過程中找到的頻繁項目集的集合Fk-1產(chǎn)生本次迭代的候選項目集的集合Ck； 然后為Ck中的每個項目集分配一個初始為零的計數(shù)器,依次掃描數(shù)據(jù)集D中的事務(wù),確定包含在每條事務(wù)中并且屬于Ck的項目集,增加這些項目集的計數(shù)器值,在所有事務(wù)都掃描完后即可得到Ck中各項目集的支持數(shù),根據(jù)數(shù)據(jù)集D的事務(wù)總數(shù)|D|和最小支持度計算各項目集的支持度就可確定Ck中頻繁項目集。重復上述過程直到?jīng)]有新的項目集產(chǎn)生為止。

為生成所有頻集,使用了遞歸的方法。首先找到頻繁1-項集的集合,記作L1,用L1找出頻繁項集L2,以此類推直到最后找到的項集為空時為止。

算法結(jié)構(gòu)化描述過程如下：

1)L1=find_frequent_1-itemsets(D);//挖掘頻繁1-項集

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

3)Ck=apriori_gen(Lk-1,min_sup);//調(diào)用apriori_gen方法生成候選頻繁k-項集

4)for each transactiont∈D{//掃描事務(wù)數(shù)據(jù)庫D

5)Ct=subset(Ck,t);

6)for each candidatec∈Ct

7)c.count++;//統(tǒng)計候選頻繁k-項集的計數(shù)

8)}

9)Lk={c∈Ck|c.count≥min_sup} //滿足最小支持度的k-項集即為頻繁k-項集

10)}

11)returnL=∪kLk;//合并頻繁k-項集(k>0)

2.2 針對無障礙Web訪問的算法改進

在Apriori算法用于網(wǎng)頁鏈接關(guān)系的發(fā)現(xiàn)中,Apriori算法中的事務(wù)對應(yīng)于用戶的一次訪問活動,數(shù)據(jù)集對應(yīng)于網(wǎng)頁頁面集,通過應(yīng)用Apriori算法來找到網(wǎng)頁頁面的鏈接關(guān)系。但如果直接應(yīng)用Apriori算法挖掘網(wǎng)頁結(jié)構(gòu)的頻繁集,頻繁集數(shù)量會非常龐大,特別是發(fā)現(xiàn)頻繁集在最壞情況下可達到指數(shù)級,使其難以應(yīng)用到現(xiàn)實的頁面關(guān)系挖掘中。

圖2 基于Apriori算法的數(shù)據(jù)挖掘過程

根據(jù)交互設(shè)計領(lǐng)域的基本理論之一的“3次點擊”原則,即對于Web設(shè)計來說,如果用戶在3次點擊中無法找到信息或完成網(wǎng)站功能,用戶就會對該網(wǎng)站失去耐心,對信息無障礙網(wǎng)站的設(shè)計和開發(fā)更需要遵循這樣的設(shè)計原則。因此,信息無障礙網(wǎng)站在網(wǎng)站的結(jié)構(gòu)設(shè)計上最多只設(shè)置3層鏈接深度,即從網(wǎng)站首頁開始到網(wǎng)站任意子頁面不超過3層鏈接。

根據(jù)上述網(wǎng)站結(jié)構(gòu)的特點,網(wǎng)頁之間的超鏈接不超過3個網(wǎng)頁,所以對于發(fā)現(xiàn)網(wǎng)頁之間的頻繁集而言,只需要發(fā)現(xiàn)頻繁3-項集即可,而不必發(fā)現(xiàn)大于3-項集的頻繁集,基于Web日志的Apriori改進算法,使頻繁集的挖掘大大減少,不僅可滿足網(wǎng)站的需要,而且降低了算法的時間復雜度。

基于改進的Apriori算法的數(shù)據(jù)挖掘過程如圖2所示。

2.3 算法實現(xiàn)過程

算法實現(xiàn)及結(jié)果如下。

Step1 數(shù)據(jù)收集及數(shù)據(jù)凈化處理。從服務(wù)端獲得Web日志數(shù)據(jù)庫信息,刪除日志文件中不是由用戶請求,而是由瀏覽器自動請求產(chǎn)生的訪問記錄。圖3是經(jīng)過處理后的數(shù)據(jù)庫。

圖3 數(shù)據(jù)預處理后的Web日志數(shù)據(jù)庫

Step2 對Web日志進行預處理,得到事務(wù)數(shù)據(jù)庫。事務(wù)數(shù)據(jù)庫主要由用戶IP及每次訪問的URL信息組成。

Step3 掃描事務(wù)數(shù)據(jù)庫,計算每個數(shù)據(jù)項出現(xiàn)的次數(shù)。根據(jù)給定的最小支持度(0.8),挖掘出挖掘頻繁1-項集的集合,每項的支持度都必須大于或等于0.8。

Step4 挖掘頻繁1-項集自身連接,重復Step3的操作,產(chǎn)生候選頻繁2-項集； 再根據(jù)給出的最小支持度(0.8)挖掘出挖掘頻繁2-項集。

Step5 挖掘頻繁2-項集的自身連接,重復Step3的操作,產(chǎn)生候選頻繁3-項集,因為其自身連接產(chǎn)生的子集為空； 再根據(jù)給出的最小支持度(0.8)挖掘出挖掘頻繁3-項集。

Step6 執(zhí)行上述過程后,程序會根據(jù)Apriori的頻繁項集的所有子集都是頻繁原理進行剪枝操作,把不符合要求的數(shù)據(jù)刪除,從而產(chǎn)生頻繁項集,最終通過程序的挖掘獲得關(guān)聯(lián)規(guī)則。

各步驟結(jié)果及數(shù)據(jù)挖掘發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則如圖4所示。

圖4 數(shù)據(jù)挖掘結(jié)果

通過上面的步驟實現(xiàn)了數(shù)據(jù)的挖掘,找到了需要的關(guān)聯(lián)規(guī)則,通過這些數(shù)據(jù)可找出訪問網(wǎng)站的用戶在瀏覽這個網(wǎng)頁的同時還喜歡瀏覽的網(wǎng)頁類型,以便為其做出推薦。

3 結(jié) 語

通過上述工作,達到了信息無障礙網(wǎng)站設(shè)計的基本目標,網(wǎng)站可通過用戶在訪問網(wǎng)站時Web日志數(shù)據(jù)庫中的信息,利用數(shù)據(jù)挖掘方法分析得到用戶訪問網(wǎng)頁之間的鏈接關(guān)系,通過分析網(wǎng)站結(jié)構(gòu),結(jié)合“3次點擊”原則,在網(wǎng)站的結(jié)構(gòu)設(shè)計上最多只設(shè)置3層鏈接深度,頻繁項集只需發(fā)現(xiàn)網(wǎng)站頻繁3-項集即可,針對此結(jié)構(gòu)特征,減少了數(shù)據(jù)集的復雜性,有效降低了算法的時間復雜度。

上述過程是對訪問過網(wǎng)站所有用戶的數(shù)據(jù)進行分析,產(chǎn)生的關(guān)聯(lián)規(guī)則適用于大多數(shù)用戶。下一步工作則主要通過對每個IP地址進行分析,借助上述方法找到每個IP地址訪問內(nèi)容的關(guān)聯(lián)規(guī)則,了解每個用戶感興趣的網(wǎng)頁,以實現(xiàn)對每個用戶進行內(nèi)容推薦,進一步完善網(wǎng)站,讓更多人受益。

參考文獻：

[1] SHADI ABOU-ZAH RA.A Data Model to Facilitate the Automation of Web Accessibility Evaluations[J].Electronic Notes in Theoretical Computer Science,2006,157(2):3-9.

[2]STUART GOOSE.Enhancing Web Accessibility via the Vox Portal and a Web-Hosted Dynamic HTML ? VoxML Converter[J].Computer Networks,2000,33(6):583-592.

[3]VICENTE LUQUE CENTENO.Web Accessibility Evaluation Tools:A Survey and Some Improvements[J].Electronic Notes in Theoretical Computer Science,2006,157(2):87-100.

[4]孫兵,劉雯,田地,等.基于時間序列的數(shù)據(jù)挖掘在證券中的應(yīng)用[J].吉林大學學報:信息科學版,2010,28(3):270-274.

SUN Bing,LIU Wen,TIAN Di,et al.Application of Time Series Data Mining on Security Analysis[J].Journal of Jilin University:Information Science Edition,2010,28(3):270-274.

[5]于曼,胡明,金剛,等.關(guān)聯(lián)規(guī)則算法的電信網(wǎng)絡(luò)告警應(yīng)用[J].吉林大學學報:信息科學版,2010,28(3):264-269.

YU Man,HU Ming,JIN Gang,et al.Association Rules Algorithm Applied to Telecommunications Network Alarms[J].Journal of Jilin University:Information Science Edition,2010,28(3):264-269.

[6]湯恒耀,占曉燕.基于Web日志挖掘的信息無障礙網(wǎng)站設(shè)計研究[J].電腦知識與技術(shù),2011,7(4):3261-3262.

TANG Heng-yao,ZHAN Xiao-yan.The Research of the Accessibility Website Design Baed on Web Log Mining[J].Computer Knowledge and Technology,2011,7(4):3261-3262.

[7]宋淑彩,祁愛華,王劍雄.面向Web的數(shù)據(jù)挖掘技術(shù)在網(wǎng)站優(yōu)化中的個性化推薦方法的研究與應(yīng)用[J].科技通報,2012,28(2):117-119.

SONG Shu-cai,QI Ai-hua,WANG Jian-xiong.Facing the Web Site of the Data Mining Technology in the Opti-Mization of Personalized Recommendation Methods of Research and Application[J].Bulletin of Science and Technology,2012,28(2):117-119.

[8]姚洪波,楊炳儒.Web日志挖掘數(shù)據(jù)預處理過程技術(shù)研究[J].微計算機信息,2006,22(18):234-236.

YAO Hong-bo,YANG Bing-ru.Research of Data Preparatin Based on Design Based on Web Log[J].Micro Computer Information,2006,22(18):234-236.

[9]AGRAWAL R,IMILIENSKI T,SWAMI A.Mining Association Rules between Sets of Items in Large Database[C]∥SIGMOD.Washington DC:[s.n.],1993:207-216.

[10]AGRAWAL R,SRIKANT R.Fast Algorithms for Mining Association Rules[C]Proceedings of the 20thInternational Conference on Very Large Databases.Santiago,Chile:[s.n.],1994:487-499.

[11]畢永成.Web日志處理中Apriori算法及其改進[J].電腦知識與技術(shù),2010,14(6):3573-3574.

BI Yong-cheng.Apriori Arithmetic and Amelioration in Weblog Disposal[J].Computer Knowledge and Technology,2010,14(6):3573-3574.