关联规则浅谈以及Apriori算法matlab实现

 

转载：https://blog.csdn.net/lfdanding/article/details/50755919 

关联规则分析是数据挖掘中最活跃的研究方法之一，目的是在一个数据集中找出各项之间的关联关系，而这种关系并没有在数据中直接表示出来。

1、常用的关联规则算法 

以下重点介绍Apriori算法。

2、Apriori算法  以超市销售数据为例，提取关联规则的最大困难在于当存在很多商品时，可能的商品的组合（规则的前项和后项）的数目会达到一种令人望而却步的程度。因而各种关联规则分析的算法从不同方面入手减小可能的搜索空间的大小，以及减小扫描数据的次数。Apriori算法是最经典的挖掘频繁项集的算法，第一次实现了在大数据集上可行的关联规则提取，其核心思想是通过连接产生候选项与其支持度，然后通过剪枝生成频繁项集。

3、关联规则和频繁项集  1）关联规则的一般形式  项集A、B同时发生的概率称为关联规则的支持度（也称相对支持度）：

项集A发生，则项集B发生的概率为关联规则的置信度：

2）最小支持度和最小置信度  最小支持度是用户或专家定义的衡量支持度的一个阈值，表示项目集在统计意义上的最低重要性；最小置信度是用户或专家定义的衡量置信度的一个阈值，表示关联规则的最低可靠性，同时满足最小支持度阈值和最小置信度阈值的规则称作强规则。

3）项集  项集是项的集合。包含k个项的项集称为k项集，如集合｛牛奶，麦片，糖｝是一个3项集。

项集的出现频率是所有包含项集的事务计数，又称做绝对支持度或支持度计数。如果项集I的相对支持度满足预定义的最小支持度阈值，则I是频繁项集。频繁k项集通常记作。

4）支持度计数  项集A的支持度计数是事务数据集中包含A的事务个数，简称为项集的频率或计数。

已知项集的支持度计数，则规则的支持度和置信度很容易从所有事务计数、项集A和项集的支持度计数推出：

 

也就是说，一旦得到所有事务的个数，A、B和的支持度计数，就可以导出对应的关联规则和，并可以检查该规则是否是强规则。

4、Apriori算法——使用候选产生频繁项集  Apriori算法的主要思想是找出存在于事务数据集中最大的频繁项集，利用得到的最大频繁项集与预先设定的最小置信度阈值生成强关联规则。

1）Apriori的性质  频繁项集的所有非空子集也必须是频繁项集。根据该性质可以得出：向不是频繁项集I的项集中添加事务A，新的项集一定也不是频繁项集。

2）Apriori算法实现的两个过程  a）找出所有的频繁项集（支持度必须大于等于给定的最小支持度阈值），在这个过程中连接步和剪枝步互相融合，最终得到最大的频繁项集。

连接步：连接步的目的是找到K项集。对给定的最小支持度阈值，分别对1项候选集，剔除小于该阈值的项集得到1项频繁项集；下一步由自身连接产生两项候选集，保留中满足约束条件的项集得到两项频繁集，记为；再下一步由与连接产生三项候选集，保留中满足约束条件的项集得到三项频繁集，记为，等等。这样循环下去，得到最大频繁项集。

剪枝步：剪枝步紧接着连接步，在产生候选项的过程中启到减小搜索空间的目的。由于是与连接产生的，根据Apriori的性质频繁项集的所有非空子集也必须是频繁项集，所以不满足该性质的项集将不会存在于中，该过程就是剪枝。

b）由频繁项集产生强关联规则：在过程a）可知未超过预定的最小支持度阈值的项集已被剔除，如果剩下这些规则又满足了预定的最小置信度阈值，那么就挖掘出了强关联规则。

下面根据实例来讲解Apriori关联规则算法挖掘的实现过程。

数据如下所示

a,c,e b,d b,c a,b,c,d a,b b,c a,b a,b,c,e a,b,c a,c,e

以上有10个事务数据集，设支持度为0.2（支持度计数为2），则Apriori算法的实现过程如下。

过程一：找最大k项频繁集

a）Apriori算法简单地扫描所有的事务，事务中的每一项都是候选1项集的集合的成员，计算每一项的支持度。比如 ；

