最初接触到数据挖掘的朋友肯定都听说过这样的一个案例:啤酒和尿布。大意是将啤酒和尿布放在一起的销售会提高。其实这背后隐含的原理就是关联分析,简单来讲就是啤酒和尿布之间存在着某种关联关系。关联关系时指从大规模的数据集中寻找物品之间的隐含关系,有时关联分析也可以称为关联规则学习。
关联分析主要要做的工作是在大规模数据集上找到某些关系。主要有两种形式:
对于一个具体的例子:
(摘自《机器学习实战》)
频繁项集是指经常出现在一起的物品的集合。如上面的例子中的
是一个项集,要使得这样的项集成为频繁项集,是指该项集在数据集中出现的次数大于某个阈值,便被称为频繁项集。
关联关系是指两种物品之间可能存在很强的关系。如上面的例子中的
的规则。
支持度是指数据集中包含某个项集的记录所占的比例。如项集
的支持度为
。
可信度是针对一条关联规则的,如关联规则
的可信度为“支持度
/支持度
”,即为
。
Apriori算法是关联分析的重要算法,Apriori算法主要是来寻找频繁项集,采用的方法是查找出所有的可能,如下图:
(摘自《机器学习实战》)
如上图所示,四种物品:0,1,2,3。列出所有的组合:
、
、...、
。这里就会出现一个问题,如果物品的数目变大,这种组合是呈现指数级的增长的:
,其中
为物品的数目,如何避免这样的指数增长对于Apriori算法的成功具有很重要的意义。Apriori原理就解释了这样的事情。
如何避免指数级增长,我们应该尽量去减少一些不必要的结点,Apriori原理是说如果某个项集是频繁的,那么他的所有子集也是频繁的。其逆否命题为:如果一个项集是非频繁的,那么他的所有超集也是非频繁的。使用这个原理就可以避免指数级增长,原理如下图所示:
(摘自《机器学习实战》)
在理解了上面的过程后,我们不难发现计算过程就是不断查找项集。首先,定义一个被称为最小支持度的量,当成阈值使用。大于这个阈值便是频繁项集,否则不是。接下来就开始计算,首先生成只含有单项的项集,如上图所示:
、
、
和
,并计算每个项集的支持度,与阈值比对。如上图所示都为频繁项集;接着生成含有两个元素的项集,如:
等等,结果发现
不是频繁项集,则去除掉。继续下去,一直到没有项集为止。上述的过程可以抽象为:其中
表示候选集,
表示频繁项集。
(实现过程)
五、从频繁项集中挖掘关联规则
主函数
%% 主函数
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
实现
第一步:
第二步:
第三步:
第四步: