基于信息熵的对象加权概念格

在大数据时代,由于数据规模越来越大,导致构造概念格的难度越来越高。在能够客观反映数据隐藏信息的前提下需删除冗余对象及属性,降低数据规模,构造更为简单的概念格,从而便于用户更高效地获取知识。为避免主观因素,本文由形式背景中属性的信息熵来获取单属性权重,采用均值方法计算对象权重,并用标准差计算对象重要性偏差值。通过设定的属性权重、对象权重和对象重要度偏差阈值,构造对象加权概念格。通过实例验证了,该方法可有效删除冗余概念,简化概念格构造过程。     

一种基于概念格属性约简的本体合并方法

提出一种基于概念格属性约简的本体合并方法。该方法先对源本体中的概念进行外延和内涵的分析,以此为形式背景构造概念格。对所构造的概念格进行属性约简,删除本体合并中的冗余信息,约简绝对不必要属性,以最少的信息精确地反映概念格及本体的本质和结构。最后通过实例分析此方法的可行性。     

一种频繁加权概念格的批处理构造算法

概念格是知识表示和数据分析的一种有效工具,加权概念格是一种刻画内涵重要性的概念格结构。文中通过引入虚结点的概念,提出一种频繁加权概念格的批处理构造算法。该算法首先通过引入虚结点概念,证明频繁加权概念格是一个完全格,从而纠正先前张继福提出的频繁加权概念格结构中某些频繁加权概念结点不存在上下确界的缺陷。其次,采用自底向上的方法来生成频繁结点和虚结点,以及对应的边关系,从而降低频繁加权概念格构造的时空复杂性,提高批处理构造效率。最后在恒星光谱数据上的实验验证算法的正确性和有效性。     

区间概念格的纵向合并算法

为解决直接对不同形式背景的数据构建区间概念格后分别抽取关联规则会存在规则缺失的实际问题,必须首先对不同的区间概念格进行合并.为提高格结构的生成与合并效率,首先对区间概念格的渐进式生成算法进行改进,将概念分为存在概念、冗余概念和空概念,分别以结构体的形式存储;进一步,分析区间概念格中外延和内涵之间的二元关系,给出了区间概念格纵向合并的充分条件——区间概念格的一致性;讨论了内涵一致的概念在合并后分为六种情况,并给出相应的判定定理;应用广度优先原则,通过对原区间概念格节点内涵的类型判定及不同的处理方法,设计了一种区间概念格的纵向合并算法.最后,通过实例验证了算法的有效性和高效性.     

基于剪枝的约束概念格的渐进式构造算法

约束概念格是数据分析的一种有效工具,在其构造的过程中,大量的内涵之间比较操作是导致格的构造效率低下的主要原因之一。采用剪枝技术来消除构造过程中存在的冗余内涵比较,给出约束概念格渐进式构造算法PCCL。该算法利用父子节点内涵的严格单调关系,自顶向下扫描格节点,减少了新增对象属性集与原概念格节点内涵的比较次数,从而提高了约束概念格的构造效率。最后以天体光谱数据作为形式背景,实验验证了PCCL算法的正确性,且构造效率平均提高了15%以上。     

约束概念格及其构造方法

概念格是一种有效的数据分析和知识提取的形式化工具．然而，随着要处理的数据量的剧增，基于原始形式背景构造出的概念格结点数目庞大，占用大的存储空间，同时概念格结点中一些属性集形成的内涵，用户并不都感兴趣，因而从中提取用户需求知识费时．为了降低概念格构造的时空复杂性，增强实用性和针对性，首先采用谓词逻辑描述用户感兴趣的背景知识，并将背景知识引入到概念格结构中，提出了一种新的概念格：约束概念格．在此基础上，提出了基于背景知识的约束概念格构造算法CCLA．理论分析表明，该算法能有效地减少概念格的存储空间和建格时间．最后，采用恒星天体光谱数据作为形式背景，实验验证了该算法的有效性．     

加权概念格的渐进式构造及其关联规则提取

概念格的每个结点本质上是一个最大项目集,非常有利于关联规则的提取。然而目前对于概念格的研究,一般都假定由属性集所组成概念格的内涵同等重要,而在现实数据库中,组成内涵的属性重要性往往是不同的,因此,内涵并非同等重要。为了充分利用概念格实现关联规则提取,提出了一种新的概念格结构:加权概念格,并给出其渐进式构造算法及基于该格结构上的关联规则提取算法,同时给出算法分析以说明其可行性。     

