一种用于FTTx网络规划的频繁序列挖掘算法FSM

针对光纤接入（fiber to the x,FTTx）网络规划中频繁路径挖掘问题,在经典算法FP-Growth,SPADE的基础上,结合格理论,利用频繁项集扩展枚举树作为搜索空间,并引入位图方便扩展运算和支持度计算,提出了一个改进的频繁序列挖掘算法FSM+。详细介绍了该算法的相关性质和基本理论,阐述了该算法的基本思想和实现伪码。在VC++6.0和单机的环境下,利用不同规模用户装机数据集和最小支持度比较了该算法与SPADE,FP-Growth算法的性能和准确性。实验证明,FSM+算法在小规模数据集下性能优势并不明显,但在大数据集下其计算性能分别是SPADE,FP-Growth的5倍和7倍多,挖掘结果与SPADE,FP-Growth算法相同。从而在实际网络规划过程中,快速计算信任度较高的频繁模式,并与人工经验干预相结合,来进一步保证预测路径准确有效。     

基于FP-tree的最大频繁项集挖掘算法

现有的最大频繁项集挖掘算法在支持度阈值较大情况下已达到较高性能,但在支持度阈值较小时,由于候选项集的快速增长,其性能往往不理想。文章提出了一种基于频繁模式树(FP-tree)存储结构的最大频繁项集挖掘算法——DMFIF算法,将FP-tree各分枝作为初始候选项集,并按维数和支持度递减排序,结合子集剪枝策略,自顶向下搜索挖掘最大频繁项集。实验结果表明,该算法在低支持度阈值下稠密数据集中挖掘长模式具有较好性能。     

DMBIT：一种有效的序列模式挖掘算法

大量候选序列模式支持度的计算所带来的时间消耗是序列模式挖掘主要问题之一,为此提出了一种有效的序列模式挖掘算法:DMBIT(Data Mining Bitmap),该算法根据位索引表和Seq-list表的结构,采用渐进的事件扩展,事务扩展方法,通过有效的剪枝策略和"与"逻辑运算操作进一步缩小了频繁序列的搜索范围,同时通过序列列表ListX的生成加快了相应候选项支持度的计算,算法分析和实验结果表明,在大数据集环境下的DMBIT算法性能优越,能够明显加速数据库中最大频繁序列的生成.     

高维数据组合关联关系挖掘方法

针对经典挖掘算法挖掘效率低、主观性强、生成关联关系过多的问题,从样本筛选和关联规则生成两个方面提出一种面向高维数据关联规则挖掘的新型算法(mining multidimensional association rules by combination, Marc)。所提算法通过计算样本的分布系数和删除阈值,综合自定义支持度在初读数据集时对样本进行双重筛选,在挖掘之初降低弱样本影响。在频繁项和关联规则生成时以样本关系表和样本全关系组合模式挖掘信息,降低挖掘过程的复杂性和资源消耗。试验结果表明：Marc算法挖掘出的频繁项和关联规则数量显著降低,在挖掘效率和内存消耗上均优于Apriori、FP-Growth和Eclat算法,且维度越高,数据集越大,优势越明显,Marc算法频繁项和关联关系挖掘的精度为100%。     

基于链表结构的频繁模式树构造

FP-Growth算法在关联规则挖掘中是最经典的算法,主要通过频繁模式树(FP树)避免生成候选频繁项目集.针对FP-Growth算法中耗费内存严重的问题,采用链表存储方式,给出了FP-Growth算法的实现方法,其中单个结点采用链表形式来产生,频繁模式树采用左孩子右兄弟的存储结构来组织.在此基础上利用索引表,实现了对频繁模式树中共同前缀结点的快速查找,提高了频繁模式树构造的效率,解决了FP树构造算法中数据存储的瓶颈问题.最后以天体光谱数据和城市土壤数据作为数据集分别对该算法进行测试,实验结果表明,该方法的构造效率要明显优于基于顺序结构的FP-Growth算法.     

一种新的基于FP_Growth的频繁项目集并行挖掘算法

