数据挖掘Apriori算法论文.doc

数据挖掘课程作业题目 基于关联规则Apriori算法的事务数据挖掘 班级 学号 姓名 日期 2010.06.13 目 录一、引言2二、正文21.背景22.算法思想23.数据集34.源代码35.算法流程166运行结果16三、结论17四、参考文献18一、 引言随着网络、数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。由此，数据挖掘技术应运而生。数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。从这个角度数据挖掘也可以描述为：按企业制定的业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。其中关联规则的算法的研究在数据挖掘算法的研究中占有相当重要的地位，关联规则算法的核心是Apriori算法，但随着对关联规则研究的深入，它的缺点也暴露出来了。本文将对数据挖掘的一种经典算法Apriori算法对于事务项目数据的挖掘应用。二、正文1、背景自1994年由Agrawal等人提出的关联规则挖掘Apriori的算法从其产生到现在，对关联规则挖掘方面的研究有着很大的影响。Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法基于这样的事实：算法使用频繁项集性质的先验知识。Apriori 使用一种称作逐层搜索的迭代方法，k-项集用于探索（k+1）-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1 用于找频繁2-项集的集合L2，而L2 用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori 性质的重要性质用于压缩搜索空间。为了提高频繁项目集逐层产生的效率，Apriori算法利用了两个重要的性质用于压缩搜索空间： （l）若X是频繁项集，则x的所有子集都是频繁项集。 （2）若x是非频繁项集，则X的所有超集都是非频繁项集。2、算法思想 算法： Apriori算法，使用逐层迭代找出频繁项集。 输入：事务数据库D；最小支持度阈值min_sup。 输出：D 中的频繁项集L。 1） L1 = find_frequent_1_itemsets（D）； 2） for （k = 2； Lk-1 ； k+） 3） Ck= aproiri_gen（Lk-1，min_sup）； 4） for each transaction t D /scan D for count 5） Ct= subset（Ck，t）； /get subsets of t that are candidates 6） for each candidate c Ct 7） c.count+； 8） 9） Lk=c Ck| c.count min_sup 10） 11） return L = kLk；3、数据集 我用的的是一个事务数据集，数据集存在一个transaction数据库中，数据库中有三个表：customer、tranDB、transactionDB，存有事务和项目的数据Transactiondb：tranDB:Customer：4、源代码/ 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_FILEstatic char THIS_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/ Standard printing commandsON_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/destructionCAprioriView:CAprioriView(): CRecordView(CAprioriView:IDD)/AFX_DATA_INIT(CAprioriView)m_pSet = NULL;nAllFreqItem=0;/AFX_DATA_INIT/ TODO: add construction code hereCAprioriView:CAprioriView()void CAprioriView:DoDataExchange(CDataExchange* pDX)CRecordView:DoDataExchange(pDX);/AFX_DATA_MAP(CAprioriView)DDX_Control(pDX, IDC_List_FreqItem, m_List_FreqItem);/AFX_DATA_MAPBOOL CAprioriView:PreCreateWindow(CREATESTRUCT& cs)/ TODO: Modify the Window class or styles here by modifying/ the CREATESTRUCT csreturn CRecordView:PreCreateWindow(cs);void CAprioriView:OnInitialUpdate()m_pSet = &GetDocument()-m_aprioriSet;CRecordView:OnInitialUpdate();GetParentFrame()-RecalcLayout();ResizeParentToFit();/ CAprioriView printingBOOL CAprioriView:OnPreparePrinting(CPrintInfo* pInfo)/ default preparationreturn DoPreparePrinting(pInfo);void CAprioriView:OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)/ TODO: add extra initialization before printingvoid CAprioriView:OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)/ TODO: add cleanup after printing/ CAprioriView diagnostics#ifdef _DEBUGvoid CAprioriView:AssertValid() constCRecordView:AssertValid();void CAprioriView:Dump(CDumpContext& dc) constCRecordView:Dump(dc);CAprioriDoc* CAprioriView:GetDocument() / non-debug version is inlineASSERT(m_pDocument-IsKindOf(RUNTIME_CLASS(CAprioriDoc);return (CAprioriDoc*)m_pDocument;#endif /_DEBUG/ CAprioriView database supportCRecordset* CAprioriView:OnGetRecordset()return m_pSet;/ CAprioriView message handlersvoid CAprioriView:OnBnFreqItem() / TODO: Add your control notification handler code hereint 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;LargeItemCountk-1!=0;k+) AprioriGen(k,1);/初始化数组for(int mm=0;mmMoveFirst();nDbCount=0;while(!m_pSet-IsEOF() TransGenCand(k,nDbCount); /统计计数for(int jj=0;jjnTransCandCount;jj+) for(int jj1=0;jj1MoveNext(); 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;kknMaxSize;kk+) LargeItemCountkk=0;for(int kk1=0;kk1nMaxSize;kk1+)for(int kk2=0;kk2nMaxSize;kk2+)LargeItemkk1kk2=;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 + LargeItemCountnCandFreqItem-1;for(int i1=0;i1LargeItemCountnCandFreqItem-1;i1+)/strTemp1=strCandFreqItemi1; strTemp1=LargeItemnCandFreqItem -1i1; nstrTemp1=strTemp1.ReverseFind(,);strRightTemp1=strTemp1.Right(strTemp1.GetLength ()-nstrTemp1-1); strLeftTemp1=strTemp1.Left(nstrTemp1);for(int j1=i1+1;j1LargeItemCountnCandFreqItem-1;)/strTemp2=strCandFreqItemj1;strTemp2=LargeItemnCandFreqItem-1j1;nstrTemp2=strTemp2.ReverseFind (,);strRightTemp2=strTemp2.Right(strTemp2.GetLength ()-nstrTemp2-1);strLeftTemp2=strTemp2.Left(nstrTemp2) ;if(strLeftTemp1=strLeftTemp2)&(strRightTemp1strRightTemp2)strTemp=strTemp1+,+strRightTemp2;if(Prune(nCandFreqItem,strTemp)CandLargeItemnCandFreqItemnCandFreqItemCount+=strTemp; j1+;elsej1+;else break; CandLargeItemCountnCandFreqItem=nCandFreqItemCount; void CAprioriView:SubItemGen(int strSubItemCount,CString strSubItem)/对每个事务分解成单个项目CString strTemp1;CString strTempSubItem10;CString strReverse;int nSubItemCount;int nstrRightTemp1;int nTempCount;strTemp1=strSubItem;nSubItemCount=0;while(nstrRightTemp1=strTemp1.ReverseFind(,)!=-1)nTempCount=strTemp1.GetLength() - nstrRightTemp1 - 1; strTempSubItemnSubItemCount+=strTemp1.Right( nTempCount);strTemp1=strTemp1.Left(nstrRightTemp1); strTempSubItemnSubItemCount+=strTemp1;for(int i2=0;i2nSubItemCount/2;i2+)strReverse=strTempSubItemnSubItemCount-i2-1;strTempSubItemnSubItemCount- i2-1=strTempSubItemi2;strTempSubItemi2=strReverse; for(int i1=0;i1GetODBCFieldCount();int nCount=0;int nFreqItem100; int nDbCount=0;CString strInit;CString strValue;CString strIntToString; / 初始化候选项目集 for(int nInitCount=0;nInitCountnItemCount;nInitCount+) strInit=;strInit.Format(%s%d,strInit,nInitCount+1); CandLargeItem0nInitCount=I+strInit;/初始化数组for(int ii=0;iiMoveFirst ();while(!m_pSet-IsEOF()for(int j=1;jGetFieldValue(j,strValue); SubItemGen(nDbCount+ ,strValue);for(int i=0;iMoveNext();nDbItemCount=nDbCount; for(int i1=0;i1=dItemSupp) LargeItem0nCount=CandLargeItem0i1; m_List_FreqItem.InsertItem(nCount,strIntToString);m_List_FreqItem.SetItemText(nCount,0,LargeItem0nCount); strIntToString=;strIntToString.Format(%s%d,strIntToString,nFreqItemi1);m_List_FreqItem.SetItemText(nCount,1,strIntToString);nCount+;LargeItemCount0=nCount;void CAprioriView:OnParameter() / TODO: Add your command handler code hereCSetPara 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 strTempSubItemnMaxSize;CString strReverse;CString strSubCandFreqItemnMaxSize;/分解候选项目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; strTempSubItemnSubItemCount+=strTemp1.Right( nTempCount);strTemp1=strTemp1.Left(nstrRightTemp1); strTempSubItemnSubItemCount+=strTemp1;for(int i2=0;i2=0;i3-) strSubTemp1=strTempSubItemi3;strSubTemp.Empty(); for(int i4=0;i4nSubItemCount;i4+)if(strSubTemp1!=strTempSubItemi4) strSubTemp=strSubTemp+strTempSubItemi4+,;strSubCandFreqItemnSubFreqItemCount+ = strSubTemp.Left(strSubTemp.GetLength()-1); for(int i5=0;i5nSubFreqItemCount;i5+) for(int i6=0;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 anMaxSize;int nCount=0;anCount=0;/初始化数组for(int nTransCand=0;nTransCandnMaxSize;nTransCand+)TransGenCandFreqnTransCand=;doif(anCount-nCount) = (DbItemCountnCurrentTempCount- nCandFreqItem -1)if(nCount=nCandFreqItem) strTransTemp=;for(int jj=0;jjnCandFreqItem;jj+)strTransTemp=strTransTemp+DbItemnCurrentTempCountajj+,;strTransTemp1=;strTransTemp1=strTransTemp+DbItemnCurrentTempCountanCandFreqItem; TransGenCandFreqnTransCandCount+=strTransTemp1; / MessageBox(strTransTemp1); anCount+; continue;nCount+;anCount=anCount-1+1;elseif(nCount=0) return;a-nCount+;while(1);/for(int ll=0;llnTransCandCount;ll+)/MessageBox(TransGenCandFreqll,NULL,MB_OK);void CAprioriView:ShowFreqItem(int nScanCount)CString strIntToString=; CString strValue;CString strjj32;int nLargeCount=-1;int nLargeItemCount=0; /以下为求频繁项目集int k,nListFreqItemCount;k=nScanCount; nListFreqItemCount=LargeItemCountk-1;m_List_FreqItem.InsertItem(0,strValue);m_List_FreqItem.SetItemText(0,0,-); m_List_FreqItem.SetItemText(0,1,-); for(int jj2=0;jj2=dItemSupp)LargeItemknLargeItemCount+=CandLargeItemkjj2;nLargeCount+;strjj31=strIntToString;strjj30=CandLargeItemkjj2;strIntToString=;strIntToString.Format(%s%d,strIntToString,nCountCandjj2); strjj31=strIntToString;m_List_FreqItem.InsertItem(nLargeCount,strValue);m_List_FreqItem.SetItemText(nLargeCount,0,LargeItemknLargeItemCount-1);m_List_FreqItem.SetItemText(nLargeCount,1,strIntToString);UpdateWindow(); /复制频繁项目个数 LargeItemCountk=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的性质剪枝：所有的频繁项集的子集都是频繁的，项集1，2，3的子集1，2不包含在频繁2-项集L2中，故删除1，2，3。项集1，3，5的子集1，5也不包含在频繁2-项集L2中，