﻿ 因素空间理论下基点分类算法研究
«上一篇
 文章快速检索 高级检索

 智能系统学报  2020, Vol. 15 Issue (3): 528-536  DOI: 10.11992/tis.201903031 0

引用本文

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. DOI: 10.11992/tis.201903031.

文章历史

1. 辽宁工程技术大学 理学院，辽宁 阜新 123000;
2. 辽宁工程技术大学 智能工程与数学研究院，辽宁 阜新 123000

Base point classification algorithm based on factor space theory
PU Lingjie 1,2, ZENG Fanhui 1,2, WANG Peizhuang 1,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.
Key words: factor space    background base    background base extraction    λ-background base    base point classification algorithm    identify new classes    data classification    background distribution    background relationship

1 背景基理论基本概念

 $X\left( {{F_i}} \right) = X\left( {{f_{(j)}}} \right) \times \cdots \times X\left( {{f_{(k)}}} \right)\\$ (1)

${X_{{\rm{max}}}} = X({f_1}) \times X({f_2}) \times \cdots \times X({f_n})$ 称为最大性状空间。对于离散型性状空间而言，任意 ${{a}} = ({a_1}, {a_2},\cdots ,{a_n}) \in X$ 称为一个性状颗粒。

 $[{{a}}] = {{{F}}^{ - 1}}({{a}}) = \{ u \in U|{{F}}(u) = {{a}}\} \\$ (2)

$[{{a}}]$ 可能是空集，若 $[{{a}}] \ne {\text{Ø}}$ ，则称a是一个实性状颗粒，否则称a是一个虚组态。全体实性状集合记为

 $\begin{array}{l} R = {{{F}}^*}(U) = \{ {{a}} = ({a_1},{a_2}, \cdots ,{a_n}) \in X|\exists u \in U \\ {\rm{ }}{f_1}(u) = {a_1},{f_2}(u) ={a_2},\cdots ,{f_n}(u) = {a_n}\},\\ \end{array}$ (3)

R称为因素 ${f_1}, {f_2},\cdots ,{f_n}$ 之间的背景关系，也称为因素F*的背景集。

 $E_x\;R\;E_y$

 $E_x \to R_y{\rm{ }}(R \text{表示} \to )$

2 改进的背景基提取算法

2.1 背景基提取原理

 $(P - O,{O^*} - O) \leqslant ({O^*} - O,{O^*} - O)$

2.2 改进的背景基提取算法

1)取S中样本xi，若|B|< $\theta$ ，则 ${x_i} \in B$ ，否则，转至2)。

2)计算B的几何中心o

 ${{o}} = \frac{1}{k}\sum\limits_{j = 1}^k {{{{b}}_j},\quad{{{b}}_j} \in {{B}}}\\$

 $({{\alpha}} ,{{{\beta}} _{{j}}}) = {{\alpha}} {{{\beta }}^{\rm{T}}_{{j}}} \\$

3)在 2)中加入xi可能会导致一个或多个基点再次变成内点，而内点需要被剔除，因此3)功能是剔除B中内点。具体如下：

①取基点 ${{{b}}_j} \in {{B}}$ 视为待测点，B中剩余的基点 ${B^{\rm{*}}} = B$ \ ${{{b}}_j}$ 视为临时背景基；然后计算B*的几何中心 ${{o}}'$ 以及内积：

 $({{\alpha}} ',{{{\beta}} _i}') = {{\alpha}} '{({{{\beta}} _i}')^{\rm{T}}},$

②若 $({{\alpha}} ',{{{\beta}} _i}') < 0$ ，则继续判断 ${b_j}$ 是否为极点，即 ${{{b}}_j} = {{P_j}^ + }$ ？或 ${{{b}}_j} = {{P_j}^ - }$ ？其中

 ${{P_j}^ + } = {\rm{argma}}{{\rm{x}}_i}\{ {b_{ij}}|{b_{ij}} \in {{B}}\}$
 ${{P_j}^ - } = {\rm{argmi}}{{\rm{n}}_i}\{ {b_{ij}}|{b_{ij}} \in B\} {\rm{ }}\left( {j = 1,2, \cdots ,|{{B}}|} \right)$

