aprioriview.cpp

Apriori算法是一个求关联规则的经典算法

// AprioriView.cpp : CAprioriView 类的实现
//

#include "stdafx.h"
#include "Apriori.h"

#include "AprioriSet.h"
#include "AprioriDoc.h"
#include "AprioriView.h"
#include ".\aprioriview.h"
#include "SetPara.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// CAprioriView

IMPLEMENT_DYNCREATE(CAprioriView, CRecordView)

BEGIN_MESSAGE_MAP(CAprioriView, CRecordView)
	// 标准打印命令
	ON_COMMAND(ID_FILE_PRINT, CRecordView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CRecordView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CRecordView::OnFilePrintPreview)
	ON_COMMAND(ID_Parameter, OnParameter)
	ON_BN_CLICKED(IDC_Bn_FreqItem, OnBnFreqItem)
END_MESSAGE_MAP()

// CAprioriView 构造/析构

CAprioriView::CAprioriView()
	: CRecordView(CAprioriView::IDD)
{
	m_pSet = NULL;
	// TODO: 在此处添加构造代码
	

}

CAprioriView::~CAprioriView()
{
}

void CAprioriView::DoDataExchange(CDataExchange* pDX)
{
	CRecordView::DoDataExchange(pDX);
	// 可以在此处插入 DDX_Field* 函数以将控件“连接”到数据库字段，例如
	// DDX_FieldText(pDX, IDC_MYEDITBOX, m_pSet->m_szColumn1, m_pSet)
	// DDX_FieldCheck(pDX, IDC_MYCHECKBOX, m_pSet->m_bColumn2, m_pSet);
	// 有关更多信息，请参阅 MSDN 和 ODBC 示例
	DDX_Control(pDX, IDC_List_FreqItem, m_List_FreqItem);
}

BOOL CAprioriView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: 在此处通过修改 CREATESTRUCT cs 来修改窗口类或
	// 样式

	return CRecordView::PreCreateWindow(cs);
}

void CAprioriView::OnInitialUpdate()
{
	m_pSet = &GetDocument()->m_AprioriSet;
	CRecordView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();
}


// CAprioriView 打印

BOOL CAprioriView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// 默认准备
	return DoPreparePrinting(pInfo);
}

void CAprioriView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: 打印前添加额外的初始化
}

void CAprioriView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: 打印后添加清除过程
}


// CAprioriView 诊断

#ifdef _DEBUG
void CAprioriView::AssertValid() const
{
	CRecordView::AssertValid();
}

void CAprioriView::Dump(CDumpContext& dc) const
{
	CRecordView::Dump(dc);
}

CAprioriDoc* CAprioriView::GetDocument() const // 非调试版本是内联的
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CAprioriDoc)));
	return (CAprioriDoc*)m_pDocument;
}
#endif //_DEBUG


// CAprioriView 数据库支持
CRecordset* CAprioriView::OnGetRecordset()
{
	return m_pSet;
}



// CAprioriView 消息处理程序

void CAprioriView::OnParameter()
{
	// TODO: 在此添加命令处理程序代码
	CSetPara dlg;
    dlg.m_ItemCount =10;
    dlg.m_Item_Supp=0.2; 
    int ren=dlg.DoModal(); 
    nItemCount=dlg.m_ItemCount;
    dItemSupp=dlg.m_Item_Supp ;
}

void CAprioriView::OnBnFreqItem()
{
	// TODO: 在此添加控件通知处理程序代码
	
    int nDbCount;
	CString strValue;
	CString strIntToString="";

	clock_t start,stop,tick;
	double timeused;
	int nLargeCount=0;
	int nListFreqItemCount=0;
    start=clock();
	ClearItem();
	
    m_List_FreqItem.InsertColumn(0,"Item",LVCFMT_LEFT,100);
	m_List_FreqItem.InsertColumn(1,"Count",LVCFMT_LEFT,100);
    
	 
	if (nItemCount<=0)
	{
		MessageBox("请先进行参数设置",NULL,MB_OK);
	    return;
	}

	FindLargeItem();//分析事务数据库并提出1—频繁项目集

    for(int k=1;LargeItemCount[k-1]!=0;k++)
	{    
	     
		 AprioriGen(k,1);//实现Apriori算法的自连和剪枝
		
		//初始化数组
		for(int mm=0;mm<CandLargeItemCount[k];mm++)
		{	
				nCountCand[mm]=0;
		}
		
        m_pSet->MoveFirst();
		nDbCount=0;

		while(!m_pSet->IsEOF()) 
		{   
		  	
			TransGenCand(k,nDbCount);//
        		
		//统计计数
			for(int jj=0;jj<nTransCandCount;jj++)
		   		for(int jj1=0;jj1<CandLargeItemCount[k];jj1++)
				{   

					if(TransGenCandFreq[jj].Find(CandLargeItem[k][jj1])!=-1) 
					{ 	
					nCountCand[jj1]++;
					 break;
					}
				}
		  
			nDbCount++;
		  
			m_pSet->MoveNext(); 
			
		}
		
	     ShowFreqItem(k);//在List control控件上显示结果


	}
	stop=clock();

	tick=stop - start;
    timeused=(double)tick/CLK_TCK;
	strIntToString="";
	strIntToString.Format("%s%f",strIntToString,timeused);
	MessageBox(strIntToString,NULL,MB_OK);
}

