类矩阵运算

类矩阵运算

掌握Apriori算法的基本概念：Apriori algorithm is the first algorithm in association rule mining, which is widely recognized for its classical status. It employs an iterative approach to analyze itemset relationships within databases, ultimately generating association rules. The process involves connecting matrix operations and pruning unnecessary intermediate results.

理解关联规则apriori算法：

一、概念

表1 某超市内的交易数据库其对应的交易号TID及顾客购买的商品信息其对应的交易号TID及顾客购买的商品信息

T1bread, cream, milk, teaT6bread, tea

T2bread, cream, milkT7beer, milk, tea

T3cake, milkT8bread, tea

T4milk, teaT9bread, cream, milk, tea

T5bread, cake, milkT10bread, milk, tea

令I={i₁,i₂,…,iₘ}是一个包含m个不同项目的集合，则每一个iₖ都被称作一个项目。这样的项目集合I则被称为项集，并被定义为其元素的数量即为项集的长度；长度为k的项集则被称为k-项集。以示例而言，在其中每一个商品都相当于一个单独的项目，则这些项目的集合被称为项集I={bread, beer, cake, cream, milk, tea}；该项集共有6个元素构成。

定义二：每笔交易T属于项集I的一个子集。每个交易都有一个唯一的标识符TID。所有这些构成了一个名为D的事务数据库，在这种情况下, |D|表示事务的数量.例如, 在示例中包含了10笔不同的事务, 因此有|D|=10.

定义三

support(X)=count(X⊆T)/|D|

引例中X={bread, milk}出现在T1，T2，T5，T9和T10中，所以支持度为0.5。

定义四指出：最小的支持度被视为项集中的最低阈值；它反映了用户对关联规则所关注的最低重要性。用SUPmin表示这一阈值。当一个项集其支持度达到或超过SUPmin时，则被称为频繁集合；这样的集合则被称为k-频繁集合（其中k为其长度）。例如，在设置SUPmin=0.3的情况下，请考虑以下示例：其中{bread, milk}这一组合的支持度计算结果为0.5；因此可以确定其属于2-频繁集合。

定义五：关联规则是一个蕴含式：

R：X⇒Y

其中X \subset I和Y \subset I均为I中的子集，并且满足X \cap Y = \emptyset。这表明项集X在某一笔交易中出现时，则会伴随有概率地呈现项集Y。对于用户而言，关联规则可以通过两个指标来评估：即支持度与可信度。

定义六：关联规则R的支持度是交易集同时包含X和Y的交易数与|D|之比。即：

support(X⇒Y)=count(X⋃Y)/|D|

发生概率表示X和Y同时发生的可能性。关联规则的发生概率等于频繁集的发生概率。

定义七：对于关联规则R来说，其置信度被定义为同时包含项X和项Y的事务总数与仅包含项X的事务总数的比例；即，在计算置信度时我们采用前者除以后者的计算方式。

confidence(X⇒Y)=support(X⇒Y)/support(X)

可信度即为交易中若含有X则同时含有Y的概率。通常情况下,仅限于那些具有较高支持度和可信度的关联规则才是用户关注的重点.

将关联规则的最小支持度与最小可信度分别设定为SUP_min 和 CONF_min（MinSup, MinConf）。其中当一个关联规则R的支持度不低于 SUP_min 且可信度不低于 CONF_min 时，则称其为强关联规则（strong association rule）。其目的是为了发现所有满足强关联规则的关系式，并据此指导商家进行决策（guide business decision-making）。

这八个概念涵盖了关联规则的相关内容；关联规则挖掘主要涉及解决两个核心问题：一是找出交易数据库中所有满足最小支持度要求的频繁项集，并且能够高效地处理大规模数据；二是确保所发现的关联规则具有较高的可信度和重要性。

基于频繁项集生成所需关联规则的过程，并通过设置最小的信任度标准来筛选出强关联规则。

当前研究人员普遍致力于解决第一个问题。识别频繁项集具有挑战性，并且一旦获得频繁项集后，则相对容易地生成强关联规则。