频繁项目集挖掘用于发现项目之间的关联规则.为了高效求解面向大数据的频繁项目集,本文提出一种新的基于FP_Growth的频繁项目集并行挖掘算法NPFP_Growth(New Parallel algorithm based on FP_Growth),该算法对频繁模式树的存储结构进行改进,基于Map/Reduce并行计算模型,利用HDFS实现数据存储,在各自计算节点上构造局部频繁模式树,求解该局部频繁模式树中每个分支的最长全局频繁项目集;对于全局非频繁项目集,计算其支持数,发送至相应计算节点进行支持度统计,从而以较为简单的算法实现频繁项目集并行挖掘.实验表明,NPFP_Growth算法具有较高的计算效率和良好的可伸缩性.     

最大频繁项集挖掘中搜索空间的剪枝策略

最大频繁项集挖掘可以广泛应用在多种重要的Web挖掘工作中.为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略.这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝.应用该策略,对MAFIA算法进行改进优化.实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原MAFIA算法提高3～5倍.     

基于数据挖掘的网络业务流分析方法

为了从业务角度对网络的性能进行评价和优化,提出了一种新的网络业务分析方法——具有时态路径约束的关联规则挖掘分析方法.该方法以网络业务为分析粒度,以与网络业务流相关的时态属性和路径属性为约束条件,对已经积累的反映网络状况的海量历史数据进行挖掘分析.在进行关联规则挖掘时,利用频繁数据项集的性质,通过引入事务标号,在求出候选频繁项集的同时也求出其支持度,避免了为求支持度而进行的扫描数据库运算,极大提高了挖掘的效率和速度.实验结果表明,进行挖掘分析的数据量越大,该方法的性能和效率就越好.     

基于布尔矩阵和MapReduce的FP-Growth算法

关联规则挖掘是数据挖掘的一个重要组成部分.为提高关联规则的挖掘效率,提出了一种基于布尔矩阵和MapReduce的FP-Growth算法(BPFP),分析了算法的时间和空间复杂度.该算法使用Hadoop框架和布尔矩阵以减少对事务数据的扫描次数,利用两次MapReduce来实现频繁项集的挖掘.在多个数据集上的实验结果表明,与原FP-Growth算法相比,BPFP算法具有更高的执行效率、更好的加速比.     

基于审计日志的关联规则挖掘

为解决审计日志信息利用不充分的问题,通过改进FP-Growth方法研究了审计日志关联规则,提出了基于相互关联规则的KAFP-Growth算法。将现有的审计日志与先进的数据挖掘分析技术结合,在详细研究Apriori算法、PCY算法和FP-Growth算法后,引入了重要属性的概念,对审计日志中的重要属性进行约束,减小了频繁项集,提高了计算性能。实验结果验证KAFP-Growth算法有效提高了审计日志的关联分析效率,相较于FP-Growth算法,在最小支持度相同的情况下,改进算法运行时间速度提升了49.3%,随着数据集规模的增大,改进算法运行时间可提升60%以上。     

混合型频繁无序树挖掘算法

吸收深度优先和广度优先算法的优点,充分利用Apriori原则,提出了一种连接-扩展混合型的频繁无序树挖掘算法.首先在兄弟模式子树间进行连接,然后只在模式子树的最右叶顶点上进行扩展.分别用人工数据集和现实数据集进行测试,结果表明,本文算法比uFreqt算法性能提高0.5～1.0倍,比HybridTreeMiner算法性能提高5～10倍.     

基于集合和剪枝原理的关联规则隐藏算法

针对传统关联规则隐藏算法直接遍历数据集,而导致输入输出流资源浪费的问题,提出一种基于集合和剪枝原理的关联规则隐藏算法。该算法首先建立频繁模式树(FP-tree),利用后剪枝原理去除属性相同规则,减少了遍历原始数据集所耗I/O时间;然后通过建立集合来保存真实频繁序列,并以集合为单位隐藏关联规则,既保证数据集质量,又提高频繁序列挖掘效率。实验结果表明,该算法与GSP、SPADE算法相比较,不仅更好地保证了数据集的高质量,而且降低了20%～50%频繁序列挖掘时间,并在隐藏敏感规则上有较好的实用性。     

基于FP-Tree的最大频繁项目集更新挖掘算法

