基于Ｆｏｃｕｓ＋Ｃｏｎｔｅｘｔ技術(shù)關(guān)聯(lián)規(guī)則交互挖掘

摘要:可視化挖掘是數(shù)據(jù)挖掘的重要研究領(lǐng)域，但目前的研究還主要集中在挖掘結(jié)果的可視化，用戶對(duì)挖掘過程仍然缺乏可控性#65377;本文利用focus+context技術(shù)實(shí)現(xiàn)探索型交互式數(shù)據(jù)挖掘#65377;充分利用人類用戶的認(rèn)知能力與計(jì)算機(jī)的數(shù)據(jù)處理能力，實(shí)現(xiàn)用戶對(duì)挖掘過程的參與從而利用用戶領(lǐng)域知識(shí)于挖掘過程#65377;適應(yīng)人類的認(rèn)知心理，便于幫助用戶對(duì)挖掘結(jié)果的定位#65380;聚焦#65380;理解與評(píng)估，進(jìn)而快速找到相對(duì)于當(dāng)前應(yīng)用上下文的有價(jià)值信息#65377;并實(shí)現(xiàn)了一個(gè)原型系統(tǒng)IMARFC#65377;

關(guān)鍵詞:關(guān)聯(lián)規(guī)則;focus+context可視化;交互式挖掘;魚眼視圖

中圖分類號(hào):TP391

文獻(xiàn)標(biāo)識(shí)碼:A

1引言

自從R. Agrawal等1993年提出關(guān)聯(lián)規(guī)則挖掘以來，關(guān)聯(lián)規(guī)則的挖掘研究一直是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)熱門研究課題，關(guān)聯(lián)規(guī)則也不僅僅局限于當(dāng)初超級(jí)商場的銷售分析應(yīng)用還成功的用于其他廣泛的業(yè)務(wù)領(lǐng)域#65377;關(guān)聯(lián)規(guī)則的挖掘主要處理2個(gè)問題:第一是從數(shù)據(jù)集中找出所有規(guī)則#65377;注意到規(guī)則的數(shù)量隨著項(xiàng)集的數(shù)量指數(shù)增長，已經(jīng)研究出各種利用一定的質(zhì)量評(píng)價(jià)方法來有效的縮減巨大的搜索空間的算法;第二就是從挖掘出的規(guī)則集合中找出感興趣的規(guī)則#65377;因?yàn)橥诰虺龅囊?guī)則數(shù)量巨大，而用戶感興趣的規(guī)則只是數(shù)量極小的一部分，因此，這一步的工作代價(jià)更大[5]#65377;這兩個(gè)問題不是彼此孤立的，因?yàn)殛P(guān)聯(lián)規(guī)則挖掘的有效應(yīng)用歸根結(jié)底是快速找到用戶感興趣的那部分規(guī)則#65377;針對(duì)這些，已經(jīng)提出了很多方法#65377;傳統(tǒng)的研究主要集中在第一個(gè)問題的算法方面即如何快速生成頻繁項(xiàng)集#65377;最近幾年的研究主要集中在關(guān)聯(lián)規(guī)則的質(zhì)量改善方面[7];其中包括，利用可視化的手段通過改善用戶對(duì)規(guī)則的理解和挖掘過程的參與程度來改善挖掘的質(zhì)量[2，6，9]，通過規(guī)則的二次挖掘來改善用戶對(duì)規(guī)則的理解[8]#65377;