二、理论基础

首先来看一个频繁集的性质。

定理：如果项目集X是频繁集，那么它的非空子集都是频繁集。

基于定理

三、算法步骤：

首先是测试数据：交易ID商品ID列表

T100I1，I2，I5

T200I2，I4

T300I2，I3

T400I1，I2，I4

T500I1，I3

T600I2，I3

T700I1，I3

T800I1，I2，I3，I5

T900I1，I2，I3

算法的步骤图：

可以看到，第三轮的候选集发生了明显的缩小，这是为什么呢？

请注意取候选集的两个条件：

成为连接的两个必要条件是它们共享了K-1个相同的项目。因此,(I2,I4)与(I3,I5)这对无法建立联系。从而减少了可选配对的数量。

2. 如果一个集合是频繁集合，则该集合不可能包含非频繁的子项集合。例如，在两个组合（I₁,I₂）与（I₁,I₄）生成一个新的组合（I₁,I₂,I₄），而这个新组合中的子项集合（I₁,I₄）并非频繁集合的存在表明原始集合仅包含必要的关联规则。进一步缩减了候选集合。

第三轮得到的2个候选集，正好支持度等于最小支持度。所以，都算入频繁集。

这时再看第四轮的候选集与频繁集结果为空

可以观察到，在计算过程中发现候选集合与频繁集合均为空集。这是因为经过第三阶段的计算后将频繁集合进行自连接操作得到{I1, I2, I3, I5}；然而其包含子集合{I2, I3, I5}这一非频繁子集的存在导致该主集合最终也被剪枝删去；因此导致整个算法提前终止；最终所得结果为最后一次计算所确定的高频集合。

也就是：['I1,I2,I3', 'I1,I2,I5']

四、代码：

生成Python代码实现Apriori算法。需要注意以下两点：基于Apriori算法的特点是项集内的项目需按字典序排列，而集合自身不具备这种顺序特性；因此，在适当的情况下我们需要将集合转换为列表以满足算法的要求。

因为要在字典中记录项集的支持度值，并且需要以项集作为键值存储于字典中；而由于不可变集合不能被用作字典的键，在适当的时候应当将项集转换为不可变集合形式frozenset。def local_data(file_path): import pandas as pd

dt = pd.read_excel(file_path)

data = dt['con']

locdata = [] for i in data:

locdata.append(str(i).split(",")) # print(locdata) # change to [[1,2,3],[1,2,3]]

length = [] for i in locdata:

length.append(len(i)) # 计算长度并存储

print(length)

ki等于长度序列在最大值位置处的元素；输出长度序列在该位置处的元素；长度序列中取得最大值的位置之后再获取该位置处的元素

return locdata,kidef create_C1(data_set): """

Create frequent candidate 1-itemset C1 by scaning data set.

Args:

data_set: A database containing a collection of transaction records. Each transaction record includes multiple item descriptions.

Returns:

C1: A set which contains all frequent candidate 1-itemsets """

C1 = set() for t in data_set: for item in t:

item_set = frozenset([item])

C1.add(item_set) return C1def is_apriori(Ck_item, Lksub1): """

Judge whether a frequent candidate k-itemset satisfy Apriori property.

Args:

Ck_item: a frequent candidate k-itemset in Ck which contains all frequent

candidate k-itemsets.

Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.

Returns:

True: satisfying Apriori property.

False: Not satisfying Apriori property. """

for item in Ck_item:

sub_Ck = Ck_item - frozenset([item]) if sub_Ck not in Lksub1: return False return Truedef create_Ck(Lksub1, k): """

Create Ck, a set which contains all all frequent candidate k-itemsets

by Lk-1's own connection operation.

Args:

Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.

k: the item number of a frequent itemset.

Return:

Ck: a set which contains all all frequent candidate k-itemsets. """

Ck = set()

len_Lksub1 = len(Lksub1)

list_Lksub1 = list(Lksub1) for i in range(len_Lksub1): for j in range(1, len_Lksub1):