4)若B中存在内点，则删除标记点di标记的基点，得到 ${{B'}}$ ，更新B ${{B}} \leftarrow {{B'}}$ ；再返回1)读取全部样本后转至5)。

5)输出背景基B

 ${{{B}}_{m \times n}} = \left[ \begin{array}{l} {b_{11}}\;\;{b_{12}}\;\; \cdots \;\;{b_{1n}} \\ {b_{21}}\;\;{b_{22}}\;\; \cdots \;\;{b_{2n}} \\ \;\ \vdots \ \ \ \ \;\; \ \vdots\ \ \ \ \ \ \ \ \;\;\; \vdots \\ {b_{m1}}\;\;{b_{m2}}\;\; \cdots \;\;{b_{mn}} \\ \end{array} \right]$

B的每一行表示一个基点。

2.3 算例

 Download: 图 2 背景基内点判别法 Fig. 2 Angle criterion for the inner points of the background base

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}} = \frac{1}{k}\sum\limits_{j = 1}^k {{b_j} = \frac{1}{2}} (a + b) = (1,2)\\$

(oc,ac)=(oc)(ac)T=(−1,−2)(−1, −1)T=3>0

(oc,bc)=(oc)(bc)T=(−1,−2)(−1, −3)T=7>0

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)。

1)从S中取样本d，count=4，此时|B|=3，|B|<2，条件不成立，转至2)。

2)~4)与上述对应步骤相同，此处省略，得到B={a, b, c, d}。

1)从S中取样本e，count=5，此时|B|=4，|B|<2，条件不成立，转至2)。

2)与上述对应步骤相同，此处省略，得到B={a, b, c, d, e}。

3) ①取Ba为待测点，B*=B\a={b, c, d, e}，判断得到a不是B*中内点；

②取Bb为待测点，B*=B\b={a, c, d, e}，判断得到b不是B*中内点；

③取Bc为待测点，B*=B\b={a, b, d, e}，判断得到c不是B*中内点；

④取Bd为待测点，B*=B\b={a, b, c, e}，判断得到dB*中的内点，再根据极点公式Pj+Pj判断得到d不是极点，因此标记d点为待删除点d1

4) B中有内点存在，删除标号d1的点，所以B={a, b, c, e}；此时count=5<|S|，则转至1)。

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}} = {\left[ \begin{array}{l} {\rm{1 }}\;1\;{\rm{ 2\; 4\; 3}} \\ {\rm{3 }}\;1\;{\rm{ 4 \; 2 \; 1}} \\ \end{array} \right]^{\rm{T}}}$

B的每列代表一个因素，如图3所示，虚线包含的区域可以近似视为由样本数据生成的背景分布，此时背景基为背景分布轮廓的特征点集合。由上述算例可得背景基在信息压缩、知识表达与存储等方面有着独具创新的优势。

 Download: 图 3 样本S背景基和背景分布 Fig. 3 Sample S background base and background distribution

①IBBE算法极大简化了计算难度和编程难度；

②算法初始化阶段不需要依赖各因素极值；

③极大降低了基点数量，有利于高维度数据提取基点。

3 基点分类算法

3.1 基本定义

BPC算法训练得到的模型相对固定。在实际中，决策者的主观因素常常扮演重要角色，基于此，BPC算法在做决策时需要加入决策者主观参数，由主观参数 $\lambda$ 变换得到的背景基称为 $\lambda$ -背景基。

 ${[{{B}}]_{{i}}} = \{ {{b}}_{{j}}^{{i}}|i \in c,j = 1,2, \cdots ,n\},\\$ (4)

 ${{B}} = \mathop\cup\limits_{i = 1}^{{c}} {{{[{{B}}]}_i}} \\$

 ${{B}} = \mathop\cup\limits_{i = 1}^{{c}} {{{{B}}_i}} \\$

 ${{{B}}_i} = {[{{B}}]_i}$

 ${[{{{B}}_{{\lambda}} }]_i} = {{\varLambda}} \otimes {[{{B}}]_i} = \{ {\lambda _{{i}}}{{{b}}_{{j}}}|j = 1,2, \cdots ,|{[{{B}}]_i}|\} \\$ (5)

 $R = \left\{ \begin{array}{l} R({{{B}}_\lambda }) \subset R\left( {{B}} \right),\quad \lambda \in [0,1) \\ R({{{B}}_\lambda }) = R\left( {{B}} \right),\quad \lambda = 1 \\ R({{{B}}_\lambda }) \supset R\left( {{B}} \right),\quad \lambda \in [1,\infty ] \\ \end{array} \right.$

 ${{b}}_{ij}^\lambda = O{\rm{ + }}\lambda {\rm{(}}O{\rm{ - }}{{{b}}_{ij}})\\$ (6)

3.2 构造基点分类算法

1)从S中取样本xk，判定xk类别i；从B中提取类别为i的背景基[B]i

