实验三、应用 Apriori 算法挖掘频繁项集
学院 计算机科学与软件学院
•实验目的：
（1）熟悉 VC++编程工具和 Apriori 频繁项集挖掘算法。
（2）根据管理层的需求，确定数据挖掘的任务，明确数据挖掘的功能，也
就是明确要挖掘什么。
（3）由确定的数据挖掘任务，从实验一处理后的结果中，采用切块或切片
等联机分析处理技术，选择出挖掘任务相关数据。
（4）用 VC++编程工具编写 Apriori 算法的程序，对任务相关数据运行 Apriori
算法，挖掘出所有的频繁项集。
1.写出实验报告。
•实验原理：
1 、Apriori 算法
Apriori 使用一种称作逐层搜索的迭代方法，k 项集用于探索（k+1）项集。
首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，
找出频繁 1 项集的集合。该集合记作 L 1 。然后，L 1 用于找频繁 2 项集的集合L 2 ，L 2 用于找 L 3 ，如此下去，直到不能再找到频繁 k 项集。找每个 L k 需要一次数据库全扫描。
2、提高频繁项集逐层产生的效率
Apriori 性质：频繁项集的所有非空子集也必须是频繁的。
三、 实验内容：
1、实验内容
在给定的数据中提取统一购物篮购买的商品信息，由这些数据构成事务数据
库 D，挖掘其中的频繁项集 L。
挖掘频繁项集的算法描述如下：
Apriori 算法：使用逐层迭代找出频繁项集
输入：事务数据库 D；最小支持度阈值。
输出：D 中的频繁项集 L。
（1） L 1 = find_frequent_1-itemsets(D); // 挖掘频繁 1-项集，比较容易
（2） for (k=2;L k-1 ≠Φ ;k++) {
（3） C k = apriori_gen(L k-1 ,min_sup); // 调用 apriori_gen 方法生成候选频繁
k-项集分为两步：合并、减枝
（4） for each transaction t ∈ D { // 扫描事务数据库 D
（5） Ct = subset(C k ,t);
（6） for each candidate c ∈ Ct
（7） c.count++; // 统计候选频繁 k-项集的计数
（8） }
（9） L k ={c ∈ Ck|c.count≥min_sup} // 满足最小支持度的 k-项集即为频
繁 k-项集
（10） }
（11） return L= ∪ k L k ; // 合并频繁 k-项集（k>0）
算法在根据频繁 k-1 项集生成频繁 K 项集过程中要计算频繁 K 项集中每个
元素的支持度，并计算 K 项集中每个 k-1 项子集是否在 F k-1 中，上述两条任何一
条不满足，则删去这个 K 项集中的元素。
2 、实验过程
1、打开试验用数据，读取出同一流水号的商品 ID 并取前 5 位，生成以行为
单位生成事务数据集 transitions;
2、ind_frequent_1-itemsets 生成频繁一项集
for（each transaction in transitions）{
for(each item in transaction）{
oneItemSet；
oneItemSet.count++；//对 1 项集进行计数
}
}
3、apriori-gen (L k-1 ) 候选集产生算法
For all itemset p∈Lk-1 do
For all itemset q∈Lk-1 do
If p.item1=q.item1, p.item2=q.item2, …,p.itemk-2=q.itemk-2,
p.item k-1 !=q.item k-1
then
begin c=p∞q//p、q 合并后任意的 L k-1 子集
if has_infrequent_subset(c, L k-1 )
then delete c //存在 c 不属于 L k-1 剪枝
else add c to Ck
End
Return Ck
4、has_infrequent_subset(c, L k-1 ）判断候选集的元素
For all (k-1)-subsets of c do
If Not(S∈Lk-1) THEN return TRUE;
Return FALSE;
1.流程图
4、主要程序代码
1、//产生事务数据库代码（加注释）
#include#include#include#includeusing namespace std;
class Sales_n
{
public:
string serial;
int market;
char date[10];
int sn;
int id;
float num;
float price;
};
int main()
{
//////////打开并创建txt文件//////////////////////////////////
char name1[50],name2[50];
ifstream infile;
cout<<"选择要打开的文件：1019n.txt 1020n.txt 1021n.txt"< cin>>name1; infile.open(name1,ios::in);
/*string contents;*/
if(infile.fail())
{
cout << "error open!" << endl;
}
cout<<"要保存的文件名："< cin>>name2; ofstream outfile(name2,ios::out);
if(!outfile)
{
cout<<"open eror!"< exit(1); }
//////////////////////访问预处理文件/////////////////////////////////////////////
Sales_n sal[10000];
int sal_size=0;
int ser_size=0;
int m = 0,n = 1;
int new1[3400][20]={0}; //暂时储存商品ID
while(!infile.eof())
{
infile >> sal[sal_size].serial >> sal[sal_size].market >> sal[sal_size].date>> sal[sal_size].sn>> sal[sal_size].id>> sal[sal_size].num>> sal[sal_size].price;
sal_size++;
}
///////////////取统一流水的商品ID前三位按升序无重复的保存起来/////////////////////////
new1[0][0]=sal[0].id/10000;
for (int i =1;i { if (sal[i].serial==sal[i-1].serial)
{
new1[m][n]=sal[i].id/10000; //////流水号相同
n++;
//outfile< } else
{
///////排序//////////
for(int k = 0;k { for(int j = 0;j < n-k-1;j++)
{
if(new1[m][j] > new1[m][j+1])
{
int t = new1[m][j];
new1[m][j] = new1[m][j+1];
new1[m][j+1] = t;
}
}
}
for(int l= 0;l< n;l++)
{
if(new1[m][l-1]!=new1[m][l])
outfile< } outfile< m++; n = 0;
new1[m][n]=sal[i].id/10000;
n++;
}
}
infile.close();//关闭文件
outfile.close();//关闭文件
system( "PAUSE ");
}
2、//Apriori算法挖掘频繁项集support = 2（加注释）
#include #include #include #include #include