b）对中各项集的支持度与预先设定的最小支持度阈值作比较，保留大于或等于该阈值的项，得一项频繁集；

c）扫描所有事务，与连接得候选2项集，并计算每一项的支持度。如

  接下来是剪枝步，由于的每个子集（即）都是频繁集，所以没有项集从中被剔除；

d）对中各项集的支持度与预先设定的最小支持度阈值作比较，保留大于或等于该阈值的项，得两项频繁集 ；

e）扫描所有事务，与连接得候选3项集，并计算每一项的支持度，如

 

过程二：由频繁集产生关联规则。

置信度的计算公式为：

                        

其中是包含项集的事务数；是包含项集A的事务数；根据该公式，可以计算关联规则的置信度。

生成的24条关联规则的支持度和置信度如下所示。

在这里我们把最小置信度设为50%，则关联规则变为16条，如图所示。

在这里举例说明置信度的计算，如

 

Matlab代码如下

首先建立数据源 

menu_orders.txt

a,c,e b,d b,c a,b,c,d a,b b,c a,b a,b,c,e a,b,c a,c,e

然后是具体的程序  cal_apriori.m

%% 使用Apriori算法挖掘关联规则 clear; % 参数初始化 inputfile = 'menu_orders.txt'; % 销量及其他属性数据 outputfile='as.txt';% 输出转换后0,1矩阵文件 minSup = 0.2; % 最小支持度 minConf = 0.5;% 最小置信度 nRules = 1000;% 输出最大规则数 sortFlag = 1;% 按照支持度排序 rulefile = 'rules.txt'; % 规则输出文件 %% 调用转换程序 ，把数据转换为0,1矩阵，自定义函数 [transactions,code] = trans2matrix(inputfile,outputfile,','); %% 调用Apriori关联规则算法，自定义函数 [Rules,FreqItemsets] = findRules(transactions, minSup, minConf, nRules, sortFlag, code, rulefile); disp('Apriori算法挖掘菜品订单关联规则完成！');

trans2matrix.m

