一种基于相对粒度的决策表约简算法

在知识粒度的基础上,针对决策表提出了相对粒度和属性相对重要性的概念,证明了知识的相对粒度随着知识粒度的增大而单调增加的变化规律,在此基础上提出了一种基于相对粒度的启发式约简算法,以弥补基于正区域的约简方法处理不一致决策表时存在的不足.通过理论分析和实例验证表明,该算法是有效的,且其时间复杂度相对较低.     

信息系统中的熵理论和信息粒度

不确定性是人工智能中的研究热点,而熵理论和信息粒度是度量信息系统不确定性的两种主要方法。本文在给出信息系统中熵的物理意义基础上,提出了信息系统中熵增加原理,给出了熵和信息粒度的公理化定义,据此构造了两种新的不确定性度量函数—α熵和α粒度,它们是已有熵和粒度度量的进一步推广。研究表明,α熵以及现有的熵度量都是广义熵的特殊形式,而α粒度以及现有的粒度度量都是广义粒度的特殊形式,从而统一、规范和发展了完备与不完备信息系统中的不确定性度量方法。     

一种基于信息粒度的信息检索优化方法

在优化信息检索系统的研究中,为了提高主题检索的效果,针对目前主题相似性计算存在的信息粒度细化而导致计算复杂度升高,使检索时间成倍增加的问题,影响快速识别和判断,提出了一种基于信息粒度主题扩展的优化算法。首先在算法中引入知识系统,对用户提交的关键词进行主题扩展;然后以相关度进行分级,并实现事件主题知识的自动模式提取;结合内容检索与跟踪的事件主题识别算法的优点,再进行二次相似度判别。最后返回满足用户要求的检索结果。实验结果表明,在同一数据集上和正确率方面,此算法的执行速度明显提高,查找出的结果比预期结果更加接近。     

Semantic Granularity in Ontology-Driven Geographic Information Systems

The integration of information of different kinds, such as spatial and alphanumeric at different levels of detail, is a challenge. While a solution is not reached, it is widely recognized that the need to integrate information is so pressing that it does not matter if detail is lost, as long as integration is achieved. This paper shows the potential for information retrieval at different levels of granularity inside the framework of information systems based on ontologies. Ontologies are theories that use a specific vocabulary to describe entities, classes, properties and functions related to a certain view of the world. The use of an ontology, translated into an active information system component, leads to ontology-driven information systems and, in the specific case of GIS, leads to what we call ontology-driven geographic information systems.     

Incomplete Information Tables and Rough Classification

The rough set theory, based on the original definition of the indiscernibility relation, is not useful for analysing incomplete information tables where some values of attributes are unknown. In this paper we distinguish two different semantics for incomplete information: the "missing value" semantics and the "absent value" semantics. The already known approaches, e.g. based on the tolerance relations, deal with the missing value case. We introduce two generalisations of the rough sets theory to handle these situations. The first generalisation introduces the use of a non symmetric similarity relation in order to formalise the idea of absent value semantics. The second proposal is based on the use of valued tolerance relations. A logical analysis and the computational experiments show that for the valued tolerance approach it is possible to obtain more informative approximations and decision rules than using the approach based on the simple tolerance relation.     

基于信息粒度和连通强度的优化学习

针对具有分布式网络和复杂的拓扑结构的认知学习问题,本文提出一种动态的基于信息粒度和连通强度的自组织的认知优化学习系统。每个网络节点的信息粒在高聚合度的情况下,具有信息表示的完整性,知识系统中节点的自组聚合和节点间的强连通性是优化学习绩效的核心模型。利用信息粒的聚合度和信息粒间的连通性的概念,信息粒度的演进流程模拟认知学习过程的静态归约,连接强度演进流程对应于认知学习的动态模拟,这两个流程在学习系统中对每个输入样本完成一个完整的模拟认知与归约表达。以分布式拓扑结构为理论模型,给出了每个节点信息粒度以及节点之间的信息处理与传递的认知优化规范。     

一个改进的主从结构表安全数据模型

到目前为止,大量的文献已经提出了许多用以实现多级安全数据库系统的安全模型,不同的模型有不同的优点。本文针对原有主从结构表安全模型容易产生语义模糊性和操作不完备性等问题,提出了一个能够消除语义模糊性和操作不完备性的新的主从结构表模型。该模型增加了基元组和数据继承的概念,重新定义了多实例完整性和参照完整性,将PUPDATE操作和数据继承完整性引入该模型,大大增强了系统的安全性和非二义性。     