當(dāng)對(duì)數(shù)據(jù)集合進(jìn)行瀏覽時(shí)，交互技術(shù)可以改善用戶對(duì)信息數(shù)據(jù)的觀察#65377;實(shí)際上，所有可視化技術(shù)都集中了動(dòng)態(tài)及交互性#65377;交互性可以大大的彌補(bǔ)技術(shù)上的不足，給用戶提供操縱大數(shù)據(jù)集復(fù)雜性的一種機(jī)制#65377;一個(gè)關(guān)鍵的區(qū)別在于，可視化數(shù)據(jù)探尋是一種完全人類引導(dǎo)的過程，而數(shù)據(jù)挖掘算法可以自動(dòng)的分析數(shù)據(jù)集以搜索有用的信息和統(tǒng)計(jì)有效模式#65377;挖掘算法的自動(dòng)化程度隨著人類引導(dǎo)的程度不同有相當(dāng)?shù)淖兓⑶彝ǔ６夹枰换ィ€是算法而不是用戶在搜尋模式#65377;相對(duì)于把可視化數(shù)據(jù)探尋和挖掘算法分開使用，數(shù)據(jù)挖掘的策略應(yīng)該是把可視化與分析過程緊密結(jié)合為一個(gè)完整的挖掘工具#65377;許多挖掘技術(shù)利用不同步驟，其間需要用戶的介入#65377;有些技術(shù)非常的復(fù)雜，這種情況下，可視化可以支持用戶介入這些技術(shù)的選擇過程#65377;從這個(gè)觀點(diǎn)來看，可視化數(shù)據(jù)挖掘技術(shù)不僅僅是用于挖掘過程中某些方面的一門可視化技術(shù)，更是一種挖掘算法，其中可視化在該算法中起著主要作用#65377;用戶對(duì)挖掘過程的各步驟可見而不僅僅是對(duì)某些步驟可見在引導(dǎo)與結(jié)束挖掘過程時(shí)將會(huì)更有助于做出更合適的決定#65377;

但是，直接利用可視化手段來進(jìn)行規(guī)則挖掘還存在著很多問題，除了可視化方法受屏幕大小的限制外(這是目前幾乎所有可視化方法企圖解決的問題)，用戶對(duì)圖形表示的理解一直沒有受到重視，似乎什么數(shù)據(jù)只要圖形表示了，一定就能夠改善用戶的理解，這是個(gè)很大的誤 區(qū)#65377;實(shí)際上，數(shù)據(jù)信息的可視化如果不恰當(dāng)，不僅不能改善用戶的理解，有時(shí)還會(huì)誤導(dǎo)用戶 #65377;比如，利用平行坐標(biāo)系對(duì)頻繁項(xiàng)集進(jìn)行圖形表示，數(shù)據(jù)量稍大就容易形成一團(tuán)亂麻，對(duì)用 戶理解數(shù)據(jù)的關(guān)聯(lián)毫無幫助#65377;

數(shù)據(jù)挖掘的可視化研究目前還主要集中在挖掘結(jié)果可視化方面，對(duì)挖掘過程的可視化少有涉及，即使是結(jié)果的可視化，其研究也主要集中在各種類型#65380;各種維度數(shù)據(jù)的圖形表示上#65377;針對(duì)挖掘結(jié)果顯示必須符合人類認(rèn)知特性以及用戶對(duì)挖掘過程參與不夠深入難以快速找到感興趣規(guī)則的問題，本文利用Focus+Context交互技術(shù)，提高用戶對(duì)數(shù)據(jù)挖掘的參與度，改善用戶對(duì)挖掘結(jié)果與挖掘過程的理解，并進(jìn)而快速聚焦挖掘出感興趣規(guī)則#65377;

2Focus+Context可視化交互技術(shù)

