一种新的概念格结构——区间概念格

对经典概念格、粗糙概念格的分析表明,其概念外延或者具有全部属性,或者只具备一个属性,从而造成所提取关联规则支持度和可信度严重下降。为此提出一种新的概念格结构——区间概念格Lαβ(Mα,Mβ,Y),其概念外延是区间[α,β](0≤α≤β≤1)范围内满足内涵属性的对象集。证明了当α=β=1时,区间概念格退化为经典概念格;当β=1,α>0时,区间概念格退化为粗糙概念格;其次,给出了区间概念格中概念度量的精度、覆盖度等概念,并给出了相关性质;接着,证明了区间概念格具有的一些独特性质;然后,初步给出了构造区间概念格的方法;最后,通过实例证明了区间概念格提出的必要性和实用性。     

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

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

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

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

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

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

树状结构组织的属性优先的概念格渐进式算法

通过对概念格渐进式构造过程的分析,采用树结构对概念格节点进行组织,研究了利用这种树状组织的渐进式生成属性优先的概念格的构造算法。并结合实例说明了概念格的树结构组织在属性优先的渐进式生成概念格时,能有效地缩小产生子格节点的搜索范围和新增格节点的父节点和子节点的搜索范围,从而能快速生成概念格。     

基于属性消减的模糊概念格渐进式构造算法

当前模糊概念格的直接构造具有指数时间复杂度,且随着真值集合L大小的增加,模糊概念格的规模变得越来越庞大。为此提出了FMBUAD算法,它能够在原有模糊概念格的基础上消去多个消减属性(冗余或者无效属性)得到新的模糊概念格,且不考虑真值集合L的大小。基于模糊概念格的基础理论证明了FMBUAD算法的正确性。该算法首先将所有概念节点内涵中的消减属性隶属度移除;然后找出模糊概念格中所有的删除节点;最后集中处理删除节点父子节点之间的偏序关系。理论证明和实验结果表明:FMBUAD算法构造L-模糊概念格具有较好的时间性能。     

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

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

粗糙形式概念抽取的属性集合幂集方法

为了最大限度地抽取出形式背景中的粗糙形式概念,以便为粗糙概念格的构建提供完整的信息源,对粗糙形式概念的抽取进行了研究,提出了粗糙形式概念抽取的属性集合幂集方法.其操作要点为:粗糙形式概念的内涵由属性集合幂集方法所求得的子集确定,粗糙形式概念的外延由属性集合幂集所对应对象的上下近似集确定.该方法实现了粗糙形式概念的抽取,...     

概念格的属性渐减原理与算法研究

渐进式算法是概念格构造的一类重要算法,但大多关注于形式背景中对象或属性增加的情况.而当形式背景的属性减少时,已有的算法则需要重新构造概念格,较为费时.针对这一情况,研究了属性消减后从原概念格渐进式产生新概念格的理论和算法,并且算法时间复杂度较低.首先分析了原概念格和新概念格中节点间的映射关系以及从原概念格到新概念格中边(节点间的前驱-后继关系)的变化规律.在此基础上,提出了自顶向下和自底向上两种渐进式的概念格属性渐减算法.算法能够对原有概念格直接进行修改来得到新的概念格,避免了从形式背景重新构造概念格,时间复杂度降低为O(‖ L ‖·G ‖·‖M ‖).实验及分析表明,当属性减少时,能比传统算法节省大量的运行时间.     

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

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用,概念格的构造在其应用过程中是一个主要问题.提出了采用树结构对概念格节点进行组织,研究了基于属性的概念格渐进式构造算法.概念格节点的树结构组织可以约束更新格节点和产生子格节点的搜索范围,从而可以有效地减少算法的执行时间.在随机生成的数据集上进行的实验测试表明,本算法的时间性能更优越.     

基于对象和属性交叉的渐进式概念格生成算法

在分析人类概念形成机理的基础上,提出一种基于对象和属性交叉渐进式概念格生成算法,从空概念格开始,逐个地将形式背景中的对象和属性交叉插入到概念格中,实现对概念格的渐进式构造。该算法能渐进式地有效构造概念格,解决了以往渐进式概念格生成算法针对属性和对象交叉渐增更新需要重新构造概念格的问题。     

