用Matlab实现apriori算法关联规则的挖掘程序，完整有详细注解

下面这段是apriori算法中由2频繁项集找k频繁项集的程序，程序中有两个问题：

1、似乎while循环的K永远都是固定的，也就是都是频繁2项集的个数。得到频繁3项集后K的个数不是要变吗？如何体现呢？

2、程序中有两个for的大循环，但是发现结果是只要找到一个频繁3项集第二个for循环就会结束，但是其实还应该有其它的频繁3项集。for循环不是应该无条件执行到参数k结束吗？当时k值是15，可是程序结束的时候i=2，j=3,然后j就不执行4以及一直到k的部分了。是什么原因呢？麻烦高手指点一下。急啊……

while( k>0)

le=length(candidate{1})

num=2

nl=0

for i=1:k-1

for j=i+1:k

x1=candidate{i} %candidate初始值为频繁2项集，这个表示频繁项集的第i项

x2=candidate{j}

c = intersect(x1, x2)

M=0

r=1

nn=0

l1=0

if (length(c)==le-1) & (sum(c==x1(1:le-1))==le-1)

houxuan=union(x1(1:le),x2(le))

%树剪枝,若一个候选项的某个K-1项子集为非频繁，则剪枝掉

sub_set=subset(houxuan)

%生成该候选项的所有K-1项子集

NN=length(sub_set)

%判断这些K-1项自己是否都为频繁的

while(r &M<NN)

M=M+1

r=in(sub_set{M},candidate)

end

if M==NN

nl=nl+1

%候选k项集

cand{nl}=houxuan

%记录每个候选k项集出现的次数

le=length(cand{1})

for i=1:m

s=cand{nl}

x=X(i,:)

if sum(x(s))==le

nn=nn+1

end

end

end

end

%从候选集中找频繁项集

if nn>=th

ll=ll+1

candmid{nl}=cand{nl}

pfxj(nl).element=cand{nl}

pfxj(nl).time=nn

disp('得到的频繁项集为:')

result=(candmid{nl})

disp(result)

end

end

end

end

学号：17020110019    姓名：高少魁

【嵌牛导读】关联规则挖掘算法是数据挖掘中的一种常用算法，用于发现隐藏在大型数据集中令人感兴趣的频繁出现的模式、关联和相关性。这里将对该算法进行简单的介绍，之后通过Apriori算法作为实例演示算法执行结果。

【嵌牛鼻子】数据挖掘    关联规则挖掘    python

【嵌牛正文】

一、算法原理

1、基本概念

关联规则用于发现隐藏在大型数据集中令人感兴趣的频繁出现的模式、关联和相关性。 而 Apriori算法则是经典的挖掘频繁项集的关联规则算法，它通过层层迭代来寻找频繁项集，最后输出关联规则：首先扫描数据集，得到 1-频繁项集，记为 L1，通过合并 L1得到 2-频繁项集 L2，再通过 L2找到 L3，如此层层迭代，直到找不到频繁项集为止。

在Apriori算法中，定义了如下几个概念：

⚫ 项与项集 ：设 I={i1,i2,…,im}是由 m个不同项构成的集合，其中的每个 ik(k=1,2,…,m)被称为一个项 (Item)，项的集合 I被称为项集和，即项集。在实验中，每一条购物记录可以被看做 一个项集，用户购买的某个商品即为一个项。

⚫ 事务与事务集：事务 T是项集 I的一个子集，而事务的全体被称为事务集。

⚫ 关联规则：形如 A=>B的表达式，其中， A和 B都属于项集 I，且 A与 B不相交。

⚫ 支持度：定义如下 support(A=>B) = P(A B)，即 A和 B所含的项在事务集中同时出现的概率。

⚫ 置信度：定义如下 confidence(A⇒B)=support(A⇒B)/support(A)=P(A B)/P(A)=P(B|A)，即如果事务包含 A，则事务中同时出现 B的概率。

⚫ 频繁项集：如果项集 I的支持度满足事先定义好的最小支持度阈值（即 I的出现频度大于相应的最小出现频度阈值），则 I是频繁项集。

⚫ 强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。

根据以上概念，要实现关联规则的挖掘，首先要找到所有的频繁项集，之后找出强关联规则（即通过多次扫描数据集，找出频繁集，然后产生关联规则）。

2、挖掘频繁项集

