基于二进制区分矩阵的约简算法研究

给出了一种基于二进制区分矩阵的约简方法.首先基于粗糙集理论定义了二进制区分矩阵及运算规则、基于二进制区分矩阵的最小约简的判别及属性重要性的计算方法.在定义的基础上,给出了基于二进制区分矩阵的求核算法、相对属性约简算法及值约简算法.该约简方法以位操作为主与传统的约简方法比较不包括复杂的逻辑化简和集合运算,在一定程度上简化了计算,提高了约简效率.将该算法应用于数字电路设计的开关电路综合中,得到最简数字电路的逻辑表达,从而说明了算法的有效性.     

粒的位表示及其在属性约简中的应用

粒计算是一种新的软计算思想,它涵盖了所有和粒度相关的理论、方法和技术.提出了一种信息粒的位表示方法,从而将繁琐的集合运算转化为更适于计算机运算的二进制数的逻辑运算,并基于此提出了一种新的属性约简算法.实验结果表明,该算法在时间上较当前的其它同类算法具有更高的效率.     

基于粒计算的Rough集模型

上近似、下近似是Rough集的基本定义,它使我们能够用精确的集合讨论不精确的概念,Rough集利用可计算的边界域实现了G.Frege的边界思想.然而,Rough集本身的代数定义和其他各种扩展模型并没有提供简单直观的计算边界元素数目的算法.在二进制粒计算的基础上,通过定义粒矩阵和粒矩阵运算,建立了基于粒计算的知识表示方法和基于粒计算的Rough集模型,据此可以获得Rough集基本概念的粒矩阵表示和粒矩阵快速计算方法,为建立基于粒计算的知识发现算法提供了理论基础.举例证明了Rough包含与Rough相等的隶属度函数定义并非充要条件.同时给出了基于粒计算的Rough包含与Rough相等的充要条件.     

Rough集理论中知识与运算的矩阵表示

同一问题在不同知识表示下算法难度不同。Rough集理论把知识定义为对对象的分类能力,并提供了一套基于代数系统的知识表达和处理方法。然而在代数表示下,知识的本质以及运算直观性较差,不易于理解。同济大学苗夺谦教授建立了知识与信息之间的关系,在此基础上给出了Rough集理论中概念和运算的信息表示,并给出了知识约简在代数和信息两种表示下的等价性证明。现进一步将知识及其运算表示成粒矩阵形式,继而给出了知识约简在代数、信息和粒矩阵3种表示下的等价性证明。     

基于二进制粒子群优化的一个最小属性约简算法

研究基于二进制粒子群优化算法思想求解决策表最小属性约简问题的方法.定义适当的适应值函数,将决策表最小属性约简问题转化为一个适合二进制粒子群优化算法求解的0-1组合优化问题,证明问题解的等价性.在此基础上,引入种子粒子概念及其自适应保护策略,提出一个改进的二进制粒子群算法,取得良好的效果.实验结果说明该算法的有效性.     

一种邻域粒K均值聚类方法

K均值聚类,对于非凸、稀疏及模糊的非线性可分数据,其聚类效果不佳.针对此问题,通过引入粒计算理论,采用邻域粒化技术,提出一种邻域粒K均值聚类方法.样本在单特征上使用邻域粒化技术构造邻域粒子,在多特征上使用邻域粒化技术形成邻域粒向量;通过定义邻域粒与邻域粒向量的大小、度量和运算规则,提出两种邻域粒距离度量,并对所提出的邻域粒距离度量进行公理化证明.采用多个UCI数据集进行实验,将K均值聚类算法分别结合两种邻域粒距离度量,在邻域参数和距离度量两个方面与经典聚类算法进行比较,结果验证了所提出的邻域粒K均值聚类方法的可行性和有效性.     

垂直划分二进制可分辨矩阵的属性约简