2)利用函数IBBE(xk, [B]i)，更新B中原来的背景基[B]i，具体做法为

 $[{{B}}]_i' = \operatorname{IBBE} ({x_k},{[{{B}}]_i}) \\$
 ${{B}} = \operatorname{update} ([{{B}}]_i',{[{{B}}]_i})\\$

3)计算每个类别的重心O

4)对B中每个类别做 $\lambda$ 变换得到 ${[{{{B}}_\lambda }]_i}$

5)输出 ${{{B}}_\lambda }$

M表示样本个数，N表示因素个数，p表示基点个数。当样本数量较少时，p2M的数量级接近；当样本数量远远大于Np2时，此时Np2可以忽略不计，时间复杂度为O(MNp2)≈O(M)。因此，BPC算法在处理大样本数据时优势明显。

4 数值实验

4.1 二维数据

BPC算法采用基点限定区域原理学习和预测，由于其原理与SVM算法原理具有相似性，所以实验结果与SVM(libsvm)算法进行比较是合理的。训练数据与测试数据为同一组数据。通过Matlab编程得到BPC算法的训练函数和预测函数。实验结果表明，BPC算法准确率为98.33%，SVM算法准确率为100.00%，两者结果相当。从实验结果来看，BPC算法在开始阶段表现良好。

1)在线性可分的样本分布下，BPC算法与SVM算法预测结果相近，但BPC算法原理更简单易懂、实验结果可解释性强，在一定程度上更符合人的思维逻辑。

2)BPC算法分类是通过构建每个类别的背景基来限定各类别区域范围，这种划分原理比SVM算法用超平面划分原理更加精准。当出现新类别样本时，BPC算法可以及时发现远离它的类别，并为其定义新标签，而SVM算法只会将该样本归类到已学习到的类别中，不会产生新类别。所以，BPC算法的一个非常明显的优势是在预测中可以发现新类别。

4.2 三维数据

BPC算法可以提取三维数据的背景基。图9展示的是用BPC算法提取到实验2数据的背景基。由于BPC算法继承了IBBE算法的优点，所以提取到的基点数量少，却又能高效覆盖所要表达的信息。从图10可以看出，各类别的背景基数量远小于样本边界的数量。

 Download: 图 11 class3的背景基B与 $\lambda$ -背景基 ${{{B}}_\lambda }$ Fig. 11 Background base B and $\lambda$ -background base ${{{B}}_\lambda }$ of class3
4.3 总结

BPC算法的特点如下：

1)上述实验只是针对二维、三维数据进行的，实际上，BPC算法可以扩展到n维数据集上，且时间复杂度随着维度增加呈线性增长，避免了高维数据基点冗余的现象。

2) BPC算法具有智能的生长机制。由于BPC算法可以发现新类别，新类别可以衍生新概念。从机制主义人工智能理论出发，机器能产生新概念则具有自我学习和扩展学习的能力。据此可得，BPC算法是具有一定智能生长机制的。

3) BPC算法使用 $\lambda$ -背景基使得预测或决策更灵活。分类器重复训练模型的代价很大，为了减小代价、充分利用已训练模型， $\lambda$ -背景基可以在原训练模型基础上，根据需要扩大或缩小预测区域，这种处理可以减少重复训练的代价，同时可以继承原有知识。

