基于频繁链表的频繁集的挖掘算法

The problem of mining frequent set is a key issue in data mining. In this paper, a new method of miningfrequent set based on the frequent link is proposed. The algorithm constructs alternate frequent link from the transac-tion, the alternate link is yielded by adding up the alternate frequent link which constructed by scanning the transac-tion database in proper order. The frequent link that comprises all the information is constructed with the frequentnode which is selected according requirement. Our algorithm need to scan the transaction database only once and easysupervises the change of frequent set in order to guarantee the right of association rule.

基于链表数组的最大频繁项集挖掘算法

挖掘密集型数据集的全部频繁项集代价高昂,针对该问题,提出一种数据结构链表数组和基于链表数组的最大频繁项集快速生成算法。该方法使用链表数组为每个项目建立事务链表,并且链表的创建过程只需扫描数据库1次。使用深度优先搜索得到所有候选最大频繁项集,利用约束条件缩小搜索空间。使用标准数据集进行验证测试并与其他算法进行比较,实验结果表明,该算法具有较快的挖掘速度。

采用频繁项目链表变换的频繁项目集挖掘算法

频繁项目集的产生是关联规则挖掘的关键问题,经典的关联规则挖掘算法是通过对事务数据库的多次扫描实现的.最新的研究已经开始探索合适的数据结构以支持进行极少次数的事务数据库的扫描,进而减少关联规则挖掘过程中巨大的I/O开销以获得更高的效率.文中利用频繁项目链表的数据结构,给出了一种仅需扫描两次事务数据库的关联规则挖掘算法,称为FILLT算法.该算法采取分而治之策略,对频繁项目链表实施分割、变换来进行关联规则挖掘.文中最后对这一算法的效率进行了理论分析和实验验证.

基于频繁闭图关联规则的AS级Internet链路预测方法

目前大多数链路预测方法都是针对丢失链路的结构性预测,缺乏针对未来时刻网络链路的时序性预测,为此提出了一种基于频繁闭图关联规则的链路预测方法。将形式化后的动态网络划分为训练集和测试集,基于Apriori思想从训练集中提取频繁闭图,并根据频繁闭图的时间间隔建立时延分布矩阵,用于表征频繁闭图之间的时序关联规则,在此基础上预测测试集中的网络结构。将该方法运用于不同时间尺度下的AS级Internet动态网络中,结果表明,该方法能够以很高的精确率预测波动型动态网络的链路。

面向链路比特流的未知帧关联分析

在电子对抗中,截获到对方的通信比特流序列之后,当链路协议类型未知时,现有的协议解析工具往往无法分析比特流所承载的有用信息。为了获取比特流承载信息,首先需要切分比特流得到链路帧。该文根据链路帧结构的一般规律,提出一种基于数据挖掘的比特流切分算法。通过频繁序列统计、关联规则分析以及关联规则整合,识别出比特流中标识帧起始的多重关联规则序列。测试结果表明,该算法能够从未知比特流中提取有效的切分标识,正确实现比特流切分。与同类基于数据挖掘的比特流分析方法相比,该算法复杂度低,输出结果唯一且可信度高。

基于循环十字链表的频繁模式挖掘算法

FP-growth算法是当前挖掘频繁模式的有效算法之一,但FP树的节点占用空间较大,长时间占用内存不释放,挖掘过程中需要产生大量的条件FP树,因而时空效率不理想。提出了一种循环十字链表结构用作存储事务数据库,而不生成FP树,在挖掘频繁项集的过程中,这种链表结构逐步缩小,减少了内存的使用率,通过构建排序的条件频繁模式树挖掘频繁项集。理论分析和实验表明基于这种结构的排序条件频繁模式树挖掘频繁项集具有较好的时空效率。

数据挖掘关联规则Apriori算法的优化

关联规则挖掘研究是数据挖掘研究的一项重要的内容.Apriori算法是挖掘关联规则的经典算法,但存在一些不足之处.本文在Apriori算法基础上,提出了基于链表数据结构的关联规则改进算法.由于该算法只需对交易数据库进行一次检索,故能大量减少所需的I/O次数,提高了系统的性能.

基于图论的最大频繁项集挖掘

利用有向项集图来存储事务数据库中有关频繁项集的信息,提出了有向项集图的三叉链表式存储结构和基于有向项集图的最大频繁项集挖掘算法。它不仅实现了事务数据库的一次扫描,减少了I/O代价,而且可以同时解决好稀疏数据库和稠密数据库的最大频繁项集挖掘问题。