基于下近似分布粒度熵的变精度悲观多粒度粗糙集粒度约简

将下近似分布约简引入变精度悲观多粒度粗糙集,定义了变精度悲观多粒度粗糙集的下近似分布粒度熵,基于下近似分布粒度熵定义了变精度悲观多粒度粗糙集粒度的重要度,并设计了基于下近似分布粒度熵的悲观多粒度粗糙集启发式粒度约简算法,通过实例验证了算法的有效性。     

Probabilistic Decision Tables in the Variable Precision Rough Set Model

The Variable Precision Rough Set Model (VPRS) is an extension of the original rough set model. This extension is directed towards deriving decision table-based predictive models from data with parametrically adjustable degrees of accuracy. The imprecise nature of such models leads to quite significant modification of the classical notion of decision table. This is accomplished by introducing the idea of approximation region-based, or probabilistic decision table which is a tabular specification of three, in general uncertain, disjunctive decision rules corresponding to rough approximation regions: positive, boundary and negative regions. The focus of the paper is on the extraction of such decision tables from data, their relationship to conjunctive rules and probabilistic assessment of decision confidence with such rules.     

基于伪树冠的细粒度可变尺寸块运动估计

为了实现细粒度的可变尺寸块运动估计算法,构造了一个三叉和四叉结构组合的伪树冠数据结构,和细粒度四叉树森林结合成一个具有单个根节点的复合树。细粒度可变尺寸块运动估计算法同粗粒度算法一样可以利用树结构的特点快速找到具有率失真斜率极值的节点。仿真试验验证了细粒度算法和粗粒度算法的不同适用范围。通过仿真试验分析了运算量减少策略、搜索窗大小、搜索深度对算法性能的影响。     

基于信息粒度的聚类分析及其应用

在处理复杂问题时,通过改变问题所在的粒度空间,不仅可以有效获取对象的特征,而且可去除干扰和非本质属性,使问题易于分析解决。所谓从粒度计算的观点来讨论聚类分析问题,就是认为聚类是在原问题的粒度下(同一问题的最细粒度空间)进行问题分析。为了简化处理,引入不同的聚类相似性函数,其实质就是得到不同粒度空间的等价类。在实际问题求解中,可以根据问题需要取不同相似性函数,以便将问题变换到所需的粒度空间进行处理。为推广其应用,将该思想应用于车牌二值化,提出了基于信息粒度的聚类变换的二值化算法,实现了从彩色3维空间到黑白1维空间的粒度变换。实验结果表明,该算法所得结果更加切合实际图像,不仅具有普适性,而且有利于下一步的识别操作,尤其对于各种斜车牌、光照不均车牌更具有一定的优越性。     

基于变粒度的大规模真值表快速知识约简

在大规模逻辑电路的分析与设计中,直接由大规模真值表得到最简逻辑函数表达式的过程往往比较复杂。针对此问题,提出了一种基于变粒度的大规模真值表快速知识约简算法。随着真值表的输入逻辑变量的粒度变化,通过引入标记矩阵和启发式算子,对大规模真值表进行知识约简,从而得到最简逻辑函数表达式。最后,通过实例分析并详述算法过程,且通过数据集进行对比实验,验证了该算法的快速性与有效性。     

可变粒度的业务质量评价模型及其算法研究

针对现有的服务质量评价多面向特定业务和特定领域的特点,提出可变粒度的通用网络业务质量管理和评价模型,可以实现从用户、业务到网络系统的多级业务质量评价.同时,由业务管理、策略管理和网络管理共同所组成的服务质量保障模块,能根据SLA协商为用户提供有QoS保障的服务.给出了业务质量的主客观评价指标形式化定义和一般的评价流程,在此基础上采用组合证据和模糊评价理论,给出了不同粒度下的业务质量模糊评价算法.该算法将用户的主观性评价和客观性评价结合起来,从而在一定程度上降低了评价中的主观随意性.     

基于信息粒度的不完备信息系统空值补齐算法

在现实世界中,不完备信息系统大量存在的,信息系统中空值的存在大大增加了信息表的不确定性,信息表无法产生更多潜在的有价值规则.处理不完备信息表的一种做法是先将空值补齐再提取规则,常用的空值补齐算法通常都是根据同属性其他值出现的频率高低估计空值,但是此方法不一定能保证规则的一致性.本文提出一种基于信息粒度的空值补齐方法GRCC,首先根据定义的信息粒度选择信息粒度最大的列,然后由相容类产生空值的属性值范围,最后利用MDL准则确定遗漏项的属性值,如此逐列进行填充直到完成全部信息表的补齐.经过实验,GRCC算法补齐的信息表比其它补齐方法产生的信息表产生更多高可信度和高支持度的规则,降低了信息表的不确定性.     

