fp_treeview.cpp

关联规则fp算法

	//////////////////////////重排表项 先构造一个vector///////////
		//tempArray从headTableArray COPY 项目的count项清0 
		tempArray.RemoveAll();
		tempArray.Copy(headTableArray);
		for(int k=0;k<headTableArray.GetSize();k++)
		{
			CHeadTable headTable;
			headTable=headTableArray.GetAt(k);
			headTable.setCount(0);
			tempArray.SetAt(k,headTable);
		}

		sortIterator=sortVector.begin();
		try
		{
			//创建实例
			m_Recordset.CreateInstance(_uuidof(Recordset));
			//将控件中的值保存到变量中,主要是保存SQL语句
			UpdateData(TRUE);
			//设定光标服务
			m_Connection->CursorLocation=adUseClient;
			//根据连接字符串开启数据连接,得到结果集
			m_Recordset->Open(m_strSQL.GetBuffer(0),m_Connection.GetInterfacePtr(),adOpenDynamic,adLockOptimistic,adCmdText);
			
			m_Recordset->MoveFirst();
			CString str,templeft,tempright;
			while(!m_Recordset->adoEOF)
			{
				_variant_t   varcheck;   
				varcheck=m_Recordset->GetCollect(_variant_t(m_strColName));
				if(varcheck.vt!=VT_NULL)
				{
					str=(char*)(_bstr_t)varcheck;	
					str.TrimLeft();
					str.TrimRight();
					int temp=0;

					char sign;
					if(str.Find(',')!=-1) sign=',';
					else if(str.Find('|')!=-1) sign='|';
					else if(str.Find(' ')!=-1) sign=' ';
					
					while(temp!=-1)
					{
						temp=str.Find(sign);
						
						if(temp==-1)
							templeft=str;
						else
							templeft=str.Left(temp);
					
						tempright=str.Right(str.GetLength()-temp-1);
						
						//检查item 修改tempArray
						int index=checkItem(headTableArray,templeft);
						if(index>=0)// item in Array count++
						{	
							CHeadTable headTable;
							headTable=tempArray.GetAt(index);
							headTable.setCount(headTable.getCount()+1);
							tempArray.SetAt(index,headTable);
						}	
					
						str=tempright;
					}//while end of temp
						
					//重排item表
					CString strBuffer="";
					BOOL signFlag=FALSE;
					
					for(int j=0;j<tempArray.GetSize();j++)
					{
						if(tempArray.GetAt(j).getCount()>0)
						{
							if(signFlag) strBuffer+=sign;
							int k=tempArray.GetAt(j).getCount();
							while(k)
							{
								if(k==1)
									strBuffer+=tempArray.GetAt(j).getItemName();
								else
									strBuffer+=tempArray.GetAt(j).getItemName()+sign;
								CHeadTable headTable;
								headTable=tempArray.GetAt(j);
								headTable.setCount(headTable.getCount()-1);
								
								tempArray.SetAt(j,headTable);
								k--;
							}
							signFlag=TRUE;
						}
					}
					sortVector.push_back(strBuffer);
					sortIterator++;
				}
				m_Recordset->MoveNext();
			} //the end of while of (adoEOF)
			m_Recordset->Close();
		}
		//捕获异常_com_error
		catch (_com_error &e)
		{
			GenerateError(e.Error(),e.Description());
		}
		//捕获其他异常
		catch(...){}

////////////////////////重排表排好了,验证一下///////////////////
		m_List2.ResetContent();
		sortIterator=sortVector.begin();
		while(sortIterator!=sortVector.end())
		{
			m_List2.AddString(*sortIterator);
			sortIterator++;
		}

	//////////////////////////////以下为构建FP树////////////
		sortIterator=sortVector.begin();
		CString str;
		while(sortIterator!=sortVector.end())
		{
			str=*sortIterator;
			str.TrimLeft();
			str.TrimRight();
	
			constructTree(str);//调用insertTree构建树
			sortIterator++;
		}
