基于FP-tree和支持度数组的最大频繁项集挖掘算法

提出了一个基于频繁模式树即FP-tree和支持度数组相结合的最大频繁项集挖掘算法,首先建立FP-tree,同时建立支持度数组,然后在此基础上建立最大频繁项集树MAXFP-tree,MAXFP-tree中包含了所有最大频繁项集,缩小了搜索空间,提高了算法的效率。算法分析和实验表明,该算法对稠密型数据集和稀疏型数据集均适用,并且特别适于挖掘具有长频繁项集的数据集。     

基于自适应哈希链的分布式频繁模式挖掘算法

针对分布式系统,提出了自适应哈希链结构的频繁模式挖掘算法。该算法首先在每个站点产生局部频繁1-项集,再产生全局频繁1-项集,根据全局频繁1-项集产生各站点的投影数据库,在各个站点分别扫描投影数据库中的交易,并根据站点可用内存情况形成相应大小的哈希链结构。通过挖掘各站点的哈希链结构得到全局频繁项集。给出了基本步骤和挖掘算法。研究表明该算法不但效率高,而且适应性强。     

在线挖掘数据流滑动窗口中最大频繁项集

相对于频繁项集,最大频繁项集的数目较少,挖掘最大频繁项集的算法具有较高的时空效率.提出了一种新的基于文法顺序FP-Tree的最大频繁项集单遍挖掘算法FPMFI-DS.该算法采用了一种混合搜索空间项顺序策略,并利用我们所提出的一种新的剪枝技术-"子集等价剪枝技术",有效缩小搜索空间的大小.基于该算法,提出了一种能够在线更新挖掘数据流滑动窗口中最大频繁项集的算法FPMFI-DS+.FPMFI-DS+算法能够在任意时刻都维护数据流当前窗口中的最大频繁项集.仿真实验表明,FPMFI-DS算法的效率接近于多遍挖掘算法FPMax*,并具有良好的可扩展性,FPMFI-DS+算法更新挖掘速度快.     

分布式系统中的元挖掘研究

针对分布式系统中的数据挖掘问题,提出了一种新颖高效的分布式元挖掘方法。该算法只需在各自站点扫描局部数据库两次即可形成局部和全局频繁项集,并根据局部和全局频繁项集形成相应的关联规则集及元规则集。在形成元规则集时无需扫描各站点中的关联规则集,这样既减少了分布式系统中需要的通信交换的数据量,也减少了各站点中的扫描数据量。研究表明所提出的算法是有效的。     

基于关联规则赋权特征选择集成的信用分类研究

针对信用分类数据集中常见的高维性特征,本文基于特征袋装法和关联规则挖掘算法,构建了新的赋权特征选择集成模型AR-WSAB.该模型能根据频繁项集的支持度和置信度,对各特征的重要度进行测度,进而选择出各特征子集,训练子分类器,再通过集成得到最终结果.通过在贷款违约预测数据集上进行实证分析,结果表明该模型分类正确率相对于Bagging集成模型和PCA算法都有显著优势,所提方法能够有效处理高维性特征,并且在各分类算法上都具有普适性.     

建立频繁项目集向量的极大频繁项目集挖掘

在分析和研究诸多经典关联规则挖掘算法或最大频繁项目集挖掘算法的基础上,提出了一种新的极大频繁项目集挖掘算法BOFPV_MMFIA算法.该算法引入频繁项目集向量FP-V,将极大频繁项目集的挖掘过程转化为频繁项目集向量FP-V的与运算过程.算法只需扫描数据库一次,克服了Apriori及其相关算法产生大量候选集和需多次扫描数据库的缺点.又不同于BOM算法,挖掘频繁k_项目集时,需要进行 次k个向量的与运算.因此,BOFPV_MMFIA算法的效率明显高于Apriori、DMFIA及BOM算法.     

基于网络的数值关联规则挖掘方法

关联规则 ( Association Rules)发现的是属性间的关系 .属性可以是逻辑型的 ,也可以是数值型的 .在从逻辑型属性描述的数据中发现关联规则方面已经有许多比较成熟的算法 ,而在数值型属性方面则不然 .将数值关联规则挖掘问题映射成逻辑关联规则挖掘问题是一种方便有效的方法 .本文给出了一个新的数值属性关联规则挖掘算法 ,该算法利用数据本身的特征决定对数值属性值域的划分 ,进而将划分后的所有区间映射为逻辑属性 (项目 ) ,在此基础上可以挖掘出更容易理解、更具有概括性的有效关联规则 .本文给出了一个发现频繁项目集搜索算法 ,并采用一种纵向数据库格式来简化项目集支持度的计算.     

移动情境感知环境下的用户行为模式挖掘算法研究

针对当前个性化精准营销推荐策略研究中用户情境多样性和动态性等问题的挑战,提出了一种移动情境感知环境下的用户行为模式挖掘算法.该方法采用一种嵌套键值模型,对多源异构的移动情境感知信息进行有效融合和存储,构建了基于规则的多维序列模式挖掘算法MSP及其改进算法UTDMSP,能够从用户移动情境感知信息和交互行为中发现全局频繁和局部频繁的用户行为模式,识别用户长期保持的行为习惯和兴趣偏好,以及近期习惯和偏好的变化新趋势.在真实数据集上验证了本文所提出模型和算法的有效性.     

频繁项目集二次挖掘方法研究

