Apriori算法及C++实现
最近工作比较忙，每天发在学习上的时间比较少，最近学的数据挖掘教程比较进度缓慢，上星期开始看的Apriori算法，这算是我接触的第一个数据挖掘方面的算法，看了2-3遍了解其原理。曾看过大侠说过，要想完全理解其算法的本质，即必须上机编写测试，哪怕是写出伪代码也要翻译成机器语言跑一遍，来感觉此算法的伟大。所以抽了个周六，详细编写了遍，并参考网上的例子，对其进行适当的优化。
首先我们要先了解Apriori算法的简介和原理，这部分都是我参考教程上及网上的，由于篇幅比较大，就简单的整理了下：
一、Apriori算法简介：
Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。
二、算法中用到一些概念
1、支持度，以购物为例，同事购买AB物品的概率即P(A ∩ B)。
2、置信度，在买A的基础上，购买了B的概率即P(B|A)= p(AB)/P(A) （条件概率公式）。
3、候选K项集，该集合含有K个元素，也即同时购买了K个物品。
4、频繁K项集，在候选K项集的基础上，大于或等于最小支持度。
5、先验性质，反单调性，链接步，剪枝步：
三、算法步骤，利用伪代码来解释更容易理解：
算法 Apriori
Input: Transaction DataBase D，Minimumsupport threshold minsup。
Output： Frequent pattern L
//相当于主程序
(1) L1=search_frequent_1-itemsets( D ); //首先计算候选1项集和频繁1项集
(2) for(k=2;Lk-1≠φ;k++)do //根据频繁集k-1项集找候选k项集，利用候选k项集找频繁k项集，直到频繁k项集为空
(3) begin
(4) Ck=apriori-gen(Lk-1); //根据频繁k-1项集，利用链接步，产生候选K项集
(5) for all transactions t D do //根据候选k项集，利用支持度刷选出频繁k项集
(6) begin
(7) Ct=subset(Ck，t);
(8) for all candidates c Ct do
(9) c.count++;
(10) end
(11) Lk ={c Ck|c.count≥minsup}
(12) end
(13) Answer L=∪kLk;
//按事务数据产生候选1项集和频繁1项集，其实就是数事务中出现的所有item的个数，再利用支持度帅选处频繁集
Procedure Search_frequent_1-itemsets( D )
(1) begin
(2) for all transactions t D do
(3) begin
(4) for each item ik t do
(5) ik.count++;
(6) end
(7) L1 ={ i I | i.count≥minsup}
(8) return L1;
(9) end
//根据频繁k-1项集，利用链接步，产生候选K项集
Procedure apriori_gen(Lk)
(1) begin
(2) for each itemset l1 Lk do
(3) for each itemset l2 Lk do
(4) begin
(5) if ( l1[1]=l2[1]) ( l1[2]=l2[2]) … ( l1[k-1]=l2[k-1]) ( l1[k]<l2[k])then
(6) begin
(7) c= l1 l2;
(8) if Is_include_infrenquent_subset(c,Lk) then
(9) delete c;
(10) else add c to Ck+1 ;
(11) end
(12) end
(13) return Ck+1 ;
(14) end
ProcedureIs_include_infrenquent_subset(c,Lk)
(1)begin
(2) for each k-subset s of c
(3) if s Lk then
(4) reture TURE;
(5) return FALSE ;
(6)end
四，从网上下了个例子：
五：C++实现代码：
<span style="font-family:Microsoft YaHei;font-size:18px;">#define ITEMMAX 100
//定义存储事务的结构，每条事务最多包含100元素
typedef struct tag_TransactionItem
{
intitem[ITEMMAX];
intitemNum; //最大值100
}STTransactionItem,*STPTransactionItem;
typedef struct tag_Transaction
{
STTransactionItemtransactions[ITEMMAX];
intTrancount;
}Transaction;
//候选集结构的定义
typedef struct tag_CondidateItem
{
intitem[ITEMMAX];
intitemcount;
}STCondidateItem,*STPCondidateItem;
typedef struct tag_Condidate
{
tag_CondidateItemitems[ITEMMAX];
intsetNum; //候选集元素个数
intCondidateIndex; //候选集下标，相当于算法里的K
}STCondidate,*STPCondidate;
//候选集结构的定义
typedef struct tag_FreQuencyItem
{
intitem[ITEMMAX];
intitemcount;
}STFreQuencyItem,*STPFreQuencyItem;
typedef struct tag_FreQuency
{
tag_CondidateItemitems[ITEMMAX];
intsetNum; //频繁集元素个数
intCondidateIndex; //频繁集下标，相当于算法里的K
}STFreQuency,*STPFreQuency;
#include "stdio.h"
Transaction curTransaction;
STCondidate curCondidates[ITEMMAX];
STFreQuency curFrequencys[ITEMMAX];
int minSup = 2;
void InitTransaction();
void printTransaction(Transactiontransaction);
void SearchFrequent_1_itemset();
void printCondidate(int set_k);
void printFrequency(int set_k);
void apriori_gen(int set_k);
void GetFrequency_set_k(int set_k);
int main()
{
InitTransaction();
printTransaction(curTransaction);
SearchFrequent_1_itemset();
intset_k=2;
while(true)
{
apriori_gen(set_k);
if(curCondidates[set_k-1].setNum == 0)
{
break;
}
GetFrequency_set_k(set_k);
printCondidate(set_k);
printFrequency(set_k);
set_k++;
}
return0;
}
void InitTransaction()
{
printf("输入当前事务的记录条数：");
scanf("%d",&(curTransaction.Trancount));
inti,j;
for(i=0;i<curTransaction.Trancount;i++)
{
printf("输入%d条记录的记录项的数目:",i);
scanf("%d",&(curTransaction.transactions[i].itemNum));
printf("输入%d条记录的记录项（以数值替代，并要求有序）:",i);
for(j=0;j<curTransaction.transactions[i].itemNum; j++)
{
scanf("%d",&(curTransaction.transactions[i].item[j]));
}
}
}
void SearchFrequent_1_itemset()
{
inti,j;
inttranCount = curTransaction.Trancount;
for(i=0; i<tranCount; i++)
{
intitemCount = curTransaction.transactions[i].itemNum;
for(j=0;j<itemCount; j++)
{
intcondItemNum = curCondidates[0].setNum;
boolisFind = false;
intk;
for(k=0; k<condItemNum; k++)
{
if(curCondidates[0].items[k].item[0] == curTransaction.transactions[i].item[j])
{
curCondidates[0].items[k].itemcount++;
isFind= true;
break;
}
}
if(!isFind)
{
intindex = 0;
for(k=0; k<condItemNum; k++)
{
if(curCondidates[0].items[k].item[0] > curTransaction.transactions[i].item[j])
{
break;
}
}
index= k;
intm;
for(m=condItemNum; m>index; m--)
{
curCondidates[0].items[m]= curCondidates[0].items[m-1];
}
curCondidates[0].items[index].itemcount= 1;
curCondidates[0].items[index].item[0]= curTransaction.transactions[i].item[j];
curCondidates[0].setNum++;
}
}
}
intsetItems = curCondidates[0].setNum;
j= 0;
for(i=0; i<setItems; i++)
{
if(curCondidates[0].items[i].itemcount>=minSup)
{
curFrequencys[0].items[j++]= curCondidates[0].items[i];
}
}
curFrequencys[0].setNum= j;
curFrequencys[0].CondidateIndex= 1;
curCondidates[0].CondidateIndex= 1;
}
void apriori_gen(int set_k)
{
if(set_k < 2)
{
return;
}
inti,j,k,l,m,n;
intsetnum = curFrequencys[set_k-2].setNum;
intcondNum = 0;
for(i=0;i<setnum; i++)
{
for(j=i+1; j<setnum; j++)
{
boolisUnion = true;
for(k=0; k<set_k-2; k++)
{
if(curFrequencys[set_k-2].items[i].item[k]!=curFrequencys[set_k-2].items[j].item[k])
{
isUnion= false;
break;
}
}
if(isUnion)
{
curCondidates[set_k-1].items[condNum]= curFrequencys[set_k-2].items[i];
curCondidates[set_k-1].items[condNum].item[set_k-1]= curFrequencys[set_k-2].items[j].item[set_k-2];
curCondidates[set_k-1].items[condNum].itemcount= 0;
condNum++;
// inttranCount = curTransaction.Trancount;
// for(m=0; m<tranCount; m++)
// {
// intitemCount = curTransaction.transactions[m].itemNum;
// for(n=0,l=0;n<itemCount && l<set_k; n++)
// {
// if(curCondidates[set_k-1].items[condNum].item[l] == curTransaction.transactions[m].item[n])
// {
// l++;
// continue;
// }
// elseif(curCondidates[set_k-1].items[condNum].item[l] <curTransaction.transactions[m].item[n])
// {
// break;
// }
// }
// if (l == set_k)
// {
// curCondidates[set_k-1].items[condNum].itemcount++;
// }
//
// }
// if(curCondidates[set_k-1].items[condNum].itemcount > 0)
// {
// condNum++;
// }
}
}
}
//curCondidates[set_k-1].setNum= condNum;
curCondidates[set_k-1].CondidateIndex= set_k;
intvalidConNum = 0;
for(i = 0; i<condNum; i++)
{
curCondidates[set_k-1].items[validConNum]= curCondidates[set_k-1].items[i];
inttranCount = curTransaction.Trancount;
for (m=0; m<tranCount; m++)
{
intitemCount = curTransaction.transactions[m].itemNum;
for(n=0,l=0;n<itemCount && l<set_k; n++)
{
if(curCondidates[set_k-1].items[validConNum].item[l] ==curTransaction.transactions[m].item[n])
{
l++;
continue;
}
elseif(curCondidates[set_k-1].items[validConNum].item[l] <curTransaction.transactions[m].item[n])
{
break;
}
}
if(l == set_k)
{
curCondidates[set_k-1].items[validConNum].itemcount++;
}
}
if(curCondidates[set_k-1].items[validConNum].itemcount > 0)
{
validConNum++;
}
}
curCondidates[set_k-1].setNum= validConNum;
}
void GetFrequency_set_k(int set_k)
{
inti,j;
intsetItems = curCondidates[set_k-1].setNum;
j= 0;
for(i=0; i<setItems; i++)
{
if(curCondidates[set_k-1].items[i].itemcount>=minSup)
{
curFrequencys[set_k-1].items[j++]= curCondidates[set_k-1].items[i];
}
}
curFrequencys[set_k-1].setNum= j;
curFrequencys[set_k-1].CondidateIndex= set_k;
}
void printCondidate(int set_k)
{
inti,j;
intsetItems = curCondidates[set_k-1].setNum;
printf("候选集[%d]中总共有%d个项集\n",set_k,setItems);
for(i=0; i<setItems; i++)
{
for(j=0;j<curCondidates[set_k-1].CondidateIndex; j++)
{
printf("%4d",curCondidates[set_k-1].items[i].item[j]);
}
printf("%8d\n",curCondidates[set_k-1].items[i].itemcount);
}
}
void printFrequency(int set_k)
{
inti,j;
intsetItems = curFrequencys[set_k-1].setNum;
printf("频繁集[%d]中总共有%d个项集\n",set_k,setItems);
for(i=0; i<setItems; i++)
{
for(j=0;j<curFrequencys[set_k-1].CondidateIndex; j++)
{
printf("%4d",curFrequencys[set_k-1].items[i].item[j]);
}
printf("%8d\n",curFrequencys[set_k-1].items[i].itemcount);
}
}
void printTransaction(Transaction transaction)
{
inti,j;
inttranCount = transaction.Trancount;
printf("事务有%d条记录:\n",tranCount);
for(i=0; i<tranCount; i++)
{
printf("%d: ", i);
intitemCount = transaction.transactions[i].itemNum;
for(j=0;j<itemCount; j++)
{
printf("%4d",transaction.transactions[i].item[j]);
}
printf("\n");
}
}</span>注：注释的是第一版本代码，发现有5层for语句，时间复杂度太高了，后面把其处理代码移到函数在外层来，分两步只需3层for语句。
六、运行结果：
七：算法运用【注：摘自百度百科】：
经典的关联规则数据挖掘算法Apriori算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。
Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。
Apriori算法应用于网络安全领域，比如时候入侵检测技术中。早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。
Apriori算法应用于高校管理中。随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。针对这一现象，提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求"与"运算，寻找频繁项集。实验结果表明，改进后的Apriori算法在运行效率上有了很大的提升，挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。
Apriori算法被广泛应用于移动通信领域。移动增值业务逐渐成为移动通信市场上最有活力、最具潜力、最受瞩目的业务。随着产业的复苏，越来越多的增值业务表现出强劲的发展势头，呈现出应用多元化、营销品牌化、管理集中化、合作纵深化的特点。针对这种趋势，在关联规则数据挖掘中广泛应用的Apriori算法被很多公司应用。依托某电信运营商正在建设的增值业务Web数据仓库平台，对来自移动增值业务方面的调查数据进行了相关的挖掘处理，从而获得了关于用户行为特征和需求的间接反映市场动态的有用信息，这些信息在指导运营商的业务运营和辅助业务提供商的决策制定等方面具有十分重要的参考价值。