基于演化算法的高效用项集挖掘算法研究
发布时间：2021-09-11 21:45
高效用项集挖掘（Mining High Utility Itemsets,简称HUIM）是数据挖掘（Data Mining,简称DM）和知识发现（Knowledge Discovery in Database,简称KDD）领域的重要课题。当数据集较大或者不同项的数量较多时,高效用项集挖掘就是一个NP问题。演化算法是经常被用来解决NP问题的方法之一。最近,一些基于演化算法挖掘高效用项集的算法被提出,比如HUPEumu-GARM、HUIM-PSO等。这些算法在时间方面比传统算法高效,但是需要多次遍历数据集;此外只能挖掘到较少的高效用项集。为了解决以上问题,现提出以下几个算法:1)提出了基于人工蜂群算法的高效用项集挖掘算法HUIM-ABC。运用人工蜂群算法（Artificial Bee Colony,简称ABC）挖掘高效用项集,运用位图表示数据集;二进制向量表示蜜源、三种蜜蜂和项集;运用PBVC和DNSG策略加快算法运行,PBVC用于检测项集是否合理,DNSG动态调整不合理项集。2)提出了基于生物启发计算的高效用项集挖掘框架Bio-HUIF。该算法将数据集表示成位图;个体用二进制向量来表示,...
【文章来源】：北方工业大学北京市
【文章页数】：75 页
【学位级别】：硕士
【部分图文】：
单
Ｐ２?０?１?１?１?０?０?１?１?０?１?１?０?０?１?Ｃ２??图２－１单点交叉??Ｐ１?丨１丨０?１丨０丨１?１丨〇｜?｜ｌ｜〇｜ｌ｜ｌ｜〇?ｌｌｏｌ?Ｃｌ??￣—￣￣?￣￣??Ｐ２?０?１?１?１?０?０?１?０?１?１?０?１?０?１?Ｃ２??图２－２双点交叉??最简单的交叉操作就是在染色体上随机选择交叉点，然后互换染色体片段。??具体的交叉操作如图２－１和图２－２所示。??２．２．６变异操作??变异操作主要是为了保持上一代到下一代的多样性。变异改变染色体上的一??个或者多个基因位。简单的形式就是人为设定变异操作的变异概率。一般而言，??变异概率设置都比较小。如果变异的概率设置的太高，这个搜索的过程有可能退??化为随机搜索。自适应的变异率［３７］比固定的变异概率表现要好。??ｎｍａｘ?＿?ｐｍｉｎ?Ｒ?ｉ??＾?＝（／ｒ?一」＾＾＿ｘｒ）ｘ?（２－１２）??ＡＴ?Ｒ??最大变异概率??ｎｍｉｎ??＆?：最小变异概率??％?：迭代次数??ｒ：时间或者迭代次数??及：排名总数??在算法ＨＵＰＥ＿－ＧＡＲＭ中，变异概率是随着迭代次数的增加而减小的，并??且子代的变异概率是与适应度相关的。最初，较大的变异概率是为了更加充分的??搜索解空间。子代的变异率与它的排名有关。排名高的个体相较于排名低的个体??变异率低。适应度最高的个体可以达到最优解。最小变异概率是为了限制群体的??１１??
因为基于演化算法挖掘ＨＵＩ并不能确保在一定的迭代次数内挖掘到所有的??高效项集，我们就需要对比不同算法挖掘到的ＨＵＩｓ个数。Ｔｗｏ－Ｐｈａｓｅ算法从４??个数据集中可以挖掘到所有的ＨＵＩｓ。图３－２展示对比试验结果。??正如图３－２所示，ＨＵＩＭ－ＡＢＣ算法在４个数据集中比其他三个基于演化算??法都可以挖掘到更多的ＨＵＩｓ。平均来看，ＨＵＩＭ－ＡＢＣ算法分别在Ｃｈｅｓｓ、??Ｍｕｓｈｒｏｏｍ、Ａｃｃｉｄｅｎｔ＿１０°／〇和?Ｃｏｎｎｅｃｔ?数据集中可以挖掘到所有?ＨＵＩｓ?的?９１．３４％，??８７．１０％，９６．６５％和９１．５９％。当阈值设置较高时，例如，Ｃｈｅｓｓ数据集相对阈值??３０．５％
【参考文献】：
期刊论文
[1]利用三角模糊数的语言变量项集减项算法[J]. 陈宇,王娜,王晋东. 清华大学学报(自然科学版). 2017(08)
[2]基于经验Rademacher复杂度的频繁项集发现随机抽样方法[J]. 叶嘉,赵成贵,吴红刚. 中国管理信息化. 2017(07)
[3]基于Nodeset的最大频繁项集挖掘算法[J]. 林晨,顾君忠. 计算机工程. 2016(12)
[4]基于云计算的最大频繁项集挖掘算法[J]. 孙鹤旭,孙泽贤,林涛. 中南民族大学学报(自然科学版). 2016(03)
[5]滑动窗口下数据流完全加权最大频繁项集挖掘[J]. 王少鹏,闻英友,赵宏. 东北大学学报(自然科学版). 2016(07)
[6]基于投影的高效用项集挖掘算法[J]. 王敬华,罗相洲,吴倩. 小型微型计算机系统. 2016(06)
[7]基于间隔链表改进的频繁项集挖掘算法[J]. 徐永秀,刘旭敏,徐维祥. 计算机应用. 2016(04)
[8]基于开项集剪枝的常量条件函数依赖挖掘[J]. 周金陵,刁兴春,曹建军. 清华大学学报(自然科学版). 2016(03)
[9]基于最大频繁项集挖掘的微博炒作群体发现方法[J]. 刘琰,张进,陈静,尹美娟,张伟丽. 计算机工程与应用. 2017(04)
[10]基于频繁项集的海量短文本聚类与主题抽取[J]. 彭敏,黄佳佳,朱佳晖,黄济民,刘纪平. 计算机研究与发展. 2015(09)
本文编号：3393775
【文章来源】：北方工业大学北京市
【文章页数】：75 页
【学位级别】：硕士
【部分图文】：
单
Ｐ２?０?１?１?１?０?０?１?１?０?１?１?０?０?１?Ｃ２??图２－１单点交叉??Ｐ１?丨１丨０?１丨０丨１?１丨〇｜?｜ｌ｜〇｜ｌ｜ｌ｜〇?ｌｌｏｌ?Ｃｌ??￣—￣￣?￣￣??Ｐ２?０?１?１?１?０?０?１?０?１?１?０?１?０?１?Ｃ２??图２－２双点交叉??最简单的交叉操作就是在染色体上随机选择交叉点，然后互换染色体片段。??具体的交叉操作如图２－１和图２－２所示。??２．２．６变异操作??变异操作主要是为了保持上一代到下一代的多样性。变异改变染色体上的一??个或者多个基因位。简单的形式就是人为设定变异操作的变异概率。一般而言，??变异概率设置都比较小。如果变异的概率设置的太高，这个搜索的过程有可能退??化为随机搜索。自适应的变异率［３７］比固定的变异概率表现要好。??ｎｍａｘ?＿?ｐｍｉｎ?Ｒ?ｉ??＾?＝（／ｒ?一」＾＾＿ｘｒ）ｘ?（２－１２）??ＡＴ?Ｒ??最大变异概率??ｎｍｉｎ??＆?：最小变异概率??％?：迭代次数??ｒ：时间或者迭代次数??及：排名总数??在算法ＨＵＰＥ＿－ＧＡＲＭ中，变异概率是随着迭代次数的增加而减小的，并??且子代的变异概率是与适应度相关的。最初，较大的变异概率是为了更加充分的??搜索解空间。子代的变异率与它的排名有关。排名高的个体相较于排名低的个体??变异率低。适应度最高的个体可以达到最优解。最小变异概率是为了限制群体的??１１??
因为基于演化算法挖掘ＨＵＩ并不能确保在一定的迭代次数内挖掘到所有的??高效项集，我们就需要对比不同算法挖掘到的ＨＵＩｓ个数。Ｔｗｏ－Ｐｈａｓｅ算法从４??个数据集中可以挖掘到所有的ＨＵＩｓ。图３－２展示对比试验结果。??正如图３－２所示，ＨＵＩＭ－ＡＢＣ算法在４个数据集中比其他三个基于演化算??法都可以挖掘到更多的ＨＵＩｓ。平均来看，ＨＵＩＭ－ＡＢＣ算法分别在Ｃｈｅｓｓ、??Ｍｕｓｈｒｏｏｍ、Ａｃｃｉｄｅｎｔ＿１０°／〇和?Ｃｏｎｎｅｃｔ?数据集中可以挖掘到所有?ＨＵＩｓ?的?９１．３４％，??８７．１０％，９６．６５％和９１．５９％。当阈值设置较高时，例如，Ｃｈｅｓｓ数据集相对阈值??３０．５％
【参考文献】：
期刊论文
[1]利用三角模糊数的语言变量项集减项算法[J]. 陈宇,王娜,王晋东. 清华大学学报(自然科学版). 2017(08)
[2]基于经验Rademacher复杂度的频繁项集发现随机抽样方法[J]. 叶嘉,赵成贵,吴红刚. 中国管理信息化. 2017(07)
[3]基于Nodeset的最大频繁项集挖掘算法[J]. 林晨,顾君忠. 计算机工程. 2016(12)
[4]基于云计算的最大频繁项集挖掘算法[J]. 孙鹤旭,孙泽贤,林涛. 中南民族大学学报(自然科学版). 2016(03)
[5]滑动窗口下数据流完全加权最大频繁项集挖掘[J]. 王少鹏,闻英友,赵宏. 东北大学学报(自然科学版). 2016(07)
[6]基于投影的高效用项集挖掘算法[J]. 王敬华,罗相洲,吴倩. 小型微型计算机系统. 2016(06)
[7]基于间隔链表改进的频繁项集挖掘算法[J]. 徐永秀,刘旭敏,徐维祥. 计算机应用. 2016(04)
[8]基于开项集剪枝的常量条件函数依赖挖掘[J]. 周金陵,刁兴春,曹建军. 清华大学学报(自然科学版). 2016(03)
[9]基于最大频繁项集挖掘的微博炒作群体发现方法[J]. 刘琰,张进,陈静,尹美娟,张伟丽. 计算机工程与应用. 2017(04)
[10]基于频繁项集的海量短文本聚类与主题抽取[J]. 彭敏,黄佳佳,朱佳晖,黄济民,刘纪平. 计算机研究与发展. 2015(09)
本文编号：3393775
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3393775.html
