数据挖掘Apriori算法论文

数据挖掘Apriori算法论文 Apriori 日期 2010.06.13 一、 引言 ?????????????????????????????????????????????????????????????????????????????? 2 二、 正文 ?????????????????????????????????????????????????????????????????????????????? 2 1.背景 ??????????????????????????????????????????????????????????????????????????????? 2 2.算法思想 ??????????????????????????????????????????????????????????????????????? 2 3.数据集 ??????????????????????????????????????????????????????????????????????????? 3 4.源代码 ??????????????????????????????????????????????????????????????????????????? 3 5.算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 ??????????????????????????????????????????????????? 16 ．运行结果……………………………………………………………………16 三、 结论 ??????????????????????????????????????? 17 四、 参考文献 ??????????????????????????????? 18 1 随着网络、数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据 越来越多。由此，数据挖掘技术应运而生。数据挖掘(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的所有超集都是非频繁项集。 算法： 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； 2 3 我用的的是一个事务数据集，数据集存在一个transaction数据库中，数据库中有三个表：customer、tranDB、transactionDB，存有事务和项目的数据 Transactiondb： tranDB: Customer： // AprioriView.cpp : implementation of the CAprioriView class // #include "stdafx.h" 3 #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() { 4 } 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*/) 5 { // 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=""; 6 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;mmMoveFirst(); nDbCount=0; while(!m_pSet->IsEOF()) { TransGenCand(k,nDbCount); //统计计数 for(int jj=0;jjMoveNext(); } 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;kkGetODBCFieldCount(); int nCount=0; int nFreqItem[100]; int nDbCount=0; CString strInit; CString strValue; CString strIntToString; // 初始化候选项目集 for(int nInitCount=0;nInitCountMoveFirst (); 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) { 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; 12 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=0;i3--) { strSubTemp1=strTempSubItem[i3]; strSubTemp.Empty(); for(int i4=0;i4=0) 13 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=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(); } //复制频繁项目个数 15 LargeItemCount[k]=nLargeItemCount; } 第一步， 经过算法的第一次迭代，对事务数据库进行一次扫描，计算出D中所包含的每个项目出现的次数，生成候选1-项集的集合C。 1 第二步，根据设定的最小支持度，从C中确定频繁1-项集L。 11 第三步，由L产生候选2-项集C，然后扫描事务数据库对C中的项集进行计数。 122 第四步，根据最小支持度，从候选集C中确定频繁集L。 22 第五步，由频繁2-项集L生成候选3-项集C，生成的候选3-项集的集合C={{1，2，233 3}，{1，3，5}，{2，3，5}}，根据Apriori的性质剪枝：所有的频繁项集的子集都是频繁 的，项集{1，2，3}的子集{1，2}不包含在频繁2-项集L2中，故删除{1，2，3}。项集{1， 3，5}的子集{1，5}也不包含在频繁2-项集L中，故删除{1，3，5}，项集{2，3，5}的所有2 子集都是L的元素，故保留。 2 1、设置参数 2、频繁数据集 16 Apriori算法的效率分析： （1）Apriori性质能显著减少候选集的数目。事务数据库TDB总共有4个项目，因此可能的2-项集有 =6个。正如本例所示，利用Apriori性质，我们只需要检查4个候选2-项集的支持度。Apriori算法在2项集这个层次上剪枝率达33.3%。随着候选集的长度逐渐 增大，可能的组合数目也急剧增大，因此Apriori算法的剪枝效率也越来越高。 （2）尽管Apriori能对大量候选集剪枝，但是在大型的事务数据库中，仍然可能有大 6量的候选集需要处理，并且这种操作相当耗时。例如，如果事务数据库包含10个项目，并 47且只有1%（即10）的项目是频繁的，Apriori需要产生超过10个候选2-项集，扫描数据库计算它们的支持度，生成L以产生候选3-项集。 2 （3）反复地扫描数据库、计算候选集的支持度，再生成新的长度加1的候选集，Apriori算法是冗长乏味的，尤其是当存在长模式的时候。Apriori是一种产生候选集，然后检测其 支持度的算法。为挖掘频集X ={x，x…，x} . Apriori需要扫描数据库100次。 12100 17 针对Apriori算法存在的缺点，人们对Apriori算法进行了多方面的改进，希望能够找 出一个高效、可靠的挖掘频繁项集的算法。这些算法大多是以 Apriori 为核心，或是其变 [1，2][3，4]体，或是其扩展。如增量更新算法、并行算法等 [1] 孙浩，赵霁，一种关联规则增量更新算法. 系统 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 与电子技术，2004年05期 [2] 李铭蔡，庆生，一个高效的关联规则增量式更新算法.计算机工程与应用， 2005（5） [3] 王运峰，张蕾，韩纪富等，数据库中关联规则的并行挖掘算法.计算机工程与应用，2001（16） [4] 林伟伟，张志立，齐德昱.基于网格的分布并行计算策略，计算机工程， 2006（9） 18 本科课程论文评分 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 班级 学号 姓名 论文题目 评阅点 评分标准（细则） 分值 给分 正确实现本程序所需全部功能，算法设40分 计正确合理且有一定创意 实现所需功能，算法正确 30分 功能及算 法 基本实现所需功能 15分 （40分） 有明显重大错误 5分 无法实现程序功能 0分 界面美观、合理，可操作性强 20分 界面和操界面合理，可操作 15分 作性 界面尚可，基本可操作 10分 （20分） 可操作较差 5分 程序可读性好、逻辑清晰，程序完整，15分 可维护性好， 程序可读、程序可读、可维护 10分 可维护性 基本可读可维护 5分 （15分） 逻辑混乱、不可读 0分 论文规范，行文流畅，层次清晰 25分 论文书写基本规范，文理较通畅 20分 论文质量 结构较合理，层次较清楚，基本符合要15分 （25分） 求 结构混乱，文不对题目，或者有明显抄5分 袭现象 教师签名： 19