概念格构造算法改进

发布时间：2020-08-24 08:36

【摘要】：概念格构造问题起源于哲学,如今已广泛应用于实际生产中,是对事物的共同本质特点进行抽取,加以概括,形成概念,并最终建立起概念之间相互关系的格状结构,即本文改进算法所要解决的问题。本文的研究目的是建立一个比目前的算法在时间和空间上实现双重压缩的概念格构造算法。首先按照批处理型、渐进构造型、并行构造型和模糊构造型对现阶段的构造算法进行了分类,并在每一类中挑选若干具有代表性的算法进行优缺点的分析,最终选择批处理型中的Chein算法作为本文改进算法的基础。Chein算法具备不依赖于形式背景的优势,且新概念的生成过程和概念之间层次关系的构造相互独立。因此提出了划分子形式背景的方式将新概念的生成过程根据交运算的左值进行子形式背景的划分,正文中给出了证明。从而相互独立的计算即可实现并行化。经过大量实验证明采用FP-Tree对概念进行存储不仅可以实现更高比例的存储空间压缩,同时极大优化了概念之间的交运算过程,效果明显优于其它算法所采用的位运算方式。本文另一个重要改进点是借助FP-Tree实现了冗余概念提早发现并直接删除,从子形式背景划分阶段就避免了冗余概念的产生,从而解决冗余概念对空间的浪费,正文中给出了详细证明。最后通过领域内通用的标准UCI数据集与其它算法进行了多维度对比,验证了改进算法的正确性和高性能的可行性,同时通过转置数据说明了批处理型算法相比于渐进构造型算法具备更好的实用性。正文也给出了实验数据,方便其它改进者进行算法类比。
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6;TP311.5
【图文】：

图５．邋１对象数目对时间的影响逡逑数据转置前后时间提升十分明显

０逦１０００逦２０００逦３０００逦４０００逦５０００逦６０００逦７０００逦８０００逦９０００逡逑对象维度逡逑图５．邋１对象数目对时间的影响逡逑数据转置前后时间提升十分明显。逡逑表５．２转置后实验对比逡逑对象数目逡逑１００逦２００逦５００逦１０００逦２０００逦５０００逦８１２４逡逑耗时逡逑Ｍｙ邋Ａｌｇｏｒｉｔｈｍ逦—１0逦１０逦２０逦４０逦６０逦１６５逦２１０￣逡逑ＩｎＣｌｏｓｅ２逦１０逦２０逦３０逦ＩＴ0逦２２０逦６５０逦９２０￣逡逑１０００逡逑９００逦少，＂逡逑８００逡逑７００逡逑＾邋６００逦Ｘ逡逑＾逦ｚ逡逑＾邋５００逦Ｚ逡逑＾逦１邋？邋Ｍｙ邋Ａｌｇｏｒｉｔｈｍ逡逑４００逦Ｚ逡逑■邋１邋ｌｎＣｌｏｓｅ２逡逑３００逡逑２００邋＾邋逦逦逡逑０逦１０００邋２０００邋３０００邋４０００邋５０００邋６０００

对象的交集，即ＦＰ－Ｔｒｅｅ中的公共前缀。而算法只需要计算非公共部分的节点之间的交逡逑运算，囡此计算量得到了极太的降低。算法的执行效率也得到了极大的提升＾逡逑对于转置后的数据，我们进行进一步的对比，将图５．１与图５．２绘制在同一张曲线逡逑图中进行对比，如图５．３所示。逡逑１０００逡逑９００逡逑８００逡逑７００逡逑＾邋６００逡逑—５００逦ｌｎＣｌｏｓｅ２逡逑宕４００逦转置前逡逑３００逦转置后逡逑２００逡逑二逡逑０逦１０００逦２０００逦３０００逦４０００逦５０００逦６０００逦７０００逦８０００逦９０００逡逑对象维度逡逑图５．３转置前后算ｔ去时间对比图逡逑通过图５．３对下述的两个问题进行分析。首先，转置对批处理算法的影响较大，因逡逑为Ｍｙ邋Ａｌｇｏｒｉｔｈｍ算法在建立ＦＰ－Ｔｒｅｅ时索引的选取决定了算法g＿多压缩的计栜羹，由于逡逑Ｍｕｓｈｒｏｏｍ（８，１２４ｘ１２５）数据集的对象较多，属性较少，因此表５．１中选择属性集作为逡逑ＦＰ－Ｔｒｅｅ的索引时数据的压缩并不明显，因此大量对象需要进行概念之间的交运算．ｓ虽逡逑然属性的交运算在ＦＰ－Ｔｒｅｅ优化下己经只进行非公共部分属性的交运算，但由于对象集逡逑基数较大，因此较高的计算量仍然无法被忽略。逡逑对比转置前后的数据

【参考文献】

相关期刊论文 前2条

1 崔芳婷;王黎明;张卓;;基于约束的模糊概念格构造算法[J];计算机科学;2015年08期

2 谢志鹏,刘宗田;概念格的快速渐进式构造算法[J];计算机学报;2002年05期

相关硕士学位论文 前3条

1 杨建峰;多值概念格和区间值概念格构造及属性约简[D];西北大学;2012年

2 刘冬;区间值信息系统上概念格的属性约简方法[D];长安大学;2012年

3 纪彤坤;概念格Chein算法的研究与改进[D];华南理工大学;2012年

本文编号：2802236