商空间研究进展

2022-09-12

自从粒度的概念首次由Zadeh[1]提出以来, 国内外研究人员对粒计算理论和模型进行了深入的研究, 有力地推动了粒度计算理论的发展。1990年, 张铃等[3]从人工智能角度的研究角度出发, 提出了问题求解的商空间理论。商空间理论[4]用商集概念来表示不同粒度, 不同的粒度层表示不同商空间, 将问题描述为论域为X, 属性为f, 结构T的一个三元组 (X, f, T) 模型。随后的20年时间里, 问题求解的商空间理论进一步发展为一种以商空间理论为基础的粒度计算理论。

一、商空间研究现状

国内张钹院士、张铃教授于1990年提出问题求解的商空间理论。2003年张铃和张钹[5]将模糊概念应用到商空间理论, 提出模糊商空间理论。2012文献中为了求解加入时间变量的问题, 张铃等[7]引入时间变量, 将原有商空间模型 (X, f, T) 扩展成动态商空间模型 (X (t) , f (t) , T (t) ) , 分别讨论结构不变与论和属性不变两种情况。2015年文献[8]建立了基于直觉模糊等价关系的商空间和由直觉模糊等价关系诱导的直觉模糊商空间模型。2016年文献[9,10]引入同余关系, 讨论商空间结构为代数结构时, 全体同余关系构成的完备半序格和保真原理、保假原理的存在性。

商空间理论在很多领域都取得了较好的研究成果。文献[11,12]将商空间理论和覆盖算法相结合, 并改进算法, 应用到数据聚类中, 提高了分类的速度。文献[13,14]将商空间粒度计算理论应用到模糊控制系统中, 通过不断调整粒度来获得理想的控制性能。总而言之, 商空间理论是人工智能领域的一个研究方向, 基于商空间理论的发展和应用仍然值得继续研究和探讨。

二、商空间理论基础

(一) 基本模型

定义2.1 (问题描述) 以三元组 (X, f, T) 描述一个问题, 其中X表示问题的论域 (universe) , f (·) 表示论域的属性, f (·) 称属性函数。T是论域的结构, 指论域X中各元素的相互关系。

(二) 基本操作

(1) 粒化。粒化问题可以从三个角度来考虑:一是直接论域X进行颗粒化;二是对属性f取不同的粒度;三是对结构去不同粒度。

(2) 商逼近。定义2.3 (商空间逼近) 给定系统 (X, f, T) , 其中f为系统的性能 (属性) 。若存在一个空商间序列[X]1, [X]2, ...[X]n, ....当[X]i (按某种意义) 趋近X时, 性能[f]i也能趋近于f, 则称性能f是商空间逼近的, 称上述问题为商空间逼近 (商逼近) 。

(三) 基本原理

定理2.1 (保假原理) 若问题[A][B]在 ([X], [f], [T]) 上无解, 则问题AB在 (X, f, T) 上也一定无解。也可叙述为, 若问题AB在 (X, f, T) 上有解, 则问题[A][B]在商空间 ([X], [f], [T]) 上也一定有解。

定理2.2 (保真原理1) 若问题[A][B]在 ([X], [f], [T]) 上有解, 而且对于任一[X], p-1[X]) 在X上是连通集, 则问题[A][B]在商空间 (X, f, T) 上也一定有解。

定理2.3 (保真原理2) 设 (X, f, T) , (X, f, T) 是 (X, f, T) 的两个商空间, 而且Ti (i=1, 2) 是半序。令 (X3, f3, T3) 是 (X1, f1, T1) 、 (X2, f2, T2) 的上确界空间 (指X3是X1, X2的上确界, T3是T1, T2的上确界) 。若问题A1→B1、A2→B2在 (X1, f1, T1) , (X2, f2, T2) 中有解, 则对应的问题A3→B3在 (X3, f3, T3) 上也有解 (其中A3=A1A2, B3=B1B2) 。

三、商空间理论发展

(一) 模糊商空间理论