4) BPC算法原理完全由智能数学描述，其算法和原理较传统数学更加简单高效。

5) BPC算法得到的模型不是“黑箱”，而是具有可解释的、符合人类逻辑思维的“白箱”。理论上，该模型是决策者思维的同构映射。

5 结束语

 [1] 钟义信. 机制主义人工智能理论−一种通用的人工智能理论[J]. 智能系统学报, 2018, 13(1): 2-18. ZHONG Yixin. Mechanism-based artificial intelligence theory: a universal theory of artificial intelligence[J]. CAAI transactions on intelligent systems, 2018, 13(1): 2-18. DOI:10.11992/tis.201711032 (0) [2] 何华灿. 泛逻辑学理论−机制主义人工智能理论的逻辑基础[J]. 智能系统学报, 2018, 13(1): 19-36. HE Huacan. Universal logic theory: logical foundation of mechanism-based artificial intelligence theory[J]. CAAI transactions on intelligent systems, 2018, 13(1): 19-36. DOI:10.11992/tis.201711033 (0) [3] 汪培庄. 因素空间理论—机制主义人工智能理论的数学基础[J]. 智能系统学报, 2018, 13(1): 37-54. WANG Peizhuang. Factor space-mathematical basis of mechanism based artificial intelligence theory[J]. CAAI transactions on intelligent systems, 2018, 13(1): 37-54. DOI:10.11992/tis.201711034 (0) [4] 汪培庄. 因素空间与因素库[J]. 辽宁工程技术大学学报(自然科学版), 2013, 32(10): 1297-1304. WANG Peizhuang. Factor spaces and factor data-bases[J]. Journal of Liaoning Technical University (Natural Science), 2013, 32(10): 1297-1304. (0) [5] 汪培庄. 因素空间与数据科学[J]. 辽宁工程技术大学学报(自然科学版), 2015, 34(2): 273-280. WANG Peizhuang. Factor spaces and data science[J]. Journal of Liaoning Technical University (Natural Science), 2015, 34(2): 273-280. (0) [6] WANG Peizhuang, LIU Zengliang, SHI Yong, et al. Factor space, the theoretical base of data science[J]. Annals of data science, 2014, 1(2): 233-251. (0) [7] WANG Peizhuang, OUYANG He, ZHONG Yixin, et al. Cognition math based on factor space[J]. Annals of data science, 2016, 3(3): 281-303. (0) [8] 钟义信. 高等人工智能原理: 观念·方法·模型·理论[M]. 北京: 科学出版社, 2014. (0) [9] 钟义信. 信息科学与技术导论[M]. 3版. 北京: 北京邮电大学出版社, 2015. (0) [10] 曲国华, 曾繁慧, 刘增良, 等. 因素空间中的背景分布与模糊背景关系[J]. 模糊系统与数学, 2017, 31(6): 66-73. QU Guohua, ZENG Fanhui, LIU Zengliang, et al. Background distribution and fuzzy background relation in factor spaces[J]. Fuzzy systems and mathematics, 2017, 31(6): 66-73. (0) [11] 曾繁慧, 郑莉. 因素分析法的样本培育[J]. 辽宁工程技术大学学报(自然科学版), 2017, 36(3): 320-323. ZENG Fanhui, ZHENG Li. Sample cultivation in factorial analysis[J]. Journal of Liaoning Technical University (Natural Science), 2017, 36(3): 320-323. (0) [12] 吕金辉, 刘海涛, 郭芳芳, 等. 因素空间背景基的信息压缩算法[J]. 模糊系统与数学, 2017, 31(6): 82-86. LV Jinhui, LIU Haitao, GUO Fangfang, et al. The algorithm of extraction of background bases[J]. Fuzzy systems and mathematics, 2017, 31(6): 82-86. (0) [13] 李建中, 李英姝. 大数据计算的复杂性理论与算法研究进展[J]. 中国科学: 信息科学, 2016, 46(9): 1255-1275. LI Jianzhong, LI Yingshu. Research progress in the complexity theory and algorithms of big-data computation[J]. SCIENTIA SINICA informationis, 2016, 46(9): 1255-1275. (0) [14] PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341-356. (0)