一种基于属性的概念格生成及维护算法

大部分概念格的生成算法都是基于对象的渐进式算法，提出了基于属性增加的概念格的生成及维护算法，解决了实际应用中对象趋于稳定而属性不断增加而造成的建格及维护问题。经验证该算法是有效可行的。     

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

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

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

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

基于对象和属性交叉渐进模糊概念格生成算法

在人类的认知过程中,真实的形式背景总是模糊和不确定的,并伴随着对象和属性交叉渐增更新。在分析人类概念形成机理的基础上,提出了一种基于对象和属性交叉渐进式模糊概念格生成算法。该算法从空概念格开始,逐个地将形式背景中的对象和属性交叉插入到模糊概念格中,实现对模糊概念格的渐进式构造。实验及分析表明该算法不仅能有效地渐进式构造模糊概念格,而且解决了以往渐进式概念格生成算法,针对属性和对象交叉渐增更新需要重新构造概念格的问题。     

基于约束的模糊概念格构造算法

一般的模糊概念格在构造过程中没有考虑用户的需求,用户对模糊概念格节点中一些属性集形成的内涵并不感兴趣。为了增强模糊概念格的针对性,降低模糊概念格构造的时空复杂性,构造满足用户需求的模糊概念格,首先将用户感兴趣的背景知识定义为约束条件,根据用户关心的属性间关系,将约束条件分为3类:单约束、与约束及或约束,并采用谓词公式表示,进而提出了基于约束的模糊概念格(Constrained Fuzzy Concept Lattice,CFCL)构造算法。该算法自底向上构造模糊概念格,利用模糊概念格父子节点内涵的单调关系,采用剪枝技术来减少构造过程中判断模糊概念是否满足约束的次数,提高了模糊概念格的构造效率。实验结果表明,该算法能够有效地减少模糊概念格的存储空间和构格时间。     

基于属性的概念格渐进式生成算法

提出了一种新的基于属性的渐进式概念格生成算法 ,通过不断地渐增属性来构造概念格 .该算法不仅为概念格的构造提供了一种新的方法 ,还解决了在已构造好概念格的前提下 ,增加属性所带来的概念格更新问题 .给出了算法的实现方法 ,并结合实例说明了概念格的更新过程 .试验表明 ,在通常情况下 ,基于属性的渐进式概念格生成算法的性能往往更优越     

基于搜索空间划分的概念生成算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用.概念格的构造在其应用过程中是一个主要问题.提出了一种基于搜索空间划分的概念生成算法SSPCG(search space partition based concepts generation),它将属性集合的幂集看作初始闭包搜索空间,迭代地将每个搜索空间划分为一些子搜索空间,并引入了子搜索空间的有效性判断,只搜索那些能生成正规闭包的子搜索空间,有效地提高了搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度.由于所有子搜索空间是独立的,所以该算法可以很容易地扩展为并行算法.在随机生成的数据集和真实数据集上进行的实验测试表明,本算法的时间性能要优于Ganter提出的NextClosure算法.     

幂集特征矩阵及其应用

定义集合子集特征向量函数、集合子集特征向量的特征函数和集合子集特征函数。给出集合幂集特征矩阵的概念,研究集合幂集特征矩阵的性质;给出“模2法”和“辗转赋值法”2种生成集合幂集特征矩阵的形式化算法,分析算法的复杂度;将幂集特征矩阵应用到自动生成集合幂集和命题公式真值表,结果显示算法合理高效。      

基于最大概念的概念格增量构造算法

针对增量概念格构造过程中,节点更新和生成元判定效率较低、边更新阶段的复杂度较高等问题,提出基于最大概念的概念格增量构造算法,通过跟踪与概念格中的概念具有相同真实内涵的最大概念,简化生成元的判断过程。该算法缩小了寻找新生节点父节点时的搜索范围,避免对生成元非必要边的判断,提高构造概念格的速度。复杂度分析结果表明,该算法的时间性能优于其他同类算法。