R語言中的資料探勘演算法/頻繁模式挖掘/Eclat演算法

簡介

Eclat演算法

Eclat演算法用於執行項集挖掘。項集挖掘使我們能夠在資料中找到頻繁模式，例如，如果消費者購買牛奶，他也會購買麵包。這種型別的模式稱為關聯規則，並用於許多應用領域。

Eclat演算法的基本思想是使用tid集交集來計算候選項集的支援度，避免生成字首樹中不存在的子集。它最初由Zaki、Parthasarathy等人提出。

演算法

Eclat演算法是遞迴定義的。初始呼叫使用所有具有其tid集的單個專案。在每次遞迴呼叫中，函式IntersectTidsets驗證每個項集-tid集對 $\left\langle {X,t(X)}\right\rangle$ 與所有其他對 $\left\langle {Y,t(Y)}\right\rangle$ 以生成新的候選 $N_{XY}$ 。如果新的候選頻繁，則將其新增到集合 $P_{X}$ 中。然後，遞迴地，它在 $X$ 分支中查詢所有頻繁項集。該演算法以DFS方式搜尋以找到所有頻繁集。

實現

Eclat演算法可以在R系統的arule包中找到。

   * R package: arules
   * Method: eclat
   * Documentation : arules package

用法

eclat(data, parameter = NULL, control = NULL)

引數

data: transactions類物件或任何可以強制轉換為transactions的資料結構（例如，二進位制矩陣、data.frame）。

parameter: ECparameter類物件或命名列表（預設值為：support 0.1和maxlen 5）

control: ECcontrol類物件或命名列表，用於演算法控制。

返回值

返回itemsets類物件

示例

data("Adult")

## Mine itemsets with minimum support of 0.1.
itemsets <- eclat(Adult, parameter = list(supp = 0.1, maxlen = 15))

視覺化

arules包為項集實現了某些視覺化方法，這些方法是Eclat演算法的返回型別。以下是一些示例

示例1

data("Adult") 

## Mine frequent itemsets with Eclat.
fsets <- eclat(Adult, parameter = list(supp = 0.5))

## Display the 5 itemsets with the highest support.
fsets.top5 <- sort(fsets)
inspect(fsets.top5)

## Get the itemsets as a list
as(items(fsets.top5), "list")

## Get the itemsets as a binary matrix
as(items(fsets.top5), "matrix")

## Get the itemsets as a sparse matrix, a ngCMatrix from package Matrix.
## Warning: for efficiency reasons, the ngCMatrix you get is transposed
as(items(fsets.top5), "ngCMatrix")

示例2

## Create transaction data set.
data <- list(
  c("a","b","c"),
  c("a","b"),
  c("a","b","d"),
  c("b","e"),
  c("b","c","e"),
  c("a","d","e"),
  c("a","c"),
  c("a","b","d"),
  c("c","e"),
  c("a","b","d","e")
)

t <- as(data, "transactions")

## Mine itemsets with tidLists.
f <- eclat(data, parameter = list(support = 0, tidLists = TRUE))

## Get dimensions of the tidLists.
dim(tidLists(f))

## Coerce tidLists to list.
as(tidLists(f), "list")

## Inspect visually.
image(tidLists(f))

##Show the Frequent itemsets and respectives supports
inspect(f)

示例2的結果

#	專案	支援度
1	{b, c, e}	0.1
2	{a, b, c}	0.1
3	{a, c}	0.2
4	{b, c}	0.2
5	{c, e}	0.2
6	{a, b,d, e}	0.1
7	{a, d, e}	0.2
8	{b, d, e}	0.1
9	{a, b, d}	0.3
10	{a, d}	0.4
11	{b, d}	0.3
12	{d, e}	0.2
13	{a, b, e}	0.1
14	{a, e}	0.2
15	{b, e}	0.3
16	{a, b}	0.5
17	{a}	0.7
18	{b}	0.7
19	{e}	0.5
20	{d}	0.4
21	{c}	0.4

用例

為了檢視Eclat演算法使用的一些實際示例，我們將使用來自northwind資料庫的一些資料。northwind資料庫可免費下載，並表示企業資料。在本示例中，我們將使用資料庫中的訂單明細表。訂單明細表用於將訂單與產品相關聯（在多對多關係中）。Eclat演算法將用於從此資料中查詢頻繁模式，以檢視是否存在一起購買的任何產品。

場景

給定來自northwind資料庫訂單明細表的資料，查詢所有支援度=0.1且長度至少為2的頻繁項集。

輸入資料

訂單明細表包含以下欄位

ID: 主鍵
訂單ID: 來自Orders表的外部鍵
產品ID: 來自Products表的外部鍵
數量: 購買的數量
折扣: 提供的折扣
單價: 產品的單價

要使用資料，需要進行一些預處理。該表可能包含許多屬於同一訂單的行，因此該表被轉換為以下方式：一個訂單的所有行在新的表中僅成為一行，其中包含屬於該訂單的產品ID。欄位ID、訂單ID、數量、折扣和單價被丟棄。資料儲存在名為northwind-orders.txt的txt檔案中。該檔案以一種方式編寫，以便在R中作為列表物件載入。

實現