function [ output,code] = trans2matrix( inputfile,outputfile,splitter ) %% 把输入事务转换为0、1矩阵；每行代表一个事务 % 输入参数： % inputfile：输入文件，空格分隔每个项目； % outputfile：输出文件，转换后的0,1矩阵文件； % splitter: 输入文件项目的间隔符,默认为空格 % 输出参数： % output : 转换后的0,1 矩阵 % code：编码规则； if nargin<3 splitter=' '; end %% 读入文件, 获得编码规则 code={}; fid= fopen(inputfile); tline = fgetl(fid); lines=0; while ischar(tline) lines=lines+1; % 记录行数 tline = deblank(tline); tline = regexp(tline,splitter,'split'); code=[code tline]; % 合并 code = unique(code); % 去除重复记录 % disp(code) tline = fgetl(fid); end disp('编码规则为：') disp(num2str(1:size(code,2))) disp( code); fclose(fid); % 关闭文档 %% 读取文件，根据编码规则对原始数据进行转换 itemsnum= size(code,2); output=zeros(lines,itemsnum); fid= fopen(inputfile); tline = fgetl(fid); lines=0; while ischar(tline) lines=lines+1; % 记录行数 tline = deblank(tline); tline = regexp(tline,splitter,'split'); [~,icode,~] = intersect(code,tline);% 寻找下标 output(lines,icode')=1; %disp(output(lines,:)) tline = fgetl(fid); end fclose(fid); %% 把转换后的矩阵写入文件 fid = fopen(outputfile, 'w'); for i=1:lines fprintf(fid,'%s\n',num2str(output(i,:))); end fclose(fid); end

findRules.m

function [Rules,FreqItemsets] = findRules(transactions, minSup, minConf, nRules, sortFlag, code, rulesfile) M = size(transactions,1); % Number of attributes in the dataset N = size(transactions,2); if nargin < 7 fname = 'default'; end if nargin < 6 labels = cellfun(@(x){num2str(x)}, num2cell(1:N)); end if nargin < 5 sortFlag = 1; end if nargin < 4 nRules = 100; end if nargin < 3 minConf = 0.5; end if nargin < 2 minSup = 0.5; end if nargin == 0 error('No input arguments were supplied. At least one is expected.'); end % Preallocate memory for Rules and FreqItemsets maxSize = 10^2; Rules = cell(2,1); Rules{1} = cell(nRules,1); Rules{2} = cell(nRules,1); FreqItemsets = cell(maxSize); RuleConf = zeros(nRules,1); RuleSup = zeros(nRules,1); ct = 1; % Find frequent item sets of size one (list of all items with minSup) T = []; for i = 1:N S = sum(transactions(:,i))/M; if S >= minSup T = [T; i]; end end FreqItemsets{1} = T; %Find frequent item sets of size >=2 and from those identify rules with minConf for steps = 2:N % If there aren't at least two items with minSup terminate U = unique(T); if isempty(U) || size(U,1) == 1 Rules{1}(ct:end) = []; Rules{2}(ct:end) = []; FreqItemsets(steps-1:end) = []; break end % Generate all combinations of items that are in frequent itemset Combinations = nchoosek(U',steps); TOld = T; T = []; for j = 1:size(Combinations,1) if ct > nRules break; else % Apriori rule: if any subset of items are not in frequent itemset do not % consider the superset (e.g., if {A, B} does not have minSup do not consider {A,B,*}) if sum(ismember(nchoosek(Combinations(j,:),steps-1),TOld,'rows')) - steps+1>0 % Calculate the support for the new itemset S = mean((sum(transactions(:,Combinations(j,:)),2)-steps)>=0); if S >= minSup T = [T; Combinations(j,:)]; % Generate potential rules and check for minConf for depth = 1:steps-1 R = nchoosek(Combinations(j,:),depth); for r = 1:size(R,1) if ct > nRules break; else % Calculate the confidence of the rule Ctemp = S/mean((sum(transactions(:,R(r,:)),2)-depth)==0); if Ctemp > minConf % Store the rules that have minSup and minConf Rules{1}{ct} = R(r,:); Rules{2}{ct} = setdiff(Combinations(j,:),R(r,:)); RuleConf(ct) = Ctemp; RuleSup(ct) = S; ct = ct+1; end end end end end end end end % Store the freqent itemsets FreqItemsets{steps} = T; end % Get rid of unnecessary rows due to preallocation (helps with speed) FreqItemsets(steps-1:end) = []; RuleConf = RuleConf(1:ct-1); RuleSup = RuleSup(1:ct-1); % Sort the rules in descending order based on the confidence or support level switch sortFlag case 1 % Sort by Support level [V ind] = sort(RuleSup,'descend'); case 2 % Sort by Confidence level [V ind] = sort(RuleConf,'descend'); end RuleConf = RuleConf(ind); RuleSup = RuleSup(ind); for i = 1:2 temp = Rules{i,1}; temp = temp(ind); Rules{i,1} = temp; end disp(['关联规则算法完成,规则数为：' num2str(size(RuleSup,1))]); % Save the rule in a text file and print them on display fid = fopen(rulesfile, 'w'); fprintf(fid, '%s (%s, %s) \n', 'Rule', 'Support', 'Confidence'); for i = 1:size(Rules{1},1) s1 = ''; s2 = ''; for j = 1:size(Rules{1}{i},2) if j == size(Rules{1}{i},2) s1 = [s1 code{Rules{1}{i}(j)}]; else s1 = [s1 code{Rules{1}{i}(j)} ',']; end end for k = 1:size(Rules{2}{i},2) if k == size(Rules{2}{i},2) s2 = [s2 code{Rules{2}{i}(k)}]; else s2 = [s2 code{Rules{2}{i}(k)} ',']; end end s3 = num2str(RuleSup(i)*100); s4 = num2str(RuleConf(i)*100); fprintf(fid, '%s -> %s (%s%%, %s%%)\n', s1, s2, s3, s4); end fclose(fid); disp(['存储规则到文件‘' rulesfile '’完成']) end

运行完程序后，会生成rules.txt和as.txt。  我们主要关心rules.txt，里面的内容就是关联规则、支持度和置信度，如下所示。