//////////////////////////////FP树构建好了遍历一下//////////////
		m_List3.ResetContent();
		for(int l=0;l<headTableArray.GetSize();l++)
		{
			CString str="";
			FPTNODE *p;
			p=headTableArray.GetAt(l).right;
			char buffer[20];
			if(p)
			{
				while(p)
				{
					str+=p->item+":"+(_itoa)(p->count,buffer,10)+" ";
					p=p->succ;
				}
				m_List3.AddString(str);	
			}
		}
	
		m_List5.ResetContent();//关键频繁项列表清空
		m_List4.ResetContent();//频繁项目集列表清空
		m_List6.ResetContent();//同步频繁项列表清空
		
		UpdateData(FALSE);
	}

}

int CFp_treeView::checkItem(CArray<CHeadTable,CHeadTable> &checkArray, CString item)
{
	for(int i=0;i<checkArray.GetSize();i++)
	{
		if(checkArray.GetAt(i).getItemName()==item)
			return i;
		else
			continue;
	}
	return -1;
}

void CFp_treeView::sortItem(int index,int count)
{
	BOOL flag=FALSE;
	for(int i=0;i<index;i++)//从表头到index 找到第一个比index小的 与其交换
	{	
		if(headTableArray.GetAt(i).getCount()<count)
		{
			CHeadTable headTable;
			headTable=headTableArray.GetAt(i);
			headTableArray.SetAt(i,headTableArray.GetAt(index));
			headTableArray.SetAt(index,headTable);
			flag=TRUE;
		}
		else 
			continue;
		if(flag) break;
	}

}

void CFp_treeView::constructTree(CString items)
{
	CString str,templeft,tempright;
	str=items;
	if(str.GetLength()==0)
		return;
	insertTree(fptree,str);
}

void CFp_treeView::insertTree(CTree &tree, CString items)
{
	CString str,templeft,tempright;
	str=items;
	
	int temp=0;
	char sign;
	if(str.Find(',')!=-1) sign=',';
	else if(str.Find('|')!=-1) sign='|';
	else if(str.Find(' ')!=-1) sign=' ';
	//取出第一个item
	temp=str.Find(sign);
	if(temp==-1)
		templeft=str;
	else
		templeft=str.Left(temp);
	
	if(str.GetLength()==templeft.GetLength())
	{
		tempright="";
		insertNode(tree,templeft,tempright);//插入本记录最后一个结点
		return;//递归终止
	}
	else
	{
		tempright=str.Right(str.GetLength()-temp-1);
		insertNode(tree,templeft,tempright);
	}
}

void CFp_treeView::insertNode(CTree &tree, CString item, CString items)
{
	//检查item 是否存在树的子结点与其同名
	BOOL sameItem;
	sameItem=FALSE;
	FPTNODE *p,*pre;
	p=tree.tree->firstchild;
	pre=p;

	if(p==NULL)
	{
		//先构造一个结点
		FPTNODE *node=new FPTNODE;
		node->count=1;
		node->item=item;
		node->firstchild=NULL;
		node->next_sibling=NULL;
		node->succ=NULL;
		node->parent=tree.tree;//care
	
		tree.tree->firstchild=node;

		fptree.tree->count++;
	
		//检查item在headTableArray中
		int index=checkItem(headTableArray,item);
		if(index>=0)// item in Array 
		{	
			if(headTableArray.GetAt(index).right)
			{
				FPTNODE *p;
				p=headTableArray.GetAt(index).right;
				while(p->succ)
				{
					p=p->succ;
				}
				p->succ=node;
			}
			else
			{
				CHeadTable headTable;
				headTable=headTableArray.GetAt(index);
				headTable.right=node;
				headTableArray.SetAt(index,headTable);
			}

		}

		if(items.GetLength()!=0)
		{
			CTree temptree;
			temptree.tree=node;
			insertTree(temptree, items);
		}
	}
	else
	{
		while(p)
		{
			if(p->item==item)
			{
				p->count++;
				sameItem=TRUE;
				fptree.tree->count++;
			}
			else
			{
				pre=p;
				p=p->next_sibling;
			}
			if(sameItem) break;
		}
		if(sameItem)//发现
		{
			if(items.GetLength()!=0)
			{
				CTree temptree;
				temptree.tree=p;
				insertTree(temptree, items);
			}
		}
		else//未发现
		{
			//先构造一个结点
			FPTNODE *node=new FPTNODE;
			node->count=1;
			node->item=item;
			node->firstchild=NULL;
			node->next_sibling=NULL;
			node->succ=NULL;
			node->parent=pre->parent;//care
			pre->next_sibling=node;

			fptree.tree->count++;
			
			//检查item在headTableArray中
			int index=checkItem(headTableArray,item);
			if(index>=0)// item in Array count++
			{	
				if(headTableArray.GetAt(index).right)
				{
					FPTNODE *p;
					p=headTableArray.GetAt(index).right;
					while(p->succ)
					{
						p=p->succ;
					}
					p->succ=node;
				}
				else
				{
					CHeadTable headTable;
					headTable=headTableArray.GetAt(index);
					headTable.right=node;
					headTableArray.SetAt(index,headTable);
				}

			}

			if(items.GetLength()!=0)
			{
				CTree temptree;
				temptree.tree=node;
				insertTree(temptree, items);
			}
		}
		
	}
}


