基于Ｆｏｃｕｓ＋Ｃｏｎｔｅｘｔ技術關聯規則交互挖掘

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

關鍵詞:關聯規則;focus+context可視化;交互式挖掘;魚眼視圖

中圖分類號:TP391

文獻標識碼:A

1引言

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

當對數據集合進行瀏覽時，交互技術可以改善用戶對信息數據的觀察#65377;實際上，所有可視化技術都集中了動態及交互性#65377;交互性可以大大的彌補技術上的不足，給用戶提供操縱大數據集復雜性的一種機制#65377;一個關鍵的區別在于，可視化數據探尋是一種完全人類引導的過程，而數據挖掘算法可以自動的分析數據集以搜索有用的信息和統計有效模式#65377;挖掘算法的自動化程度隨著人類引導的程度不同有相當的變化并且通常都需要交互，但還是算法而不是用戶在搜尋模式#65377;相對于把可視化數據探尋和挖掘算法分開使用，數據挖掘的策略應該是把可視化與分析過程緊密結合為一個完整的挖掘工具#65377;許多挖掘技術利用不同步驟，其間需要用戶的介入#65377;有些技術非常的復雜，這種情況下，可視化可以支持用戶介入這些技術的選擇過程#65377;從這個觀點來看，可視化數據挖掘技術不僅僅是用于挖掘過程中某些方面的一門可視化技術，更是一種挖掘算法，其中可視化在該算法中起著主要作用#65377;用戶對挖掘過程的各步驟可見而不僅僅是對某些步驟可見在引導與結束挖掘過程時將會更有助于做出更合適的決定#65377;

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

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

2Focus+Context可視化交互技術

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

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

3基于Focus+Context技術的關聯規則交互式挖掘

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

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

3.1表層交互:信息數據的層次化呈現

3.1.1關聯規則的聚類分析與每個聚類的代表元素

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

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

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

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

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

3.1.2基于凝聚聚類的關聯規則Focus+Context展現

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

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

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

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

(1)把關聯規則集合聚集為k個聚類;

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

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

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

4一個原型

為了驗證基于規則聚類的Focus+Context可視化關聯規則交互挖掘技術，我們開發了一個原型系統IMARFC(Interactive Mining of Association Rules Based on Focus + Context Technique)#65377;圖-2是該系統對UCI數據集mushroom.data的關聯規則交互挖掘的一個視圖#65377;系統分左邊表層交互(Mining Result區)與右邊深層交互(Control Panel區)兩個區域#65377;

表層交互:圖中上部明細區，為當前焦點，顯示規則的詳細參數，顯示的規則包括由同一頻繁項集導出的各條規則;下左部為梗概區，顯示當前焦點臨近各元素的概要(這里與焦點元素處于同一個聚類)，由同一頻繁項集導出的規則只顯示其中的任一條;下右部為標志區，僅顯示其它各個聚類中的代表元素#65377;規則的詳細參數包括規則的前件各項#65380;規則的后件各項#65380;對應頻繁項集的支持度#65380;前件項集的支持度以及后件項集的支持度#65377;規則元素的概要僅包括規則的前件#65380;后件以及導出該規則的頻繁項集的支持度#65377;規則元素的標志代表元素僅顯示其前件與后件#65377;通過與Mining Result區交互，當焦點(鼠標雙擊一個非焦點區域，即下左部和下右部)更換時，各區域的數據顯示隨之更換#65377;當雙擊下右部時，該代表元素即更換到焦點區并按焦點區的特征顯示，該代表元素所在聚類的其它元素的概要就顯示在下左部的梗概區，原來的明細區元素及其所在的梗概區的元素就按標志區的特征顯示在標志區#65377;當雙擊下左部時，雙擊到的元素就與當前焦點更換顯示，并各自按明細區與梗概區的特征顯示規則數據#65377;通過表層交互，用戶對當前的規則集有一個詳略得當的認識#65377;

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

5結論

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

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。