void CAprioriView::ClearItem()
{   
	//清除列表显示的内容
    m_List_FreqItem.DeleteAllItems ();
	while(m_List_FreqItem.DeleteColumn (0));
	UpdateWindow();
	for(int kk=0;kk<nMaxSize;kk++)
	    LargeItemCount[kk]=0;
	for(int kk1=0;kk1<nMaxSize;kk1++)
		for(int kk2=0;kk2<nMaxSize;kk2++)
			LargeItem[kk1][kk2]="";

}


//分析事务数据库并提出1—频繁项目集

void CAprioriView::FindLargeItem()
{
	//显示1-频繁项目集
	int nFieldCount=m_pSet->GetODBCFieldCount();//获取字段个数
	int nCount=0;
	int nFreqItem[100];
	
    int nDbCount=0;
	CString strInit;
	CString strValue;
	CString strIntToString;
		
  // 初始C(1)候选项目集	
    for(int nInitCount=0;nInitCount<nItemCount;nInitCount++)
   {       
		strInit="";
		strInit.Format("%s%d",strInit,nInitCount+1); 
		CandLargeItem[0][nInitCount]='I'+strInit;

	}
  //初始化对C(1)项目记数的数组
	for(int ii=0;ii<nItemCount;ii++)
		nFreqItem[ii]=0;
	
	m_pSet->MoveFirst ();//移动到第一条记录指针
  //对C(1)项目集中的项目并记数
	while(!m_pSet->IsEOF())
	{
		for(int j=1;j<nFieldCount;j++)
		{
			m_pSet->GetFieldValue(j,strValue);
            //分解strValue值即事务值
            SubItemGen(nDbCount++ ,strValue);
            //记数		
			for(int i=0;i<nItemCount;i++)
				if(strValue.Find(CandLargeItem[0][i])!=-1)
					nFreqItem[i]++;
				
			
		}
		m_pSet->MoveNext();
	}

	nDbItemCount=nDbCount;//求出数据库事务个数

    //将候选集中大于最小支持度的项目找出并存储
    for(int i1=0;i1<nItemCount;i1++)
	{  strIntToString="";
	   if(double(nFreqItem[i1])/double(nDbItemCount)>=dItemSupp)//求出满足最小支持度的1频繁项目
		{  
		    LargeItem[0][nCount]=CandLargeItem[0][i1];
			m_List_FreqItem.InsertItem(nCount,strIntToString);
			m_List_FreqItem.SetItemText(nCount,0,LargeItem[0][nCount]);
			strIntToString="";
			strIntToString.Format("%s%d",strIntToString,nFreqItem[i1]);
			m_List_FreqItem.SetItemText(nCount,1,strIntToString);
			nCount++;
		}

	}
	//满足最小支持度的1-LargeItem的个数
	LargeItemCount[0]=nCount;


}