发现最大频繁项目集是多种数据挖掘应用中的重要问题．在应用中用户需要调整最小支持度,以发现更有用的最大频繁项目集．为此提出了一种最大频繁项目集更新算法(UMFPA),该算法通过对频繁模式树(FP-Tree)中的频繁项目头表(H Table)增加两个域,从而将减少在数据库不变而最小支持度变化的情况下的更新挖掘最大频繁项目集的费用．实验结果表明,算法在进行最大频繁项目集更新挖掘时具有很好的性能．     

基于分区的改进Apriori算法

分析了Apriori算法存在之不足,在此基础上提出了一种基于分区思想的IABP算法．该算法首先将待挖掘的数据集分成若干块,然后分别对各块进行挖掘．在挖掘过程中,只存储满足最小支持度的频繁项,并删除不满足最小支持度的非频繁项．测试结果表明,该挖掘方法降低了挖掘算法的时闻复杂度,提高了挖掘算法的效率．     

转换时间数据流的加权FP-Tree挖掘算法

数据流中的数据分布随着时间动态变化.为了解决传统基于事务的挖掘算法较难建立时间特征和关系特征的相关性,事务和时间作为不同维度的基本单元耗费较高数据存储量的问题,基于事务的FP-Tree挖掘算法,提出了时间间断度的概念.引入了FP-Tree结点权重的概念,将时间数据进行动态转换,设计了基于加权FP-Tree的挖掘算法,对时间数据流关联规则挖掘.在实际数据集上完成了挖掘试验.结果表明,该算法相对传统FP-Growth算法能在计算效率降低约20%的情况下,提高10%以上的平均查全率和5%以上的平均查准率.     

关联规则在路由监测系统的应用

本文为了改善路由监测系统的性能,对数据挖掘中的关联规则的两个经典挖掘算法Apriori和FP-Growth进行了仔细的比较分析。结合路由监测系统的实际情况,根据超大网络数据集的特点,在两种流行的关联规则挖掘算法中选出最适合的算法。     

基于免疫算法的频繁项集挖掘

设计了一种不同于传统关联规则挖掘算法(如Apriori算法等)频繁项集产生算法.该算法借鉴一般免疫算法思想,并从新的角度来看频繁项集的定义,避免了传统算法中存在的"项集生成瓶颈"问题.通过对mushroom数据的频繁项集挖掘的实验,与传统方法进行了比较,其结果表明,基于免疫算法的频繁项集挖掘算法在大数据集、低支持度情况下平均挖掘时间短.     

基于关联规则的数据挖掘算法研究

关联规则是数据挖掘的重要手段,它基于支持度、置信度等对规则进行筛选,生成有用的规则。关联规则反映了大量数据中项集之间的相互依存性和关联性。Apriori算法和FP-Growth算法是关联规则挖掘中的两个典型算法。本文阐述了这两种算法的基本思想、数据挖掘步骤,并讨论了它们的优缺点及差异。     

一种基于节点交换的FP-tree构造算法

基于FP树的FP-Growth关联规则挖掘算法,不需要产生候选项集,是当前频繁项集挖掘算法中应用最为广泛的算法之一.针对该算法在对大型的数据库挖掘的时候,存在运行速度慢,占用资源多的问题,文中发现算法中FP树和条件FP树的构建是最占资源的阶段.为此,提出了一种基于改进的FP树的构造算法.该算法一方面通过节点交换的方式压缩树的规模,提高挖掘的效率;另一方面,利用节点支持度计数的差值作为阈值以限定节点交换的条件,避免了由于交换过于频繁,造成不必要的系统开销,并把这种基于节点交换FP树构造算法称为TFP树算法.经过实验验证和性能分析,结果表明新算法有效,执行时间少,效率高.     

基于哈希和合并技术的FP-Growth新算法

对频繁模式增长(FP-Growth)算法进行了改进,用哈希头表代替头表.通过合并频繁模式树(FP-Tree)中支持数相同的结点,压缩了树的规模,有效地节省了空间.实验结果表明,改进后的算法在查找效率上有了大幅度的提高,可以更好地适用于大规模数据集的关联规则挖掘.