Focus+Context技術(shù)主要由2部分組成[1，3]#65377;一是交互，其特征是隨著對(duì)焦點(diǎn)的選定#65380;數(shù)據(jù)的顯示也隨之變化#65377;如果當(dāng)前焦點(diǎn)為x，則需要解決的問題是在可視化的要求下，其它對(duì)象與x有什么關(guān)系?其它對(duì)象的重要性即興趣度(DoI，Degree of Interest)怎樣?這種關(guān)系表現(xiàn)為該對(duì)象與x的距離(一種自定義的距離，不一定是幾何距離)，其中還含有對(duì)象的細(xì)節(jié)等級(jí)(LoD，Level of Detail)，對(duì)象x的LoD反映了x在一種層次結(jié)構(gòu)中的位置，處于更高級(jí)的層次更抽象其LoD值也就更小#65377;Focus+Context技術(shù)的另一個(gè)方面是可視化，給定當(dāng)前的焦點(diǎn)以及其它對(duì)象相對(duì)于該焦點(diǎn)的重要性，在有限資源的限制下，該如何給出一個(gè)可視化展示?這里根據(jù)可視化的各種具體要求，可以有各種實(shí)現(xiàn)#65377;可以根據(jù)與焦點(diǎn)距離的遠(yuǎn)近設(shè)置對(duì)象的顯示細(xì)節(jié)，或設(shè)置一個(gè)閥值，距離低于這個(gè)閥值的對(duì)象只顯示一個(gè)標(biāo)志，表示那里有一個(gè)對(duì)象，或者甚至不顯示#65377;

當(dāng)描述信息可視化時(shí)，指出數(shù)據(jù)如何可視表示以及這種表示下允許什么樣的操作或交互就足夠了#65377;操作即操作數(shù)據(jù)本身，如果可視化是交互式的，還可以操作數(shù)據(jù)表示的方法#65377;在Focus+Context可視化的情形，操作或交互的結(jié)果可以分為2個(gè)層次，即深層改變后臺(tái)的數(shù)據(jù)以及表層僅僅改變后臺(tái)數(shù)據(jù)的顯示方式#65377;

3基于Focus+Context技術(shù)的關(guān)聯(lián)規(guī)則交互式挖掘

在眾多的關(guān)聯(lián)規(guī)則挖掘的研究文獻(xiàn)中，基本上都集中在自主挖掘上，即把挖掘算法當(dāng)作一個(gè)黑箱，處理好的原始數(shù)據(jù)經(jīng)過該黑箱后，產(chǎn)生出一系列的關(guān)聯(lián)規(guī)則#65377;可視化數(shù)據(jù)挖掘的研究也主要集中在可視化的數(shù)據(jù)探尋上，與挖掘算法是分開使用的#65377;數(shù)據(jù)挖掘的策略應(yīng)該是把可視化與分析過程緊密結(jié)合為一個(gè)完整的挖掘工具，應(yīng)該是一個(gè)能夠充分利用人類認(rèn)知能力與計(jì)算機(jī)數(shù)據(jù)處理能力的一個(gè)集成系統(tǒng)#65377;而在關(guān)聯(lián)規(guī)則的挖掘應(yīng)用實(shí)踐中，常常需要定向挖掘#65377;比如，有時(shí)候需要尋找某些指定的項(xiàng)集是否有關(guān)聯(lián)，確定的兩個(gè)關(guān)聯(lián)項(xiàng)是否總是要伴隨其他某些項(xiàng)，在支持度變化時(shí)，這些關(guān)聯(lián)是如何變化的，等等#65377;

關(guān)聯(lián)規(guī)則的定向挖掘，即把用戶的意愿在挖掘過程表示出來，這些用戶挖掘意愿包括前件指定#65380;后件指定#65380;規(guī)則各部件的支持度指定，等等#65377;通過與挖掘過程的不斷交互，用戶可以逐漸找到自己感興趣的模式，或者發(fā)現(xiàn)從已有的數(shù)據(jù)中難以得出有用規(guī)則的結(jié)論#65377;用戶與系統(tǒng)的交互可以分為兩類，即，表層交互:只影響信息數(shù)據(jù)的呈現(xiàn)方式，以及深層交互:還影響后臺(tái)信息數(shù)據(jù)的內(nèi)容#65377;

3.1表層交互:信息數(shù)據(jù)的層次化呈現(xiàn)

3.1.1關(guān)聯(lián)規(guī)則的聚類分析與每個(gè)聚類的代表元素