要執行示例，需要在R中載入arules包。

首先，資料在R中載入到列表物件中

## 1041 transactions is loaded, the listing below was shortened
## some duplicates transactions was introduced to produce some results for the algorithm
data = list(
 c("2","3","4","6","7","8","10","12","13","14","16","20","23","32","39","41","46","52","55","60","64","66","73","75","77"),
 c("11","42","72"),
 c("14","51"),
 c("41","51","65"),
 c("22","57","65"),
 ...)

其次，使用Eclat演算法。

itemsets <- eclat(data, parameter = list(support = 0.1, minlen=2, tidLists = TRUE, target="frequent itemsets"))

parameter specification:
 tidLists support minlen maxlen            target   ext
     TRUE     0.1      2      5 frequent itemsets FALSE

algorithmic control:
 sparse sort verbose
      7   -2    TRUE

eclat - find frequent item sets with the eclat algorithm
version 2.6 (2004.08.16)         (c) 2002-2004   Christian Borgelt
create itemset ... 
set transactions ...[78 item(s), 1041 transaction(s)] done [0.00s].
sorting and recoding items ... [3 item(s)] done [0.00s].
creating bit matrix ... [3 row(s), 1041 column(s)] done [0.00s].
writing  ... [4 set(s)] done [0.00s].
Creating S4 object  ... done [0.00s].

輸出資料

itemsets物件儲存Eclat演算法執行的輸出。如上所示，生成了4個集合。要檢視結果，可以使用

inspect(itemsets)

  items   support
1 {11,           
   42,           
   72}  0.1940442
2 {42,           
   72}  0.1940442
3 {11,           
   42}  0.1940442
4 {11,           
   72}  0.1959654

分析

如上所示，eclat演算法的結果有4個頻繁項集。這個輸出是由資料中多次重複事務{11, 42, 72}引起的。結果表明，元組{11,42,72}、{42,72}和{11,42}的支援度為19.40%；元組{11,72}的支援度為19.60%。

產品ID 11、42和72分別代表產品Queso Cabrales、Singaporean Hokkien Fried Mee和Mozzarella di Giovanni。因此，eclat演算法的輸出表明，購買這些商品一起的購物模式非常頻繁。

變體

PPV、PrePost和FIN演算法

這三種演算法由Deng等人提出^[1] ^[2] ^[3]，並基於三種新穎的資料結構，分別稱為節點列表^[1]、N列表^[2]和節點集^[3]，以方便頻繁項集的挖掘過程。它們是FP樹中節點的集合，每個節點都使用先序遍歷和後序遍歷進行編碼。與節點列表相比，N列表和節點集效率更高。這導致PrePost^[2]和FIN^[3]的效率高於PPV^[1]。更多細節請參見^[1] ^[2] ^[3]。

參考文獻

Hahsler, M.；Buchta, C.；Gruen, B. & Hornik, K. arules：挖掘關聯規則和頻繁項集。2009年。
Hahsler, M.；Gruen, B. & Hornik, K. arules -- 挖掘關聯規則和頻繁項集的計算環境。《統計軟體雜誌》，2005年，14卷，1-25頁。
Mohammed Javeed Zaki，Srinivasan Parthasarathy，Wei Li。用於並行關聯挖掘的區域性演算法。SPAA 1997：321-330。
Mohammed Javeed Zaki，Srinivasan Parthasarathy，Mitsunori Ogihara，Wei Li。快速發現關聯規則的新演算法。KDD 1997：283-286。
Mohammed Javeed Zaki，Srinivasan Parthasarathy，Mitsunori Ogihara，Wei Li。關聯規則發現的並行演算法。《資料探勘與知識發現》，1卷（4期）：343-373（1997）。
Christian Borgelt（2003）Apriori和Eclat的有效實現。頻繁項集挖掘實現研討會（FIMI 2003，美國佛羅里達州梅爾本）。

↑ ^a ^b ^c ^d Deng，Z. & Wang，Z. 用於挖掘頻繁模式的一種新的快速垂直方法[1]。《國際計算智慧系統雜誌》，3卷（6期）：733-744，2010年。
↑ ^a ^b ^c ^d Deng，Z.；Wang，Z. & Jiang，J. 使用N列表快速挖掘頻繁項集的一種新演算法[2]。《中國科學資訊科學》，55卷（9期）：2008-2030，2012年。
↑ ^a ^b ^c ^d Deng，Z. & Lv，S. 使用節點集快速挖掘頻繁項集[3]。《應用專家系統》，41卷（10期）：4505–4512，2014年。

[Deng2010-1] Deng，Z. & Wang，Z. 用於挖掘頻繁模式的一種新的快速垂直方法[1]。《國際計算智慧系統雜誌》，3卷（6期）：733-744，2010年。

[Deng2012-2] Deng，Z.；Wang，Z. & Jiang，J. 使用N列表快速挖掘頻繁項集的一種新演算法[2]。《中國科學資訊科學》，55卷（9期）：2008-2030，2012年。

[Deng2014-3] Deng，Z. & Lv，S. 使用節點集快速挖掘頻繁項集[3]。《應用專家系統》，41卷（10期）：4505–4512，2014年。

[1]

[2]

[3]