频繁项集挖掘之Eclat算法

1.Eclat算法

Eclat算法用于执行项集挖掘。项集挖掘让我们在数据中找到频繁的模式，就像消费者购买牛奶一样，他也会购买面包。这种类型的模式称为关联规则，用于许多应用领域。

Eclat算法的基本思想是使用tidset交集来计算候选项集的支持，从而避免生成前缀树中不存在的子集。它最初是由Zaki，Parthasarathy等人提出的。

算法

Eclat算法是递归定义的。初始调用时使用所有单个项及其tidsets。在每次调用中，函数IntersectTidsets将验证每个项集-tidset对与所有的其他对，以生成新的候选集。如果新的候选集是频繁的，它将被添加到集合中。然后，迭代地，它将找到所有在X的分支上的频繁项集。该算法搜索使用深度优先搜索策略DFS以发现所有的频繁项集。

实现

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

用法

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

参数

data

类事务或任何可以强制转换为事务的任何数据集结构对象（例如，二分类矩阵，数据框）.

parameter

ECparameter类或命名列表的对象 (默认值为: 支持度 0.1 和 最大长度 5)

control

ECcontrol类或算法控件的命名列表的对象。

Value

返回类itemsets的一个对象

示例

data("Adult")

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

可视化

arules包为itemset实现了一些可视化方法，这些方法是eclat算法的返回类型。这里有些例子：

示例1：

library(arules)
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的结果：

> inspect(f)
     items     support count
[1]  {b,c,e}   0.1     1    
[2]  {a,b,c}   0.1     1    
[3]  {a,c}     0.2     2    
[4]  {b,c}     0.2     2    
[5]  {c,e}     0.2     2    
[6]  {a,b,d,e} 0.1     1    
[7]  {a,d,e}   0.2     2    
[8]  {b,d,e}   0.1     1    
[9]  {a,b,d}   0.3     3    
[10] {a,d}     0.4     4    
[11] {b,d}     0.3     3    
[12] {d,e}     0.2     2    
[13] {a,b,e}   0.1     1    
[14] {a,e}     0.2     2    
[15] {b,e}     0.3     3    
[16] {a,b}     0.5     5    
[17] {a}       0.7     7    
[18] {b}       0.7     7    
[19] {e}       0.5     5    
[20] {d}       0.4     4    
[21] {c}       0.4     4

用例

要查看使用Eclat算法的一些真实示例，将使用来自northwind数据库的一些数据。 northwind数据库可免费下载并代表企业的数据。 在此示例中，将使用数据库中的表顺序详细信息。 订单明细表用于将订单与产品相关联（以n到n的关系）。 Eclat算法将用于从该数据中查找频繁模式，以查看是否有任何产品一起购买。

脚本

给定来自northwind数据库的订单详细信息表中的数据，找到支持= 0.1且长度至少为2的所有频繁项集。

输入数据

订单明细表包含以下字段：

ID：主键

Order ID： 来自订单表的外键

Product ID：来自产品表的外键

Quantity：购买数量

Discount：提供的折扣

Unit Price：产品单价

要使用这些数据，需要进行一些预处理。 该表可能有许多属于同一订单的行，因此表的转换方式使得一个订单的所有行只变成新表中包含属于该订单的产品的产品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％。

产品编号11,42和72分别代表产品Queso Cabrales，Singaporean Hokkien Fried Mee和Mozzarella di Giovanni。 因此，eclat算法的输出表明了购买这些物品的强烈频繁商店模式。

变化

PPV, PrePost, and FIN 算法

这三种算法由Deng等[1] [2] [3]提出，并基于三种新颖的数据结构，分别称为Node-list [1]，N-list [2]和Nodeset [3]。 频繁项集的挖掘过程。 它们是FP树中的节点集，每个节点使用预先顺序遍历和后序遍历进行编码。 与节点列表相比，N列表和节点集更有效。 这导致PrePost [2]和FIN [3]的效率高于PPV [1]的效率。 有关详细信息，请参见[1] [2] [3]。

References[edit]

• Hahsler, M.; Buchta, C.; Gruen, B. & Hornik, K. arules: Mining Association Rules and Frequent Itemsets. 2009.
• Hahsler, M.; Gruen, B. & Hornik, K. arules -- A Computational Environment for Mining Association Rules and Frequent Item Sets. Journal of Statistical Software, 2005, 14, 1-25
• Mohammed Javeed Zaki, Srinivasan Parthasarathy, Wei Li. A Localized Algorithm for Parallel Association Mining. SPAA 1997: 321-330.
• Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li. New Algorithms for Fast Discovery of Association Rules. KDD 1997: 283-286.
• Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li. Parallel Algorithms for Discovery of Association Rules. Data Min. Knowl. Discov. 1(4): 343-373 (1997).
• Christian Borgelt (2003) Efficient Implementations of Apriori and Eclat. Workshop of Frequent Item Set Mining Implementations (FIMI 2003, Melbourne, FL, USA).

1. ↑ Jump up to:a b c d Deng, Z. & Wang, Z. A New Fast Vertical Method for Mining Frequent Patterns [1]. International Journal of Computational Intelligence Systems, 3(6): 733 - 744, 2010.
2. ↑ Jump up to:a b c d Deng, Z.; Wang, Z. & Jiang, J. A New Algorithm for Fast Mining Frequent Itemsets Using N-Lists [2]. SCIENCE CHINA Information Sciences, 55 (9): 2008 - 2030, 2012.
3. ↑ Jump up to:a b c d Deng, Z. & Lv, S. Fast mining frequent itemsets using Nodesets [3]. Expert Systems with Applications, 41(10): 4505–4512, 2014.