数据挖掘-FP-tree算法

#include<bits/stdc++.h>
using namespace std;
#define maxn 90000
#define N 88162
#define min_t 88162*0.01 
#define Max 300000//开一个堆定义的数组就不会崩掉
int cnt_sum = 0 ; 
using namespace std;
struct Dnode//数据库节点 
{int num;//数据项 int cnt;//次数 
};
struct Tnode //树的节点 存下孩子节点以及双亲节点 
{int po; //在数组的下标位置 int num;//项 int cnt;//次数 vector<int> v;//孩子节点 int pre;//前驱节点 
};
struct Hnode//头表的节点 存下所有当前值的叶子结点 
{int num;//项int cnt;//次数vector<int> v;//所有同项的"叶子"节点 
};
char db[maxn][505]; 
list<Dnode> DB[maxn];//定义一个数据库 每个记录都是一个list
list<Dnode> ::iterator DB_iter;
bool cmp(Dnode x,Dnode y)
{if(x.cnt!=y.cnt)return x.cnt>y.cnt;elsereturn x.num>y.num; 
}
bool h_cmp(Hnode x,Hnode y)
{if(x.cnt!=y.cnt)return x.cnt>y.cnt;elsereturn x.num>y.num; 
}
void init()//初始化 只进行字符转int 
{for(int i = 1;i<=N;i++)gets(db[i]);for(int i = 1;i<=N;i++){int len = strlen(db[i]);//每条记录的长度 int j = 0;while(j< len){if(db[i][j] == ' ')//是空格 跳过{j++;continue;}else{//计算数值Dnode data;int value = 0;while(j< len&&db[i][j]!=' ')//直到出现空格或者结束为止{//开始 字符转数字int x = 0;x = db[i][j]-'0';value = value * 10 + x;  j++;if(j==len)break;} data.num = value;data.cnt = 1;DB[i].push_back(data);//一个规整的数据集 } }}	
}
//由数据库 得到条件模式集CPB 即删除和排序
list<Hnode> GetCPB_and_Head(list<Dnode> *data_base,int db_cnt)//由数据集 得到条件模式集 
{list<Dnode> ::iterator db_iter;map<int,int> one_f;//记录单个项出现次数map<int,int> ::iterator one_f_iter;one_f.clear();for(int i = 1;i<=db_cnt;i++){for(db_iter = data_base[i].begin();db_iter != data_base[i].end();db_iter++){int value = (*db_iter).num;one_f[value] +=(*db_iter).cnt;//注意数据库的单项次数 不一定是1 再递归的时候可能不是 }} for(one_f_iter = one_f.begin();one_f_iter != one_f.end();){if(one_f_iter->second<min_t)//删除one_f.erase(one_f_iter++);elseone_f_iter++;}list<Hnode> head;for(one_f_iter = one_f.begin();one_f_iter != one_f.end();one_f_iter++){Hnode h;h.num = one_f_iter->first;h.cnt = one_f_iter->second;h.v.clear();head.push_back(h);}head.sort(h_cmp);//得到 数据集 for(int i = 1;i<=db_cnt;i++)//删库排序 {for(db_iter = data_base[i].begin();db_iter!=data_base[i].end();){int n_num = (*db_iter).num;if(one_f[n_num]<min_t)data_base[i].erase(db_iter++);else{
//				(*db_iter).cnt = one_f[n_num];db_iter++;}}DB[i].sort(cmp);//构建了排序后的数据集 	}return head;
} 
//list<Hnode>* GetHead(list<Dnode> data_base[],int db_cnt)//由数据集得到头表 
//{
//	list<Hnode> head[Max];
//	list<Dnode> ::iterator db_iter;
//	map<int,int> one_f;//记录单个项出现次数
//	map<int,int> ::iterator one_f_iter;
//}
int maxn_t ;//tree树的数组最大长度 
/*vector<Tnode>*/int BuildTree(Tnode *node_tree,list<Hnode> &head,list<Dnode> data_db[],int db_cnt)
{
//	vector<Tnode> node_tree;
//	Tnode node_tree[100];
//	node_tree.clear();int data_tree_cnt = 1;//计数器 Tnode t_tree,dx_tree;t_tree.num = 0;t_tree.cnt = 0;t_tree.pre= -1;t_tree.v.clear();t_tree.po = 0;//在数组的位置 node_tree[0] = t_tree;for(int i = 1;i <= db_cnt ;i++)//遍历每一条记录 {
//		if(DB[i].size()==0)
//			continue;//从根节点开始判断是否已经存在dx_tree = node_tree[0];//取出排序的记录list<Dnode> d_l;list<Dnode> ::iterator d_l_iter;d_l = data_db[i];for(d_l_iter = d_l.begin();d_l_iter!=d_l.end();d_l_iter++)//迭代 记录的每个单项 (结构体){//判断当前项在此节点的孩子中是否出现  
//			vector<int> dx_v = dx_tree.v;//找到存孩子的容器 
//			cout<<(*d_l_iter).num<<" ";vector<int> ::iterator dx_tree_iter;bool flag = false;//判断是否时孩子节点 
//			int pre_po = dx_tree.po;//当该节点不是这个的孩子时 要指向这个节点 
//			cout<<dx_tree.v.size()<<"#";for(dx_tree_iter = dx_tree.v.begin();dx_tree_iter!=dx_tree.v.end();dx_tree_iter++){
//				cout<<data_tree[*(dx_tree_iter)]<<" "<<(*d_l_iter).num<<endl;
//				cout<<"i: "<<i;if(node_tree[*(dx_tree_iter)].num == (*d_l_iter).num)//是同一个项{
//					cout<<"-1";
//					dx_po = *(dx_tree_iter);//更改新的路径 node_tree[*(dx_tree_iter)].cnt+= (*d_l_iter).cnt;//计数加一 dx_tree = node_tree[*(dx_tree_iter)];//找到这个路径flag = true;break;} }if(flag == false){//如果没有出现过的话：新建立一个节点，保存在数组中 保存数据 次数为1 项表头存下这个节点在数组的下标
//				cout<<"-1"; Tnode new_node;new_node.po  = data_tree_cnt;new_node.cnt = (*d_l_iter).cnt;new_node.num = (*d_l_iter).num;
//				cout<<(*d_l_iter).num;new_node.pre = dx_tree.po;new_node.v.clear();node_tree[data_tree_cnt] = new_node;
//				data_tree[data_tree_cnt] = new_node.num;
//				int po = one_f[new_node.num];
//				cout<<dx_po<<endl;list<Hnode> ::iterator H_iter;for(H_iter = head.begin();H_iter != head.end();H_iter++){if((*H_iter).num == (*d_l_iter).num)//找到这个表头{(*H_iter).v.push_back(data_tree_cnt);break;} }
//				head[po].v.push_back(data_tree_cnt); //项表头 
//				cout<<"head: "<<head_num[po].v.size();node_tree[dx_tree.po].v.push_back(data_tree_cnt); dx_tree = node_tree[data_tree_cnt];
//				dx_po = data_tree_cnt;
//				cout<<node_tree[dx_po].v.size()<<endl;data_tree_cnt++;} }}maxn_t = data_tree_cnt+5;//多开几个 防止溢出  return --data_tree_cnt;
//	return node_tree;
}
void FP_Growth(list<Dnode> data_b[],int db_cnt,list<Dnode> pattern)//传记录数据集 以及后缀模式 
{
//	list<Dnode> * old_data = data_b;list<Hnode> h ;h.clear(); h = GetCPB_and_Head(data_b,db_cnt);//剪枝 排序的数据集 以及得到头表 Tnode *tree_ = new Tnode[Max] ;//构建树的数组 int tree_cnt = BuildTree(tree_,h,data_b,db_cnt);//头表更新 且树建好int tree_maxn = maxn_t+5;//接下来判断树是否只有一条路径：特别的 没有路径直接返回if(tree_[0].v.size()==0)return ;//只有一条路径的时候 说明数据库的所有记录是相同的 头表元素容器都只有一个 list<Hnode> ::iterator h_iter;//借用下面的迭代器 bool flag = true; //判断头表是否只有一个 
//	if(h.size()!=0)
//		flag = true;//	list<Hnode> ::iterator hh_iter;
//	for(hh_iter = h.begin();hh_iter!=h.end();hh_iter++)
//	{
//		cout<<(*hh_iter).num<<" "<<(*hh_iter).cnt<<" "<<(*hh_iter).v.size()<<endl;
//	}
//	cout<<endl;if(flag == true)//说明只有一条路径{list<Dnode> ::iterator pat_iter;//输出后缀模式和 当前所有头节点的 子集 for(h_iter = h.begin();h_iter!=h.end();h_iter++){cout<<(*h_iter).num;
//			cout<<" :"<<(*h_iter).cnt; 
//			cout<<" #"<<pattern.size()<<"# ";for(pat_iter = pattern.begin();pat_iter != pattern.end();pat_iter++){cout<<","<<(*pat_iter).num;}cnt_sum ++;cout<<" "<<endl;}} 
//	for()//遍历下头表 /*...写 :求出 只有一条路径的时候 怎么和pattern 一起求出所有的集合 *///判断是否只有一条路径 //遍历表头 从下往上遍历:反向迭代 list<Hnode> ::reverse_iterator r_h_iter;for(r_h_iter = h.rbegin();r_h_iter!=h.rend();r_h_iter++){Hnode h_c = *(r_h_iter);//取出头表一个元素//找前驱项/* 新建一个数据记录表 存下前驱*/list<Dnode> data_little[maxn_t] ;int data_little_cnt = 1;//计数 vector<int> h_to_tree = h_c.v;//头表映射到树的数组里面vector<int> ::iterator h_tree_iter;//转换类型 Dnode new_h; new_h.num = h_c.num;new_h.cnt = h_c.cnt; 
//		//把当前元素放到 后缀模式中 list<Dnode> new_pat,old_pat = pattern ;new_pat.clear();new_pat = pattern ; 
//		cout<<"个数:#"<<new_pat.size()<<" ";new_pat.push_back(new_h); new_pat.sort(cmp);//新的后缀模式 for(h_tree_iter = h_to_tree.begin();h_tree_iter!=h_to_tree.end();h_tree_iter++){//每一个节点元素到顶 代表数据库的一个新的记录 并且当前节点的次数是这个路径上面所有元素的次数 Tnode new_tnode = tree_[*h_tree_iter];
//			cout<<"首个兄弟的位置:"<<*h_tree_iter;int path_cnt = new_tnode.cnt;//取出叶子的频率 if(new_tnode.pre==0||new_tnode.pre==-1)//直接与根相连continue; while(new_tnode.pre!=-1){new_tnode = tree_[new_tnode.pre];Dnode data;data.num = new_tnode.num;data.cnt = path_cnt;if(new_tnode.pre==-1)break; data_little[data_little_cnt].push_back(data);}data_little_cnt++;
//			data_little[data_little_cnt].push_back()}
//		cout<<"data_little_cnt:"<<data_little_cnt<<" ";
//		cout<<new_pat.size()<<"#"<<endl;;FP_Growth(data_little,--data_little_cnt,new_pat);maxn_t = tree_maxn+5;
//		cout<<"manx:"<<maxn_t<<"   "; 
//		data_b =  old_data;} 
}
int main()
{
//	freopen("Aprior-测试数据.txt","r",stdin); freopen("1.txt","r",stdin); init();list<Dnode> pat ; pat.clear();FP_Growth(DB,N,pat);cout<<"总个数: "<<cnt_sum<<endl; 
//	list<Hnode> ::iterator h_iter;
//	list<Hnode> h =  GetCPB_and_Head(DB,N);//更新数据集 变成了排序后的 并且得到了头表 
//	list<Dnode> *t = DB;//得到新的数据集 
//	Tnode tree[Max] ;int num =  BuildTree(tree,h,DB,N);/*vector<Tnode>*/ //数组的大小 //得到树的数组 并且更新了头表 
//	FP_Growth()
//	for(int i=1;i<=N;i++)
//	{
//		for(DB_iter = t[i].begin();DB_iter != t[i].end();DB_iter++)
//			cout<<(*DB_iter).num<<" ";
//		cout<<endl;
//	}
//	cout<<endl;
//	for(h_iter = h.begin();h_iter!=h.end();h_iter++)
//	{
//		cout<<(*h_iter).num<<" "<<(*h_iter).cnt<<" "<<(*h_iter).v.size()<<endl;
//	}
//	vector<Tnode> ::iterator t_v;
//	for(t_v = tree.begin();t_v != tree.end();t_v++)
//	{
//		cout<<tree
//	}
//	for(int i=1;i<=num;i++)
//	{
//		cout<<"num:"<<tree[i].num<<"  cnt:"<<tree[i].cnt<<"  pre:"<<tree[i].pre<<"  child.size:"<<tree[i].v.size()<<endl;
//	}
}