fp_treeview.cpp

关联规则fp算法

			{
				CHeadTable headTable;
				headTable=headTableArray.GetAt(j);
				headTable.setCount(0);
				headTable.right=NULL;
				projectArray.SetAt(j,headTable);
			}

			int count=array.GetAt(i).getCount();
			char buffer[20];
			if(item.GetLength())
			{
				suitem=str+","+item;
				if(findKeyitem(suitem))
					m_List4.InsertString(m_List4.GetCount(),suitem +":"+(_itoa)(count,buffer,10));
				//构建频繁模式基
			}
			else
			{
				suitem=str;
				if(findKeyitem(suitem))
					m_List4.InsertString(0,suitem +":"+(_itoa)(count,buffer,10));
			}	
			if(i)//最顶的头表项不用建频繁树
			{
				FPTNODE *line,*up;
				line=array.GetAt(i).right;
				while(line)
				{
					up=line;
					BOOL newLine=TRUE;
					FPTNODE *lastNode;
					lastNode=NULL;
					while(up->parent!=tree.tree)
					{
						up=up->parent;
						//newnode
						FPTNODE *node=new FPTNODE;
						node->count=line->count;
						node->item=up->item;
						//判断project树的情况
						if(newLine)
						{//新分支中第一个节点压入
							newLine=FALSE;
						
							node->firstchild=NULL;
							node->next_sibling=NULL;
							node->succ=NULL;
							
							node->parent=projectTree.tree;
												
							int index=checkItem(projectArray,node->item);
							if(projectArray.GetAt(index).right==NULL)//no this item in Array,add it into Array
							{
								CHeadTable headTable;
								headTable=projectArray.GetAt(index);
								headTable.setCount(node->count);
								headTable.right=node;
								projectArray.SetAt(index,headTable);
							}
							else
							{	
								CHeadTable headTable;
								headTable=projectArray.GetAt(index);
								headTable.setCount(headTable.getCount()+node->count);
								projectArray.SetAt(index,headTable);
								
								FPTNODE *pre,*p;
								p=projectArray.GetAt(index).right;
								pre=p;
								while(p->succ)
								{	pre=p;
									p=p->succ;
								}
								pre->succ=node;
								node->next_sibling=pre;//利用一下,作为左指针
							}
							lastNode=node;
						}
						else
						{	
							node->next_sibling=NULL;
							node->succ=NULL;

							node->parent=projectTree.tree;
							node->firstchild=lastNode;
							lastNode->parent=node;
							
							int index=checkItem(projectArray,node->item);
							if(projectArray.GetAt(index).right==NULL)//no this item in Array,add it into Array
							{
								CHeadTable headTable;
								headTable=projectArray.GetAt(index);
								headTable.setCount(node->count);
								headTable.right=node;
								projectArray.SetAt(index,headTable);
							}
							else
							{	
								CHeadTable headTable;
								headTable=projectArray.GetAt(index);
								headTable.setCount(headTable.getCount()+node->count);
								projectArray.SetAt(index,headTable);
								
								FPTNODE *pre,*p;
								p=projectArray.GetAt(index).right;
								pre=p;
								while(p->succ)
								{	pre=p;
									p=p->succ;
								}
								pre->succ=node;
								node->next_sibling=pre;//利用一下,作为左指针
							}
							lastNode=node;
						}
					}
						
					line=line->succ;
				}
				
				/////////////////修剪投影树 去掉支持度较小的头表项/////////
				for(int i=0;i<projectArray.GetSize();i++)
				{
					if(projectArray.GetAt(i).getCount()<m_minCount)
					{
						if(projectArray.GetAt(i).getCount()==0)
						{
							projectArray.RemoveAt(i);
							i--;
						}
						else
						{
							FPTNODE *p,*pre,*del;
							p=projectArray.GetAt(i).right;
							pre=p;
							while(p)
							{//四种情况
								if(p->firstchild)
								{
									if(p->parent==projectTree.tree)
									{
										p->firstchild->parent=projectTree.tree;
										del=p;
										p=p->succ;
										delete del;
									}
									else
									{
										p->parent->firstchild=p->firstchild;
										p->firstchild->parent=p->parent;
										del=p;
										p=p->succ;
										delete del;
									}
								}
								else
								{
									if(p->parent==projectTree.tree)
									{
										del=p;
										p=p->succ;
										delete del;
									}
									else
									{
										p->parent->firstchild=NULL;
										del=p;
										p=p->succ;
										delete del;
									}
								}
								
							}
							projectArray.RemoveAt(i);
							i--;	
						}
					}
				}
				/////////////////构建条件树 合并有相同父结点的项///////////
				for(int j=0;j<projectArray.GetSize();j++)
				{
					FPTNODE *first,*p,*del;
					first=projectArray.GetAt(j).right;
					while(first->succ)
					{
						p=first->succ;
						while(p)
						{
							
							while(p)
							{
								if(p->parent==first->parent)
									break;
								else
									p=p->succ;
									
							}
							if(p)//找到了相同父结点 处理一下
							{
								
								if(p->succ)
								{
									if(p->firstchild)
									{
										p->firstchild->parent=first;
									
										p->next_sibling->succ=p->succ;
										p->succ->next_sibling=p->next_sibling;
										first->count+=p->count;
										del=p;
										p=p->succ;
										delete del;

									}
									else
									{
										p->next_sibling->succ=p->succ;
										p->succ->next_sibling=p->next_sibling;
										first->count+=p->count;
										del=p;
										p=p->succ;
										delete del;
									
									}

								}
								else
								{
									if(p->firstchild)
									{	
										p->firstchild->parent=first;

										p->next_sibling->succ=NULL;
										first->count+=p->count;
										del=p;
										p=NULL;
										delete del;
									}
									else
									{
										p->next_sibling->succ=NULL;
										first->count+=p->count;
										del=p;
										p=NULL;
										delete del;
									}

									
								}
								
							}
							else
								p=NULL;
															
						}
						if(first->succ)
							first=first->succ;								
					}
								
				}
			///////////////////验证一下条件树 头表/////////////////////////////////////////
			/*	{
					m_List5.ResetContent();
					char buffer[20];
					for(int i=0;i<projectArray.GetSize();i++)
					{
						CString str="";
						str=projectArray.GetAt(i).getItemName()+':'+(_itoa)(projectArray.GetAt(i).getCount(),buffer,10);
						str+='|';
						FPTNODE *p;
						p=projectArray.GetAt(i).right;
						while(p)
						{
							str+=p->item+':'+(_itoa)(p->count,buffer,10);
							if(p->succ)
								str+=',';
							p=p->succ;
						}
						m_List5.AddString(str);	
					}
					//MessageBox("stop");

				}

			*/
			///////////////////条件树好了下面递归调用条件树////////////////////////////
				if(projectArray.GetSize()>0)
					fpGrowth(projectTree,projectArray,suitem);
					
			}
		
		}
		

	}
}