张铃等[5]给出了模糊商空间理论的基本性质 (两个定理) 。

定义3.1 X×X表示X与X的积空间, T (X×X) 表示积空间上一切模糊子集的集合。

1. 设R∈T (X×X) , 若满足

则称R是X上的一个模糊等价关系。

定义3.2 (归一化等腰距离) 设归一化距离空间 (X, d) (所谓归一化, 即?a, b∈[X], 有d (a, b) ≤1) , 若X中任取3点构成的三角形均为等腰三角形, 且腰是大边, 则称其为等腰距离.

定理3.1设[X]是X的商空间, 在[X]上给定一个归一化等腰距离函数d (·, ·) , 令?x, y∈X, R (x, y) =1?d (x, y) , 则R (x, y) 是X上的一个模糊等价关系.

定理3.2设{X (λ) |0≤λ≤1}是X上的一个分层递阶结构, 则存在X上的一个模糊等价关系R, 其截关系为Rλ, Rλ对应的商空间为X (λ) , λ∈[0, 1].

定义3.3 (分层递阶结构) 对0≤λ≤1, Rλ为X上的等价关系, 对应的商空间为记为X (λ) , 如果商空间簇{X (λ) 0≤λ≤1}按商集的包含关系构成一个有序链, 则称{X (λ) 0≤λ≤1}构成对论域X的一个分层递阶结构.

2. 定理3.4下面断言是等价的

(1) 给定论域X上的一个模糊等价关系;

(2) 给定X的商空间上的一个归一化等腰距离;

(3) 给定X的一个分层递阶结构;

(4) 给定一个X的模糊知识基。

(二) 动态商空间模型

为解决动态环境下的问题求解, 在原有的商空间模型 (X, f, T) 的基础上, 引入[7]时间变量, 将它扩展成动态商空间模型 (X (t) , f (t) , T (t) ) 。然后, 分两种情况进行讨论: (1) 当结构T不变时, 即 (X (t) , f (t) , T) , 通过对论域增加时间维的方法, 将动态的商空间模型又转换成高维的静态模型, 于是能利用静态商空间模型的特性; (2) 当论域与属性不变时, 即 (X, f, T (t) ) , 研究在这种情况下构成商空间链的充分必要条件, 建立相应的商逼近原理, 并讨论其基本性质.

(三) 基于代数结构的商空间理论

目前的商空间模型中论域结构通常被指定为拓扑结构, 问题的粒度由等价关系唯一地确定.当论域结构由拓扑结构变成应用广泛的代数结构时, 引入[9,10,11,12,13,14,15,16]同余关系的概念, 系统地论证全体同余关系构成的完备半序格和保假, 保真原理的存在性.而当等价关系不是同余关系时, 对偶地定义了上 (下) 同余与上 (下) 商, 并证明了它们的存在性并得出了一些重要性质, 为商空间的合成与分解提供了理论依据.

四、商空间理论的应用

(一) 机器学习

文献[18]2007在商空间模型下, 研究了从样本集的选择和学习顺序、隐含层神经元数的降低、泛化能力和识别精度的提高等方面对覆盖算法进行了改进, 从而降低识别的维数, 减少运算复杂度。文献[11]2008将商空间理论和覆盖算法结合起来应用到高维大规模数据库的数据聚类中, 实验结果表明算法性能好, 实用性强。

(二) 模糊控制

2004文献[13]将商空间的粒度计算理论应用到模糊控制系统中, 通过系统控制粒度的不断改变, 采用粗粒度粗调、细粒度细调的方法, 最终获得理想的控制性能。

(三) 数据挖掘

文献[17]将商空间理论与形式概念分析理论相结合来解决到图像数据挖掘问题, 使用商空间粒度计算理论来描述图像数据挖掘的不同的粒度世界, 建立图像数据挖掘的形式化分析体系, 从而挖掘出图像数据中隐含的潜在有用的规律性的知识。

五、总结与展望

(一) 理论