基于区别度概念格的关联规则的挖掘*

针对大部分文献在构造概念格时都把属性看做是同等重要,而将导致冗余问题,提出了一个新的概念——属性区别度（内涵区别度）。在建造概念格的过程中将去掉那些属性区别度（DISP）比较低的内涵,从而加速概念格的构造;同时不再每一次都扫描数据库计算项集或内涵的支持度,而是有条件地计算和重置DISP,这将减少扫描数据库的次数,从而达到减少生成关联规则时间的目的。     

区间概念格的纵向维护原理与算法

区间概念格是唯一能直接反映具备一定数量或比例的内涵中属性的对象集合的格结构。格结构是根据对象-属性的二元关系构造的,形式背景中的属性是时刻变化的,为使概念格能反映属性变化后的数据规律进而提取新的规则,提出了区间概念格的纵向维护算法。算法在分析了区间概念格的概念外延特点及结构特征后,给出了区间概念格在增加属性、删除属性两种情况下的维护算法,进而通过算法分析表明了维护较重构在时间与空间上的高效性,最终用实例表明了维护算法的可行性。     

基于属性的概念格快速渐进式构造算法优化

文章提出一种基于属性的概念格快速渐进式构造算法,主要解决传统算法存在执行时间长和准确率低等问题。首先,该算法引入单属性权值、多属性权值、阈值设定3个内容,并对其进行优化。其次,利用信息熵和偏好修正系数,对单属性权值获取进行调整,从原始数据中获取多属性权值。最后,通过阈值设定衡量多属性的重要性,同时约束条件获取合理的属性权值取值结果。实验结果表明,该算法优化后生成的概念数量小于原概念格中概念的总数,执行时间更短,准确率更高。     

基于二元关系消减的概念格维护算法

针对有限空间下如何快速维护概念格的问题,提出一种消减形式背景中冗余二元关系的概念格维护算法。传统的算法删除冗余关系后需要重新构造概念格,这种方式较为费时。而所提算法能够在原始概念格的基础上直接调整得到新概念格的方法,可以处理任意位置的二元关系消减的情况。它采用自底向上广度优先方式遍历格节点,首先根据当前节点是否同时包含冗余关系对象和冗余关系属性,将当前节点分为受影响的节点和不变节点;然后根据当前节点与父子节点的外延和内涵的关系,再将受影响的节点细分为4类,即减对象节点、减属性节点、分割节点、删除节点;最后根据父子节点的类型更新边。实验结果表明,在一定程度上与传统算法相比,所提算法能够获得更好的时间性能。     

对偶区间集概念格上区间集协调集的判定方法

对偶区间集概念格是将区间集引入到对偶概念格产生的,它将对偶概念的外延与内涵从经典集合推广到区间集,使之成为一种描述不确定性概念的数学方法。而属性约简是数据挖掘的核心内容之一,是一种研究概念格本质特征的方法,它通过删除冗余属性使数据表中概念的获取与表示变得更简洁。文中主要研究对偶区间集概念格上区间集协调集的判定方法。首先基于对偶区间集概念格的同构,引入了区间集协调集,给出了对偶区间集概念格上区间集协调集的一系列判定定理,进而讨论了利用区间集协调集获取区间集属性约简的方法。     

基于优化可辨识矩阵和改进差别信息树的属性约简算法