针对二进制可分辨矩阵属性约简方法在处理大数据集时的不足,首先给出两种二进制可分辨矩阵属性约简的定义,并证明这两个属性约简定义与正区域的属性约简定义是等价的;然后,给出对二进制可分辨矩阵按条件属性垂直划分后进行属性约简的方法;为了进一步降低空间开销,提出将垂直分解的二进制可分辨矩阵存于外部介质中,在约简过程中,仅将所需部分调入内存,由此设计启发式属性约简算法,其时间和空间复杂度的上界分别为 (∣ ∣∣ ∣2)和 (∣ ∣2);最后,理论分析和实验结果验证了该算法的正确性和高效性.     

一种高效的基于相似性查找时间序列的位符号化表示方法*

到目前为止能够计算字符化时间序列的距离度量的方法很少,为此,提出了一种新的字符化的时间序列表示方法BSAP。该方法既能进行维度约简又允许在符号化后的时间序列表示法上定义距离度量。实验分别在合成数据和实际数据上进行,实验表明该方法具有更高的运算效率且需要较少的空间。     

基于模糊邻域粗糙集的启发式属性约简算法

属性约简是机器学习等领域中常用的数据预处理方法。在基于粗糙集理论的属性约简算法中,大多是根据单一的方法来度量属性重要度。为了从多角度对属性达到更为优越的评估效果,首先在已有的模糊邻域粗糙集模型中定义属性依赖度度量,然后根据粒计算理论中知识粒度的概念,在模糊邻域粗糙集模型下提出了模糊邻域粒度度量。由于属性依赖度和知识粒度代表了不同视角的属性评估方法,因此将这两种方法结合起来用于信息系统的属性重要度评估,最后给出一种启发式属性约简算法。实验结果表明,所提出的算法具有较好的属性约简性能。     

基于粒计算的决策树并行算法的应用

针对传统的决策树分类算法不能有效解决海量数据挖掘的问题,结合并行处理模型M apReduce ,研究基于粒计算的ID3决策树分类的并行化处理方法。基于信息粒的二进制表示来构建属性的二进制信息粒向量,给出数据集的二进制信息粒关联矩阵表示;基于二进制信息粒关联矩阵,提出属性的信息增益的计算方法,设计基于M apReduce的粒计算决策树并行分类算法。通过使用标准数据集和实际气象领域的雷电真实数据集进行测试,验证了该算法的有效性。     

基于二进制信息粒的数据挖掘算法研究

本文利用二进制数来表示基于粗糙集思想的信息粒的概念,定义了基于上述信息粒的一些粒计算的基本定义.并且提出了两个典型的基于粒计算的数据挖掘算法,即基于二进制信息粒的属性重要度算法和决策树算法.最后实验和分析验证了研究的有效性.     

粒计算下的粗糙集模型比较*

提出了几种组合粒下的粗糙集模型,并将其与单一粒下的粗糙集进行了比较,同时与粒逻辑运算下的粗糙集模型进行了比对,创造性地得到了组合粒、单一粒以及粒逻辑运算下的粗糙集模型之间的关系。结果表明,组合粒与粒逻辑运算组成了一个链结构,这为研究基于信息粒的知识获取以及动态粒的推理奠定了基础。     

基于宽度优先搜索的K-medoids聚类算法

针对传统K-medoids聚类算法对初始值敏感、中心点随机选择以及聚类精度不够高等缺点,在粒计算有效初始化的基础上,提出中心点宽度优先搜索策略. 首先,利用粒计算初始化获取K个有效粒子,遴选该K个粒子所对应的K个中心点作为K个初始中心点;然后,根据对象间的相似性分别对K个粒子中的对象建立以中心点为根节点的相似对象二叉树,通过宽度优先搜索遍历二叉树迭代出最优中心点, 同时采用簇间距离和簇内距离优化准则函数. 实验结果表明,所提算法在UCI中Iris和Wine标准数据集中测试,在有效缩短迭代次数的同时保证了算法聚类准确率.     

决策表的粒计算方法研究

粒计算是一种基于问题概念空间划分的智能计算方法。在基于粗集理论的粒度模型基础上,给出了决策表的粒空间分解方法,并给出了决策表在粒表示下属性必要性和属性约简的判定条件。最后,比较了粒度模型和传统的粗集理论在处理属性约简问题上的差异。     