基于Focus+Context的可視化，需要預(yù)先對(duì)數(shù)據(jù)集進(jìn)行分析，確定什么是數(shù)據(jù)集的概觀(Broad view)#65380;什么是數(shù)據(jù)集的細(xì)節(jié)(Detail)#65377;為此，我們首先對(duì)挖掘出來的關(guān)聯(lián)規(guī)則集進(jìn)行聚類分析，將整個(gè)規(guī)則集劃分成若干組，使得組類的規(guī)則彼此相似#65380;組間規(guī)則彼此不同#65377;為了完成規(guī)則集的劃分，需要對(duì)規(guī)則之間的距離做出定義，使得這種距離度量能夠反映規(guī)則之間的相似性#65377;由于關(guān)聯(lián)規(guī)則的特點(diǎn)，我們采用如下的Jaccard系數(shù)[4]來定義規(guī)則間的距離:其中，s是規(guī)則x#65380;y的相同項(xiàng)的數(shù)目，t是x#65380;y相異項(xiàng)的數(shù)目之和#65377;d( x， y )值越小表明x與y不同的項(xiàng)數(shù)愈少，距離就越近，從而就更相似#65377;可以看出，由同一個(gè)頻繁項(xiàng)集導(dǎo)出的規(guī)則的距離為0#65377;

設(shè)數(shù)據(jù)集有n個(gè)元素(為{x(1)，x(2)，…，x(n)})，任意2個(gè)聚類Ci和Cj間的距離定義為元素之間距離的均值:

算法:ACAR(Agglomerating Clustering of Association Rules，關(guān)聯(lián)規(guī)則的凝聚聚類)給定任一

正整數(shù)k;//希望聚類的數(shù)量while(聚類數(shù)量>k)do令Ci和Cj為使系統(tǒng)中任意2個(gè)聚類間的距離D(Ck， Ch)最小化的2個(gè)聚類;合并Ci#65380;Cj; end;

聚類Ci的代表元素ri定義為該聚類中與其它元素距離的均值最小的元素#65377;即ri為下列集合中的任一元素:

3.1.2基于凝聚聚類的關(guān)聯(lián)規(guī)則Focus+Context展現(xiàn)

要實(shí)現(xiàn)數(shù)據(jù)集合的Focus+Context顯示，首先需要對(duì)數(shù)據(jù)的興趣度進(jìn)行定量描述，并且完成對(duì)關(guān)鍵要素的定義:Focus是什么?Context是什么?Level of Detail如何劃分?因?yàn)橛脩魧?duì)一條規(guī)則是否感興趣，當(dāng)前應(yīng)用的上下文起著重要的作用，因此，希望以平等地位看待每條規(guī)則，在這個(gè)前提下，我們可以假定每條規(guī)則的全局興趣度相同#65377;因此，當(dāng)前焦點(diǎn)為x時(shí)，其它對(duì)象y的相對(duì)興趣度DoI可以定義為3.1.1節(jié)中的距離d( x， y )#65377;

為了把當(dāng)前焦點(diǎn)Focus的上下文Context劃分，我們需要分析清楚關(guān)聯(lián)規(guī)則集合中元素之間的關(guān)系#65377;假設(shè)規(guī)則聚集為n個(gè)聚類，那么全體規(guī)則所構(gòu)成集合中的規(guī)則x和y的關(guān)系有以下3種情況:(1)x#65380;y由同一頻繁項(xiàng)集導(dǎo)出;(2)x#65380;y處于同一個(gè)聚類中但由不同的頻繁項(xiàng)集導(dǎo)出;(3)x#65380;y處于不同的聚類#65377;

