关联规则挖掘算法 |
您所在的位置：网站首页 › 经典推荐算法是什么 › 关联规则挖掘算法 |
关联规则挖掘算法
|
一、基本概念
1. 关联规则
关联规则是形如X=>Y的蕴含式，其中X、Y分别是一事务的真子集，且X∩Y=Φ。X称为规则的前提，Y称为规则的结果。关联规则反映出X中的项目在事务中出现时，Y中的项目也跟着出现的规律。 2.支持度关联规则的支持度是事务集中同时包含X和Y的事务数量与所有事务数量之比，它反映了X和Y中所含的事务的项在事务集中同时出现的频率，记为support（X=>Y），即support（X=>Y)=support(X∪Y)=P(XY) 3.置信度关联规则的置信度是事务集中同时包含X和Y的事务数量与包含X的事务数量之比，记为confidence（X=>Y），置信度反映了包含X的事务中出现Y的条件概率。即 confidence（X=>Y）=support（X∪Y）/support（X）=P(XY) 4. 频繁项集设U∈I，项目集U在事务集T上的支持度是包含U的事务在T中所占的百分比，即support（U）=|| {t∈T | U∈t} || / ||T||。式中，|| … ||表示集合中的元素数目。对项目集I，在事务数据库T中所有满足用户指定的最小支持度的项目集，即不小于最小支持度阀值的I的非空子集，称为频繁项目集或大项目集。 二、Apriori算法原理 1.算法思想Apriori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描，第一次扫描得到频繁1-项集L1，第k(k>1)次扫描首先利用第（k-1）次扫描的结果L(k-1)来产生候选k-项集的集合Ck，然后在扫描过程中确定Ck中元素的支持度，最后在每一次扫描结束时计算频繁k-项集的集合Lk，算法在当候选k-项集的集合Ck为空时结束。 2.Apriori算法产生频繁项集产生频繁项集的过程主要分为连接和剪枝两步： （1）连接步。为找到Lk（k≧2），通过L(k-1）与自身连接产生候选k-项集的集合Ck。自身连接时，两个项集对应的想按从小到大顺序排列好，当前除最后一项外的其他项都相等时，两个项集可连接，连接产生的结果为（l1[1], l1[2], …, l1[k-1], l2[k-2])。 （2）剪枝步。由Apriori算法的性质可知，频繁k-项集的任何子集必须是频繁项集。由连接步产生的集合Ck需进行验证，除去不满足支持度的非频繁k-项集。 3.Apriori算法的基本步骤（1）扫描全部数据，产生候选1-项集的集合C1； （2）根据最小支持度，由候选1-项集的集合C1产生频繁1-项集的集合L； （3）对k>1，重复执行步骤（4）、（5）、（6）； （4）由Lk执行连接和剪枝操作，产生候选（k+1）-项集的集合C（k+1）。 （5）根据最小支持度，由候选（k+1）-项集的集合C（k+1），产生频繁（k+1）-项集的集合L（k+1）； （6）若L≠Ф，则k=k+1，跳往步骤（4）；否则往下执行； （7）根据最小置信度，由频繁项集产生强关联规则，程序结束。 三.Apriori算法实例下表是一个数据库事物列表，在数据库中有9笔交易，即 |D| =9下面描述一下Apriori算法寻找D中频繁项集的过程。 4）第四次扫描 算法使用L3∞L3产生候选集4-项集的集合C4。L3∞L3={{I1, I2, I3, I4}}，根据Apriori性质，因为它的子集{I2, I3, I5}不是频繁的，使用这个项集被删除。这样C4=Φ，因此算法结束，找到了所有频繁项集。 四、源码 #include #include #include #include #include using namespace std; class Apriori { public: Apriori(size_t is = 0, unsigned int mv = 0) { item_size = is; min_value = mv; } //~Apriori() {}; void getItem(); map< vector, unsigned int> find_freitem();//求事务的频繁项 //连接连个k-1级频繁项，得到第k级频繁项 map< vector, unsigned int > apri_gen(unsigned int K, map< vector, unsigned int > K_item); //展示频繁项集 void showAprioriItem(unsigned int K, map< vector, unsigned int > showmap); private: map< int, vector > item;//存储所有最开始的事务及其项 map< vector, unsigned int > K_item;//存储频繁项集 size_t item_size;//事务数目 unsigned int min_value;//最小阈值 }; void Apriori::getItem()//用户输入最初的事务集 { int ci = item_size; for (int i = 0;i < ci;i++) { string str; vector temp; cout ret = item.insert(make_pair(i + 1, temp)); if (!ret.second) { --i; cout pre_K_item = K_item; size_t Kitemsize = K_item.size(); //存储应该删除的第K级频繁项集，不能和其他K级频繁项集构成第K+1级项集的集合 if (Kitemsize != 1 && i != 1) { vector< map< vector, unsigned int >::iterator > eraseVecMit; map< vector, unsigned int >::iterator pre_K_item_it1 = pre_K_item.begin(), pre_K_item_it2; while (pre_K_item_it1 != pre_K_item.end()) { map< vector, unsigned int >::iterator mit = pre_K_item_it1; bool isExist = true; vector vec1; vec1 = pre_K_item_it1->first; vector vec11(vec1.begin(), vec1.end() - 1); while (mit != pre_K_item.end()) { vector vec2; vec2 = mit->first; vector vec22(vec2.begin(), vec2.end() - 1); if (vec11 == vec22) break; ++mit; } if (mit == pre_K_item.end()) isExist = false; if (!isExist && pre_K_item_it1 != pre_K_item.end()) eraseVecMit.push_back(pre_K_item_it1);//该第K级频繁项应该删除 ++pre_K_item_it1; } size_t eraseSetSize = eraseVecMit.size(); if (eraseSetSize == Kitemsize) break; else { vector< map< vector, unsigned int >::iterator >::iterator currentErs = eraseVecMit.begin(); while (currentErs != eraseVecMit.end())//删除所有应该删除的第K级频繁项 { map< vector, unsigned int >::iterator eraseMit = *currentErs; K_item.erase(eraseMit); ++currentErs; } } } else if (Kitemsize == 1) break; } cout Apriori::apri_gen(unsigned int K, map< vector, unsigned int > K_item) { if (1 == K)//求候选集C1 { size_t c1 = item_size; map< int, vector >::iterator mapit = item.begin(); vector vec; map c1_itemtemp; while (mapit != item.end())//将原事务中所有的单项统计出来 { vector temp = mapit->second; vector::iterator vecit = temp.begin(); while (vecit != temp.end()) { pair< map::iterator, bool > ret = c1_itemtemp.insert(make_pair(*vecit++, 1)); if (!ret.second) { ++ret.first->second; } } ++mapit; } map::iterator item_it = c1_itemtemp.begin(); map< vector, unsigned int > c1_item; while (item_it != c1_itemtemp.end())//构造第一级频繁项集 { vector temp; if (item_it->second >= min_value) { temp.push_back(item_it->first); c1_item.insert(make_pair(temp, item_it->second)); } ++item_it; } return c1_item; } else { cout ::iterator ck_item_it1 = K_item.begin(), ck_item_it2; map< vector, unsigned int > ck_item; while (ck_item_it1 != K_item.end()) { ck_item_it2 = ck_item_it1; ++ck_item_it2; map< vector, unsigned int >::iterator mit = ck_item_it2; //取当前第K级频繁项与其后面的第K级频繁项集联合，但要注意联合条件 //联合条件：连个频繁项的前K-1项完全相同，只是第K项不同，然后两个联合生成第K+1级候选频繁项 while (mit != K_item.end()) { vector vec, vec1, vec2; vec1 = ck_item_it1->first; vec2 = mit->first; vector::iterator vit1, vit2; vit1 = vec1.begin(); vit2 = vec2.begin(); while (vit1 < vec1.end() && vit2 < vec2.end()) { string str1 = *vit1; string str2 = *vit2; ++vit1; ++vit2; if (K == 2 || str1 == str2) { if (vit1 != vec1.end() && vit2 != vec2.end()) { vec.push_back(str1); } } else break; } if (vit1 == vec1.end() && vit2 == vec2.end()) { --vit1; --vit2; string str1 = *vit1; string str2 = *vit2; if (str1 > str2) { vec.push_back(str2); vec.push_back(str1); } else { vec.push_back(str1); vec.push_back(str2); } map< int, vector >::iterator base_item = item.begin(); unsigned int Acount = 0; while (base_item != item.end())//统计该K+1级候选项在原事务集出现次数 { unsigned int count = 0, mincount = UINT_MAX; vector vv = base_item->second; vector::iterator vecit, bvit; for (vecit = vec.begin();vecit < vec.end();vecit++) { string t = *vecit; count = 0; for (bvit = vv.begin();bvit < vv.end();bvit++) { if (t == *bvit) count++; } mincount = (count < mincount ? count : mincount); } if (mincount >= 1 && mincount != UINT_MAX) Acount += mincount; ++base_item; } if (Acount >= min_value && Acount != 0) { sort(vec.begin(), vec.end()); //该第K+1级候选项为频繁项，插入频繁项集 pair< map< vector, unsigned int >::iterator, bool> ret = ck_item.insert(make_pair(vec, Acount)); if (!ret.second) { ret.first->second += Acount; } } } ++mit; } ++ck_item_it1; } if (ck_item.empty())//该第K+1级频繁项集为空，说明调用结束，把上一级频繁项集返回 return K_item; else return ck_item; } } void Apriori::showAprioriItem(unsigned int K, map< vector, unsigned int > showmap) { map< vector, unsigned int >::iterator showit = showmap.begin(); if (K != UINT_MAX) cout |
设最小支持度为2，产生候选项集及频繁项集的过程如下： 1）第一次扫描 扫描数据库D获得每个候选项的计数： 
由于最小事务支持数为2，没有删除任何项目。 2）第二次扫描 为发现频繁2-项集的集合L2，算法使用L1∞L1产生候选2-项集的集合C2。在剪枝步没有候选项集从C2删除，因为这些候选项的子集也是频繁的。 
3）第三次扫描 L2∞L2产生候选3-项集的集合C3。 
候选3项集C3产生的详细列表如下： ①连接C3=L2∞L2={{I1, I2}, {I1, I3},{I1, I5},{I2, I3},{I2, I4},{I2, I5},}∞{{I1, I2}, {I1, I3},{I1, I5},{I2, I3},{I2, I4},{I2, I5},}={{I1, I2, I3}, {I1, I2, I5},{I1, I3, I5},{I2, I3, I4},{I2, I3, I5},{I2, I4, I5},}。 ②使用Apriori性质剪枝：频繁项集的所有非空子集也必须是频繁的。例如{I1, I3, I5}的2-项子集是{I1, I3}, {I1, I5}, {I3, I5}。{I3, I5}不是L2的元素，因此不是频繁的。所有删掉C3中的{I1, I3, I5}。剪枝C3={{I1, I2, I3}，{I1, I2, I5}}。【本文地址】