Dynamic computing rough approximations approach to time-evolving information granule interval-valued ordered information system

With the advent of Big Data era has seen both the volumes and update rates of data increase rapidly. The granular structure of an information system is evolving with time when redundancy data leaves and new data arrives. In order to quickly achieve the rough approximations of dynamic attribute set interval-valued ordered information system that the attribute set varies over time. In this study, we proposed two dynamic computing rough approximations approaches for time-evolving information granule interval-valued ordered information system which induced by the deletion or addition some attributes, respectively. The updating mechanisms enable obtaining additional knowledge from the varied data without forgetting the prior knowledge. According to these established computing rules, two corresponding dynamic computing algorithms are designed and some examples are illustrated to explain updating principles and show computing process. Furthermore, a series of experiments were conducted to evaluate the computational efficiency of the studied updating mechanisms based on several UCI datasets. The experimental results clearly indicate that these methods significantly outperform the traditional approaches with a dramatic reduction in the computational efficiency to update the rough approximations.     

基于云计算的层次粗糙集模型约简算法研究

传统的并行属性约简算法通过利用抽样技术获取小数据样本进行知识约简,但对于大数据集来说,样本数据不具有一般性且无法代表整个数据集.为了弥补传统并行属性约简算法只能用来计算最小属性约简、处理小数据集的缺陷,论文通过分析了先验知识在粒计算中的重要性,结合云计算技术处理海量数据的优势,以粗糙集理论为背景,从不同角度、层次出发建立层次粗糙集模型,提出基于云计算的层次粗糙集模型约简算法,讨论并实现了知识约简算法中的可并行化操作,利用Hadoop在普通计算机集群上进行试验,从运行时间、加速比、可扩展性三个方面对所提出基于正区域、信息熵、边界域算法的重要性进行评价.实验证明：基于云计算的层次粗糙集模型约简算法可以有效处理大数据集.     

基于最大粒的规则获取算法

粒计算是模拟人类思维和解决复杂问题的方法,它是复杂问题求解、海量数据挖掘、模糊信息处理的有效工具.文中首先分析并指出传统的规则获取方法存在的某些弊端,并从粒计算的角度分析属性约简的粒度原理,指出属性约简过程的本质是寻找决策划分空间的一个极大近似划分空间,而在极大近似划分空间上提取的规则可能不是最简规则.为此,提出一种基于最大粒的规则获取算法,该算法根据条件属性对论域形成的分层递阶的划分空间,自顶向下逐渐提取最大粒对应的规则.仿真实验表明该算法提高粗糙集的泛化能力.     

Generalized rough sets based on relations

Rough set theory has been proposed by Pawlak as a tool for dealing with the vagueness and granularity in information systems. The core concepts of classical rough sets are lower and upper approximations based on equivalence relations. This paper studies arbitrary binary relation based generalized rough sets. In this setting, a binary relation can generate a lower approximation operation and an upper approximation operation, but some of common properties of classical lower and upper approximation operations are no longer satisfied. We investigate conditions for a relation under which these properties hold for the relation based lower and upper approximation operations.This paper also explores the relationships between the lower or the upper approximation operation generated by the intersection of two binary relations and those generated by these two binary relations, respectively. Through these relationships, we prove that two different binary relations will certainly generate two different lower approximation operations and two different upper approximation operations.     

Particle swarm optimization for bitmap join indexes selection problem in data warehouses

Data warehouses are very large databases usually designed using the star schema. Queries defined on data warehouses are generally complex due to join operations involved. The performance of star schema queries in data warehouses is highly critical and its optimization is hard in general. Several query performance optimization methods exist, such as indexes and table partitioning. In this paper, we propose a new approach based on binary particle swarm optimization for solving the bitmap join index selection problem in data warehouses. This approach selects the optimal set of bitmap join indexes based on a mathematical cost model. Several experiments are performed to demonstrate the effectiveness of the proposed method on the bitmap join index selection problem. Further testing of the method is performed using a database environment specific cost function. The binary particle swarm optimization is found to be more effective than both the genetic algorithm and data mining based approaches.