//把每个事务分解成单个项目并存储
void CAprioriView::SubItemGen(int strSubItemCount,CString strSubItem)
{
	CString strTemp1;
	CString strTempSubItem[10];
	CString strReverse;
	
	int nSubItemCount;
	int nstrRightTemp1;
	int nTempCount;

	strTemp1=strSubItem;
	nSubItemCount=0;
	//分解事务
	while((nstrRightTemp1=strTemp1.ReverseFind(','))!=-1)
	{
		nTempCount=strTemp1.GetLength() - nstrRightTemp1 - 1; 
		
		strTempSubItem[nSubItemCount++]=strTemp1.Right( nTempCount);
		strTemp1=strTemp1.Left(nstrRightTemp1);
	}
	//把一个事务最后的一个项目存入
    strTempSubItem[nSubItemCount++]=strTemp1;

    //交换存储顺序
	for(int i2=0;i2<nSubItemCount/2;i2++)
	{
		strReverse=strTempSubItem[nSubItemCount-i2-1];
		strTempSubItem[nSubItemCount- i2-1]=strTempSubItem[i2];
		strTempSubItem[i2]=strReverse;
	}
    //用二维数组存储事务数据库
     for(int i1=0;i1<nSubItemCount;i1++)
	 { 
		 DbItem[strSubItemCount][i1]=strTempSubItem[i1];
	    
   
	 }
	 DbItemCount[strSubItemCount]=nSubItemCount;//存入数据库中每个事务项目的个数
    
}

void CAprioriView::AprioriGen(int nCandFreqItem, int nMinSupp)
{
	//由L(k-1)生成C(k)
	CString strTemp1,strTemp2,strRightTemp1,strRightTemp2;
	CString strTemp,strLeftTemp1,strLeftTemp2;
	int nstrTemp1,nstrTemp2;
    int nCandFreqItemCount=0;
	strTemp1="";
	strTemp2="";
	strRightTemp1="";
	strRightTemp2="";
	strTemp="";
	strLeftTemp1="";
    strLeftTemp2="";
	nstrTemp1=0;
	nstrTemp2=0;
	
	for(int i1=0;i1<LargeItemCount[nCandFreqItem-1];i1++)
	{
		
		//strTemp1=strCandFreqItem[i1];
        strTemp1=LargeItem[nCandFreqItem -1][i1];
		nstrTemp1=strTemp1.ReverseFind(',');
		strRightTemp1=strTemp1.Right(strTemp1.GetLength ()-nstrTemp1-1);
	    strLeftTemp1=strTemp1.Left(nstrTemp1);
		

		for(int j1=i1+1;j1<LargeItemCount[nCandFreqItem-1];)
		{
			//strTemp2=strCandFreqItem[j1];
			strTemp2=LargeItem[nCandFreqItem-1][j1];
			nstrTemp2=strTemp2.ReverseFind (',');
			strRightTemp2=strTemp2.Right(strTemp2.GetLength ()-nstrTemp2-1);
			strLeftTemp2=strTemp2.Left(nstrTemp2) ;
		
            //自连  
			if((strLeftTemp1==strLeftTemp2)&&(strRightTemp1<strRightTemp2))
			{
				strTemp=strTemp1+','+strRightTemp2;

				if(Prune(nCandFreqItem,strTemp))//剪枝
				{	CandLargeItem[nCandFreqItem][nCandFreqItemCount++]=strTemp;//把剪枝后的侯选项目集存入CandLargeItem
		   	
					j1++;
				}
				else
				{
					j1++;

				}
			}
			else 
				break;
		}
		
	}
    //存储自连并剪枝后但未计算最小支持度的候选频繁项目的个数
	CandLargeItemCount[nCandFreqItem]=nCandFreqItemCount;
    

}
BOOL CAprioriView::Prune(int nCandFreqItemCount,CString strCandFreqItem)
{
	CString strTemp1;
	CString strTempSubItem[nMaxSize];
	CString strReverse;
	CString strSubCandFreqItem[nMaxSize];//分解候选项目
	CString strSubTemp="";
	CString strSubTemp1;
	int nSubFreqItemCount=0;//统计分解候选项目的个数
	int nSubItemCount;
	int nstrRightTemp1;
	int nTempCount;
	int nPruneCount=0;

	strTemp1=strCandFreqItem;
	nSubItemCount=0;
	while((nstrRightTemp1=strTemp1.ReverseFind(','))!=-1)//以下程序用于分解候选频繁项目集
	{
		nTempCount=strTemp1.GetLength() - nstrRightTemp1 - 1; 
		strTempSubItem[nSubItemCount++]=strTemp1.Right( nTempCount);
		strTemp1=strTemp1.Left(nstrRightTemp1);
	}
    strTempSubItem[nSubItemCount++]=strTemp1;
	for(int i2=0;i2<nSubItemCount/2;i2++)//以下交换存储顺序
	{
		strReverse=strTempSubItem[nSubItemCount-i2-1];
		strTempSubItem[nSubItemCount- i2-1]=strTempSubItem[i2];
		strTempSubItem[i2]=strReverse;
	}
	
	//求候选项目子集
	for(int i3=nSubItemCount-1;i3>=0;i3--)
	{   
		strSubTemp1=strTempSubItem[i3];
		strSubTemp.Empty(); 
		for(int i4=0;i4<nSubItemCount;i4++)
			if(strSubTemp1!=strTempSubItem[i4])
            {
				strSubTemp=strSubTemp+strTempSubItem[i4]+',';
				
			}
			strSubCandFreqItem[nSubFreqItemCount++] = strSubTemp.Left(strSubTemp.GetLength()-1); 
	}
    
	//验证侯选项目子集是否频繁
	for(int i5=0;i5<nSubFreqItemCount;i5++)
	{   
		for(int i6=0;i6<LargeItemCount[nCandFreqItemCount-1];i6++)
		   if(strSubCandFreqItem[i5].Find(LargeItem[nCandFreqItemCount-1][i6])>=0)
			      nPruneCount++;
	}
	if(nPruneCount==nSubItemCount)
	{
	
		return TRUE;
	}
	
	return FALSE;

}


