aprioriview.cpp

数据挖掘中的关联规则算法

// AprioriView.cpp : implementation of the CAprioriView class
//

#include "stdafx.h"
#include "Apriori.h"
#include "time.h"
#include "AprioriSet.h"
#include "AprioriDoc.h"
#include "AprioriView.h"
#include "SetPara.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAprioriView
IMPLEMENT_DYNCREATE(CAprioriView, CRecordView)

BEGIN_MESSAGE_MAP(CAprioriView, CRecordView)
	//{{AFX_MSG_MAP(CAprioriView)
	ON_BN_CLICKED(IDC_Bn_FreqItem, OnBnFreqItem)
	ON_COMMAND(ID_Parameter, OnParameter)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CRecordView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CRecordView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CRecordView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAprioriView construction/destruction

CAprioriView::CAprioriView()
	: CRecordView(CAprioriView::IDD)
{
	//{{AFX_DATA_INIT(CAprioriView)
	m_pSet = NULL;
	nAllFreqItem=0;

	//}}AFX_DATA_INIT
	// TODO: add construction code here

}

CAprioriView::~CAprioriView()
{
}

void CAprioriView::DoDataExchange(CDataExchange* pDX)
{
	CRecordView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAprioriView)

	DDX_Control(pDX, IDC_List_FreqItem, m_List_FreqItem);

	//}}AFX_DATA_MAP
}

BOOL CAprioriView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CRecordView::PreCreateWindow(cs);
}

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

}

/////////////////////////////////////////////////////////////////////////////
// CAprioriView printing

BOOL CAprioriView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CAprioriView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CAprioriView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CAprioriView diagnostics

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

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

CAprioriDoc* CAprioriView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CAprioriDoc)));
	return (CAprioriDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CAprioriView database support
CRecordset* CAprioriView::OnGetRecordset()
{
	return m_pSet;
}


/////////////////////////////////////////////////////////////////////////////
// CAprioriView message handlers

void CAprioriView::OnBnFreqItem() 
{
	// TODO: Add your control notification handler code here
	int nFieldCount=m_pSet->GetODBCFieldCount();
	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();

    for(int k=1;LargeItemCount[k-1]!=0;k++)
	{    
	     
		 AprioriGen(k,1);
		
		//初始化数组
		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);


	}
	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]="";

}



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;
	nAllFreqItem=nAllFreqItem + LargeItemCount[nCandFreqItem-1];
	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;
		   	
					j1++;
				}
				else
				{
					j1++;

				}
			}
			else 
				break;
		}
		
	}
    
	CandLargeItemCount[nCandFreqItem]=nCandFreqItemCount;
    

}

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::FindLargeItem()
{
	//显示1-频繁项目集
	int nFieldCount=m_pSet->GetODBCFieldCount();
	int nCount=0;
	int nFreqItem[100];
	
    int nDbCount=0;
	CString strInit;
	CString strValue;
	CString strIntToString;
  // 初始化候选项目集	
    for(int nInitCount=0;nInitCount<nItemCount;nInitCount++)
	{   
		strInit="";
		strInit.Format("%s%d",strInit,nInitCount+1); 
		CandLargeItem[0][nInitCount]='I'+strInit;

	}
//初始化数组
	for(int ii=0;ii<nItemCount;ii++)
		nFreqItem[ii]=0;
	
	m_pSet->MoveFirst ();
	while(!m_pSet->IsEOF())
	{
		for(int j=1;j<nFieldCount;j++){
			m_pSet->GetFieldValue(j,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)
		{  
		    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++;
		}

	}
	LargeItemCount[0]=nCount;


}

void CAprioriView::OnParameter() 
{
	// TODO: Add your command handler code here
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 ;
	
}

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;

}