Apriori基础算法（C++实现）
发布时间
阅读量：
阅读量
本人学艺不精，如有错误，还请多担待。
对于Apriori算法中的一些概念，这里不做过多阐述，感兴趣的朋友可自行搜索查看。
1.需求和规格说明
关联分析是数据挖掘中的一个重要任务，Apriori 算法是一种典型的关联分析算法。多用于超市的销售决策，如通过统计一段时间内，用户买商品 A 和 B 同时发生的概率，得出了顾客买 A 则很可能会买 B 的一条规则。
本课题要求对给定的训练数据，实现 Apriori 算法，构件关联规则集合。
2.设计
(1)整体构架。本算法的目的是找出强关联规则，而强关联规则取决于最小支持度（MinSup）和最小置信度（MinConf）。第一步就是找到频繁项集，也就是大于最小支持度的项集，第二步是从中筛选强关联规则，也就是大于最小置信度的项集。找频繁项集主要通过“自连接”和“剪枝”两部分完成，“自连接”是对于满足条件的项集进行连接，而“剪枝”是剔除小于最小支持度的项集。因此，为了“剪枝”的方便，采用链表来连接每个项集，用数组来储存项集中的内容。
(2)变量设置。算法中的最小置信度和最小支持度要求用户来自行输入，那么将MinSup和MinConf设为全局变量。算法中的数据保存在文件中，为了读取和计算的方便，首先需要知道数据库中商品的数目（ItemNumber）和总共的订单数量（TIDNumber），并且设为常量。除此以外，为了判断是否继续进行“自连接”和“剪枝”，设全局变量continual（bool类型），true则继续，false则停止。
(3）存储内容。每个订单都是一个项集，它有支持度、置信度和所包含的商品种类，由于是链表连接项集，故还存在指针域指向下一个项集。置信度是在满足最小支持度的基础上所讨论的，因此暂时不将它纳入考虑范围。我们可以用一个结构体来表示一个订单，它有购买的商品item[ItemNumber]，支持度min_support(double)，指针域next。同时设置一个项集类Set（链表）存放结构体（结点）。
（4）文件格式。文件中一行一个项集（订单），每个订单中若存在某个商品，则在商品所对应的序列号下填“1”，不存在填“0”。数字之间以空格符分隔开。
（5）具体结构与函数。
全局变量：
| 全局变量 | 类型 | 名称 | 描述 |
|---|---|---|---|
| int | ItemNumber | 商品数 | |
| int | TIDNumber | 订单数 | |
| double | MinSup | 最小支持度 | |
| double | MinConf | 最小置信度 | |
| bool | continual | 判断是否继续操作项集 |
结点（订单）（项集）：
| frequestSet（node） | 类型 | 名称 | 描述 |
|---|---|---|---|
| Int | item[itemNumber] | 所含商品 | |
| double | min_support | 支持度 | |
| node*next | 指针域 | 指向下一个订单 |
函数：
| 类型 | 名称 | 描述 |
|---|---|---|
| 无 | Set::Set() | 构造函数 |
| 无 | Set::~Set() | 析构函数 |
| void | Set::initialSet(int a[][ItemNumber]) | 构建长度为1的项集 |
| void | Set::setPrune() | 剔除不满足最小支持度的项集 |
| void | Set::candidateSet(int a[][ItemNumber]) | 自连接，产生候选集 |
| void | Set::sumItem(inta[],b[],c[]) | 求a,b的并集 |
| bool | Set::IsDifferent(int a[]) | 判断已经连接的项集中没有该项集 |
| void | Set::calculateMinSup(node*&T,int a[][ItemNumber]) | 计算该项集的最小支持度 |
| void | Set::select(int a[][ItemNumber]) | 挑选频繁项集中满足最小置信度的项集，将其关系写入文件 |
| void | Set::print() | 输出项集 |
| void | setMinSupAndMinConf() | 设置最小支持度和最小置信度 |
| void | readDate(int a[][ItemNumber]) | 从数据库中读数据到二维数组 |
（6）部分细节。每个项集由一个数组a[ItemNumber]来存储，a[0]用来存放项集的个数，这样可以为后期“自连接”提供很多方便，比如：在连接两个集合时所需遍历的个数，连接后是否为k+1的项集。这样一来，项集中最多存放ItemNumber-1个商品，不过不用担心，在实际情况下，选择的商品不可能都存在关联规则。
3.用户手册
- 创建一个文本文件，将商品订单输入数据文件中，详情见2（4）文件格式
- 统计出商品数和订单数并修改代码中的ItemNumber和TIDNumber
- 更改readDate函数中的数据库（“数据库1.txt”），改为你所创建的数据库名称。
点击运行，程序会将关联规则写入“关联规则集”文件（也可自己改动）
代码：
#pragma once#include<iostream>#include<fstream>using namespace std;const int ItemNumber = 11; //产品种类const int TIDNumber = 17; //订单数extern double MinSup; //最小支持度extern double MinConf; //最小置信度extern bool continual; //判断是否继续产生候选集struct frequestSet {int item[ItemNumber] = { 0 } ; //0位置放集合个数,能存放ItemNumber-1个数double min_support = 0; //每个集合的支持度frequestSet* next; //指向下一个集合的指针};typedef frequestSet node;class Set {public:Set();~Set();void initialSet(int a[][ItemNumber]); //构建长度为1的项集void setPrune(); //剪枝（剔除支持度小于阈值的项集（结点））void candidateSet(int a[][ItemNumber]); //产生候选集void sumItem(int a[], int b[],int c[]); //产生一个连接集合c(项集的并集)bool IsDifferent(int a[]); //判断新连接的集合是否已经存在void calculateMinSup(node*& T, int a[][ItemNumber]); //计算最小支持度void select(int a[][ItemNumber]); //挑选满足条件的频繁项集并写入文件void printSet(); //输出项集private:node* L; //头节点int setLen ; //表长}; #include"Apriori.h"Set::Set(){L = new node;L->next = NULL;setLen = 0;}Set::~Set(){node* p = L;node* s = NULL;while (p != NULL) {s = p->next;delete p;p = s;}L = NULL;}void Set::initialSet(int a[][ItemNumber]){node* p = L;node* s = NULL;while (setLen < ItemNumber) {s = new node; s->item[0] = 1;setLen++;s->item[1] =setLen;int num = 0;for (int i = 0; i < TIDNumber; i++) {if (a[i][setLen - 1] == 1) {num++;}}s->min_support = (double)num / TIDNumber; //求支持度s->next = p->next;p->next = s;p = p->next;}cout << "初始集：" << endl;printSet();setPrune();cout << "剪枝后：" << endl;printSet();}void Set::setPrune(){node* p = L;node* u = NULL;while (p ->next!= NULL) {if (p->next->min_support < MinSup) {u = p->next;p->next = u->next;delete u;setLen--; //更新频繁集个数}else {p = p->next;}}}void Set::candidateSet(int a[][ItemNumber]){continual = false;node* C = L->next; //更新为候选集时释放原集合内存node* k = L->next; //连接时的基结点if (k==NULL||k->next == NULL) { //没有或只剩一个频繁项集,结束程序return;}node* p = L->next->next;L->next = NULL; //b表头置0，重写插入node* Pi = L; //指向新表的指针node* s = NULL; //插入新表的结点int tempArr[ItemNumber] = { 0 }; while (k->next != NULL) { //循环将自身集合两两连接while (p != NULL) {sumItem(k->item, p->item, tempArr); //求两集合的并集if (tempArr[0] == k->item[0] + 1) { //判断是否满足连接条件（连接成为k+1项集）if (IsDifferent(tempArr)) { //判断是否已经存在该集合s = new node;for (int i = 0; i <= tempArr[0]; i++) {s->item[i] = tempArr[i];}calculateMinSup(s, a); //为即将插入的结点计算最小支持度if (s->min_support >= MinSup) {continual = true; //有结点插入s->next = Pi->next;Pi->next = s;Pi = s;}else {delete s;}}}p = p->next;}k = k->next;p = k->next;}if (continual == false||L->next==NULL) { //判断是否有新结点插入，没有说明表为空，头节点重新指向原表L->next =C;continual = false;}else {//释放原表内存p = C;while (p != NULL) {k = p->next;delete p;p = k;}}}void Set::sumItem(int a[], int b[], int c[]){int Pa = 1, Pb = 1, Pc = 1;c[0] = 0;while (Pa <= a[0] && Pb <= b[0]) {if (a[Pa] < b[Pb]) {c[Pc] = a[Pa];c[0]++;Pa++;Pc++;}else if(b[Pb]<a[Pa]) {c[Pc] = b[Pb];c[0]++;Pc++;Pb++;}else {c[Pc] = a[Pa];c[0]++;Pc++;Pa++;Pb++;}}if (Pa >a[0]&&Pb<=b[0]) {while (Pb <= b[0]) {c[Pc] = b[Pb];c[0]++;Pc++;Pb++;}}else if (Pa <= a[0] && Pb > b[0]) {while (Pa <= a[0]) {c[Pc] = a[Pa];c[0]++;Pc++;Pa++;}}}bool Set::IsDifferent(int a[]){node* p = L->next;if (p == NULL) {return true;}int num = 0;while (p != NULL) {for (int i = 0; i <= a[0]; i++) {if (a[i] == p->item[i]) {num++;}}if (num == a[0]+1) {return false;}num = 0;p = p->next;}return true;}void Set::calculateMinSup(node*& T, int a[][ItemNumber]){int num = 0;//TID（订单数）中出现某集合的次数int count = 0;//判断某集合是否在某一TID中存在for (int i = 0; i < TIDNumber; i++) {for (int j = 1; j <= T->item[0]; j++) {if (a[i][T->item[j] - 1] == 1) {count++;}}if (count == T->item[0]) { //存在num++;}count = 0;}T->min_support = (double)num / TIDNumber;}void Set::select(int a[][ItemNumber]){ofstream ofs;ofs.open("关联规则集3.txt", ios::out);if (!ofs.is_open()) {cout << "文件打开失败" << endl;return;}node* p = L->next;ofs << "频繁项集：" <<endl;while (p != NULL) {for (int i = 1; i <= p->item[0]; i++) {ofs << p->item[i] << " ";}ofs << endl;p = p->next;}p = L->next;int num1 = 0;//买x的TID数int num2 = 0;//买x，y的TID数if (p==NULL||p->item[0] == 1) {cout << "不存在关联规则集" << endl;ofs.close();return;}while (p != NULL) {for (int i = 1; i <= p->item[0]; i++) {for (int j = 1; j <= p->item[0]; j++) {if (i != j) {for (int k = 0; k < TIDNumber; k++) {if (a[k][p->item[i] - 1] == 1 && a[k][p->item[j] - 1] == 1) {num2++;num1++;}else if (a[k][p->item[i] - 1] == 1 && a[k][p->item[j] - 1] == 0) {num1++;}}if ((double)num2 / num1 >= MinConf) {cout << "买" << p->item[i] << "会买" <<p->item[j] << "的支持度：" << (double)num2 / TIDNumber << "置信度：" << (double)num2 / num1 << endl; ofs<< "买" << p->item[i] << "会买" << p->item[j] << "的支持度：" << (double)num2 / TIDNumber << "置信度：" << (double)num2 / num1 << endl;}num1 = 0;num2 = 0;}}}p = p->next;}ofs.close();}void Set::printSet(){node* p = L->next;while (p != NULL) {for (int i = 1; i <= p->item[0]; i++) {cout << p->item[i] << " ";}cout <<"最小支持度："<< p->min_support << endl;p = p->next;}} #include<iostream>using namespace std;#include<string>#include<fstream>#include"Apriori.h"double MinSup; //支持度阈值double MinConf; //置信度阈值bool continual; //判断是否继续产生候选集/*"数据库1.txt"题目中的例子，TIDNumber=6，ItemNumber=4 支持度：0.5 置信度：0.6"数据库2.txt" TIDNumber=9，ItemNumber=6 支持度：0.4 置信度：0.6"数据库3.txt"TIDNumber=17,ItemNumber=11 支持度0.4 置信度 0.6（数据随机输入）*/void setMinSupAndMinConf() {cout << "输入支持度阈值：";cin >> MinSup;cout << "输入置信度阈值：";cin >> MinConf;}void readDate(int a[TIDNumber][ItemNumber]) { //从数据库里面读取数据到二维数组FILE* fp = fopen("数据库3.txt", "r");if (fp == NULL) {cout << "读取错误" << endl;return;}for (int i = 0; i < TIDNumber; i++) {for (int j = 0; j < ItemNumber; j++) {fscanf_s(fp, "%d", &a[i][j]); //fscanf_s函数遇到空格、换行会停止}fscanf_s(fp, "
");}fclose(fp);}int main() {int a[TIDNumber][ItemNumber] = { 0 };readDate(a); //读取数据setMinSupAndMinConf(); Set set;set.initialSet(a);continual = true;while (continual == true) {set.candidateSet(a);cout << "连接后的频繁项集：" << endl;set.printSet();}set.select(a);system("pause");return 0;}数据库1.txt
1 1 1 0
1 1 0 0
1 0 0 0
1 0 1 0
0 1 1 1
1 1 0 0
数据库2.txt
1 1 0 0 1 0
0 1 0 1 0 0
0 1 1 0 0 0
1 1 0 1 0 0
1 0 1 0 0 0
0 1 1 0 0 0
1 0 1 0 0 0
1 1 1 0 1 0
1 1 1 0 0 0
数据库3.txt
1 1 1 1 0 1 0 0 0 1 0
1 0 0 0 0 1 1 1 0 0 0
1 0 1 1 1 1 0 0 1 0 1
0 1 1 1 1 0 0 0 1 0 0
1 0 1 0 1 1 0 1 0 1 0
0 0 1 0 0 1 1 0 0 0 1
1 1 0 0 0 0 0 1 1 0 1
1 0 1 0 1 1 1 1 0 1 0
1 1 0 0 1 0 1 0 0 0 1
1 0 1 1 0 1 0 1 0 1 0
1 0 0 0 0 1 0 1 0 1 0
1 1 1 0 1 1 0 0 1 0 1
0 0 1 1 0 1 1 0 1 0 0
1 1 1 0 1 1 0 1 0 0 1
0 1 1 1 0 0 1 0 0 0 1
1 0 1 0 1 1 1 0 0 1 1
1 1 1 1 0 1 1 0 0 1 0
运行结果：（只演示数据库3）
数据库3：
注：没有明显的候选集，在产生一个候选集时同时判断是否满足，并从中剔除。
全部评论 (0)
还没有任何评论哟~