l1 = list(list_Lksub1[i])

l2 = list(list_Lksub1[j])

l1.sort()

l2.sort() if l1[0:k-2] == l2[0:k-2]:

Ck_item = list_Lksub1[i] | list_Lksub1[j] # pruning

if is_apriori(Ck_item, Lksub1):

Ck.insert(C_k_item) returns C_kdef generate_L_k_by_C_k(data_set, C_k, min_support, support_data):

Generate Lk by executing a delete policy from Ck.

Args:

This dataset comprises a collection of transactions. Every transaction includes multiple items.

Ck: A set which contains all all frequent candidate k-itemsets.

min_support: The minimum support.

支持数据集：表示为字典。其中键是频繁项集，并且值是支持

Returns:

Lk: A set which contains all all frequent k-itemsets. """

Lk = set()

初始化item_count为一个空字典；然后遍历数据集data_set中的每一个元素t；接着对于集合Ck中的每一个元素item；如果该集合是t的一个子集；则将该元素加入到item_count中。

item_count[item] = 1 else:

item_count[item] += 1

计算数据集的大小t_num为浮点数，并遍历每一个项item。对于每一个项item，在满足条件（即某项的频率除以总数据量的比例至少达到最小支持阈值min_support）的情况下执行后续操作

Lk.add(item)

support_data[item] = (item_count[item] / t_num) return Lkdef generate_L(data_set, k, min_support): """

Generate all frequent itemsets.

Args:

我们定义数据集为一系列由多个交易组成的集合

k: Maximum number of items for all frequent itemsets.

min_support: The minimum support.

Returns:

L: The list of Lk.

support_data为一个字典类型变量

support_data = {}

C1 = create_C1(data_set)

L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)

Lksub1 = L1.copy()

L = []

L.append(Lksub1) for i in range(2, k+1):

Ci = create_Ck(Lksub1, i)

Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)

Lksub1 = Li.copy()

将L中的元素Lksub1添加进去后返回列表L及其相关支持数据support_data。
该函数体接受三个参数：输入列表L、支持数据support_data以及最小置信度min_conf，并以空括号结束。

Generate big rules from frequent itemsets.

Args:

L: The list of Lk.

data object: a data structure. The key field is for frequent itemsets, while the value field corresponds to their support.

min_conf: Minimal confidence.

Returns:

big_rule_list: A comprehensive list that encompasses all significant rules. Every major rule is expressed within this structure.

as a 3-tuple. """

big_rule_list = []

初始化子集列表为空
遍历索引i从0到L的长度-1
对于每个索引i对应的集合freq_set
遍历子集列表中的每个子集sub_set
如果子集sub_set包含于freq_set中

conf = support_data[freq_set] / support_data[freq_set - sub_set]

big_rule被赋值为差集以及子集元组（freq_set - sub_set）与子集sub_set和置信度conf的元组；如果满足置信度大于等于阈值min_conf以及该规则不在列表中，则继续；最后将该规则添加到列表中。

sub_set_list.append(freq_set) return big_rule_listif name == "main": """

Test """

file_path = "test_aa.xlsx"

data_set,k = local_data(file_path)

L, support_data = generate_L(data_set, k, min_support=0.2)

big_rules_list = generate_big_rules(L, support_data, min_conf=0.4) 输出结果：print(L) 遍历规则集中的每个元素：for Lk in L: 如果当前规则集为空，则退出循环：if len(list(Lk)) == 0: break

print("="*50)
print("common " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport")
print("="*50)
for freq_set in Lk:
print(freq_set, support_data[freq_set])
print()
print("Major Association Rules")
for item in big_rules_list:
lhs, rhs = item[0], item[1]
conf = item[2]
print(f"{lhs} → {rhs}, confidence: {conf}")

文件格式：

test_aa.xlsxname con

T1 2,3,5T2 1,2,4T3 3,5T5 2,3,4T6 2,3,5T7 1,2,4T8 3,5T9 2,3,4T10 1,2,3,4,5