数据挖掘Apriori算法论文

《数据挖掘》课程作业题目基于关联规则Apriori算法的事务数据挖掘班级学号姓名日期2010.06.13目录TOC\o"1-5"\h\z一、引言2二、正文2背景2算法思想2数据集3源代码3算法流程16运行结果16四、参考文献18一、引言随着网络、数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。由此，数据挖掘技术应运而生。数据挖掘(DataMining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。从这个角度数据挖掘也可以描述为：按企业制定的业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。其中关联规则的算法的研究在数据挖掘算法的研究中占有相当重要的地位，关联规则算法的核心是Apriori算法，但随着对关联规则研究的深入，它的缺点也暴露出来了。本文将对数据挖掘的一种经典算法Apriori算法对于事务项目数据的挖掘应用。二、正文1、背景自1994年由Agrawal等人提出的关联规则挖掘Apriori的算法从其产生到现在，对关联规则挖掘方面的研究有着很大的影响。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法基于这样的事实：算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。为了提高频繁项目集逐层产生的效率，Apriori算法利用了两个重要的性质用于压缩搜索空间：若X是频繁项集，则x的所有子集都是频繁项集。若乂是非频繁项集，则X的所有超集都是非频繁项集。2、算法思想算法：Apriori算法，使用逐层迭代找出频繁项集。输入：事务数据库D；最小支持度阈值min_sup。输出：D中的频繁项集L。L1=find_frequent_1_itemsets(D)；for(k=2；Lk-1尹；k++)(Ck=aproiri_gen(Lk-1，min_sup)；foreachtransactiontD(//scanDforcountCt=subset(Ck，t)；//getsubsetsoftthatarecandidatesforeachcandidatecCtc.count++；Lk=(cCk|c.countNmin_sup}}returnL=UkLk；3、数据集我用的的是一个事务数据集，数据集存在一个transaction数据库中，数据库中有三个表：customer、tranDB、transactionDB,存有事务和项目的数据Transactiondb：表^rans^iactilTID11+em►J11,12,IE,16,19212?14,183N,13,17,19411,12,145口,13,14,16,18612?13,IE,197口，13,16,IT8口门匕13,15,18911,12,13,191011,13,16,1911IW,15,IT,1912R15,1713口，工幻14,IT14工l’lW,15,18tranDB:'时姬j套期血isi西n*up一.』.工一.『|i.」：-.•「：E:二项二二:r二■3ULL}:':，5：：.二：：i：：、■3UU.：':二•］二':二:r二T4■■■■-■MI.；：-:二•］二::二:r二■3UU.：：:二项二':二:r二■3UL}i_.113:■S二:二:r二:':，S二二：：i::'

Customer：表pTID|ITEM011,1^1512j1412,IS11,12,14Customer：表pTID|ITEM011,1^1512j1412,IS11,12,14EII,1312,13IIj13II,12j13,152II,12j134、源代码//AprioriView.cpp:implementationoftheCAprioriViewclass//#include"stdafx.h"#include"Apriori.h”#include"time.h"#include"AprioriSet.h”#include"AprioriDoc.h”#include"AprioriView.h”#include"SetPara.h”#ifdefDEBUG#definenewDEBUG_NEW#undefTHIS_FILEstaticcharTHIS_FILE[]=__FILE__;#endif///////////////////////////////////////////////////////////////////////////////CAprioriViewIMPLEMENT_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//StandardprintingcommandsON_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()///////////////////////////////////////////////////////////////////////////////CAprioriViewconstruction/destructionCAprioriView::CAprioriView():CRecordView(CAprioriView::IDD)(//{{AFX_DATA_INIT(CAprioriView)m_pSet=NULL;nAllFreqItem=0;//}}AFX_DATA_INIT//TODO:addconstructioncodehere}CAprioriView::~CAprioriView()(}voidCAprioriView::DoDataExchange(CDataExchange*pDX)CRecordView::DoDataExchange(pDX);//{{AFX_DATA_MAP(CAprioriView)DDX_Control(pDX,IDC_List_FreqItem,m_List_FreqItem);//}}AFX_DATA_MAP}BOOLCAprioriView::PreCreateWindow(CREATESTRUCT&cs)(//TODO:ModifytheWindowclassorstylesherebymodifying//theCREATESTRUCTcsreturnCRecordView::PreCreateWindow(cs);}voidCAprioriView::OnInitialUpdate()(m_pSet=&GetDocument()->m_aprioriSet;CRecordView::OnInitialUpdate();GetParentFrame()->RecalcLayout();ResizeParentToFit();///////////////////////////////////////////////////////////////////////////////CAprioriViewprintingBOOLCAprioriView::OnPreparePrinting(CPrintInfo*pInfo)(//defaultpreparationreturnDoPreparePrinting(pInfo);}voidCAprioriView::OnBeginPrinting(CDC*/*pDC*/,CPrintInfo*/*pInfo*/)(//TODO:addextrainitializationbeforeprinting}voidCAprioriView::OnEndPrinting(CDC*/*pDC*/,CPrintInfo*/*pInfo*/)//TODO:addcleanupafterprinting///////////////////////////////////////////////////////////////////////////////CAprioriViewdiagnostics#ifdef_DEBUGvoidCAprioriView::AssertValid()const(CRecordView::AssertValid();}voidCAprioriView::Dump(CDumpContext&dc)const(CRecordView::Dump(dc);}CAprioriDoc*CAprioriView::GetDocument()//non-debugversionisinline(ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CAprioriDoc)));return(CAprioriDoc*)m_pDocument;#endif//_DEBUG///////////////////////////////////////////////////////////////////////////////CAprioriViewdatabasesupportCRecordset*CAprioriView::OnGetRecordset()(returnm_pSet;}///////////////////////////////////////////////////////////////////////////////CAprioriViewmessagehandlersvoidCAprioriView::OnBnFreqItem()(//TODO:AddyourcontrolnotificationhandlercodehereintnFieldCount=m_pSet->GetODBCFieldCount();intnDbCount;CStringstrValue;CStringstrIntToString=〃〃；clock_tstart,stop,tick;doubletimeused;intnLargeCount=0;intnListFreqItemCount=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(intk=1;LargeItemCount[k-1]!=0;k++)AprioriGen(k,1);〃初始化数组for(intmm=0;mm<CandLargeItemCount[k];mm++)(nCountCand[mm]=0;}m_pSet->MoveFirst();nDbCount=0;while(!m_pSet->IsEOF())(TransGenCand(k,nDbCount);〃统计计数for(intjj=0;jj<nTransCandCount;jj++)for(intjj1=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);voidCAprioriView::ClearItem()(//清除列表显示的内容m_List_FreqItem.DeleteAllItems();while(m_List_FreqItem.DeleteColumn(0));UpdateWindow();for(intkk=0;kk<nMaxSize;kk++)LargeItemCount[kk]=0;for(intkk1=0;kk1<nMaxSize;kk1++)for(intkk2=0;kk2<nMaxSize;kk2++)LargeItem[kk1][kk2]="";}voidCAprioriView::AprioriGen(intnCandFreqItem,intnMinSupp)(〃由L(k-1)生成C(k)CStringstrTemp1,strTemp2,strRightTemp1,strRightTemp2;CStringstrTemp,strLeftTemp1,strLeftTemp2;intnstrTemp1,nstrTemp2;intnCandFreqItemCount=0;strTemp1=〃〃；strTemp2="";strRightTempl=〃〃；strRightTemp2="";strlemp—;strLeftTemp1=〃〃；strLeftTemp2="";nstrTemp1=0;nstrTemp2=0;nAllFreqItem=nAllFreqItem+LargeItemCount[nCandFreqItem-1];for(inti1=0;i1<LargeItemCount[nCandFreqItem-1];i1++)(//strTemp1=strCandFreqItem[i1];strTemp1=LargeItem[nCandFreqItem-1][i1];nstrTemp1=strTemp1.ReverseFind(',');strRightTempl二strTemp1.Right(strTemp1.GetLength()-nstrTemp1-1);strLeftTempl二strTempl.Left(nstrTempl);for(intj1=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++;}elsej1++;}}elsebreak;}}CandLargeItemCount[nCandFreqItem]=nCandFreqItemCount;}voidCAprioriView::SubItemGen(intstrSubItemCount,CStringstrSubItem)(//对每个事务分解成单个项目CStringstrTemp1;CStringstrTempSubItem[10];CStringstrReverse;intnSubItemCount;intnstrRightTempl;intnTempCount;strTempl二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(inti2=0;i2<nSubItemCount/2;i2++)(strReverse二strTempSubItem[nSubItemCount-i2-1];strTempSubItem[nSubItemCount-i2-1]=strTempSubItem[i2];strTempSubItem[i2]=strReverse;for(inti1=0;i1<nSubItemCount;i1++)(DbItem[strSubItemCount][i1]=strTempSubItem[i1];}DbItemCount[strSubItemCount]=nSubItemCount;}voidCAprioriView::FindLargeItem()(〃显示1-频繁项目集intnFieldCount=m_pSet->GetODBCFieldCount();intnCount=0;intnFreqItem[100];intnDbCount=0;CStringstrInit;CStringstrValue;CStringstrIntToString;//初始化候选项目集for(intnInitCount=0;nInitCount<nItemCount;nInitCount++)(strInit=〃〃；strInit.Format("%s%d",strInit,nInitCount+1);CandLargeItem[0][nInitCount]='I'+strInit;}〃初始化数组for(intii=0;ii<nItemCount;ii++)nFreqItem[ii]=0;m_pSet->MoveFirst();while(!m_pSet->IsEOF())(for(intj=1;j<nFieldCount;j++)(m_pSet->GetFieldValue(j,strValue);SubItemGen(nDbCount++,strValue);for(inti=0;i<nItemCount;i++)if(strValue.Find(CandLargeItem[0][i])!=-1)nFreqItem[i]++;}m_pSet->MoveNext();}nDbItemCount二nDbCount;for(inti1=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;}voidCAprioriView::OnParameter()(//TODO:AddyourcommandhandlercodehereCSetParadlg;dlg.m_ItemCount=10;dlg.m_Item_Supp=0.2;intren=dlg.DoModal();nItemCount二dlg.m_ItemCount;dItemSupp二dlg.m_Item_Supp;}BOOLCAprioriView::Prune(intnCandFreqItemCount,CStringstrCandFreqItem)(CStringstrTemp1;CStringstrTempSubItem[nMaxSize];CStringstrReverse;CStringstrSubCandFreqItem[nMaxSize];//分解候选项目CStringstrSubTemp=〃〃；CStringstrSubTemp1;intnSubFreqItemCount=0;//统计分解候选项目的个数intnSubItemCount;intnstrRightTemp1;intnTempCount;intnPruneCount=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++]=strTempl;for(inti2=0;i2<nSubItemCount/2;i2++)(strReverse二strTempSubItem[nSubItemCount-i2-1];strTempSubItem[nSubItemCount-i2-1]=strTempSubItem[i2];strTempSubItem[i2]=strReverse;}for(inti3=nSubItemCount-1;i3>=0;i3--)(strSubTemp1=strTempSubItem[i3];strSubTemp.Empty();for(inti4=0;i4<nSubItemCount;i4++)if(strSubTemp1!=strTempSubItem[i4])(strSubTemp二strSubTemp+strTempSubItem[i4]+',';strSubCandFreqItem[nSubFreqItemCount++]=strSubTemp.Left(strSubTemp.GetLength()-1);}for(inti5=0;i5<nSubFreqItemCount;i5++)(for(inti6=0;i6<LargeItemCount[nCandFreqItemCount-1];i6++)if(strSubCandFreqItem[i5].Find(LargeItem[nCandFreqItemCount-1][i6])>=0)nPruneCount++;}if(nPruneCount==nSubItemCount)(returnTRUE;}returnFALSE;}voidCAprioriView::TransGenCand(intnCandFreqItem,intnCurrentCount)CStringstrTransTemp;CStringstrTransTempl;nTransCandCount=0;intnCurrentTempCount二nCurrentCount;inta[nMaxSize];intnCount=0;a[nCount]=0;〃初始化数组for(intnTransCand=0;nTransCand<nMaxSize;nTransCand++)(TransGenCandFreq[nTransCand]="";}do(if((a[nCount]-nCount)<=(DbItemCount[nCurrentTempCount]-nCandFreqItem-1))(if(nCount==nCandFreqItem)jmm—〃〃strlranslemp—;for(intjj-0;jj<nCandFreqItem;jj++)strTransTemp-strTransTemp+DbItem[nCurrentTempCount][a[jj]]+',';strTransTempl-"”;strTransTemp1-strTransTemp+DbItem[nCurrentTempCount][a[nCandFreqItem]];TransGenCandFreq[nTransCandCount++]-strTransTemp1;//MessageBox(strTransTempl);a[nCount]++;continue;}nCount++;a[nCount]—a[nCount-1]+1;}elseif(nCount==0)return;a[--nCount]++;}}while(1);//for(intll=0;ll<nTransCandCount;ll++)//MessageBox(TransGenCandFreq[ll],NULL,MB_OK);}voidCAprioriView::ShowFreqItem(intnScanCount)(CStringstrIntToString=〃〃；CStringstrValue;CStringstrjj3[2];intnLargeCount=-1;intnLargeItemCount=0;〃以下为求频繁项目集intk,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(intjj2=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;｝5、算法流程第一步，经过算法的第一次迭代，对事务数据库进行一次扫描，计算出D中所包含的每个项目出现的次数，生成候选1-项集的集合C1。第二步，根据设定的最小支持度，从C1中确定频繁1-项集L1。第三步，由L1产生候选2-项集C2，然后扫描事务数据库对C2中的项集进行计数。第四步，根据最小支持度，从候选集C2中确定频繁集L2。第五步，由频繁2-项集L2生成候选3-项集C3,生成的候选3-项集的集合C3=｛｛1，2，3｝，｛1，3，5｝，｛2，3，5｝｝，根据Apriori的性质剪枝：所有的频繁项集的子集都是频繁的，