//////////////////////////////从FP树中挖掘频繁项目集////////////
void CFp_treeView::OnTest1() 
{
	if(m_ButtonFlag==0)//没有选中列
		return;
	// TODO: Add your control notification handler code here
	clock_t start;
	start = clock();
	CString time="";
	char buffer[20];
	
	
	m_List4.ResetContent();
	CString str="";
	if(headTableArray.GetSize()>0)
		fpGrowth(fptree,headTableArray,str);

	time=_itoa((clock()-start),buffer,10);
	m_dmTime=_T("挖掘时间:\n"+time+"毫秒");

	m_Edit1=(_itoa)(m_List4.GetCount(),buffer,10);
	UpdateData(FALSE);
	
}


void CFp_treeView::fpGrowth(CTree &tree, CArray<CHeadTable,CHeadTable> &array, CString item)
{
	
	//判断tree是否是单枝树 单枝树的判定(很有技巧)
	BOOL singleFlag=TRUE;
	FPTNODE *p;
	p=array.GetAt(array.GetSize()-1).right;
	
	/*	
	if((array.GetSize()>1)&&(p->parent==tree.tree))
		singleFlag=FALSE;
		
	while(p!=tree.tree)
	{
		if(p->succ)			
		{
			singleFlag=FALSE;
			break;
		}
		else
			p=p->parent;
	}*/

		
	while(p!=tree.tree)
	{
		if(p->succ||(p->parent==tree.tree&&array.GetAt(0).right!=p))			
		{
			singleFlag=FALSE;
			break;
		}
		else
			p=p->parent;
	}


	if(singleFlag)
	{
		//m_List4.AddString("是单枝树用组合输出频繁项");
		CArray<CHeadTable,CHeadTable> keyItemArray,notkeyItemArray,keyItemset,notkeyItemset;
		FPTNODE *p;
		p=array.GetAt(array.GetSize()-1).right;
		while(p!=tree.tree)
		{
			if(findKeyitem(p->item))
			{
				CHeadTable headTable;
				headTable.right=NULL;
				headTable.setCount(p->count);
				headTable.setItemName(p->item);
				keyItemArray.Add(headTable);
				p=p->parent;
					
			}
			else
			{
				CHeadTable headTable;
				headTable.right=NULL;
				headTable.setCount(p->count);
				headTable.setItemName(p->item);
				notkeyItemArray.Add(headTable);
				p=p->parent;
			}
		}
			
		
		//关键项目组合
		{
			int buffer1[100];
			for(int i=1;i<=keyItemArray.GetSize();i++)
				comb(keyItemArray.GetSize(),i,buffer1,0,keyItemArray,keyItemset);
		}
		//关键项目组合
		{
			int buffer2[100];
			for(int i=1;i<=notkeyItemArray.GetSize();i++)
				comb(notkeyItemArray.GetSize(),i,buffer2,0,notkeyItemArray,notkeyItemset);
		}
		
	
		
		//输出单枝树频繁项
		if(findKeyitem(item))//关键项在后缀项上,全输出
		{
			char buffer[20];
			for(int i=0;i<keyItemset.GetSize();i++)
			{
				CString str;
				if(item.GetLength())
					 str=keyItemset.GetAt(i).getItemName()+","+item+":"+(_itoa)(keyItemset.GetAt(i).getCount(),buffer,10);
				else
					 str=keyItemset.GetAt(i).getItemName()+":"+(_itoa)(keyItemset.GetAt(i).getCount(),buffer,10);

				m_List4.AddString(str);
			}
			
			for(int j=0;j<keyItemset.GetSize();j++)//关键项和非关键项的组合输出
				for(int k=0;k<notkeyItemset.GetSize();k++)
				{
					CString str;
					if(item.GetLength())
						 str=keyItemset.GetAt(j).getItemName()+","+notkeyItemset.GetAt(k).getItemName()+","+item+":"+(_itoa)(minValue(keyItemset.GetAt(j).getCount(),notkeyItemset.GetAt(k).getCount()),buffer,10);
					else
						 str=keyItemset.GetAt(j).getItemName()+","+notkeyItemset.GetAt(k).getItemName()+":"+(_itoa)(minValue(keyItemset.GetAt(j).getCount(),notkeyItemset.GetAt(k).getCount()),buffer,10);
					m_List4.AddString(str);
					
				}

			for(int k=0;k<notkeyItemset.GetSize();k++)//非关键项组合输出(因为关键项在后缀项上)
			{
				CString str;
				if(item.GetLength())
					 str=notkeyItemset.GetAt(k).getItemName()+","+item+":"+(_itoa)(notkeyItemset.GetAt(k).getCount(),buffer,10);
				else
					 str=notkeyItemset.GetAt(k).getItemName()+":"+(_itoa)(notkeyItemset.GetAt(k).getCount(),buffer,10);

				m_List4.AddString(str);
			
			}

		}
		else//关键项不在头表,分二步输出
		{
			char buffer[20];
			for(int i=0;i<keyItemset.GetSize();i++)
			{
				CString str;
				if(item.GetLength())
					 str=keyItemset.GetAt(i).getItemName()+","+item+":"+(_itoa)(keyItemset.GetAt(i).getCount(),buffer,10);
				else
					 str=keyItemset.GetAt(i).getItemName()+":"+(_itoa)(keyItemset.GetAt(i).getCount(),buffer,10);

				m_List4.AddString(str);
			
			}
			
			for(int j=0;j<keyItemset.GetSize();j++)//关键项和非关键项的组合输出
				for(int k=0;k<notkeyItemset.GetSize();k++)
				{
					CString str;
					if(item.GetLength())
						 str=keyItemset.GetAt(j).getItemName()+","+notkeyItemset.GetAt(k).getItemName()+","+item+":"+(_itoa)(minValue(keyItemset.GetAt(j).getCount(),notkeyItemset.GetAt(k).getCount()),buffer,10);
					else
						 str=keyItemset.GetAt(j).getItemName()+","+notkeyItemset.GetAt(k).getItemName()+":"+(_itoa)(minValue(keyItemset.GetAt(j).getCount(),notkeyItemset.GetAt(k).getCount()),buffer,10);
					m_List4.AddString(str);
				}
		}
	
	}
	else
	{	
		//m_List4.AddString("分枝树先构建频繁模式基");
	
		int i=array.GetSize()-1;
		for(i;i>=0;i--)
		{
			CString str=array.GetAt(i).getItemName();
			CString suitem;				//后缀项
			CTree projectTree;
			
			CArray<CHeadTable,CHeadTable> projectArray;//新头表
			projectArray.RemoveAll();
			projectArray.Copy(headTableArray);
			for(int j=0;j<headTableArray.GetSize();j++)