自身发展: (1) 在利用商空间理论求解复杂问题时, 如何将问题空间粒化和如何确定粒化的程度是关键。粒度过粗容易丢失重要的信息, 粒度过细容易导致信息的冗余以增加问题求解的复杂度。因此, 寻找最优粒化程度和判断最优粒化程度的标准是非常值得研究的。 (2) 商空间理论和其他理论的结合:例如将商空间理论与粗糙集方法相结合。

(二) 应用推广

目前商空间理论已经在启发式搜索、路径规划, 数据挖掘方面, 复杂问题求解, 网络路径分析已取得成果。下面两个方面值得继续探讨, 大数据分析:通过粒计算技术建立商空间模型, 将数据信息分成不同的粒层, 从而解决了大数据的“多样性”和“分布式”问题。社交网络分析:通过分析社交网络数据, 建立商空间粒计算模型, 从而挖掘出有价值的信息。总而言之, 商空间理论在大数据的驱动下将有广泛的应用前景。

摘要：粒计算是当人工智能领域中的一个热门研究方向。商空间理论是粒计算的重要方法之一。本文首先回顾了商空间理论的研究现状, 其次介绍了商空间理论基础及基本模型、操作和原理, 然后从模糊商空间理论、模糊λ商空间理论、动态商空间模型和基于代数结构的商空间理论四个方面对其发展过程进行了扩充, 最后探讨了商空间理论在机器学习、模糊控制、数据挖掘领域中的应用。

关键词：粒计算,人工智能,商空间

参考文献

[1] ZADEH L A.Toward a theory of fuzzy information granulation its centrality in human reasoning and fuzzy logic[J].Fuzzy sets and systems, 1997, 90 (2) :111-127.

[2] Yao Y.Perspectives of granular computing[J].Gr C, 2005 (5) :85-90.

[3] Zhang Bo, Zhang Ling.Theory and Application of Problem Solving.Beijing:Tsinghua University Press, 1990 (in Chinese) (张钹, 张铃.问题求解的理论及应用[M].北京:清华大学出版社, 1990.90-102.

[4] Zhao L Q, Zhang L.Advances in the quotient space theory and its applications[C]//International Conference on Rough Sets and Knowledge Technology.Springer, Berlin, Heidelberg, 2006:363-370.

[5] 张铃, 张钹.模糊商空间理论 (模糊粒度计算方法) [J].软件学报, 2003, 14 (4) :770-776.

[6] 王加阳, 彭岚琳.模糊λ商空间研究[J].计算机工程与应用, 2009, 45 (6) :63-65.

[7] 张铃, 张钹.动态商空间模型及其基本性质[J].模式识别与人工智能, 2012, 25 (2) :181-185.

[8] 秦华妮.直觉模糊集的商空间[J].计算机工程与应用, 2015, 51 (2) :21-25.

[9] 陈林书, 王加阳, 杨正华, 李力.基于代数结构的商空间模型研究[J].电子学报, 2016, 44 (4) :952-958.

[10] Chen L S, Wang J Y, Li L.Quotient space model based on algebraic structure[J].High Technology Letters, 2016 (2) :160-169.

[11] 严莉莉, 张燕平, 胡必云.基于商空间粒度的覆盖聚类算法[J].计算机应用研究, 2008, 25 (1) :47-49.

[12] 赵晓敏.基于商空间的聚类方法研究及其在CRM中的应用[D].河北:华北电力大学, 2009.

[13] 张持健, 李旸, 张铃.商空间理论 (粒度计算方法) 实现高精度模糊控制[J].计算机工程与应用, 2004, 40 (11) :37-39.

[14] 张世杰.基于商空间理论的模糊PID控制的研究[D].太原:太原理工大学, 2014.

[15] 刘仁金, 黄贤武.图像分割的商空间粒度原理[J].计算机学报, 2005, 28 (10) :1680-1685.

[16] 张向荣, 谭山, 焦李成.基于商空间粒度计算的SAR图像分类[J].计算机学报, 2007, 30 (3) :483-490.