概念格与粗糙集的数据分析方法研究

概念格和粗糙集是数据挖掘中对数据进行分析与处理的两个有力工具,它们在数据分析方面有相似之处.通过运用概念格刻画粗糙集的一些概念与性质给二者建立了联系.指出了概念格每个结点都是粗糙集中一个等价类,并借鉴粗糙集的思想,提出了在概念格中进行概念近似的方法.同时使用概念格中的概念重新描述了粗糙集的上下近似,最后通过事例将粗糙集中改进的区分矩阵运用于概念格中的属性约简,从而减少了区别矩阵的存储空间,并同时减少了区别矩阵的计算量,真正从一定意义上结合了二者的优点.     

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

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

本体映射中的概念相似度计算

本体是概念、属性和关系的集合．本体映射是解决本体异构的最好方法。文中针对目前本体映射过程中概念相似度计算存在的问题,提出一种综合的相似度计算方法。先根据本体中两个概念名称的相似性,选出最相关的概念,减少相似度的计算,然后分别基于概念的属性、实例和关系来计算概念相似度,并进行综合得到概念相似度。在计算属性相似度时,先通过计算属性的信息增益来确定各个属性的优先级,最后只选取几个信息增益大的属性进行相似度的计算,从而减小计算量。     

本体映射中的概念相似度计算

本体是概念、属性和关系的集合,本体映射是解决本体异构的最好方法.文中针对目前本体映射过程中概念相似度计算存在的问题,提出一种综合的相似度计算方法.先根据本体中两个概念名称的相似性,选出最相关的概念,减少相似度的计算,然后分别基于概念的属性、实例和关系来计算概念相似度,并进行综合得到概念相似度.在计算属性相似度时,先通过计算属性的信息增益来确定各个属性的优先级,最后只选取几个信息增益大的属性进行相似度的计算,从而减小计算量.     

基于概念格的概念相似度计算

为了提高信息检索的查全率和查准率,经常要处理相似的概念,因此计算概念间的相似度是必要的.概念由对象和属性两部分组成,所以基于概念格相似度计算的也分为两部分:一是利用概念格的层次关系计算对象的相似度,另一部分计算属性的相似度.其次,概念间的相似度与概念在概念格中的深度有关,计算时利用深度对结果加以修正.计算模型利用了概念较为完整的信息,计算结果与人工判断基本吻合.     

基于属性约简的概念格构造

概念格是数据处理和规则提取的重要工具。对于数据较大的形式背景,由于产生的概念格结构复杂,部分有用的信息将被这种复杂的结构所掩没。本文利用属性约简理论,首先在没有构造概念格的前提下将概念格的属性进行约简,从而进一步构造出约简后的概念格。实验证明,该方法简洁高效。     

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

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

构造概念格的权值优化改进算法

针对基于信息熵与偏差的加权概念格在合并加权概念子格时,所得多属性内涵集权值较其整体在形式背景中的实际权重偏大,权重取值阈值的设置受主观因素干扰导致合并后的概念格规模过大的问题,提出了一种构造概念格的权值优化改进算法.以多属性内涵集在形式背景中的整体信息熵来设置其权值;采用方差计算各概念结点属性内涵集权值的阈值区间,克服了主观意识对阈值设置的影响;通过剪除不满足阈值区间的冗余概念结点,缩小了构造概念格的整体规模,减少了构造概念格的时间消耗.实验结果表明:对比基于信息熵与偏差的加权概念格减少了9.87％的冗余结点,构造整体概念格的时间消耗减少了7.36％,有效提高了加权概念格的构造效率.     

基于属性一致度的属性约简算法

在属性一致度的概念和性质基础之上,提出一种基于属性一致度的属性约简算法。利用一致度构造属性间模糊相似矩阵,并用模糊聚类分析方法对属性重要性作了分类,从而得到动态属性分类图,得到了与粗糙集属性约简方法完全一致的结果。最后,用实例表明算法的有效性。     

基于支撑函数的概念格属性约简

依据概念格中一个概念的内涵属性相对于另一个概念的内涵的不同关系,提出了区分属性概念,并研究了其性质;利用区分属性构造出概念格支撑函数.提出并证明了以支撑函数为基础的形式背景属性约简定理,改进了文献[7]中基于辨识函数的属性约简方法.     

基于概念格外延信息量的属性约简算法

概念格是知识处理与分析的一个有力的工具,在知识约简和数据挖掘方面有着重要的利用。首先给出了概念格外延信息量的概念,在此基础上研究了合理刻画属性重要性的指标,并给出了概念格核心属性的判定定理,然后以这些指标作为启发式信息设计了一种新颖的概念格启发式属性约简算法,最后通过实例表明了该约简算法的可行性与有效性。     