在该步骤中有两个较为重要的部分 ：连接和修剪。连接步骤即使用k-1频繁项集，通过连接得到 k-候选项集，并且只有相差一个项的项集才能进行连接，如 {A,B}和 {B,C}连接成为 {A,B,C}。修剪步骤基于一个性质：一个 k-项集，如果它的一个 k-1项集（子集）不是频繁的，那么它本身也不可能是频繁的。 因此可以基于这个性质，通过判断先验性质来对候选集进行修剪。

3、产生关联规则

经过连接和修剪之后，即找到了所有的频繁项集，此时可以在此基础上产生关联规则，步骤如下

（1）对于每个频繁项集 l，产生 l的所有非空子集（这些非空子集一定是频繁项集）；

（2）对于 l的每一个非空子集 x，计算 confidence(x =>(l-x))，如果 confidence(x =>(l-x)) confmin，那么规则 x =>(l-x)”成立。

二、算法设计

1、数据集

通过语句 import xlrd导入相关的库来进行数据的读取 。数据内容为十条购物记录 ，每条购物记录有若干个商品，表示某个顾客的购买记录 ，如图

对于数据加载部分 使用了 xlrd库中的函数 open_workbook来 打开一个表格文件，使用sheet_by_index函数得到一个工作表， row_values函数即可读取表格中的内容。由于每个购物记录的商品数不一定相同，导致读取的内容含有空格 (’ ’)，因此对数据进行删减以得到紧凑的数据 ，最终读取数据的结果以列表的形式返回。

2、连接

对于连接部分，主要目标是根据已有的k-1频繁项集生成 k-候选频繁项集。算法步骤为：首先将项集中的项按照字典顺序排序，之后将 k-1项集中两个项作比较，如果两个项集中前 k-2个项是相同的，则可以通过或运算（|）将它们连接起来。

3、修剪

修剪 *** 作主要使用一个判断函数，通过传入连接 *** 作后的项集和之前的k-1频繁项集，对新的项集中的每一个项的补集进行判断，如果该补集不是 k-1频繁项集的子集，则证明新的项集不满足先验性质，即一个频繁项集的所有非空子集一定是频繁的 ，否则就满足先验形式。返回布尔类型的参数来供调用它的函数作判断。

经过连接和修剪步骤之后，项基要成为频繁项集还必须满足最小支持度的条件，笔者设计了generateFrequentItems函数来对连接、修剪后产生的 k-候选项集进行判断，通过遍历数据集，计算其支持度，满足最小支持度的项集即是 一个频繁项集，可将其返回。

以上，经过不断的遍历、连接、修剪、删除，可将得到的所有结果以列表形式返回。笔者还设计了字典类型的变量 support_data，以得到某个频繁项集及其支持度 。

4、挖掘关联规则

generateRules函数用来挖掘关联规则，通过传入 最小置信度、 频繁项集及其 支持度来生成规则 。根据定理：对于频繁项集 l的每一个非空子集 x，计算 confidence(x =>(l-x))，如果 confidence(x =>(l-x)) confmin，那么规则 x =>(l-x)”成立，因此，该函数重点在扫描频繁项集，得到每一个子集，并计算置信度，当置信度满足条件（即大于等于最小置信度）时，生成一条规则。在函数中，使用了元组来表示一条规则，元组中包含 x、 l-x以及其置信度 ，最后返回生成的所有规则的列表。

三、算法执行结果

设置最大频繁项集数k为 3，最小支持度为 0.2，最小置信度为 0.8 使用 pycharm运行程序 ，得到以下结果：

