第15卷第3期 智能系统学报 Vol.15 No.3 2020年5月 CAAI Transactions on Intelligent Systems May 2020 D0:10.1992tis.201903031 因素空间理论下基点分类算法研究 蒲凌杰2，曾繁慧2，汪培庄2 (1.辽宁工程技术大学理学院，辽宁阜新123000；2.辽宁工程技术大学智能工程与数学研究院，辽宁阜新 123000) 摘要：目前.基于因素空间理论的背景基提取算法计算过程复杂，初始化必须依赖各因素极值，基点数量提取 冗余等原因，未能在应用中取得很好效果。为此，结合内点判别法和知识可继承、可扩展的思想，提出一种计 算简单、初始化独立、基点数量小的改进的背景基提取算法。然后，利用改进的背景基提取算法构造出一种全 新的数据分类算法一基点分类算法，基点分类算法以提取每一类样本的背景基为预测模型，再通过新定义 的-背景基，优化预测模型。数值实验表明：基点分类算法原理简单、构造难度小、分类模型泛化能力强，预测 能力准确率高，同时严格的模型限定区域又能为识别新类别提供新方法。 关键词：因素空间：背景基：背景基提取；-背景基：基点分类算法：识别新类别：数据分类：背景分布：背景关系 中图分类号：TP18文献标志码：A 文章编号：1673-4785(2020)03-0528-09 中文引用格式：蒲凌杰，曾繁慧，汪培庄.因素空间理论下基点分类算法研究.智能系统学报，2020,15(3)：528-536. 英文引用格式：PU Lingjic,,ZENG Fanhui,WANG Peizhuang.Base point classification algorithm based on factor space theory, CAAI transactions on intelligent systems,2020,15(3):528-536. Base point classification algorithm based on factor space theory PU Lingjie2,ZENG Fanhui2,WANG Peizhuang2 (1.College of Science,Liaoning Technical University,Fuxin 123000,China;2.College of Intelligent Engineering and Mathematics, Liaoning Technical University,Fuxin 123000,China) Abstract:At present,the background-based extraction algorithm based on factor space theory has not achieved good results when used in applications.Reasons for its inefficiency are the calculation process is complicated,initialization depends on the extreme values of each factor,and redundancy of the number of base points extracted.Therefore,com- bining the inner point judgment method and a novel idea,an improved background-based extraction algorithm with simple calculation,independent initialization,and a few number of base points is proposed.Using the improved back- ground-based extraction algorithm,a new data classification algorithm,i.e.,base point classification algorithm,is con- structed.The algorithm extracts the background base of each type of sample as the prediction model and optimizes the prediction model through the newly defined A-background base.Finally,numerical experiments show that the base point classification algorithm is simple in principle,easy in construction,strong in generalizing the ability of classification model,and high in accuracy of prediction ability.Moreover,strict-utility model can provide new methods for identify- ing new classes Keywords:factor space;background base;background base extraction;-background base;base point classification al- gorithm;identify new classes;data classification;background distribution;background relationship 机制主义人工智能理论框架包括：机制主义论。因素空间理论是机制主义人工智能的数学 人工智能理论、泛逻辑学理论)和因素空间理 基础。背景基理论是因素空间理论框架下的一个 收稿日期：2019-03-23 重要分支。因素空间理论是现有人工智能数学理 基金项目：国家自然科学基金委主任基金项目(61350003)辽 论的进一步提升，该理论从形成事物的本质出 宁省教育厅科学技术研究经费项目(LJ2019L019). 通信作者：蒲凌杰.E-mail:1901676469@qq.com. 发，以构成事物的“基因”为维度，形成一个描述
DOI: 10.11992/tis.201903031 因素空间理论下基点分类算法研究 蒲凌杰1,2，曾繁慧1,2，汪培庄1,2 （1. 辽宁工程技术大学 理学院，辽宁 阜新 123000; 2. 辽宁工程技术大学 智能工程与数学研究院，辽宁 阜新 123000） 摘 要：目前，基于因素空间理论的背景基提取算法计算过程复杂，初始化必须依赖各因素极值，基点数量提取 冗余等原因，未能在应用中取得很好效果。为此，结合内点判别法和知识可继承、可扩展的思想，提出一种计 算简单、初始化独立、基点数量小的改进的背景基提取算法。然后，利用改进的背景基提取算法构造出一种全 新的数据分类算法−基点分类算法，基点分类算法以提取每一类样本的背景基为预测模型，再通过新定义 的 λ-背景基，优化预测模型。数值实验表明：基点分类算法原理简单、构造难度小、分类模型泛化能力强，预测 能力准确率高，同时严格的模型限定区域又能为识别新类别提供新方法。 关键词：因素空间；背景基；背景基提取；λ-背景基；基点分类算法；识别新类别；数据分类；背景分布；背景关系 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2020)03−0528−09 中文引用格式：蒲凌杰, 曾繁慧, 汪培庄. 因素空间理论下基点分类算法研究 [J]. 智能系统学报, 2020, 15(3): 528–536. 英文引用格式：PU Lingjie, ZENG Fanhui, WANG Peizhuang. Base point classification algorithm based on factor space theory[J]. CAAI transactions on intelligent systems, 2020, 15(3): 528–536. Base point classification algorithm based on factor space theory PU Lingjie1,2 ，ZENG Fanhui1,2 ，WANG Peizhuang1,2 (1. College of Science, Liaoning Technical University, Fuxin 123000, China; 2. College of Intelligent Engineering and Mathematics, Liaoning Technical University, Fuxin 123000, China) Abstract: At present, the background-based extraction algorithm based on factor space theory has not achieved good results when used in applications. Reasons for its inefficiency are the calculation process is complicated, initialization depends on the extreme values of each factor, and redundancy of the number of base points extracted. Therefore, combining the inner point judgment method and a novel idea, an improved background-based extraction algorithm with simple calculation, independent initialization, and a few number of base points is proposed. Using the improved background-based extraction algorithm, a new data classification algorithm, i.e., base point classification algorithm, is constructed. The algorithm extracts the background base of each type of sample as the prediction model and optimizes the prediction model through the newly defined λ-background base. Finally, numerical experiments show that the base point classification algorithm is simple in principle, easy in construction, strong in generalizing the ability of classification model, and high in accuracy of prediction ability. Moreover, strict-utility model can provide new methods for identifying new classes. Keywords: factor space; background base; background base extraction; λ-background base; base point classification algorithm; identify new classes; data classification; background distribution; background relationship 机制主义人工智能理论框架包括：机制主义 人工智能理论[1] 、泛逻辑学理论[2] 和因素空间理 论 [3]。因素空间理论是机制主义人工智能的数学 基础。背景基理论是因素空间理论框架下的一个 重要分支。因素空间理论是现有人工智能数学理 论的进一步提升，该理论从形成事物的本质出 发，以构成事物的“基因”为维度，形成一个描述 收稿日期：2019−03−23. 基金项目：国家自然科学基金委主任基金项目 (61350003)；辽 宁省教育厅科学技术研究经费项目 (LJ2019JL019). 通信作者：蒲凌杰. E-mail：1901676469@qq.com. 第 15 卷第 3 期 智 能 系 统 学 报 Vol.15 No.3 2020 年 5 月 CAAI Transactions on Intelligent Systems May 2020
第3期 蒲凌杰，等：因素空间理论下基点分类算法研究 ·529· 事物的“基因空间”。基因最早的英文名称是 U→X(F),其性状空间是 Factor,因素就是广义的基因，所以用“因素空间 X(F)=X(f)×…×X(f) (1) 描述事物更具有普适价值。背景分布是因素空间 理论下的一个重要概念。2013年，汪培庄在讨 记为F=fUUf。式(1)的含义是：合成 论因素空间与因素库的关系时提出背景分布概 因素F的性状空间X(F)被定义成一个笛卡尔乘 念。2014一2015年，汪培庄6-1在因素空间与数 积X(f)×…×X(f). 据科学一文中讨论了数据科学与因素背景关系的 定义3因素空间。记Xr=(X(F)Fr~w,称 深刻联系。“背景分布-背景关系-背景基”模型是 Φ=(U,X)为U上的一个因素空间。 人对客观事物从观察到认识事物，再到知识形成的过 记Xx=X(f)×X()X…×X(f)称为最大性状 程。背景基的提出就是为了描述因素的背景 空间。对于离散型性状空间而言，任意a=(a, 关系。曲国华等心研究了背景分布与模糊背景 a2,…,an)∈X称为一个性状颗粒。 之间的关系。与此同时，汪培庄提出了一种构造 因素空间定义的更多解释，可参考文献[3]中 背景基的判别方法：内点判别法。该算法简单、 第1章的相关内容。 高效，可以近似描述背景关系。吕金辉等2] 定义4背景关系。给定U上的定性因素空 为了弥补该算法的近似性，给出了完整的夹角判 间中=(U,Xr),对任意相a=(a,a2,…,an)∈X,记 别定理，使得内点判别法成为一种精确的算法， 其在U上的原相为 但该方法计算较复杂，且在高维空间中提取的基 [a]=F-(a)=uEU F(u)=a) (2) 点较冗余。此外，目前大数据计算复杂性理论仍 然需要时间突破。跳出时间复杂度成指数增长 [a可能是空集，若[a侧≠O,则称a是一个实 性状颗粒，否则称a是一个虚组态。全体实性状 的约束仍是专家学者们继续研究的热点。针对以 上问题，提出了一种基于背景基的数据分类算 集合记为 法：基点分类算法。该算法可以模仿人类认识事 R=F(U)={a=(a1,a2,·,an)∈X日u∈U 物的过程，把人类学习到的知识用背景基刻画， (3) fi()=a1,f(u)=a2,…,fn(u)=an}, 不同的背景基容纳不同知识体，最终实现知识的 R称为因素，，…，n之间的背景关系，也称为因 分类与预测。从机制主义人工智能理论的角度来 素F的背景集。 看，该算法不但有监督学习和预测的能力，而且 在遇到全新知识时，有自我判断和自我分类的能 机器学习中a可以视为一条样本，[表示 力，所以说，该算法从原理上可以认为是具有一 a的对应标签。如果一个a有对应标签，则a是 定的智能生长能力。本文提出可继承可扩展的 有意义的，即a是一个实性状颗粒，否则a是没有 意义的，称a是一个虚组态。背景关系可以理解 改进的背景基提取算法(improved background-base extraction,IBBE),设计基点分类算法，通过定义- 为：所有有意义的样本构成的集合S与样本的标 签之间的因果关系。若要深入讨论集合S的分布 背景基优化预测模型，数值实验验证算法有效性。 问题，则引出定义5。 1 背景基理论基本概念 定义5背景分布。设论域U=(U,A,p)是一 个概率场，Φ=(U,X)是定义在U上的一个因素 因素空间理论中，认为因素是事物的质根，强调 空间，X=(X,B)是最大性状空间上的一个可测结 事物构成的根本。背景基则强调用集合理论表达知识 构。若所有F中的f都是可测映射，记p=pF 定义1一类事物的集合称为论域，用U表示。 为p经过F·在X上所诱导出来的概率，亦即对任 定义2映射。f:U→X(f)称为一个因素，其 意BeB,都有p(B)=pP(F)(B)。B称为因素F 中X()是∫从事物所映射出来的性状的集合，称 的背景分布。 为f的性状空间。 定义6背景基。若每个性状空间X()都 对于给定论域U上的一组因素f:U→X(f分 是有序集，背景关系R是X中的凸集，记R的所 j=1,2,…,n),称集合F={fi,f2,…,f}为当前论 有顶点所构成的集合为B=B(R)F{PP是R的顶点}， 域U的一个因素集。P(F)为F的幂集，元素个 称作背景基。S表示样本集合，当S=R时，记B的 数为2F1,此处F=n,P(F)的任意元素F:= 所有顶点构成的集合为B(S)={PP是S的顶点}， {f…,fh,其中i=1,2,…,2,{fn…,f}是P(F) 称为样本背景基。 的一个子集合，定义一个U上的合成因素F: 背景基可以生成背景关系，是背景关系的无
λ 事物的“基因空间”。基因最早的英文名称是 Factor，因素就是广义的基因，所以用“因素空间” 描述事物更具有普适价值。背景分布是因素空间 理论下的一个重要概念。2013 年，汪培庄[4] 在讨 论因素空间与因素库的关系时提出背景分布概 念。2014—2015 年，汪培庄[5-6] 在因素空间与数 据科学一文中讨论了数据科学与因素背景关系的 深刻联系。“背景分布−背景关系−背景基”模型是 人对客观事物从观察到认识事物，再到知识形成的过 程 [7-9]。背景基的提出就是为了描述因素的背景 关系。曲国华等[10-11] 研究了背景分布与模糊背景 之间的关系。与此同时，汪培庄提出了一种构造 背景基的判别方法：内点判别法。该算法简单、 高效，可以近似描述背景关系。吕金辉等 [ 1 2 ] 为了弥补该算法的近似性，给出了完整的夹角判 别定理，使得内点判别法成为一种精确的算法， 但该方法计算较复杂，且在高维空间中提取的基 点较冗余。此外，目前大数据计算复杂性理论仍 然需要时间突破[13]。跳出时间复杂度成指数增长 的约束仍是专家学者们继续研究的热点。针对以 上问题，提出了一种基于背景基的数据分类算 法：基点分类算法。该算法可以模仿人类认识事 物的过程，把人类学习到的知识用背景基刻画， 不同的背景基容纳不同知识体，最终实现知识的 分类与预测。从机制主义人工智能理论的角度来 看，该算法不但有监督学习和预测的能力，而且 在遇到全新知识时，有自我判断和自我分类的能 力，所以说，该算法从原理上可以认为是具有一 定的智能生长能力[14]。本文提出可继承可扩展的 改进的背景基提取算法 (improved background-base extraction, IBBE)，设计基点分类算法，通过定义 - 背景基优化预测模型，数值实验验证算法有效性。 1 背景基理论基本概念 因素空间理论中，认为因素是事物的质根，强调 事物构成的根本。背景基则强调用集合理论表达知识 定义 1 一类事物的集合称为论域，用 U 表示。 f : U → X(f) X(f) 定义 2 映射。 称为一个因素，其 中 是 f 从事物所映射出来的性状的集合，称 为 f 的性状空间。 fj : U → X(fj) (j = 1,2,··· ,n) F ∗ = {f1, f2,··· , fn} P(F ∗ ) 2 |F ∗ | |F ∗ | = n P(F ∗ ) Fi = { f(j) ,··· , f(k) } i = 1,2,··· ,2 |F ∗ | { f(j) ,··· , f(k) } P(F ∗ ) Fi : 对于给定论域 U 上的一组因素 ，称集合 为当前论 域 U 的一个因素集。 为 F *的幂集，元素个 数 为 ，此处 ， 的任意元素 ，其中 ， 是 的一个子集合，定义一个 U 上的合成因素 U → X(Fi) ，其性状空间是 X (Fi) = X ( f(j) ) × ··· × X ( f(k) ) (1) Fi = f(j) ∪ ··· ∪ f(k) X(Fi) X(f(j))× ··· × X(f(k)) 记为 。式 (1) 的含义是：合成 因素 Fi 的性状空间 被定义成一个笛卡尔乘 积 。 XF∗ = {X (F)}(F∈P(F∗ )) Φ = (U,XF∗ ) 定义 3 因素空间。 记 ，称 为 U 上的一个因素空间。 Xmax = X(f1)× X(f2)× ··· × X(fn) a = (a1, a2,··· ,an) ∈ X 记 称为最大性状 空间。对于离散型性状空间而言，任意 称为一个性状颗粒。 因素空间定义的更多解释，可参考文献 [3] 中 第 1 章的相关内容。 Φ = (U,XF∗ ) a = (a1,a2,··· ,an) ∈ X 定义 4 背景关系。 给定 U 上的定性因素空 间 ，对任意相 ，记 其在 U 上的原相为 [a] = F −1 (a) = {u ∈ U|F(u) = a} (2) [a] 可能是空集，若 [a] , Ø ，则称 a 是一个实 性状颗粒，否则称 a 是一个虚组态。全体实性状 集合记为 R = F ∗ (U) = {a = (a1,a2,··· ,an) ∈ X|∃u ∈ U f1(u) = a1 , f2(u) = a2 ,··· , fn(u) = an}, (3) R 称为因素 f1, f2,··· , fn 之间的背景关系，也称为因 素 F *的背景集。 机器学习中 a 可以视为一条样本，[a] 表示 a 的对应标签。如果一个 a 有对应标签，则 a 是 有意义的，即 a 是一个实性状颗粒，否则 a 是没有 意义的，称 a 是一个虚组态。背景关系可以理解 为：所有有意义的样本构成的集合 S 与样本的标 签之间的因果关系。若要深入讨论集合 S 的分布 问题，则引出定义 5。 U = (U, A, p) Φ = (U,XF∗ ) X = (X,B) F ∗ fj p = pF∗ F ∗ B ∈ B p(B) = p ( (F ∗ ) −1 (B) ) F ∗ 定义 5 背景分布。设论域 是一 个概率场， 是定义在 U 上的一个因素 空间， 是最大性状空间上的一个可测结 构。若所有 中的 都是可测映射，记 为 p 经过 在 X 上所诱导出来的概率，亦即对任 意 ，都有 。B 称为因素 的背景分布。 X(f 定义 6 背景基。 若每个性状空间 j) 都 是有序集，背景关系 R 是 X 中的凸集，记 R 的所 有顶点所构成的集合为 B=B(R)={P|P 是 R 的顶点}， 称作背景基。S 表示样本集合，当 S=R 时，记 B 的 所有顶点构成的集合为 B(S)={P|P 是 S 的顶点}， 称为样本背景基。 背景基可以生成背景关系，是背景关系的无 第 3 期 蒲凌杰，等：因素空间理论下基点分类算法研究 ·529·
·530· 智能系统学报 第15卷 信息损失的压缩，对因素库的实际应用具有重 新的样本点。它可被删除当且仅当存在一点 要的意义。 QeS,使射线PQ与射线PO形成钝角，亦即 为了更好地说明背景关系、背景分布、背景基 (Q-PO-P)<0。而且，对于任意Q∈SQ1,都有 三者概念之间的联系，以图1为例进行图示说明。 (P-0,0*-0)≤(0*-0,0°-0) 这里，0是0在直线QQ°上的垂足。 内点判别法设S为数据样本集，P是S的 一个内点当且仅当在S中存在一点Q,使射线 PQ与射线PO形成钝角，亦即(Q-P,O-P)<0。 夹角判别定理是一种精确求取背景基的方 法，但该方法在计算时较复杂，在高维空间提取 的基点较冗余。为此，在简化计算的同时，减少 背景基点个数，同时保证信息不损失是本章算法 改进的目的。 图1“背景分布-背景关系-背景基”关系 内点判别法计算简单，基点提取率高效，有利 Fig.1 "Background distribution-background rela- 于处理大样本高维度数据。为此，本章采用内点 tionship-background base"relationship 判别法作为改进背景基提取算法的理论基础。 设集合X、Y、R,其中ESX,E,SY,集合R称 2.2改进的背景基提取算法 为背景关系，集合R的“边缘”构成背景基B,p是 给定一组样本集合S={=(,2,…,m)}, 背景分布，视为集合R的概率密度，可以由样本 n表示样本个数，S1表示样本数量，S=m,i= 的相a的频率逼近来实现。背景关系R表示集 1,2,·,m,且m>n。设B为背景基，初始值B=O, 合X和集合Y之间的关联性。这里有 含义表示人对事物的认知初始处于混沌状态，随 E,RE 着对样本的学习，B0,表示人对事物开始有了一 可得逻辑推理： 定的判断力，随着样本量的增加，B的泛化能力越 Ex→R,(R表示→) 来越强，当样本足够充分时，就会形成对特定事 因此可以认为，背景关系R保证了X与Y的 物的认知包，一个认知包就是一个知识，或者一 因果关系，背景基则限定了背景关系区域，背景 个概念。 分布表示了因果关系的概率。 改进的背景基提取算法就是在模仿人学习过 程同时提取知识轮廓，保存学到的知识。下面给 2改进的背景基提取算法 出改进的背景基提取算法步骤。 集合论的诞生，使得数学与认知实现了潜在 算法改进的背景基提取算法(BBE算法)。 的融合。人类对事物的认知表现可以用数学中的 输入样本S={:=(化1，x2,…,m)川。 集合刻画，集合可以表现概念，认知的逻辑特性 初始化背景基B=O;样本个数S;计数器 被集合论充分地表现出来。因素空间的背景基理 count=-O;0为初始基点个数。 论就是力求用数学刻画人的学习过程。从技术层 1)取S中样本x,若B<0,则x∈B,否则，转 面来讲，目前由夹角判别定理实现的知识归纳算 至2)。 法有背景基提取算法，但是该算法判别条件复 2)计算B的几何中心0： 杂、时间复杂度较大，搜寻到的基点数量太多。 这些导致表达的知识不利于继承和保存。为此， b,∈B 本章对现有算法改进，使其在减少复杂度同时， 更符合人的思维逻辑。 计算内积： 2.1背景基提取原理 (a.Bj)=aB 用技术手段实现背景基的提取，是“背景关 其中：m=0-x,B=bj-x,j=1,2,…,B。 系-背景分布-背景基”从理论到实践的关键。目 若存在B,使得(a,B)<0,那么x,是背景基 前背景基提取主要用到夹角判别定理。 B的内点，舍去，并转至1)；否则x,是B的一个基 夹角判别定理设S是一个样本集。S是 点，即∈B,然后转至3)。 S的一个基点集合，其中心为O。P∈xS是一个 3)在2)中加入x可能会导致一个或多个基
信息损失的压缩，对因素库[4] 的实际应用具有重 要的意义。 为了更好地说明背景关系、背景分布、背景基 三者概念之间的联系，以图 1 为例进行图示说明。 R X Ex Ey Y B 图 1 “背景分布−背景关系−背景基”关系 Fig. 1 “Background distribution-background relationship-background base” relationship 设集合 X、Y、R，其中 Ex ⊆ X,Ey ⊆ Y ，集合 R 称 为背景关系，集合 R 的“边缘”构成背景基 B，p 是 背景分布，视为集合 R 的概率密度，可以由样本 的相 a 的频率逼近来实现。背景关系 R 表示集 合 X 和集合 Y 之间的关联性。这里有 Ex R Ey 可得逻辑推理： Ex → Ry(R表示 →) 因此可以认为，背景关系 R 保证了 X 与 Y 的 因果关系，背景基则限定了背景关系区域，背景 分布表示了因果关系的概率。 2 改进的背景基提取算法 集合论的诞生，使得数学与认知实现了潜在 的融合。人类对事物的认知表现可以用数学中的 集合刻画，集合可以表现概念，认知的逻辑特性 被集合论充分地表现出来。因素空间的背景基理 论就是力求用数学刻画人的学习过程。从技术层 面来讲，目前由夹角判别定理实现的知识归纳算 法有背景基提取算法[12] ，但是该算法判别条件复 杂、时间复杂度较大，搜寻到的基点数量太多。 这些导致表达的知识不利于继承和保存。为此， 本章对现有算法改进，使其在减少复杂度同时， 更符合人的思维逻辑。 2.1 背景基提取原理 用技术手段实现背景基的提取，是“背景关 系−背景分布−背景基”从理论到实践的关键。目 前背景基提取主要用到夹角判别定理。 S ∗ P ∈ X S ∗ 夹角判别定理[12] 设 S 是一个样本集。 是 S 的一个基点集合，其中心为 O。 \ 是一个 Q ∈ S ∗ (Q− P, O− P) < 0 Q ′ ∈ S ∗ {Q} 新的样本点。它可被删除当且仅当存在一点 ，使射 线 PQ 与 射 线 PO 形成钝角，亦即 。而且，对于任意 \ ，都有 (P−O,O ∗ −O) ⩽ (O ∗ −O,O ∗ −O) O 这里， ∗是 O 在直线 QQ’上的垂足。 内点判别法 设 S 为数据样本集，P 是 S 的 一个内点当且仅当在 S 中存在一点 Q，使射线 PQ 与射线 PO 形成钝角，亦即 (Q−P, O−P)<0。 夹角判别定理是一种精确求取背景基的方 法，但该方法在计算时较复杂，在高维空间提取 的基点较冗余。为此，在简化计算的同时，减少 背景基点个数，同时保证信息不损失是本章算法 改进的目的。 内点判别法计算简单，基点提取率高效，有利 于处理大样本高维度数据。为此，本章采用内点 判别法作为改进背景基提取算法的理论基础。 2.2 改进的背景基提取算法 S = {xi = (xi1 , xi2 ,··· , xin)} |S | i = 1,2,··· ,m 给定一组样本集合 ， n 表示样本个数， 表示样本数量， |S|=m， ，且 m>n。设 B 为背景基，初始值 B=Ø， 含义表示人对事物的认知初始处于混沌状态，随 着对样本的学习，B≠Ø，表示人对事物开始有了一 定的判断力，随着样本量的增加，B 的泛化能力越 来越强，当样本足够充分时，就会形成对特定事 物的认知包，一个认知包就是一个知识，或者一 个概念。 改进的背景基提取算法就是在模仿人学习过 程同时提取知识轮廓，保存学到的知识。下面给 出改进的背景基提取算法步骤。 算法 改进的背景基提取算法 (IBBE 算法)。 S = {xi = (xi1 , xi2 输入 样本 ,··· , xin)}。 B = Ø θ 初始化 背景基 ；样本个数|S|；计数器 count=0； 为初始基点个数。 1) 取 S 中样本 xi，若|B|< θ ，则 xi ∈ B ，否则，转 至 2)。 2) 计算 B 的几何中心 o： o = 1 k ∑k j=1 bj , bj ∈ B 计算内积： (α,βj) = αβT j α = o− xi βj = bj − xi 其中： , , j = 1,2,··· ,|B|。 βj (α,βj) < 0 xi ∈ B 若存在 使得 ，那么 xi 是背景基 B 的内点，舍去，并转至 1)；否则 xi 是 B 的一个基 点，即 ，然后转至 3)。 3) 在 2) 中加入 xi 可能会导致一个或多个基 ·530· 智 能 系 统 学 报 第 15 卷
第3期 蒲凌杰，等：因素空间理论下基点分类算法研究 ·531· 点再次变成内点，而内点需要被别除，因此3)功 选代=1： 能是别除B中内点。具体如下： 1)从S中读取一个样本a,count=l,此时 ①取基点b,∈B视为待测点，B中剩余的基 1B=1,B<3,不做任何判断，此时B={a; 点B=Bb视为临时背景基；然后计算B的几何 从S中取样本b,count=-2,此时B=2,lB<3,不 中心o以及内积： 做任何判断，此时B={a,b; (.B)='(B:)T, 从S中取样本c,count=3,此时1B=2,B<3,条 其中：a=0-b,B'=b-b,b∈B。 件不成立，转至2)。 ②若(，B)<0,则继续判断b,是否为极点， 2)先计算B的中心： 即b,=P?或b,=P;?其中 P;=argmax,{blb∈B} bi 2a+b)=(1,2) P,=argminbb∈BU=1,2,…,lBD 如果不是各因素的极点，则标记b,为待删除 再计算内积： 点d:依此类推，检测B中所有基点。 4)若B中存在内点，则删除标记点d标记的 (0-c,-c(0-c(a-c)=(-1,-2)-1,-1)=3>0 基点，得到B,更新B:B←-B';再返回1)读取全 (0-c,b-c=(0-c(b-c)=(-1,-2)(-1,-3)-7>0 部样本后转至5)。 因为上述内积结果都为正，即交成锐角，所以 5)输出背景基B。 认为c是一个基点，即B={a,b,c}。 通常背景基B是由矩阵存储，若样本S有n 3)在2)中B的更新可能产生新的内点，需要 个因素，B的基点个数Bm,则B是一个mm的矩阵： 进一步筛选和剔除： b11b12…b1m ①将B中的a视为内点，B=B\={b,c},按照 b2b22…b2n 2)方法判断，得到a不是B中的内点： ②将B中的b视为内点，B=B\b={a,c},按照 bml bm2…bmn 2)方法判断，得到b不是B中内点：转至4)。 B的每一行表示一个基点。 4)B中没有内点，故B={a,b,c};此时 2.3算例 count=-3<S,则转至1). 图2中，样本集合S包含点=(1,3)、b=(1,1)、 选代=2： c=(2,4)、d(2,3)、e=(4,2)和f=(3,1),利用上述改进 1)从S中取样本d,count=-4,此时1B=3,IB<2, 算法生成样本集合S的背景基B。 条件不成立，转至2)。 2)4)与上述对应步骤相同，此处省略，得到 B={a,b,c,d}。 选代=3： 1)从S中取样本e,count-=5,此时1B=4,lB<2, 条件不成立，转至2)如 2)与上述对应步骤相同，此处省略，得到 B={a,b,c,de}。 h 3)①取B中a为待测点，B=B\={b,c,d,e}, 判断得到a不是B中内点； ②取B中b为待测点，B=B\b={a,c,d,e,判 (0,0) 断得到b不是B中内点； 图2背景基内点判别法 ③取B中c为待测点，B=B\b={a,b,d,e},判 Fig.2 Angle criterion for the inner points of the back- 断得到c不是B中内点； ground base ④取B中d为待测点，B=B\b={a,b,c,e},判 计算步骤如下： 断得到d是B中的内点，再根据极点公式P、P, 输入样本集合S={a,bc,d,e,乃。 判断得到d不是极点，因此标记d点为待删除点d。 初始化背景基B=O:样本个数S=6;计数 4)B中有内点存在，删除标号d1的点，所以 器count=0。 B={a,b,c,e};此时count=-5<S,则转至1)o
点再次变成内点，而内点需要被剔除，因此 3) 功 能是剔除 B 中内点。具体如下： bj ∈ B B ∗ = B bj o ′ ①取基点 视为待测点，B 中剩余的基 点 \ 视为临时背景基；然后计算 B *的几何 中心 以及内积： (α ′ ,βi ′ ) = α ′ (βi ′ ) T , α ′ = o ′ − bj , βi ′ = b ∗ i − bj , b ∗ ∈ B 其中： ∗。 (α ′ ,βi ′ ) < 0 bj bj = Pj + bj = Pj − ②若 ，则继续判断 是否为极点， 即 ？或 ？其中 Pj + = argmaxi{bi j|bi j ∈ B} Pj − = argmini{bi j|bi j ∈ B}(j = 1,2,··· ,|B|) 如果不是各因素的极点，则标记 bi 为待删除 点 di；依此类推，检测 B 中所有基点。 B ′ B ← B ′ 4) 若 B 中存在内点，则删除标记点 di 标记的 基点，得到 ，更新 B： ；再返回 1) 读取全 部样本后转至 5)。 5) 输出背景基 B。 通常背景基 B 是由矩阵存储，若样本 S 有 n 个因素，B 的基点个数|B|=m，则 B 是一个 m×n 的矩阵： Bm×n = b11 b12 ··· b1n b21 b22 ··· b2n . . . . . . . . . bm1 bm2 ··· bmn B 的每一行表示一个基点。 2.3 算例 图 2 中，样本集合 S 包含点 a=(1,3)、b=(1,1)、 c=(2,4)、d=(2,3)、e=(4,2) 和 f=(3,1)，利用上述改进 算法生成样本集合 S 的背景基 B。 a b f d e c (0, 0) 图 2 背景基内点判别法 Fig. 2 Angle criterion for the inner points of the background base 计算步骤如下： 输入 样本集合 S={a, b, c, d, e, f}。 初始化 背景基 B = Ø ；样本个数|S|=6; 计数 器 count=0。 选代 t=1： 1) 从 S 中读取一个样本 a， count=1，此时 |B|=1，|B|<3，不做任何判断，此时 B={a}; 从 S 中取样本 b，count=2，此时|B|=2，|B|<3,不 做任何判断，此时 B={a, b}； 从 S 中取样本 c, count=3，此时|B|=2，|B|<3，条 件不成立，转至 2)。 2) 先计算 B 的中心： o = 1 k ∑k j=1 bj = 1 2 (a+b) = (1,2) 再计算内积： (o−c,a−c)=(o−c)(a−c) T =(−1,−2)(−1, −1)T =3>0 (o−c,b−c)=(o−c)(b−c) T =(−1,−2)(−1, −3)T =7>0 因为上述内积结果都为正，即交成锐角，所以 认为 c 是一个基点，即 B={a, b, c}。 3) 在 2) 中 B 的更新可能产生新的内点，需要 进一步筛选和剔除： ①将 B 中的 a 视为内点，B * =B\a={b,c}，按照 2) 方法判断，得到 a 不是 B *中的内点； ②将 B 中的 b 视为内点，B * =B\b={a,c}，按照 2) 方法判断，得到 b 不是 B *中内点；转至 4)。 4 ) B 中没有内点， 故 B = { a , b , c } ； 此 时 count=3<|S|，则转至 1)。 选代 t=2： 1) 从 S 中取样本 d，count=4，此时|B|=3，|B|<2， 条件不成立，转至 2)。 2)~4) 与上述对应步骤相同，此处省略，得到 B={a, b, c, d}。 选代 t=3： 1) 从 S 中取样本 e，count=5，此时|B|=4，|B|<2， 条件不成立，转至 2)。 2) 与上述对应步骤相同，此处省略，得到 B={a, b, c, d, e}。 3) ①取 B 中 a 为待测点，B * =B\a={b, c, d, e}， 判断得到 a 不是 B *中内点； ②取 B 中 b 为待测点，B * =B\b={a, c, d, e}，判 断得到 b 不是 B *中内点； ③取 B 中 c 为待测点，B * =B\b={a, b, d, e}，判 断得到 c 不是 B *中内点； ④取 B 中 d 为待测点，B * =B\b={a, b, c, e}，判 断得到 d 是 B *中的内点，再根据极点公式 Pj + 、Pj − 判断得到 d 不是极点，因此标记 d 点为待删除点 d1。 4) B 中有内点存在，删除标号 d1 的点，所以 B={a, b, c, e}；此时 count=5<|S|，则转至 1)。 第 3 期 蒲凌杰，等：因素空间理论下基点分类算法研究 ·531·
·532· 智能系统学报 第15卷 选代仁4： 3.1 基本定义 1)从S中取样本∫，count=6,此时1B=4,B<2, BPC算法训练得到的模型相对固定。在实际 条件不成立，转至2)。 中，决策者的主观因素常常扮演重要角色，基于 2)、3)与上述对应步骤相同，此处省略，得到 此，BPC算法在做决策时需要加入决策者主观参 B=fa,b,c,e,fo 数，由主观参数A变换得到的背景基称为入背 4)B中没有内点，故B={a,b,c,e,f乃；此时 景基。 count=-6=S,循环结束。 定义7设集合B:≠O,由c个类别生成的背景 输出背景基B。 基B=B,各类别用i表示，i=1,2,…,c,b,∈B,则有 输出的背景基B是5×2矩阵，为表达上的美 观，采用B的转置表达，即 [B]={biec,j=1,2,…,n, (4) 11243 其中n=[B]l,称[B]:为类别i的背景基。 31421 命题1如果[B]:为类别i的背景基，则B:=[B]o 证明设[B]:为类别i的背景基，i=1,2,…, B的每列代表一个因素，如图3所示，虚线包 c,B为由c个类别生成的背景基，则有 含的区域可以近似视为由样本数据生成的背景分 布，此时背景基为背景分布轮廓的特征点集合。 B=[B] 由上述算例可得背景基在信息压缩、知识表达与 而由定义7得 存储等方面有着独具创新的优势。 B=UB 因此有 B:=[B] 证毕。 定义8设B为c个类别的背景基，[B],为类 别i的背景基，b,∈[B],向量A=(,2,…,), >0,i=1,2,…,c,使得 [B]:=A⑧[B]:=bj=1,2,…,lB]} (5) 则称B=9[Bl:为-背景基。 (0,0) 从几何学角度看，λ-背景基B,是普通背景基 图3样本S背景基和背景分布 B的放大或缩小。当A∈[0，I)时，背景基B锁定 Fig.3 Sample S background base and background distri- 的区域R(B)包含B锁定的区域R(Bu),即 bution R(B)CR(B);当A=1时，满足关系R(B)=R(B):当 结合算法和算例，总结BBE算法的优点： A∈(1，∞)时，R(B)bR(B)。综上所言，对于区域 ①BBE算法极大简化了计算难度和编程难度； R关系满足： ②算法初始化阶段不需要依赖各因素极值： R(B)cR(B),A∈[0,1) ③极大降低了基点数量，有利于高维度数据 R(B)=R(B),A=1 提取基点。 R= R(B)pR(B)A∈[1，o] 3基点分类算法 实现A-背景基具体方法见定义9。 人工智能对数据的分类其实质是对同一类 定义9设O为第i类背景基[B],的重心，其 别的数据形成概念。本文提出的基点分类算法 中m=lB]l,jem,bge[B],则 (base point classification algorithm),简称BPC算 b=0+(0-b) (6) 法，以背景基提取算法为核心。通过对不同类别 样本进行分类打包和学习，最终将给定样本归纳 这里[B=O。 成以各类别为单位的认知包，一个认知包就是一 3.2构造基点分类算法 个概念。 据第2章的IBBE算法和第3.1节中相关定
选代 t=4： 1) 从 S 中取样本 f，count=6，此时|B|=4，|B|<2， 条件不成立，转至 2)。 2)、3) 与上述对应步骤相同，此处省略，得到 B={a, b, c, e, f}。 4) B 中没有内点，故 B={a, b, c, e, f}；此时 count=6=|S|，循环结束。 输出 背景基 B。 输出的背景基 B 是 5×2 矩阵，为表达上的美 观，采用 B 的转置表达，即 B = 1 1 2 4 3 3 1 4 2 1 T B 的每列代表一个因素，如图 3 所示，虚线包 含的区域可以近似视为由样本数据生成的背景分 布，此时背景基为背景分布轮廓的特征点集合。 由上述算例可得背景基在信息压缩、知识表达与 存储等方面有着独具创新的优势。 a b f e c (0, 0) 图 3 样本 S 背景基和背景分布 Fig. 3 Sample S background base and background distribution 结合算法和算例，总结 IBBE 算法的优点： ①IBBE 算法极大简化了计算难度和编程难度； ②算法初始化阶段不需要依赖各因素极值； ③极大降低了基点数量，有利于高维度数据 提取基点。 3 基点分类算法 人工智能对数据的分类其实质是对同一类 别的数据形成概念。本文提出的基点分类算法 (base point classification algorithm)，简称 BPC 算 法，以背景基提取算法为核心。通过对不同类别 样本进行分类打包和学习，最终将给定样本归纳 成以各类别为单位的认知包，一个认知包就是一 个概念。 3.1 基本定义 λ λ BPC 算法训练得到的模型相对固定。在实际 中，决策者的主观因素常常扮演重要角色，基于 此，BPC 算法在做决策时需要加入决策者主观参 数，由主观参数 变换得到的背景基称为 -背 景基。 Bi , Ø B= c ∪ i=1 Bi i = 1,2,··· , c bj ∈ B 定义 7 设集合 ，由 c 个类别生成的背景 基 ，各类别用 i 表示， ， ，则有 [B]i = {b i j |i ∈ c, j = 1,2,··· ,n}, (4) n = |[B]i 其中 | ，称 [B]i 为类别 i 的背景基。 命题1 如果 [B]i为类别i的背景基，则 Bi = [B]i。 [B]i i = 1,2,··· , c 证明 设 为类别 i 的背景基， ，B 为由 c 个类别生成的背景基，则有 B = c ∪ i=1 [B]i 而由定义 7 得 B = c ∪ i=1 Bi 因此有 Bi = [B]i 证毕。 Λ= (λ1, λ2,··· , λc) λi> 0 i = 1,2,··· , c 定义 8 设 B 为 c 个类别的背景基，[B]i 为类 别 i 的背景基， b j∈[B]i，向量 ， ， ，使得 [Bλ]i = Λ⊗[B]i = {λibj | j = 1,2,··· ,|[B]i |} (5) Bλ = n ∪ i=1 [Bλ] 则称 i 为 λ-背景基。 λ Bλ λ ∈ [0,1) Bλ Bλ Bλ ⊂ λ = 1 Bλ λ ∈ (1,∞) Bλ ⊃ 从几何学角度看， -背景基 是普通背景基 B 的放大或缩小。当 时，背景基 B 锁定 的 区 域 R (B) 包 含 锁定的区域 R ( ) ， 即 R( ) R(B)；当 时，满足关系 R( ) = R(B)；当 时 ，R( ) R(B)。综上所言，对于区域 R 关系满足： R = R(Bλ) ⊂ R(B), λ ∈ [0,1) R(Bλ) = R(B), λ = 1 R(Bλ) ⊃ R(B), λ ∈ [1,∞] 实现 λ-背景基具体方法见定义 9。 [B]i m = |[B]i | j ∈ m [B]i 定义 9 设 O 为第 i 类背景基 的重心，其 中 ， ，bij∈ ，则 b λ i j = O+λ(O−bi j) (6) [Bλ]i = m ∪ j=1 b λ 这里 i j。 3.2 构造基点分类算法 据第 2 章的 IBBE 算法和第 3.1 节中相关定 ·532· 智 能 系 统 学 报 第 15 卷