void CFp_treeView::OnDblclkList1()//头表 
{
	// TODO: Add your control notification handler code here
	if(m_List1.GetCount())
	{	
		CString str;
		m_List1.GetText(m_List1.GetCurSel(),str);
		m_List5.AddString(str);
		m_List1.DeleteString(m_List1.GetCurSel());

		//同时增加同步的m_List6 去尾;
		CString left;
		int temp;
		temp=str.Find('-');
		left=str.Left(temp);
		m_List6.AddString(left);

		UpdateData(FALSE);
	}
}

void CFp_treeView::OnDblclkList5()//关键频繁项表 
{
	// TODO: Add your control notification handler code here
	if(m_List5.GetCount())
	{	
		CString str;
		m_List5.GetText(m_List5.GetCurSel(),str);
		m_List1.AddString(str);
		int index=m_List5.GetCurSel();
		m_List5.DeleteString(index);
		//同时去掉同步的m_List6;
		m_List6.DeleteString(index);
		UpdateData(FALSE);
	}
	
}



BOOL CFp_treeView::findKeyitem(CString str)
{
	CString templeft,tempright;
	int temp=0;
	while(temp!=-1)
	{
		temp=str.Find(',');
		
		if(temp==-1)
			templeft=str;
		else
			templeft=str.Left(temp);
	
		tempright=str.Right(str.GetLength()-temp-1);
		
		//检查item 是否在m_List6里
		if(m_List6.GetCount())//到头表中查
		{
			if(m_List6.FindStringExact(-1,templeft)!=LB_ERR) return TRUE;
			str=tempright;
		}
		else
		{
			int index=checkItem(headTableArray,templeft);
			if(index>=0)// item in Array count++
			{	
				return TRUE;
			}	
	
			str=tempright;
		}
	}//while end of temp

	return FALSE;
}

int CFp_treeView::minValue(int x, int y)
{
	if(x<=y)
		return x;
	else 
		return y;
}