不完备信息系统中知识粒度的公理化定义与度量方法

给出不完备信息系统中知识粒度的公理化定义,在此基础上提出一系列知识粒度度量方法.其中有不带参数的具体度量,也有带参数的一般性度量,并比较3个知识粒度的大小.另外,还给出不同粒度的4种组合形式.本文所给出的知识粒度度量方法对于在不完备信息系统中建立粒度计算有着重要的理论意义和应用价值.     

变阶式递推增广算法及应用

本文给出一种能自动改变模型阶数的变阶式递推增广的最小二乘法,在此基础上,对一类ＣＡＲＭＡ系统给出一种在线自动辨识机。实际应用表明,这种辨识机不仅可用于模型的在线辨识,大大减小建模的计算量,而且对系统进行预报时,具有较高的精度。     

基于粒度变换的多范畴复杂信息分类方法

针对大数据处理中多范畴复杂信息处理能力弱的问题,提出一种基于粒度变换的多范畴复杂信息对象的分类方法。首先在分类中引入映射表和误分类率阈值,然后构建等价类,设定对应不同范畴的属性,通过多种无损粒度变换和有损粒度变换的计算分析,获得多范畴复杂信息对象约泛化算子,并依此计算多范畴复杂信息分类对象的误分类率,并依误分类率对分类对象进行标引,实现有效分类。此方法在一定程度上解决多范畴复杂信息对象的分类问题,通过与另一套多范畴分类测试系统MCTS的对比,验证建立在此方法基础之上的多范畴复杂信息分类系统在误分类率上有较明显的优势。     

DNF are teachable in the average case

We study the average number of well-chosen labeled examples that are required for a helpful teacher to uniquely specify a target function within a concept class. This “average teaching dimension” has been studied in learning theory and combinatorics and is an attractive alternative to the “worst-case” teaching dimension of Goldman and Kearns which is exponential for many interesting concept classes. Recently Balbach showed that the classes of 1-decision lists and 2-term DNF each have linear average teaching dimension. As our main result, we extend Balbach’s teaching result for 2-term DNF by showing that for any 1≤s≤2 ^Θ(n), the well-studied concept classes of at-most-s-term DNF and at-most-s-term monotone DNF each have average teaching dimension O(ns). The proofs use detailed analyses of the combinatorial structure of “most” DNF formulas and monotone DNF formulas. We also establish asymptotic separations between the worst-case and average teaching dimension for various other interesting Boolean concept classes such as juntas and sparse GF ₂ polynomials.     

一种基于信息粒度的动态属性约简求解算法

动态属性约简是粗糙集理论的重要研究内容之一.针对动态决策表构造了一种基于信息粒度的动态属性约简模型,详细分析了决策表中出现新属性动态增加时信息粒度的增量式计算方法;在此基础上,以信息粒度作为启发信息,设计了一种动态属性约简求解算法,该算法能有效利用原决策表的属性约简结果和信息粒度来降低算法的计算复杂度,并使得约简结果具有较好传承性;最后通过算例分析和实验比较进一步验证了本算法的可行性和有效性.     

On Learning Visual Concepts and DNF Formulae

We consider the problem of learning DNF formulae in the mistake-bound and the PAC models. We develop a new approach, which is called polynomial explainability, that is shown to be useful for learning some new subclasses of DNF (and CNF) formulae that were not known to be learnable before. Unlike previous learnability results for DNF (and CNF) formulae, these subclasses are not limited in the number of terms or in the number of variables per term; yet, they contain the subclasses of k-DNF and k-term-DNF (and the corresponding classes of CNF) as special cases. We apply our DNF results to the problem of learning visual concepts and obtain learning algorithms for several natural subclasses of visual concepts that appear to have no natural boolean counterpart. On the other hand, we show that learning some other natural subclasses of visual concepts is as hard as learning the class of all DNF formulae. We also consider the robustness of these results under various types of noise.An earlier version of this paper appeared in the Proceedings of the Sixth Annual ACM Workshop on Computational Learning Theory, COLT93.Current address: Department of Computer Science, Technion, Israel. e-mail:eyalk@cs.technion.ac.il