欲顯示的規(guī)則集合中元素的Level of Detail可以劃分為:(1)規(guī)則元素內(nèi)容明細(xì)，Detail，包括前件項(xiàng)premise#65380;后件項(xiàng)conquence#65380;對(duì)應(yīng)的頻繁項(xiàng)集的支持度isupp#65380;前件項(xiàng)的支持度psupp#65380;后件項(xiàng)的支持度csupp，等(其他的度量實(shí)際上都可由這3個(gè)值導(dǎo)出);(2)規(guī)則元素梗概，Sketch，僅包括規(guī)則的前件項(xiàng)#65380;后件項(xiàng)#65380;對(duì)應(yīng)的頻繁項(xiàng)集的支持度;(3)規(guī)則元素代表，Representative，為該元素所在聚類的代表元素#65377;

因此，通過以上的分析，我們把關(guān)聯(lián)規(guī)則的Focus+Context可視化方法表層交互概括如下:

(1)把關(guān)聯(lián)規(guī)則集合聚集為k個(gè)聚類;

(2)把屏幕顯示區(qū)域一分為三:第一為明細(xì)區(qū)(Detail)，為當(dāng)前焦點(diǎn)，顯示當(dāng)前規(guī)則的明細(xì)——包括由同一頻繁項(xiàng)集導(dǎo)出的各規(guī)則的明細(xì);第二為梗概區(qū)(Sketch)，焦點(diǎn)元素所在聚類的元素(此為近距離上下文)，這些元素顯示其梗概;第三為標(biāo)志區(qū)，Landmark，整個(gè)規(guī)則集合的其他元素為當(dāng)前焦點(diǎn)遠(yuǎn)距離上下文，這些元素僅顯示其所在聚類的代表，一個(gè)代表元素表示一個(gè)聚類#65377;圖1基于focus+context的交互挖掘

3.2深層交互:后臺(tái)數(shù)據(jù)的定位處理與新信息數(shù)據(jù)下的數(shù)據(jù)展現(xiàn) 用戶的表層交互只是改變數(shù)據(jù)的顯示形態(tài)以適應(yīng)人類的視覺習(xí)慣，以便能夠快速定位到感興趣的模式上，實(shí)際上只實(shí)現(xiàn)了數(shù)據(jù)的一種特殊的展現(xiàn)形式#65377;而交互式挖掘的結(jié)果可能會(huì)引起后臺(tái)數(shù)據(jù)的變化#65377;比如，如果通過瀏覽先前挖掘的結(jié)果用戶希望對(duì)結(jié)果中某一特定部分相關(guān)的一些規(guī)則作進(jìn)一步挖掘，則當(dāng)用戶把視點(diǎn)聚焦到該項(xiàng)時(shí)，系統(tǒng)就需要針對(duì)這個(gè)特定需求實(shí)行進(jìn)一步深層次的挖掘，這時(shí)，系統(tǒng)后臺(tái)的數(shù)據(jù)變了，按Focus+Context方法顯示的各個(gè)方面都要發(fā)生相應(yīng)的變化#65377;

圖1表示基于Focus+Context可視化技術(shù)的交互挖掘過程#65377;在初始需求下，挖掘出的結(jié)果經(jīng)過交互分析用戶可能改變挖掘的需求#65380;提出新的挖掘愿望，這時(shí)，挖掘就進(jìn)入了一個(gè)迭代的過程，一直到找到感興趣的模式或發(fā)現(xiàn)不了什么新奇的信息時(shí)為止#65377;

4一個(gè)原型

為了驗(yàn)證基于規(guī)則聚類的Focus+Context可視化關(guān)聯(lián)規(guī)則交互挖掘技術(shù)，我們開發(fā)了一個(gè)原型系統(tǒng)IMARFC(Interactive Mining of Association Rules Based on Focus + Context Technique)#65377;圖-2是該系統(tǒng)對(duì)UCI數(shù)據(jù)集mushroom.data的關(guān)聯(lián)規(guī)則交互挖掘的一個(gè)視圖#65377;系統(tǒng)分左邊表層交互(Mining Result區(qū))與右邊深層交互(Control Panel區(qū))兩個(gè)區(qū)域#65377;