一种基于直积运算的概念格合并算法

现有的渐进式概念格构造算法,不能有效利用已有的概念格.当形式背景的属性数目发生变化时,需要以单个属性或属性集合为对象,重新构造概念格.为此,提出了一种基于已有概念格的概念格合并算法,对已有概念格做直积运算,通过直积格和总格的映射关系,自底向上直接构造出总概念格.这个算法适用于属性交集为空的形式背景的合并.     

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

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

基于概念格的关联规则挖掘方法

对概念格在关联规则挖掘中的应用进行了研究.通过将概念格的外延和内涵分别与事务数据库中的事务和特征相对应,可以从概念格上产生频繁项集,进而挖掘关联规则.提出了一种基于概念格的关联规则挖掘方法,在背景中对象约简的基础上,构造出对象约简后的概念格,从新的概念格中先产生基本规则集,再根据用户给出的支持度阈值从基本规则集中挖掘出对用户有意义的规则,并给出了算法描述.该方法求出的关联规则和利用Apriori算法求出的结果是一致的.     

Incrementally building frequent closed itemset lattice

A concept lattice is an ordered structure between concepts. It is particularly effective in mining association rules. However, a concept lattice is not efficient for large databases because the lattice size increases with the number of transactions. Finding an efficient strategy for dynamically updating the lattice is an important issue for real-world applications, where new transactions are constantly inserted into databases. To build an efficient storage structure for mining association rules, this study proposes a method for building the initial frequent closed itemset lattice from the original database. The lattice is updated when new transactions are inserted. The number of database rescans over the entire database is reduced in the maintenance process. The proposed algorithm is compared with building a lattice in batch mode to demonstrate the effectiveness of the proposed algorithm.     

一种新的核线性鉴别分析算法及其在人脸识别上的应用

基于核策略的核Fisher鉴别分析（KFD）算法已成为非线性特征抽取的最有效方法之一。但是先前的基于核Fisher鉴别分析算法的特征抽取过程都是基于2值分类问题而言的。如何从重叠（离群）样本中抽取有效的分类特征没有得到有效的解决。本文在结合模糊集理论的基础上,利用模糊隶属度函数的概念,在特征提取过程中融入了样本的分布信息,提出了一种新的核Fisher鉴别分析方法——模糊核鉴别分析算法。在ORL人脸数据库上的实验结果验证了该算法的有效性。     

一种基于属性分割的产生式/判别式混合分类器

为了利用产生式和判别式方法各自的优势,研究了基于属性分割的产生式/判别式混合分类模型框架,提出了一种基于属性分割的产生式/判别式混合分类器学习算法GDGA。其利用遗传算法,将属性集X划分为两个子集XG和XD,并相应地将训练集D垂直分割为两个子集DG和DD,在两个训练子集上分别学习产生式分类器和判别式分类器;最后将两个分类器合并形成一个混合分类器。实验结果表明,在大多数数据集上,混合分类器的分类正确率优于其成员分类器。在训练数据不足或数据属性分布不清楚的情况下,该混合分类器具有特别的优势。     

An efficient algorithm for increasing the granularity levels of attributes in formal concept analysis

In the basic setting of formal concept analysis, a many-valued attribute needs to be replaced with several one-valued attributes. These one-valued attributes can be interpreted as a certain level of granularity of the corresponding many-valued attribute. In this paper, we explore theoretical relationships between concepts before and after increasing the granularity level of one attribute, based on which we introduce an efficient method of concept classification. Moreover, a new preprocessing routine is proposed to help generate new concepts and restore lattice order relation. These two procedures can considerably reduce the comparisons between sets, compared to the original Zoom-In algorithm. By employing these two procedures, we introduce an efficient algorithm, referred to as Unfold, to increase the granularity levels of attributes. The algorithm can perform a Zoom-In operation on a concept lattice associated with a coarser data granularity to obtain a new one that consists of finer formal concepts without building the new lattice from scratch. We describe the algorithm and present an experimental evaluation of its performance and comparison with another Zoom-In algorithm. Empirical analyses demonstrate that our algorithm is superior when applied to various types of datasets.     

概念格属性约简的启发式算法

概念格是知识处理与分析的一个有力的工具,在知识约简和数据挖掘方面有着重要的应用。该文首先从概念外延的角度研究了合理刻画属性重要性的指标,并给出了概念格属性约简的判定定理,然后以这些指标作为启发式信息设计了一种新颖的概念格启发式属性约简算法,最后通过实例表明了该约简算法的可行性与有效性。