针对关联规则数据挖掘中频繁项目集的二次挖掘问题,提出了一种能够解决当最小支持度发生变化而交易数据库不变情况下进行二次挖掘的改进算法(UMSA)。该算法充分利用频繁项目集的特性,通过新的拼接方法来减少候选项目集的生成,在扫描交易数据库确定k维频繁项目集时,采用在交易数据库中剔除无用的交易,达到不断减小交易数据库规模的目的,克服了一些算法中存在的漏采现象,并在一定程度上解决了非确定性问题。通过举例说明该算法的执行过程及其算法的正确性和有效性,并对其性能进行了分析。     

基于改进蚁群优化的多目标资源受限项目调度方法

多目标资源受限项目调度是一类典型的NP难组合优化问题,具有广泛的实际应用背景.本文提出了一种带局部搜索的改进蚁群优化算法用于求解多目标资源受限项目调度问题,优化指标为最小化项目工期和资源投资.首先,采用改进的蚁群优化算法获取Pareto解集;其次,通过基于带逻辑约束的Insert和Swap邻域搜索方法对已获得的非支配解进行局部搜索,进一步提高算法的性能;最后,基于PSPLIB国际标准测试集的数值仿真实验与现有最好的算法比较,验证了所提算法的有效性和高效性.     

在线挖掘数据流滑动窗口中频繁闭项集

在线挖掘滑动窗口中的频繁闭项集是一类重要的数据流挖掘问题.提出了一种新的频繁闭项集挖掘算法FPCFI-DS.该算法能够在有限的存储空间中高速挖掘数据流滑动窗口中的频繁闭项集,并且能够在任意时刻维护当前窗口中精确的频繁闭项集.对于第一个窗口中的数据,FPCFI-DS算法采用单遍过程FPCFI进行挖掘,挖掘结果被保存于一棵全局闭项集树GCT中.当窗口向前滑动时,FPCFI-DS算法采用更新挖掘方式快速挖掘出当前窗口中的频繁闭项集.实验结果表明,FPCFI-DS算法的空间效率和时间效率都显著优于同类经典算法Moment.     

基于兴趣度的数据流频繁模式散列挖掘算法

频繁模式挖掘是很多数据流挖掘工作的基础.现有算法虽然能够有效的在数据流中挖掘近似的频繁模式, 但是由于数据流数据的不确定性、连续性以及海量性, 始终不能有效的将算法的时间效率和空间效率控制在一个可以接受的范围内. 本文通过使用散列表作为概要数据的存储结构, 并引入关联规则兴趣度的概念, 提出了数据流频繁模式挖掘算法MIFS-HT(mining interesting frequent itemsets with hash table), 不仅有效降低现有算法的时空复杂度, 同时提高了算法的应用价值. 最后, 实验结果表明: MIFS-HT是一种高效的数据流频繁模式挖掘算法, 其性能优于FP-Stream、Lossy Counting等算法, 并且挖掘结果更具有现实意义.     

频繁项集的简洁表示方法研究

提出了通过逻辑蕴涵的演绎规则来构建频繁项集的简洁表示,而不是挖掘所有的频繁项,来降低频繁项集中的冗余性,并利用演绎规则来构建所有频繁项集的简洁表示,从而减少存取数据库和对项集进行计数的次数,最终提供一个更加紧凑的频繁项集输出.最后,通过试验说明了该方法的有效性.     

Efficient Algorithm Based on Itemset-lattice and Bitmap Index for Finding Frequent Itemsets

Finding frequent itemsets is the key problem in association rules mining. A new algorithm based on the lattice theory and bitmap index for mining frequent itemsets is proposed. The algorithm converts the original transaction database to an itemset-lattice in the pre-processing, where each itemset vertex has a label to save its support, and the complicated task of mining frequent itemsets in the database is thus changed to the simpler one that searches vertexes in the lattice. The efficiency of the mining process is enhanced greatly. Since the support counting in the association rules mining incurs a high cost regarding the I/O, a bitmap index technique is used to speed up the counting process. To address the issue that the intact bitmap usually needs a big memory space for storage, the bit vector is partitioned into blocks, which can be encoded as a symbol. This makes the original bitmap more compact in storage and improve the support counting efficiency as well. Finally, experimental and analytical results are presented.     

基于包含索引的频繁闭序列模式挖掘的新算法

频繁闭序列模式惟一确定全体频繁序列模式,且规模小得多.传统的闭序列模式挖掘算法对每个频繁项目都进行扩展,往往会产生大量的非闭合序列.为解决这一问题,提出了一种新的基于包含索引的频繁闭序列模式挖掘算法,其主要思想是只对闭项集进行扩展,大大减少了非闭合序列的产生.首先,论证了闭序列模式只能由闭项集组成;其次,说明了如何利用包含索引来快速发现闭项集;最后,给出了一种深度优先的挖掘频繁闭序列模式的新算法.实验结果表明,该算法具有较高的效率.     

基于路径QoS加权分解的工作流调度算法

采用有向无环图DAG(Directed Acyclic Graph)描述的工作流在QoS约束下的调度问题是一类典型的NP难问题。分析了DAG工作流调度问题的调度目标,提出了一种基于路径QoS加权分解的工作流调度算法,通过将工作流的全局QoS约束分解为单个任务的局部QoS约束,将整个工作流的全局优化问题转化为单个任务的局部优化问题,降低了问题的复杂度。在对整个DAG工作流的QoS约束进行分解时,算法对工作流的每条路径的QoS约束进行分解,并以任务可选能力服务间的单位QoS增益之和作为权值,将单条路径的QoS约束分解到组成路径的每个任务。仿真结果表明,与其他基于QoS分解的DTL、DBL等算法相比,该算法具有更高的调度效率,能够找到更好的调度方案。