由图中结果可以看出，对于频繁 1-项集，有五个满足的项集，频繁 2-项集有 6个，频繁 3-项集有 2个，它们都满足支持度大于或等于最小支持度 0.2。根据频繁项集，程序得到的关联规则有三条，即 {面包 }=>{牛奶 }，，{鸡蛋 }=>{牛奶 }，，{面包，苹果 }=>{牛奶 其中，这些规则的置信度都是 1.0，满足大于或等于最小置信度 0.8的条件 。

四、程序源码

当你双击一个TXT文件时，通常情况下系统会启动“记事本”打开这个文件。可是，当系统中安装的另一个应用程序接管了这个任务后，双击TXT文件，打开该文件的程序就会变成另外一个。我们说，这是文件关联发生了变化。如何关联文件，如何改变文件的关联，如何恢复文件的默认关联，如何取消文件的关联等问题是初学者常常感到为难和需要解决的问题。下文可以为你指点迷津。

文件关联就是将一种类型的文件与一个可以打开它的程序建立起一种依存关系。举个例子来说，位图文件(BMP文件)在Windows中的默认关联程序是“画图”，如果将其默认关联改为用ACDSee程序来打开，那么ACDSee就成了它的默认关联程序。一个文件可以与多个应用程序发生关联，我们可以利用文件的“打开方式”进行关联选择。我们也可以删除因误 *** 作而引起的错误文件关联，可以根据需要新建文件关联，在有些软件中还可以恢复文件的关联。下面就具体来谈谈文件关联的一些方法和技巧。

一、利用“打开方式”即时新建文件关联

用鼠标双击一个没有被任何程序关联的文件，桌面上就会d出一个“打开方式”的窗口。在这里就可以根据不同文件的打开方式选择合适的程序来打开文件了。这里要注意的是，如果在下面的“始终使用该程序打开这种类型的文件”前打勾，就会默认为当你双击这类文件时将自动启动那个被选中的程序来打开这类文件。

二、利用“文件夹选项”全面定制文件关联 应用程序和文档之间的文件关联是可以自己新建的：

打开Windows的“资源管理器”，选择系统菜单中的“查看”→“文件夹选项”→“文件类型”，在其中单击“新类型”，可以打开“添加新文件类型”窗口，在这里可以编辑新的文件类型。假定希望扩展名为AAA的文件用“记事本”程序打开，就可以在“相关扩展名”中输入AAA。点击“更改图标”按钮，可以选择自己喜欢的文件图标。因为是新建的文件类型，“ *** 作”栏中没有任何用来编辑或打开的程序。点击“新建”按钮就可以进行这项编辑。在d出的“新 *** 作”窗口的“ *** 作”栏中输入open，为默认的打开命令，在“用于执行 *** 作的应用程序”栏中输入打开程序的路径，也可以通过“浏览”按钮进行选择(这里使用“记事本”作为编辑程序)。好了，新建一个扩展名为AAA的文件看看，是不是可以用“记事本”直接打开了？

三、为一个文档建立多个程序关联 当一个文档与多个应用程序建立了关联后，在右键菜单中会形成多个不同的打开该文档的程序选项，这样可以根据不同需要选择不同的方式打开文件。为一个文档建立多个程序关联的方法与第二项中提到的方法相同，只是重复几个过程罢了。这里不再赘述。

四、更改文件关联的方法 要关联一个已经被关联的文件，可以在用鼠标右键单击这个文件的同时按住Shift键不放，这样在d出的菜单中就会出现一个“打开方式”的选项，选中这一项会d出“打开方式”的窗口，同样可以选择其中的一个程序作为它的默认打开方式。

上面说的是Windows 98的情况，在Windows 2000以上版本中不需要按Shift键，直接用右键菜单选择打开程序。

五、删除误 *** 作的文件关联选项 有时我们可能会误把图片类文件当作文本文件用“记事本”程序打开，那么在这类图片文件的“打开方式”菜单中就会出现“记事本”一项，非常讨厌。这时可以通过修改注册表来删除误 *** 作的文件关联项目。方法如下：

打开“注册表编辑器”，找到[HKEY_CURRENT_USER＼Software＼Microsoft＼Windows＼CurrentVersion＼Explorer＼FileExts]子键，再选择要修改的“打开方式”菜单的扩展名的子项，然后选择该子项中的OpenwillList,删除右侧窗口中误编辑的程序的键值后，重新启动电脑就可以了。

启动“注册表编辑器”的方法是，在“开始”菜单的“运行”命令框中键入regedit，然后回车。

六、恢复常用软件的文件关联 你可能会遇到这样的情况，当安装了一个新软件后，原来熟悉的文件图标突然改变了，打开它的程序也不是原来的了。其实，如果你想要恢复原来的默认打开方式，还是有办法的。一般来说，一款负责任的应用程序本身就提供这种文件关联的恢复功能。这里列举三个软件来说说如何恢复常用软件的文件关联。

1.看图软件ACDSee。打开“工具”菜单上的“文件关联”，会d出一个“ACDSee集成环境”窗口，在“图像文件”栏中可以恢复常用的图像文件与ACDSee的关联。

2.播放软件Winamp。在Winamp界面上单击鼠标右键，依次选择“选项”→“参数选择”→“文件类型”，在“文件类型设置”中可以恢复音乐文件与Winamp的关联。

3.压缩软件WinZip。依次选择“选项”→“配制”→“系统”→“关联”，会d出一个“WinZip关联窗口”，在这里可以恢复压缩文件WinZip的关联。

---