void CFp_treeView::OnSave() 
{
	// TODO: Add your control notification handler code here

	if(m_Connection!=NULL&&m_List4.GetCount())
	{
		m_ListBox.ResetContent();
		getTables();
		
		CString kooky;
		try
		{
			//创建实例
			m_Recordset.CreateInstance(_uuidof(Recordset));
			//以只读方式打开结果集,得到表名信息
			m_Recordset=m_Connection->OpenSchema(adSchemaTables,vtMissing,vtMissing);
			_CommandPtr pCmd(_uuidof(Command));
			pCmd->put_ActiveConnection(_variant_t((IDispatch*)m_Connection));
			if(m_ListBox.FindStringExact(-1,"fp_table")!=LB_ERR)
			{
				pCmd->CommandText="DROP TABLE fp_table";
				pCmd->Execute(NULL,NULL,adCmdText);
				pCmd->CommandText="CREATE TABLE fp_table (fpSets Text NULL)";
				pCmd->Execute(NULL,NULL,adCmdText);
			}
			else
			{
				pCmd->CommandText="CREATE TABLE fp_table (fpSets Text NULL)";
				pCmd->Execute(NULL,NULL,adCmdText);
			}
			//把频繁项集插入新建表中
			m_Recordset=NULL;
			m_Recordset.CreateInstance(_uuidof(Recordset));
			//开启数据连接,得到结果集
			m_Recordset->Open("fp_table",m_Connection.GetInterfacePtr(),adOpenDynamic,adLockOptimistic,adCmdTable);
		
			CString str;
			for(int i=0;i<m_List4.GetCount();i++)
			{
				m_List4.GetText(i,str);
				m_Recordset->AddNew();
				m_Recordset->PutCollect("fpSets",_variant_t(str));
				m_Recordset->Update();
			}

		}
		//捕获异常_com_error
		catch(_com_error &e)
		{
			GenerateError(e.Error(),e.Description());
		}
		//捕获其他异常
		catch(...){}
		m_ListBox.ResetContent();
		getTables();

	}

	
}

void CFp_treeView::OnDel() 
{
	// TODO: Add your control notification handler code here
	if(m_Connection!=NULL&&m_ListBox.GetCount())
	{	
		m_ListBox.ResetContent();
		getTables();
		
		try
		{
		
			_CommandPtr pCmd(_uuidof(Command));
			pCmd->put_ActiveConnection(_variant_t((IDispatch*)m_Connection));
			if(m_ListBox.FindStringExact(-1,"fp_table")!=LB_ERR)
			{
				pCmd->CommandText="DROP TABLE fp_table";
				pCmd->Execute(NULL,NULL,adCmdText);
				m_ListBox.ResetContent();
				getTables();
			
				if(m_strTableName=="fp_table")
				{
					m_DataGrid.SetRefDataSource((LPUNKNOWN)m_Recordset);
					//刷新DataGrid
					m_DataGrid.Refresh();
					resetList();
					
				}
			}
			
		}
		//捕获异常_com_error
		catch(_com_error &e)
		{
			GenerateError(e.Error(),e.Description());
		}
		//捕获其他异常
		catch(...){}
		
	}

}



void CFp_treeView::resetList()
{
	m_List1.ResetContent();
	m_List2.ResetContent();
	m_List3.ResetContent();
	m_List4.ResetContent();
	m_List5.ResetContent();
	m_List6.ResetContent();

	m_Edit1="";
	m_dmTime = _T("挖掘时间:");
	UpdateData(FALSE);

}

void CFp_treeView::comb(int n, int m, int buff[], int count, CArray<CHeadTable,CHeadTable> &itemArray, CArray<CHeadTable,CHeadTable> &itemSet)
{
	if( m == 0 )
	{// 递归退出条件
		int minCount,currCount;
		minCount=itemArray.GetAt(0).getCount();
		CHeadTable headTable;
		CString str="";
		for( int i=0;i<count;++i)
		{
		//	printf("%c ", chart[buff[i]-1]);
			int j=buff[i]-1;
			currCount=itemArray.GetAt(j).getCount();
			if(str.GetLength())
			{
				str+=','+itemArray.GetAt(j).getItemName();
					
			}
			else
			{
				str=itemArray.GetAt(j).getItemName();
			}
			minCount=minValue(minCount,currCount);

		}

						
		headTable.right=NULL;
		headTable.setCount(minCount);
		headTable.setItemName(str);
		itemSet.Add(headTable);
		
		return;
	} 
	for( int i=0; i<= n - m; ++i )
	{
	  buff[count++] = n-i;
	  comb( n-i-1, m-1,buff,count,itemArray,itemSet);
	  --count;
	}
}