【数据挖掘】关联分析基本概念与术语

- 日理万妓 2022-01-16 13:37 574阅读 0赞

本文介绍数据挖掘中关联分析的基本概念与基本术语。

## 基本概念与术语 ##

#### 1. 事务： ####

一条数据也叫一条事务(transaction)，数据的ID即事务的ID，简写为TID，表6-1是购物篮事务的例子，可以理解为顾客的购物记录。  
![在这里插入图片描述][2019061520180643.png]

#### 2. 二元表示 （这个术语暂时不理解也没关系） ####

如表6-2所示，每行对应一个事务，每一列对应一个项。  
项用**二元变量**表示：如果项在事务中出现，则它的值是1，否则为0。  
因为通常认为项在事务中出现比不出现更重要，所以项是**非对称(asymmetric)二元变量**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

#### 3. 关联分析(association analysis)： ####

用于发现隐藏在大型数据之中的有意义的联系。  
所发现的联系可以用关联规则(association rule)或者频繁项集表示。  
表6-1可以提取出如下规则：  
\{尿布\} → \{啤酒\}  
表示尿布和啤酒之间存在着很强的联系，因为很多购买尿布的顾客也购买了啤酒。

#### 4. 项集和支持度计数 ####

令 I = \{ i 1 , i 2 , … , i d \} I=\\\{i\_1, i\_2, …, i\_d\\\} I=\{ i1,i2,…,id\}是数据中所有项的集合， T = \{ t 1 , t 2 , … , t N \} T = \\\{t\_1, t\_2, …, t\_N\\\} T=\{ t1,t2,…,tN\} 是所有事务的集合，则每个事务 t i t\_i ti包含的项集都是I的子集。  
在关联分析中，包含0个或多个的项的集合叫 **项集(itemset)** 。如果一个项集包含了k个项，则称它为 k-项集。  
项集的 **支持度计数 σ ( X ) σ(X) σ(X)** ：（X表示某项集）  
![在这里插入图片描述][20190615202346643.png]  
支持度计数表示包含了项集X的事务个数。

#### 5. 关联规则： ####

关联规则是形如 X → Y X → Y X→Y 的蕴涵表达式，其中 X 和 Y 是不相交的项集。  
关联规则的强度可以用它的 **支持度(support)** 和 **置信度(confidence)** 度量。  
**支持度 ( s )** 表示同时包含项集 X、Y 的事务总数，即该规则在总数据集出现的频繁程度。  
**置信度 ( c )** 表示 Y 在包含项集 X 的事务中出现的频繁程度。  
他们的计算公式如下：  
![在这里插入图片描述][20190615202407421.png]  
N: 事务总数

由公式(6-1)可以看出，规则  X → Y X → Y X→Y 的支持度仅依赖于其对应项集 X ∪ Y X∪Y X∪Y的支持度，因此为了提高效率，避免不必要的计算，目前的大多数关联规则挖掘算法都将关联规则挖掘任务分解为以下两个主要的子任务：  
**1. 频繁项集产生**：目标是发现满足最小支持度阈值的所有项集，这些项集称作**频繁项集(frequent itemset)**。  
**2. 规则的产生**：目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称为**强规则(strong rule)**。  
这样就避免了非频繁项集置信度的计算，节省了很多时间。

然而，频繁项集产生所需要的计算量也是很大的，发现频繁项集的一种原始方法是确定每个 **候选项集(candidate itemset)** 的支持度计数。为了完成这一任务，必须将每个候选项集与每个事务进行比较，计算每个候选项集的支持度，这个过程中也包含着很多不必要的计算，因此还需要降低频繁项集的计算复杂度，目前常用以下两种方法：  
1. 减少候选项集的数目：常用基于[先验(apriori)原理的算法][apriori]。  
2. 减少比较次数：使用更高级的数据结构，用于存储候选项集或压缩数据集。

#### 6. 格结构(lattice structure) ####

格结构常常被用来枚举所有可能的项集。图 6-1 是  I = \{ a , b , c , d , e \} I=\\\{a, b, c, d, e\\\} I=\{ a,b,c,d,e\}的项集格。一般包含k个项的数据集可能产生 2 k − 1 2^k - 1 2k−1个项集，不包括空集在内。所以当 k 非常大时，项集的搜索空间是指数规模的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]

参考资料：  
《数据挖掘导论》

[2019061520180643.png]: /images/20220114/bdd34303ed3848118c867409cd782d65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220114/0988931629564906ae7d63120b6456b4.png
[20190615202346643.png]: /images/20220114/3931751864564f37bc5d7ac829704f1f.png
[20190615202407421.png]: /images/20220114/b2921cc745fc43ac8d3c543007f813c8.png
[apriori]: https://steve.blog.csdn.net/article/details/92198700
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20220114/0d9883e9744b44748436c70bf178f5a0.png