运用可辨识矩阵表示信息系统中所有对象的区分信息,为研究属性约简提供了新方向。然而,传统的可辨识矩阵在构造结束后才利用核属性消除冗余元素项,忽略了核属性在矩阵构建过程中的作用。针对这一问题,文中做了以下研究:1)优化可辨识矩阵的构造方式,在计算任意两个对象的区分信息之前,先判断核属性上的取值是否相等,如果不相等,则直接将对应元素项记为Φ,忽略对其他条件属性的判断;2)提出属性加权重要度的概念,综合考虑每个条件属性占可辨识矩阵中非空元素项的比率(称为宏观重要度)与每个属性对区分对象的贡献程度(称为微观重要度),并通过例子说明了该度量方法的合理性;3)针对优化后的矩阵仍然存在大量冗余元素和空集这一缺陷,结合差别信息树的概念提出基于优化可辨识矩阵和属性加权重要度的差别信息树。按照属性加权重要度对优化可辨识矩阵中所有非空元素项进行排序,使得重要度高的属性被更多的节点共享;且在构建过程中将不包含核属性的元素项映射到树中的一条路径上,而包含核属性的元素项则被直接忽略。最后,提出基于优化可辨识矩阵和改进差别信息树的约简算法HSDI-tree。在UCI的5个数据集上分别比较了HSDI-tree算法与CDI-tree,DI-tree和IDI-tree算法的约简结果和节点个数,实验结果表明HSDI-tree算法能有效找到最小属性约简且空间压缩能力更好。     

概念格的内涵缩减研究

利用概念格作为属性约简的数据模型,对概念格上的父子关系和内涵属性来源进行了分析:在概念格中任意若干个概念如果存在共同的子概念,那么只存在一个共同的子概念;概念的属性有两种来源,其一是继承的父节点的属性,其二是概念细化过程中增加的属性。相应地提出了两条内涵缩减的规则:如果一个节点只有一个父节点,那么其内涵缩减来源于它的内涵与父节点内涵的差集;如果一个节点有两个或两个以上的父节点,那么其内涵缩减来源于任意两个父亲节点属性的并集。然后对两条规则进行了证明,并设计了计算内涵缩减的算法。     

概念格属性约简的判定

引入Galois联络,利用Galois联络深入研究了概念格的基本性质。指出概念格同构是格同构。为了寻求更为简洁、合理的约简算法,在更一般的形式背景（即对象集和属性集有限或无限）中,给出协调集的四类判定定理,将已有结果做了推广而且丰富了协调集的判定。举例说明在一般的形式背景中,约简不一定存在。     

基于内涵亏值的概念格渐进式构建

为了避免构建概念格时的繁琐过程,提高概念格构建的效率,提出了一种基于内涵亏值通过查找顶元素来快速渐进式生成概念格的新方法。首先,形式化地定义了顶元素、旧概念、产生概念、新概念、产生子概念、内涵亏值集合、剩留父概念、超集删除与正则队列;提出了概念格元素是否为顶元素的判定定理并给出了其证明;其次,在原概念格的正则队列中依次取概念元素,经超集删除后得到剩留父概念;最后,从剩留父概念查找其所在等价类的顶元素,逐步生成新概念格的正则队列。理论分析时间复杂度较基于属性的渐进式概念格生成（CLIF_A）算法与FastAddIntent算法有效降低,在实验例证对比中,概念数目大于150时,所用时间远少于对比算法。实验结果表明该算法方法简单,构建效率较对比算法明显提高。     

An outlier mining algorithm based on constrained concept lattice

Traditional outlier mining methods identify outliers from a global point of view. These methods are inefficient to find locally biased data points (outliers) in low dimensional subspaces. Constrained concept lattices can be used as an effective formal tool for data analysis because constrained concept lattices have the characteristics of high constructing efficiency, practicability and pertinency. In this paper, we propose an outlier mining algorithm that treats the intent of any constrained concept lattice node as a subspace. We introduce sparsity and density coefficients to measure outliers in low dimensional subspaces. The intent of any constrained concept lattice node is regarded as a subspace, and sparsity subspaces are searched by traversing the constrained concept lattice according to a sparsity coefficient threshold. If the intent of any father node of the sparsity subspace is a density subspace according to a density coefficient threshold, then objects contained in the extent of the sparsity subspace node are considered as bias data points or outliers. Our experimental results show that the proposed algorithm performs very well for high red-shift spectral data sets.     

形式概念中的内涵亏值及属性约简

属性约简一直是概念格领域研究的热门话题。文中借助内涵亏值的思想证明在每个唯一上近邻概念的内涵亏值中各任取一个元素组成的集合就是一个约简,从而给出一个求全部约简的简单算法,并且这个算法在Hasse 图中有较直观的形象。由于该算法只涉及唯一上近邻概念,所以不需求出全部概念格,只需对背景进行一些并交运算即可全部完成,因此算法的时间复杂度及空间复杂度都是多项式的。