void CAprioriView::TransGenCand(int nCandFreqItem,int nCurrentCount )
{
	CString strTransTemp;
	CString strTransTemp1;
    nTransCandCount=0;
	int nCurrentTempCount=nCurrentCount;
	int a[nMaxSize];
	int nCount=0;
	a[nCount]=0;
	//初始化数组
	for(int nTransCand=0;nTransCand<nMaxSize;nTransCand++)
	{TransGenCandFreq[nTransCand]="";
	}
	do{	
		
		if((a[nCount]-nCount) <= (DbItemCount[nCurrentTempCount]- nCandFreqItem -1))
		{
			if(nCount==nCandFreqItem)
			{   
				strTransTemp="";
				for(int jj=0;jj<nCandFreqItem;jj++)
					strTransTemp=strTransTemp+DbItem[nCurrentTempCount][a[jj]]+',';
				
				strTransTemp1="";
				strTransTemp1=strTransTemp+DbItem[nCurrentTempCount][a[nCandFreqItem]];
			    TransGenCandFreq[nTransCandCount++]=strTransTemp1;
			   // MessageBox(strTransTemp1);
			     a[nCount]++;
				 continue;
			}
			nCount++;
			a[nCount]=a[nCount-1]+1;
		}
		else
		{
			if(nCount==0) return;
			a[--nCount]++;
		}
	}while(1);


//	for(int ll=0;ll<nTransCandCount;ll++)
//			MessageBox(TransGenCandFreq[ll],NULL,MB_OK);

    
 
}

void CAprioriView::ShowFreqItem(int nScanCount)
{	CString strIntToString="";
    CString strValue;
	CString strjj3[2];
	int nLargeCount=-1;
	int nLargeItemCount=0;
	
   	//以下为求频繁项目集
	int k,nListFreqItemCount;
	k=nScanCount;  
	nListFreqItemCount=LargeItemCount[k-1];
	m_List_FreqItem.InsertItem(0,strValue);

	m_List_FreqItem.SetItemText(0,0,"-----------"); 
    m_List_FreqItem.SetItemText(0,1,"-----------"); 
	for(int jj2=0;jj2<CandLargeItemCount[k];jj2++)
		if(double(nCountCand[jj2])/double(nDbItemCount)>=dItemSupp)
		{
			LargeItem[k][nLargeItemCount++]=CandLargeItem[k][jj2];
			nLargeCount++;
			
			strjj3[1]=strIntToString;	
			strjj3[0]=CandLargeItem[k][jj2];
			strIntToString="";
			strIntToString.Format("%s%d",strIntToString,nCountCand[jj2]);
	     	strjj3[1]=strIntToString;
			
			m_List_FreqItem.InsertItem(nLargeCount,strValue);
			
			m_List_FreqItem.SetItemText(nLargeCount,0,LargeItem[k][nLargeItemCount-1]);
			m_List_FreqItem.SetItemText(nLargeCount,1,strIntToString);



			UpdateWindow(); 
			}
		
	        //复制频繁项目个数
		  LargeItemCount[k]=nLargeItemCount;

}