基于信息粒的關聯規則提取研究

摘要：粒計算作為一種新的信息和知識處理的方法，近年來在許多領域中得到了應用。本文在學習和研究粒計算基本理論與技術的基礎上，將其應用于關聯規則提取中。通過對信息粒進行二進制的與運算，分析計算結果中出現1的次數來進行規則的提取。

關鍵詞：粒計算；信息粒；關聯規則；

中圖分類號：TP39文獻標識碼：A 文章編號：1009-3044(2008)12-20000-00

The Study of Association Rules Mining Based Information Granule

WANG Jun， WANG Yuan-Yun

(Department of Computer， Yang-En University， QuanZhou 362014，China)

Abstract: Granular computing is a new information processing method. Many models and methods of granular computing have been proposed and studied， and it has been applied in lots of fields. On the basis of studying fundamental principles and techniques of granular computing ，the concerning knowledge is applied in Association rules in the paper. The \"And\" operation is processing passing the Information Granule， the times of\"1\" to decide if the rules is mining.

Key words:Granular Computing; Information Granule; Association rules

1 引言

粒計算[1，2]方法能將復雜問題劃分為一系列更容易管理和更小的子問題，并且能更好地領悟問題同時提供一種對其本質更好的洞察力，避免陷入不必要的細節中去，對于一些包含不完備、不確定性和模糊信息的復雜問題可以比較好的解決。又因為圖像具有層次結構的特點，與粒計算方法的特點相似，本文將通過對粒計算的基本概念和方法的研究，將其應用到圖像分類中。利用粒計算方法分析研究圖像的特征信息，形成圖像特征信息粒；并對圖像特征信息粒進行分析，建立圖像特征信息粒格，在此基礎上進行圖像的分類。

通過對粒計算這種新的信息處理和計算范式的深入研究和實際應用，可以更加有效地對圖像特征信息進行描述；基于粒計算的圖像分類模型將為模式分類提供一種新的有效的方法。

2 信息粒及粒計算

由于人類自身能力有限，只能把大量復雜信息按其各自的特征和性能將其劃分成若干個較簡單的塊，如此劃分出的每一塊可看作是一個信息粒，也就是說信息粒是將具有特征相似性、功能近似、具有不分明性等實體的集合。而把信息劃分為信息粒的過程就稱為信息粒化。使用信息粒進行計算是粒計算的基本思想，在問題描述和求解中都具有重要的意義。我們可以把粒計算定義為：研究信息分類、被分成的塊是兩兩分離的劃分還是兩兩可能有交的模糊分割；研究分成的粒度大小、不同粒度層之間的關系，粒度分解和合并等[3，4]。粒計算是信息處理的一種新的概念和計算范式，主要用于處理不確定的、模糊的、不完整的和海量的信息。粗略的說，一方面它是Fuzzy信息粒理論、Rough集理論、商空間理論擴充，另一方面也是一種數學計算工具。具體的講，凡是在分析問題和求解問題中，應用了分組、分類、聚類以及融合等手段的一切理論和方法均屬于粒計算的范疇。粒計算已成為人工智能領域新的研究熱點方向之一。粒計算主要有兩個方面的問題：粒的構造和使用粒的計算。前者處理粒的形成、表示和解釋，后者處理在問題求解中的粒的運算[5]。簡單地說，粒計算就是表示和處理信息粒。

3 關聯規則

關聯規則提取是發現大量數據庫中項集之間的關聯關系。隨著大量數據的增加和存儲，如何發現海量信息中的隱藏信息，如從大量商務事務中發現有趣的關聯關系，從而可以幫助商務決策的制定；目前關聯規則提取已經成為數據挖掘領域中的重要研究方向。關聯規則模式屬于描述型模式，發現關聯規則的算法屬于無監督學習的方法。

3.1 關聯規則提取的原理

關聯規則反映了一個事件和其他事件之間的關聯。數據庫中的數據關系是現實世界中事務聯系的表現。數據之間的關系是復雜的，關聯規則提取的目的就是找出數據庫中隱藏的關聯信息。關聯可以分為簡單關聯、時序關聯、因果關聯和數據關聯等。從廣義上講，關聯分析是數據挖掘的本質。支持度和置信度是描述關聯分析中的兩個重要指標。一般來說，不同置信度和支持度的關聯規則是滿足不同用戶的游泳規則。在不同置信度和支持度下提取關聯規則就是在不同粒度層次下求解問題的粒計算思想的具體體現。

設I＝{i1， i1，…，im}是所有項目的集合，D為所有事務的集合(即事務數據庫)，每個事務T是項目的集合，T包含在I中，T???I；對每一個事務有唯一的標識，記做TID。設X是某些項目的集合，如果X包含在T中，則稱事務T包含X。

