数据挖掘实验三应用 Apriori 算法挖掘频繁项集 下载本文

实验三、应用 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

#include using 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 << \ }

cout<<\要保存的文件名:\ cin>>name2;

ofstream outfile(name2,ios::out); if(!outfile) {

cout<<\ 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