一种高效挖掘关联规则中频繁项集的方法

摘要

本发明提供一种高效挖掘关联规则中频繁项集的方法，属于数据挖掘技术领域，本发明通过支持度矩阵表示数据库中所有一项集和二项集的支持度,减轻内存负担,减少扫描数据库次数，通过生成二项集支持度矩阵避免了产生无效的二项集，解决了二项集瓶颈的问题。同时利用矩阵的优势对连接和剪枝步做了改进，提高了挖掘频繁项的效率。

主权项

一种高效挖掘关联规则中频繁项集的方法，其特征在于，（1）扫描数据库，构造二项集的支持度矩阵；分别以项目集合I中的各个项作为矩阵的行标和列标，用Iik表示项二项集｛Ii，Ik｝（i≤k）在事务数据库D中出现的次数，此矩阵为对称矩阵；（2）逐行扫描矩阵，找出该行中不小于最小支持度计数的元素Iij，到j行搜索该行中不小于最小支持度计数的元素Ijk，再定位到矩阵Iik中，若Iik不小于最小支持度计数，则连接生成候选三项集｛Ii，Ij，Ik｝；（3）由Ck生成候选k+1项集表Ck+1（k≥3），由于生成的候选k项集表Ck是按字典顺序排列的，对于每个候选k项集X，从X在Ck之后的位置中查找以X后k‑1个项开始的其他候选k项集，若找到这样一个候选k项集Y，则把X的第一个项Ir和Y的最后一个项Is的标号连接形成矩阵坐标[r，s]，到矩阵M中查找这个坐标上的值是否大于最小支持度计数，如果大于或等于，则生成候选k+1项集，如果不大于，则不予连接，继续查找下一个，直到Ck中的最后一个k项集，至此候选k+1项集表构造结束；（4）第二次扫描数据库，因在生成支持度矩阵时，已经产生了频繁二项集，所以这里只对生成的候选k项集表Ck（k≥3） 中的每个k项集进行计数，并对其进行筛选，最后形成频繁k项集。