基于时间序列数据的紧密连续频繁序列挖掘算法

针对股票数据给出了一种符号化方法,并提出了一种利用互关联后继树和统计线索树挖掘紧密连续频繁序列算法,对符号化后的序列进行挖掘,证明了该算法是高效的、正确的.

基于连接的频繁集聚类算法

针对大型事务数据库中频繁集的多属性聚类问题,提出一种高效的频繁集聚类算法。以往聚类算法采用基于距离的计算方法,由于受到属性数据的制约,在频繁集挖掘中具有一定的限制。在属性聚类基础上,基于连接对频繁集进行聚类。在算法中先找出数据点的邻居和计算相似度,构造邻居矩阵；然后计算连接数目,确定邻居数目矩阵；最后通过设置判定函数和阈值确定聚类数。通过实验证明,算法能够不仅能有效地完成频繁集的多属性聚类问题,而且还可以进一步发现频繁集在某一层次的相关性。

稀疏矩阵的关联规则挖掘算法研究

关联规则是数据挖掘中的一种重要模式,自1993年R.Agrawal引入关联规则概念和提出第一个关联规则算法以来,诸多研究人员对关联规则挖掘的算法进行了广泛的研究.但专门研究挖掘稀疏数据的有效算法较少.针对稀疏数据,提出了一个使用简单数据结构——链表的挖掘算法,与其它算法比较,实验结果表明是非常有效的.

基于图论的频繁闭项集挖掘

利用了有向项集图来存储事务数据库中有关频繁项集的信息,提出了有向项集图的三叉链表式存储结构和基于有向项集图的频繁闭项集挖掘算法。不仅实现了事务数据库的一次扫描,减少了I/O代价,而且提高了数据结构的存储空间效率和频繁闭项集挖掘算法的执行时间效率。

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

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

基于频繁链表-存取树的Web用户浏览模式挖掘算法

为了观察网络用户浏览行为以研究用户偏爱的浏览模式集和个人兴趣,本文采用频繁链表结合存取树的增量式结构,使用捕获的网络用户浏览轨迹构建、更新该结构并使用同类合并的思想挖掘该结构以获得用户偏爱浏览模式集。实验通过对比本算法与GSP算法在同一测试集上的更新和挖掘情况,证明本算法在准确度和效率上都大幅领先。同时,该算法也为后续的长期观察研究提供了理论基础。

基于图的四叉链表存储结构的最大频繁项集挖掘算法

虽然已有的最大频繁项集挖掘算法在结构和技术上已经做了很多改进,但还是存在挖掘速度慢、效率低的缺点,在此提出了图的四叉链表存储结构和基于该存储结构的最大频繁项集挖掘算法,该结构具有一次生成多次使用,不必耗用额外的存储空间等特点,基于该存储结构的最大频繁项集挖掘算法充分利用了该存储结构的特点以及频繁扩展集的性质,有效地减少了冗余候选集的生成,降低了串的冗余存储,将串集合间的比较转化为整型数组的比较,从而使得它比已有的最大频繁项集挖掘算法在挖掘效率上有了明显的提高,最后通过实验证明了该算法较其他已有算法效率有了较大的提高.

频繁量化模式图挖掘及应用

频繁模式挖掘(FPM)是图数据研究领域的一个经典问题,单一大图上的FPM问题近年来受到了更加广泛的关注。该问题被定义为根据用户给定的频率阈值查找在大图(Graph)中频繁出现的所有模式图(Pattern)。近年来,人们见证了FPM在多个领域的广泛应用,例如社交网络分析、欺诈检测等。然而,面对新兴的应用需求,人们需要更具语义表达力的模式图及其挖掘技术。为此,在传统模式图的基础上,首先提出了量化模式图(Quantified Graph Patterns,QGPs)——一类具有计数量词约束的模式图,实现了模式图语义的扩展;其次设计了一种在分布式场景下挖掘QGPs的算法,提出了量化图模式关联规则(Quantified Graph Pattern Association Rules,QGPARs)及其挖掘技术,用于预测(社交)网络中实体之间的潜在联系,然后利用真实图和合成图数据,通过翔实的实验验证了QGPs挖掘算法的计算效率,通过与经典链接预测方法进行对比,发现QGPARs可以取得更高的链接预测准确性;最后通过与传统图模式关联规则(Graph Pattern Association Rules,GPARs)的链接预测结果进行对比,验证了QGPARs与GPARs之间在链接预测结果方面存在显著差异,也进一步验证了QGPARs在链接预测中的有效性。