FP-growth优化算法

// FpTree.cpp: implementation of the CFpTree class. // ////////////////////////////////////////////////////////////////////// #include "FpTree.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// CFpTree::CFpTree() { } CFpTree::~CFpTree() { } /************************************************************************/ /* 释放项头列表的空间 释放数空间 */ /************************************************************************/ void CFpTree::Destroy() { delete []headerTableLink; delete []m_DB; destroyTree(root); destroyLargeItemset(); } void CFpTree::destroyTree(FPTreeNode node) { childLink temp1, temp2; if (node == NULL) return; temp1 = node->children; while(temp1 != NULL) { temp2 = temp1->next; destroyTree(temp1->node); free(temp1); temp1 = temp2; } free(node); return; } void CFpTree::destroyLargeItemset() { LargeItemPtr temp; temp = largeItemset->next; while (temp != NULL) { free(largeItemset); largeItemset = temp; temp = largeItemset->next; } free(largeItemset); } /************************************************************************/ /* 构造函数 传入数据：事务数据库 最小支持数 */ /************************************************************************/ CFpTree::CFpTree(CElement lst[], int minSupport) { threshold = minSupport; largeItemsetNum = 0; m_DB = new CElement[NUMBERTRANS]; for (int i=0; i<NUMBERTRANS;i++) { m_DB[i] = lst[i]; // Sort(m_DB[i]); } /* for (int j=0; j<NUMBERTRANS;j++) { for (int k=0; k<m_DB[j].size(); k++) { cout<<m_DB[j][k]; } cout<<endl; } */ } /************************************************************************/ /* 生成一阶频繁项集 生成的一阶频繁项集保存在类成员变量 largeItemset1 对应频繁项集的支持数保存在类成员变量largeItemSup1 */ /************************************************************************/ void CFpTree::GenFrequentPattern1() { int i,j,k; CElement ItemSet1(MAXITEMNUM); // 存储事务中的单个项 vector<int> ItemSup1(MAXITEMNUM); // 存储支持度计数 int G_num=0; for (i = 0;i < NUMBERTRANS; i++) { CElement G_tempelement; //互联设备挖掘需要读数据库 //读入一个事务 G_tempelement = m_DB[i]; for (j = 0; j < G_tempelement.size(); j++) { //判断是否有相同的项出现，若有则计数加1 for (k = 0; k < G_num; k++) { if (ItemSet1[k] == G_tempelement[j]) { ItemSup1[k]++; break; } } //如果遍历没有出现相同的项，则加入新出现的项到 ItemSet1 if (k == G_num) { ItemSet1[G_num] = G_tempelement[j]; ItemSup1[G_num] = 1; //项第一次出现，计数为1 G_num++; //存储的项的长度加1 } } } vector<bool> G_iflag(G_num); largeItemNum1=0; //用于记录一阶频繁项集的个数 for( i = 0; i < G_num; i++) { G_iflag[i]=false; // 判断支持度 if (ItemSup1[i] >= threshold) { G_iflag[i] = true; largeItemNum1++; } } CElement G_OneItemFrequentSet(largeItemNum1); //用于存储一阶频繁项集 vector<int> G_OneItemFrequentSup(largeItemNum1); //用于存储一阶频繁项集的支持度计数 int tempitemnum=0; for (i = 0; i < G_num; i++) { if (G_iflag[i]) { G_OneItemFrequentSet[tempitemnum] = ItemSet1[i]; G_OneItemFrequentSup[tempitemnum] = ItemSup1[i]; tempitemnum++; } } largeItemset1 = G_OneItemFrequentSet; largeItemSup1 = G_OneItemFrequentSup; SortItemset(); //按照支持度排序 // 逐次加入一阶频繁项集的各个项 for (i = 0; i < largeItemset1.size(); i++) { CElement aitemset1(1); aitemset1[0] = largeItemset1[i]; AddLargeToList(aitemset1,largeItemSup1[i], i); //将一阶频繁项集加入链表 largeItemsetNum++; //频繁项集的个数加1 } //输出一阶频繁项集 cout<<"一阶频繁项集为："<<endl; for (i = 0; i < largeItemset1.size(); i++) { cout<<largeItemset1[i]; cout<<" "<<largeItemSup1[i]<<endl; } } /*********************************************************************** 函数说明: 建立频繁项集链表，将频繁项集存入链表 参数说明： aitemset: 频繁项集 msupport: 频繁项集的支持数 start: 用于判断是否为头结点 ************************************************************************ ***********************************************************************/ void CFpTree::AddLargeToList(CElement aitemset, int msupport, int start) { //当前的要插入链表的频繁项集的节点指针 LargeItemPtr tempptr; // 分配内存 tempptr = (LargeItemPtr) malloc (sizeof(ItemsetNode)); //获取频繁项集的信息 tempptr->support = msupport; //频繁项集的支持数 tempptr->itemnum = aitemset.size(); //频繁项集的项数 tempptr->next = NULL; //指向下一个频繁项集的指针 //将频繁项集的各个项赋值给节点中的项 for (int i=0; i<aitemset.size(); i++) { tempptr->itemset[i] = aitemset[i]; } //判断是否为头结点，即是否为第一次执行 if (start == 0) { largeItemset = tempptr; } else { LargeItemPtr pre = largeItemset; // pre是头节点的指针 LargeItemPtr post = largeItemset->next; // post是头节点的 nxet 的指针 //找到待插入的位置，以频繁项集的个数，和频繁项集的支持数排序 //第一次执行，post为空 while (post != NULL) { //首先比较节点之间的频繁项集的项的个数 if (post->itemnum < tempptr->itemnum)//插入的频繁项集的项数大于已经插入的频繁项集的项数 { pre = pre->next; post = post->next; } else if (post->itemnum == tempptr->itemnum) { //如果项的个数相等，则比较节点之间的频繁项集的支持度 if (post->support > tempptr->support) { pre = pre->next; post = post->next; } else { break; } } else { break; } } tempptr->next = post; //将post指针copy给当前节点所指向的下一个节点 pre->next = tempptr; //将当前节点指针copy给前一节点的next指针 // largeItemsetlast->next = tempptr; // largeItemsetlast = tempptr; } } /************************************************************************/ /* 冒泡排序:根据各项的支持数对项集进行排序，从大到小 根据各个项的支持数对项集进行排序：冒泡排序方法 被调用：GenFrequentPattern1() 生成一阶频繁项集的时候会用到 调用：无 输出：依照支持数排好序的一阶频繁项集*/ /************************************************************************/ void CFpTree::SortItemset() { int j, acount; int pass = 1; int exchange = 1; //标记是否互换 while (pass < largeItemNum1 && exchange) // largeItemNum1为一阶频繁项集的个数 { exchange = 0; // 从后向前遍历一阶频繁项集 for ( j = largeItemNum1-1; j >= pass; j--) { if ( (largeItemSup1[j-1] < largeItemSup1[j]) || ( (largeItemSup1[j-1] == largeItemSup1[j]) && (largeItemset1[j-1] > largeItemset1[j]) ) ) { // 项互换 ItemType aitem = largeItemset1[j]; largeItemset1[j] = largeItemset1[j-1]; largeItemset1[j-1] = aitem; // 相应的支持度互换 acount = largeItemSup1[j]; largeItemSup1[j] = largeItemSup1[j-1]; largeItemSup1[j-1] = acount; exchange = 1; } } pass++; } } ///////////对当前一条事务进行排序并且将非频繁1项集从事务中删除////////////////// void CFpTree::SortItemsetByHT(CTransaction & aitemset) { int i,j; bool Sorted=false; int clength=aitemset.size(); /* cout<<"事务："; for(i=0;i<clength;i++) { cout<<aitemset[i]<<" "; } cout<<endl; */ vector<bool> flag(largeItemNum1); for (i=0;i<largeItemNum1;i++) { flag[i]=false; } int largefreitemnum=0; //比较当前事务中的项是否和一阶频繁项集中有相同的项,做标记 for (i=0;i<largeItemNum1;i++) { for (j=0;j<clength;j++) { if (largeItemset1[i]==aitemset[j]) { //给存在的项做标记，以便