表層交互:圖中上部明細(xì)區(qū)，為當(dāng)前焦點(diǎn)，顯示規(guī)則的詳細(xì)參數(shù)，顯示的規(guī)則包括由同一頻繁項(xiàng)集導(dǎo)出的各條規(guī)則;下左部為梗概區(qū)，顯示當(dāng)前焦點(diǎn)臨近各元素的概要(這里與焦點(diǎn)元素處于同一個(gè)聚類)，由同一頻繁項(xiàng)集導(dǎo)出的規(guī)則只顯示其中的任一條;下右部為標(biāo)志區(qū)，僅顯示其它各個(gè)聚類中的代表元素#65377;規(guī)則的詳細(xì)參數(shù)包括規(guī)則的前件各項(xiàng)#65380;規(guī)則的后件各項(xiàng)#65380;對(duì)應(yīng)頻繁項(xiàng)集的支持度#65380;前件項(xiàng)集的支持度以及后件項(xiàng)集的支持度#65377;規(guī)則元素的概要僅包括規(guī)則的前件#65380;后件以及導(dǎo)出該規(guī)則的頻繁項(xiàng)集的支持度#65377;規(guī)則元素的標(biāo)志代表元素僅顯示其前件與后件#65377;通過與Mining Result區(qū)交互，當(dāng)焦點(diǎn)(鼠標(biāo)雙擊一個(gè)非焦點(diǎn)區(qū)域，即下左部和下右部)更換時(shí)，各區(qū)域的數(shù)據(jù)顯示隨之更換#65377;當(dāng)雙擊下右部時(shí)，該代表元素即更換到焦點(diǎn)區(qū)并按焦點(diǎn)區(qū)的特征顯示，該代表元素所在聚類的其它元素的概要就顯示在下左部的梗概區(qū)，原來的明細(xì)區(qū)元素及其所在的梗概區(qū)的元素就按標(biāo)志區(qū)的特征顯示在標(biāo)志區(qū)#65377;當(dāng)雙擊下左部時(shí)，雙擊到的元素就與當(dāng)前焦點(diǎn)更換顯示，并各自按明細(xì)區(qū)與梗概區(qū)的特征顯示規(guī)則數(shù)據(jù)#65377;通過表層交互，用戶對(duì)當(dāng)前的規(guī)則集有一個(gè)詳略得當(dāng)?shù)恼J(rèn)識(shí)#65377;

深層交互:通過與Control Panel區(qū)的交互實(shí)現(xiàn)#65377;在這里用戶可以設(shè)置挖掘參數(shù)，如頻繁項(xiàng)集#65380;關(guān)聯(lián)規(guī)則的前件#65380;后件以及頻繁項(xiàng)集的支持度#65380;規(guī)則前件支持度#65380;后件支持度等，從而控制挖掘過程，挖掘出的結(jié)果顯示在表層交互區(qū)以幫助盡快找到感興趣的模式#65377;圖2基于focus+context的關(guān)聯(lián)規(guī)則交互挖掘原型

5結(jié)論

數(shù)據(jù)挖掘不是一蹴而就的，往往是一個(gè)迭代的逐步逼近的過程#65377;基于Focus+Context技術(shù)的關(guān)聯(lián)規(guī)則交互式挖掘通過增加用戶對(duì)挖掘過程的介入，充分利用人類用戶的認(rèn)知能力以及計(jì)算機(jī)的數(shù)據(jù)處理能力，使得整個(gè)挖掘更能夠適應(yīng)用戶的需求，快速找到用戶感興趣的模式#65377;當(dāng)挖掘結(jié)果較大時(shí)，基于Focus+Context技術(shù)把數(shù)據(jù)按概觀或細(xì)節(jié)的方式進(jìn)行展現(xiàn)而不是把所有數(shù)據(jù)沒有主次層次的顯示，這樣更符合人類的認(rèn)知習(xí)性，便于用戶逐步求精的進(jìn)行數(shù)據(jù)挖掘#65377;

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。