简单易学的机器学习算法——Apriori算法
简单易学的机器学习算法——Apriori算法
一、关联分析
最初接触到数据挖掘的朋友肯定都听说过这样的一个案例：啤酒和尿布。大意是将啤酒和尿布放在一起的销售会提高。其实这背后隐含的原理就是关联分析，简单来讲就是啤酒和尿布之间存在着某种关联关系。关联关系时指从大规模的数据集中寻找物品之间的隐含关系，有时关联分析也可以称为关联规则学习。
二、关联分析的重要概念
关联分析主要要做的工作是在大规模数据集上找到某些关系。主要有两种形式：
- 频繁项集
- 关联关系
对于一个具体的例子：
(摘自《机器学习实战》)
1、频繁项集
频繁项集是指经常出现在一起的物品的集合。如上面的例子中的
是一个项集，要使得这样的项集成为频繁项集，是指该项集在数据集中出现的次数大于某个阈值，便被称为频繁项集。
2、关联关系
关联关系是指两种物品之间可能存在很强的关系。如上面的例子中的
的规则。
3、支持度
支持度是指数据集中包含某个项集的记录所占的比例。如项集
的支持度为
。
4、可信度
可信度是针对一条关联规则的，如关联规则
的可信度为“支持度
/支持度
”，即为
。
三、Apriori算法
1、Apriori算法
Apriori算法是关联分析的重要算法，Apriori算法主要是来寻找频繁项集，采用的方法是查找出所有的可能，如下图：
（摘自《机器学习实战》）
如上图所示，四种物品：0，1，2，3。列出所有的组合:
、
、...、
。这里就会出现一个问题，如果物品的数目变大，这种组合是呈现指数级的增长的：
，其中
为物品的数目，如何避免这样的指数增长对于Apriori算法的成功具有很重要的意义。Apriori原理就解释了这样的事情。
2、Apriori原理
如何避免指数级增长，我们应该尽量去减少一些不必要的结点，Apriori原理是说如果某个项集是频繁的，那么他的所有子集也是频繁的。其逆否命题为：如果一个项集是非频繁的，那么他的所有超集也是非频繁的。使用这个原理就可以避免指数级增长，原理如下图所示：
(摘自《机器学习实战》)
四、使用Apriori算法发现频繁项集
在理解了上面的过程后，我们不难发现计算过程就是不断查找项集。首先，定义一个被称为最小支持度的量，当成阈值使用。大于这个阈值便是频繁项集，否则不是。接下来就开始计算，首先生成只含有单项的项集，如上图所示：
、
、
和
，并计算每个项集的支持度，与阈值比对。如上图所示都为频繁项集；接着生成含有两个元素的项集，如：
等等，结果发现
不是频繁项集，则去除掉。继续下去，一直到没有项集为止。上述的过程可以抽象为：其中
表示候选集，
表示频繁项集。
（实现过程）
五、从频繁项集中挖掘关联规则
六、Matlab实现
1、频繁项集
主函数
%% 主函数
clear all;
clc;
%% 导入数据
% 数据集中的0表示无
dataSet = load('data.txt');
% %构建第一个候选集C1
% C1 = createC1(dataSet);
%
% %构建第一个频繁项集L1
% [retList, supportData] = scanD(dataSet, C1, 0.7)
% 调用产生频繁项集
[L, supportData] = apriori(dataSet, 0.5);查找候选集C1
%% 查找候选集C1
function [ C1 ] = createC1( dataSet )
C1 = unique(dataSet);%取得所有相异元素
end生成频繁项集
%% 计算频繁项集L1
function [ retList, supportData ] = scanD( dataSet, Ck, minSupport )
[m,n] = size(Ck);
if m==0
retList = [];
supportData = 0;
else
if n==1
Ck(Ck==0)=[];%将候选集中的0去掉
[m,n] = size(Ck);%获得候选集的大小，注意候选集的大小
[m_1,n_1] = size(dataSet);%获得整个数据集的大小
%% 统计候选集中的元素在dataSet中出现的次数
dataNum = zeros(m,1);
for i = 1:m%行数为候选集中元素的个数
for j = 1:m_1
if all(ismember(Ck(i,:), dataSet(j,:)))==1
dataNum(i,1) = dataNum(i,1)+1;
end
end
% if all(ismember(Ck(i,:), dataSet))==1
% dataNum(i,1) = dataNum(i,1)+1;
% end
end
else
[m,n] = size(Ck);%获得候选集的大小，注意候选集的大小
[m_1,n_1] = size(dataSet);%获得整个数据集的大小
%% 统计候选集中的元素在dataSet中出现的次数
dataNum = zeros(m,1);
for i = 1:m%行数为候选集中元素的个数
tmp = Ck(i,:);
tmp(tmp==0)=[];%将候选集中的0去掉
for j = 1:m_1
if all(ismember(tmp, dataSet(j,:)))==1
dataNum(i,1) = dataNum(i,1)+1;
end
end
% if all(ismember(Ck(i,:), dataSet))==1
% dataNum(i,1) = dataNum(i,1)+1;
% end
end
end
%% 计算每个元素出现的比率
numItems = length(dataSet);
supportData = zeros(length(dataNum), 1);
retListSize = 1;
for i = 1:length(dataNum)
supportData(i, 1) = dataNum(i, 1)/numItems;
if supportData(i ,1) >= minSupport
retList(retListSize, :) = Ck(i, :);
retListSize = retListSize+1;
end
end
end
end生成后续的候选集
function [ retList ] = aprioriGen( Lk )
[m,n] = size(Lk);%得到Lk矩阵的大小
r = 1;
for i = 1:m-1
for j = i+1:m
retListTmp_1(r,:) = [Lk(i,:),Lk(j,:)];
tmp = unique(retListTmp_1(r,:));
if length(tmp)<2*n
tmp(1,2*n) = 0;%补0
end
retListTmp_2(r,:) = tmp;
r = r+1;
end
end
if m~=1
retList=unique(retListTmp_2,'rows');
else
retList=[];
end
end总的生成频繁项集的模块
%% 控制整个频繁项集的生成
function [ L, supportData ] = apriori( dataSet, minSupport )
C1 = createC1(dataSet)%生成最初的候选集
[L1, supportData] = scanD(dataSet, C1, minSupport)%生成最初的频繁项集
L = L1;
while ~isempty(L)
Ck = aprioriGen(L)
[Lk, supportData] = scanD(dataSet, Ck, minSupport)
L = Lk;
end
end实现
第一步：
第二步：
第三步：
第四步：