定義3.1.1：關聯規則是形如A→B的蘊含式，其中A ??I，B??I，并且A∩B＝??。

此定義的意義在于一個事務中的某些項的出現，可推導出另一些項在同一事務中也出現，其中A稱為關聯規則的先決條件，B為關聯規則的結果[6]。

事務D中的規則A???B是由支持度s(support)和確信度c(confidence)約束的。確信度表示規則的強度，支持度表示在規則中出現的頻度。數據項集A的支持度s(A)是D中包含A的事務數量與D的總事務數量之比，用|A|表示包含A的事務的個數，則s(A)為|A|與|D|的比值；同理A???B的支持度表示同時包含A和B的事務數量與D的總事務數量之比；A??B的確信度c定義為表示D中包含A事務的同時也包含B的可能性。

最小支持度閾值minsupport表示數據項集在統計意義上的最低主要性，最小確信度閾值minconfidence表示規則的最低可靠性。如果數據項集A的支持度大于最小支持度，則A是最大項目集。一般由用戶給定最下確信度閾值和最下支持度閾值。確信度和支持度大于相應閾值的規則為強關聯規則。發現關聯規則的任務就是從數據庫中發現確信度和支持度大于給定值的規則。

4 基于信息粒的關聯規則提取

粒計算可以將大的復雜的問題分解成若干個小的容易的問題，我們可以通過信息系統的等價類的劃分，將等價類定義為粒并與一個二進制數對應起來，然后基于經典的頻集挖掘算法[7]，對不同的粒進行組合，通過二進制的布爾與運算產生新的頻繁組合粒。

定義4.1.1 集合U上的等價關系R，其等價類集合{[u]R|u?U}是Ｕ關于R的商集U/R，商集中的元素(等價類)定義為R-基本粒。

定義4.1.2 設二進制串Bchar=0110…1110，二進制串的基數定義為此串中含1的個數，記為|Bchar|。

設S=（U，A）是一個信息系統，其中U={u1，u2，…un，}是所討論對象的個體域，A={a1，a2，…an，}是屬性集，(a，v)或av是指定義在S上的一種描述，其中a?A是屬性集A上的一個屬性，v是a關于個體集U上的個體x?U的屬性值，也就是v=a(x)。商集U/IND(a)中v等價類的二進制粒表示為B(av)，B(av)的基數為|B(av)|。則av二進制粒表示為 (av， B(av))。信息系統S中任一av表示成二進制粒(av， B(av))的過程稱為信息系統的二進制粒化。

關聯規則提取是尋找給定關系中具有一定形式的關聯規則。對于給定的基本集，如果給定的關系中的個體出現次數大于最小的支持度，則該規則是可提取的。一般的提取關聯規則(A，B)的過程如下：首先計算所有可能的基本集A和B的組合形式；再統計某種可能形式出現在給定形式中的次數；然后找出在給定關系中出現次數頻率大于最小支持度的關聯規則。給定A和B，計算A B的二進制粒中出現1的個數是否大于最小的支持度，則該規則(A，B)是可提取的。

5 結語

在本文中，通過對粒計算理論進行深入的學習、分析和研究，并結合關聯規則提取的特點，對不同的信息粒進行二進制的與運算，根據所得結果的二進制數中1的個數來判斷該組合是否頻繁，然后從頻繁項集中進行關聯規則的提取。

參考文獻：

[1] L.A.Zadeh.Towards a theory of fuzzy information granulation and its centrality in human reasoning

and fuzzy logic， FuzzySets and Systems， 19， 1997：111-127.

[2] Z.Pawlak.Rough Sets，International Journal of Computer and Information Science，1982，11(5)：341-356.

[3] 劉清.Rough集及Rough推理[M].科學出版社，2001.

[4] Y.Y.Yao.Information granulation and Rough Set Approximation， International Journal of Intelligence Systems，16，87-104，2001

[5]卜東坡，等.聚類/分類中的粒度原理[J].計算機學報 Vol.25 No8 .

[6] 陸麗娜，陳亞萍.挖掘關聯規則算法的優化處理[J].計算機工程與應用，P99-101，2000.8.

[7] 操海燕，王志強.粗糙集屬性約簡算法研究[J].電腦知識與技術，P114-118，2007.1.

收稿日期：2008-03-27

作者簡介：王軍（1979-），男，江西彭澤人，助教，碩士，主要研究方向：數據庫、人工智能；王員云（1982-），女，江西臨川人，助教，碩士，主要研究方向：管理信息系統、軟件工程。

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