定义1^[15] 设三元组(U, A, I)为一个形式背景, 其中, U为对象集合, A为属性集合, 均为非空有限集, $ I: U \times A \rightarrow\{0, 1\}$为对象与属性之间的二元关系.对于$ \forall x \in U$, $ a \in A$ , 若对象x具有属性a, 则I(x, a)=1, 否则I(x, a)=0.$ \mathcal{F}: 2^{U} \rightarrow 2^{A}$和$ g: 2^{A} \rightarrow 2^{U}$为一对集合值映射, 定义如下:

$ \begin{array}{l} \mathcal{F}(X)=\{a \in A \mid \forall x \in X, I(x, a)=1\}, \\ \mathcal{G}(B)=\{x \in U \mid \forall a \in B, I(x, a)=1\}, \end{array}$

其中, X⊆U, B⊆A.$ \mathcal{F}(X) $表示对象集合X中所有对象共有的属性集合, 而G(B)表示具有属性集合B中所有属性的对象集合.

定义2^[15] 在形式背景(U, A, I)中, 对于任意子集X⊆U和B⊆A, 若满足F(X)=B且G(B)=X, 则称(X, B)为一个形式概念, 其中, X表示该形式概念的外延, B表示该形式概念的内涵, 后面简称形式概念为概念.

定义3^[16] 在形式背景(U, A, I)中, 对∀ x∈ U, 由对象x诱导得到对象粒概念(GF(x), F(x)).对∀ a∈ A, 由属性a诱导得到属性粒概念(G(a), FG(a)).对象粒概念与属性粒概念统称为粒概念.

性质1^[16] 在形式背景(U, A, I)中, 对于任意概念(X, B), 有

$ (X, B)=\bigvee_{x \in X}(\mathscr{G} \mathscr{F}(x), \mathcal{F}(x))=\bigwedge_{a \in B}(\mathscr{G}(a), \mathcal{F} \mathcal{G}(a)) . $

性质1表明, 每个概念既可由对象粒概念通过上确界运算得到, 也可由属性粒概念通过下确界运算得到.

在经典形式背景中, 对象与属性之间的二元关系为二值关系.然而, 在实际问题中, 对象与属性之间往往存在不同程度的模糊关联, 即每组对象属性配对都对应一个隶属度, 表征对象拥有该属性的程度.基于上述现实情形, 引出模糊形式背景.

定义4^[17] 设U={x₁, x₂, …, x_n}为一个非空有限对象集合, 定义在U上的模糊集:

$ \widetilde{H}=\left\{\left\langle x, \mu_{\widetilde{H}}(x)\right\rangle \mid x \in U\right\}, $

其中 μH˜(x)∈ [0, 1]表示对象x在模糊集 H˜中的隶属度,

$ \mu_{\widetilde{H}}^{c}(x)=1-\mu_{\widetilde{H}}(x) $

表示其非隶属度.记L^U为定义在U上的所有模糊集的集合, 类似地, L^A为定义在A上的所有模糊集.

定义5^[18] 三元组$ (U, A, \tilde{I}) $为模糊形式背景, 其中, U为对象集合, A为属性集合, $ \widetilde{I}$为U与A之间的模糊关系.对于∀ (x, a), 关系$ \widetilde{I}$赋予一个隶属度值 μI˜(x, a)∈ [0, 1].为了简化表示, 记

$ \widetilde{I}(x, a)=\mu_{\check{I}}(x, a) . $

定义6^[19] 在模糊形式背景$ (U, A, \tilde{I}) $中, 记2^U为U的幂集.对于X⊆U和$ \widetilde{B}$∈ L^A, 定义算子$ \widetilde{F}$和$ \widetilde{G}$如下:

$ \begin{array}{l} \widetilde{f}(X)(a)=\bigwedge_{x \in X} \tilde{I}(x, a), a \in A, \\ \widetilde{g}(\widetilde{B})=\{x \in U \mid \forall a \in A, \widetilde{B}(a) \leqslant \widetilde{I}(x, a)\}, \end{array} $

其中$ \widetilde{B}$ (a)为模糊集$ \widetilde{B}$在属性a下的隶属度.若满足$ \widetilde{F}$(X)= $ \widetilde{B}$且$ \widetilde{G}$($ \widetilde{B}$)=X, 则称$(X, \widetilde{B})$为模糊形式背景$(U, A, \tilde{I})$中的一个模糊概念.

定义7^[4] 在模糊形式背景$(U, A, \tilde{I})$中, 模糊对象粒概念$(\widetilde{g} \widetilde{\mathcal{G}}(x), \widetilde{\mathcal{F}}(x))$可由对象$x \in U$诱导得到.

定义8^[4] 五元组$(U, A, \tilde{I}, D, J)$称为模糊形式决策背景, 若对∀ k₁∈ D, k₂∈ D, k₁≠ k₂, 满足

$\mathscr{G}^{D}\left(k_{1}\right) \cap \mathscr{G}^{D}\left(k_{2}\right)=\emptyset, $

其中, A为条件属性集合, D为决策属性集合, J为对象与决策属性之间的关系, 对∀ k∈ D,

$\mathscr{G}^{D}(k)=\{x \in U \mid J(x, k)=1\} .$

需要指出的是, 模糊形式背景主要用于描述对象与属性之间的模糊关联关系, 其中对象与属性之间的关系由相应的隶属程度进行刻画, 主要用于模糊概念、粒概念及相关认知结构的构造.在此基础上, 当属性进一步区分为条件属性与决策属性时, 可形成模糊形式决策背景, 其中, 条件属性用于描述对象的特征信息, 决策属性用于表征与决策相关的信息.

在分类问题中, 类别标签可视为决策属性的一种具体形式.因此, 当仅研究对象与属性之间的模糊关联及其概念结构时, 可采用模糊形式背景; 当需要同时考虑条件属性信息与决策属性信息, 并分析二者之间的关系时, 采用模糊形式决策背景.因此, 本文依据是否引入并区分决策属性信息确定两类背景的使用.

性质2^[5] 在模糊形式背景$(U, A, \tilde{I})$中, 任意模糊概念$(X, \widetilde{B})$均可由其对应的模糊属性粒概念通过下确界运算诱导得到或对应的对象粒概念通过上确界运算得到.

已有研究在非三支概念认知学习的情况下定义模糊属性粒概念, 能从模糊形式背景中提取更加全面的信息.本节首先介绍模糊属性粒概念, 并进一步讨论其向模糊三支概念的扩展.

定义9^[5] 给定一个模糊形式背景$(U, A, \tilde{I})$, 对于∀ x∈ U, a∈ A, 定义算子S:

$S_{(x, a)}=\{z \in U \mid \widetilde{I}(z, a)> \widetilde{I}(x, a)\} .$

当S_{(x, a)}≠ Ø 时, S_{(x, a)}为非空对象子集.根据定义6二元组$\left(\widetilde{g} \widetilde{\mathcal{G}}\left(S_{(x, a)}\right), \widetilde{\mathcal{F}}\left(S_{(x, a)}\right)\right)$构成对应的模糊概念, 并由该集合可生成模糊属性粒概念.若S_{(x, a)}=Ø , 则无法生成对应的模糊属性粒概念, 在后续模糊三支属性粒概念空间构造中不考虑该项.

性质3^[5] 在模糊形式背景$(U, A, \widetilde{I})$中, 有

$\left(\widetilde{\mathcal{G}} \widetilde{\mathcal{H}}\left(S_{(x, a)}\right), \widetilde{\mathcal{H}}\left(S_{(x, a)}\right)\right)=\left(S_{(x, a)}, \widetilde{\mathcal{H}}\left(S_{(x, a)}\right)\right) .$

模糊三支概念通过融合对象或属性的共有信息及它们共同缺失的信息, 从而提供更全面的信息描述.为了刻画对象与属性之间的互补关联关系, 本文在补模糊关系 I˜c上定义一对与原模糊关系上派生算子对应的算子, 称为逆算子.这里的逆并非通常函数意义下的逆映射, 而是指该算子基于原模糊关系的补关系构造.

定义10^[6] 在模糊形式背景$(U, A, \tilde{I})$中, 对于$X \subseteq U$, $ \widetilde{B} \in L^{A}$, 定义基于补模糊关系的逆算子$\widetilde{\mathcal{F}}^{-}$和$\widetilde{g}^{-}$如下:

$\begin{array}{l} \widetilde{\mathcal{F}}^{-}(X)(a)=\inf _{x \in X} \tilde{I}^{c}(x, a), a \in A, \\ \widetilde{g}^{-}(\widetilde{B})=\left\{x \in U \mid \forall a \in A, \widetilde{B}(a) \leqslant \widetilde{I}^{c}(x, a)\right\}, \end{array}$

其中

$\tilde{I}^{c}(x, a)=1-\tilde{I}(x, a) .$

由模糊形式背景的定义可知, $ \widetilde{I}(x, a) \in[0, 1]$表示对象x对属性a的隶属度, 因此其补关系值$\tilde{I}^{c}(x, a)$同样属于[0, 1]区间.

定义11^[20] 在模糊形式背景$(U, A, \widetilde{I})$中, 对于$\forall X \subseteq U, \widetilde{B}_{1} \in L^{A}, \widetilde{B}_{2} \in L^{A}$, 定义模糊三支概念算子$\widetilde{\mathcal{F}}^{\triangleleft}: 2^{U} \rightarrow L^{A} \times L^{A}$和$\widetilde{g}^{\triangleright}: L^{A} \times L^{A} \rightarrow 2^{U}$如下:

$\begin{array}{l} \widetilde{f}^{\triangleleft}(X)=\left(\widetilde{f}(X), \widetilde{f}^{-}(X)\right), \\ \widetilde{g}^{\triangleright}\left(\widetilde{B}_{1}, \widetilde{B}_{2}\right)=\widetilde{g}\left(\widetilde{B}_{1}\right) \cap \widetilde{g}^{-}\left(\widetilde{B}_{2}\right) . \end{array}$

若二元组$\left(X, \left(\widetilde{B}_{1}, \widetilde{B}_{2}\right)\right)$满足

$\widetilde{F}^{\triangleleft}(X)=\left(\widetilde{B}_{1}, \widetilde{B}_{2}\right), G^{\triangleright}\left(\widetilde{B}_{1}, \widetilde{B}_{2}\right)=X, $

称为一个模糊三支概念, 该概念为对象诱导的模糊三支概念.鉴于后续算法需要统一概念空间的构造形式, 本文仅讨论对象诱导的模糊三支概念.

粒计算通过模糊粒概念表示对象及其属性, 并通过模糊属性粒概念增强对属性的理解, 从而提供一种灵活、高效的框架.相比传统模糊概念认知学习方法, 模糊三支概念认知学习方法具有更高的学习效率, 同时能提取更多信息.

性质4^[6] 设$(U, A, \widetilde{I})$为一个模糊形式背景,

$\begin{array}{l} \forall X \subseteq U, \\ \left(\widetilde{g} \widetilde{\mathcal{F}}(X) \cap \widetilde{g}^{-} \widetilde{\mathcal{F}}^{-}(X), \left(\widetilde{\mathcal{F}}(X), \widetilde{\mathcal{F}}^{-}(X)\right)\right) \end{array}$

构成一个模糊三支概念.

为了避免退化概念影响后续聚类, 本文将外延为空集的模糊三支概念称为空概念.具体而言, 对于模糊三支概念$\left(X, \left(\widetilde{B}, \widetilde{B}^{c}\right)\right)$, 若$X=\emptyset$, 则称该概念为空概念.由于该类概念不包含可用于概念聚类和分类学习的对象信息, 本文在构建模糊三支属性粒概念空间时将其剔除.

定义12 在模糊形式背景$(U, A, \tilde{I})$中, 与属性a∈ A相关的模糊三支属性粒概念定义如下:

$\begin{aligned} A S_{a}= & \cup_{x \in U}\left(\left(\widetilde{G} \widetilde{\mathcal{F}}\left(S_{(x, a)}\right) \cap \widetilde{\mathcal{G}}^{-} \widetilde{\mathcal{F}}^{-}\left(S_{(x, a)}\right)\right), \right. \\ & \left.\left(\widetilde{\mathcal{F}}\left(S_{(x, a)}\right), \widetilde{\mathcal{F}}^{-}\left(S_{(x, a)}\right)\right)\right) \backslash\{\text { 空概念 }\} . \end{aligned}$

类似地, 对于∀ x∈ U, 对应的模糊三支对象粒概念定义如下:

$O S_{x}=\left(\widetilde{g} \widetilde{\mathcal{G}}(x) \cap \widetilde{g}^{-} \widetilde{\mathscr{F}}^{-}(x), \left(\widetilde{\mathcal{F}}(x), \widetilde{\mathscr{F}}^{-}(x)\right)\right) . $

因此, 集合

$A S_{A}=\left\{A S_{a} \mid a \in A\right\} $

包含模糊形式背景$(U, A, \tilde{I})$中所有模糊三支属性粒概念, 而

$O S_{U}=\left\{O S_{x} \mid x \in U\right\}$

包含所有模糊三支对象粒概念.

在模糊形式决策背景$(U, A, \tilde{I}, D, J)$中, 可在类别k的标签下生成第k个子背景, 记为(U_k, A, I˜k, D, J_k).在每个子背景中, 同样可定义A SAk, A Sak, O SUk.

由于每个模糊三支对象粒概念仅包含一个对象概念, 因此在聚类过程中将其排除, 而本文主要关注对模糊三支属性粒概念的聚类.

算法1 模糊三支粒概念空间构建算法

输入 模糊形式决策背景(U, A, I˜, D, J)

输出 模糊三支属性粒概念空间AS_A,

模糊三支对象粒概念空间OS_U

初始化AS_A=Ø , OS_U=Ø

for each 类别k∈ D:

for each i=1到|U_k|:

根据定义12计算 OSxi

更新 OSUk← OSUk∪ OSxi

for each a∈ A:

$\begin{aligned} A S_{a, x_{i}}^{k}= & \left(\widetilde{g} \widetilde{\mathcal{F}}\left(S_{\left(x_{i}, a\right)}\right) \cap \widetilde{\mathcal{G}}^{-} \widetilde{\mathcal{F}}^{-}\left(S_{\left(x_{i}, a\right)}\right), \right. \\ & \left.\widetilde{\mathcal{F}}\left(S_{\left(x_{i}, a\right)}\right), \widetilde{\mathcal{F}}^{-}\left(S_{\left(x_{i}, a\right)}\right)\right) \backslash\{\text { 空概念 }\} \\ A S_{a}^{k} \leftarrow & A S_{a}^{k} \cup A S_{a, x_{i}}^{k} \end{aligned}$

end for

AS_A← AS_A∪ ASak

end for

OS_U← OS_U∪ OSUk

end for

返回AS_A和OS_U

算法1给出模糊三支粒概念空间的构建过程, 包括两个主要部分:模糊三支属性粒概念空间的构建及模糊三支对象粒概念空间的构建.

模糊三支概念认知学习是一个逐步进行的过程, 每个阶段都反映对应层次下的认知状态.下面从数学角度揭示模糊粒三支概念认知学习的机制.在动态环境下, 对于第k类, 在第i阶段的对象集合 Uik是通过在上一阶段的集合 Ui-1k上加入新对象得到的.同样, 第i阶段的属性集合A_i是在第i-1阶段属性集合A_i-1的基础上扩展新属性得到的.通过不断迭代该过程, 可得到一系列对象集合和属性集合.

定义13^[21] 在模糊形式决策背景(U, A, I˜, D, J)中, 定义增量变化

$\Delta U_{i-1}^{k}=U_{i}^{k} \backslash U_{i-1}^{k}, \Delta A_{i-1}=A_{i} \backslash A_{i-1}, $

则有如下映射关系:

1)$ \widetilde{\mathcal{F}}_{k, i-1}: 2^{U_{i-1}^{k}} \longrightarrow L^{A_{i-1}}, \widetilde{G}_{k, i-1}: L^{A_{i-1}} \longrightarrow 2^{U_{i-1}^{k}} ; $

2)$ \widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}: 2^{\Delta U_{i-1}^{k}} \longrightarrow L^{A_{i-1}}, \widetilde{\mathcal{G}}_{k, \Delta U_{i-1}^{k}}: L^{A_{i-1}} \longrightarrow 2^{\Delta U_{i-1}^{k}} ; $

3)$ \widetilde{\mathcal{F}}_{k, \Delta A_{i-1}}: 2^{U_{i}^{k}} \longrightarrow L^{\Delta A_{i-1}}, \widetilde{G}_{k, \Delta A_{i-1}}: L^{\Delta A_{i-1}} \longrightarrow 2^{U_{i}^{k}} ; $

4)$ \widetilde{\mathcal{F}}_{k, i}: 2^{U_{i}^{k}} \longrightarrow L^{A_{i}}, \widetilde{G}_{k, i}: L^{A_{i}} \longrightarrow 2^{U_{i}^{k}} .$

由于逆算子的定义与上述类似, 这里不再给出.上述4组认知算子满足如下性质:

$\begin{array}{l} \widetilde{\mathcal{F}}_{k, i}(x)=\left\{\begin{array}{ll} \widetilde{\mathcal{I}}_{k, i-1}(x) \cup \widetilde{F}_{k, \Delta A_{i-1}}(x), & x \in U_{i-1}^{k} \\ \widetilde{\mathfrak{F}}_{k, \Delta U_{i-1}^{k}}(x) \cup \widetilde{\mathcal{F}}_{k, \Delta A_{i-1}}(x), & \text { 其它 } \end{array}\right. \\ \widetilde{G}_{k, i}(a)=\left\{\begin{array}{ll} \widetilde{G}_{k, i-1}(a) \cup \widetilde{G}_{k, \Delta U_{i-1}^{k}}(a), & a \in A_{i-1} \\ \widetilde{G}_{k, \Delta A_{i-1}}(a), & \text { 其它 } \end{array}\right. \end{array}$

根据新增信息Δ Ui-1k和Δ A_i-1更新算子 F˜k, i和 G˜k, i, 未涉及新增对象或新增属性的部分不发生变化.在后续框架中, 随着新信息的不断加入, 将逐步更新模糊三支概念.

性质5^[10] 设 Uik为第i阶段中标签为k的对象集合.对于∀ x∈ Uik, a∈ A_i及其对应的S_{(x, a)}, 记Δ S_{(x, a)}为当前阶段i与上一阶段i-1中S'_{(x, a)}的差异.

1)对∀ x∈ Uik, 如果x∈ Ui-1k, 那么

$\begin{array}{l} \left(\widetilde{\Theta}_{k, i} \widetilde{\mathcal{T}}_{k, i}(x) \cap \widetilde{\Theta}_{k, i}^{-} \widetilde{\mathcal{F}}_{k, i}^{-}(x), \left(\widetilde{\mathcal{F}}_{k, i}(x), \widetilde{\mathcal{F}}_{k, i}^{-}(x)\right)\right)= \\ \quad\left(\left(\widetilde{\Theta}_{k, i-1} \widetilde{\mathcal{F}}_{k, i-1}(x) \cap \widetilde{\mathcal{G}}_{k, i-1}^{-} \widetilde{\mathcal{F}}_{k, i-1}^{-}(x)\right) \cup\left(\widetilde{\mathcal{G}}_{k, \Delta U_{i-1}^{k}} \widetilde{\mathcal{F}}_{k, i-1}(x) \cap \widetilde{\mathcal{G}}_{k, \Delta U_{i-1}^{k}} \widetilde{\mathcal{F}}_{k, i-1}^{-}(x)\right), \left(\widetilde{\mathcal{F}}_{k, i-1}(x), \widetilde{\mathcal{F}}_{k, i-1}^{-}(x)\right)\right), \end{array}$

在该阶段, 由x诱导得到的S_{(x, a)}满足

$\begin{array}{l} \left(\widetilde{\mathcal{G}}_{k, i} \widetilde{\mathcal{I}}_{k, i}\left(S_{(x, a)}\right) \cap \widetilde{\mathcal{G}}_{k, i}^{-} \widetilde{\mathcal{F}}_{k, i}^{-}\left(S_{(x, a)}\right), \left(\widetilde{\mathcal{F}}_{k, i}\left(S_{(x, a)}\right), \widetilde{\mathcal{F}}_{k, i}^{-}\left(S_{(x, a)}\right)\right)\right)= \\ \quad\left(\left(\widetilde{G}_{k, i-1} \widetilde{\mathcal{F}}_{k, i-1}\left(S_{(x, a)}\right) \cap \widetilde{G}_{k, i-1}^{-} \widetilde{\mathcal{F}}_{k, i-1}^{-}\left(S_{(x, a)}\right)\right) \cup\right. \\ \left.\quad\left(\widetilde{G}_{k, \Delta U_{i-1}^{k}} \widetilde{\mathcal{F}}_{k, i-1}\left(S_{(x, a)}\right) \cap \widetilde{G}_{k, \Delta U_{i-1}^{k}}^{-} \widetilde{\mathcal{F}}_{k, i-1}^{-}\left(S_{(x, a)}\right)\right), \left(\widetilde{\mathcal{F}}_{k, i-1}\left(S_{(x, a)}\right), \widetilde{\mathcal{F}}_{k, i-1}^{-}\left(S_{(x, a)}\right)\right)\right) . \end{array}$

2)对于∀ x∈ Uik, 如果x∉ Ui-1k, 那么

$\begin{array}{l} \left(\widetilde{G}_{k, i} \widetilde{\mathcal{I}}_{k, i}(x) \cap{\widetilde{\mathcal{G}_{k, i}}}_{k, i} \widetilde{\mathcal{F}}_{k, i}^{-}(x), \left(\widetilde{\mathcal{F}}_{k, i}(x), \widetilde{\mathcal{F}}_{k, i}^{-}(x)\right)\right)= \\ \quad\left(\left(\widetilde{G}_{k, i-1} \widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}(x) \cap \widetilde{G}_{k, i-1}^{-} \widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}^{-}(x)\right) \cup\right. \\ \left.\quad\left(\widetilde{G}_{k, \Delta U_{i-1}^{k}} \widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}(x) \cap \widetilde{G}_{k, \Delta U_{i-1}^{k}} \widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}^{-}(x)\right), \left(\widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}(x), \widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}^{-}(x)\right)\right) . \end{array}$

类似地, 有

$\begin{array}{l} \left(\widetilde{\Im}_{k, i} \widetilde{\mathcal{F}}_{k, i}\left(S_{(x, a)}\right) \cap \widetilde{G}_{k, i}^{-} \widetilde{\mathcal{F}}_{k, i}^{-}\left(S_{(x, a)}\right), \left(\widetilde{\mathcal{F}}_{k, i}\left(S_{(x, a)}\right), \widetilde{\mathcal{F}}_{k, i}^{-}\left(S_{(x, a)}\right)\right)\right)= \\ \quad\left(\left(\widetilde{\mathcal{G}}_{k, i-1}\left(\widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}\left(\Delta S_{(x, a)}\right) \cup \widetilde{\mathcal{F}}_{k, i-1}\left(S_{(x, a)}^{\prime}\right)\right)\right) \cap\left(\widetilde{\mathcal{G}}_{k, i-1}^{-}\left(\widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}^{-}\left(\Delta S_{(x, a)}\right) \cup \widetilde{\mathcal{F}}_{k, i-1}^{-}\left(S_{(x, a)}^{\prime}\right)\right)\right)\right) \cup \\ \quad\left(\left(\widetilde{\mathcal{G}}_{\Delta U_{i-1}^{k}}\left(\widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}\left(\Delta S_{(x, a)}\right) \cup \widetilde{\mathcal{F}}_{k, i-1}\left(S_{(x, a)}^{\prime}\right)\right)\right) \cap\left(\widetilde{\mathcal{G}}_{\Delta U_{i-1}^{k}}^{-}\left(\widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}^{-}\left(\Delta S_{(x, a)}\right) \cup \widetilde{\mathcal{F}}_{k, i-1}^{-}\left(S_{(x, a)}^{\prime}\right)\right)\right), \right. \\ \left.\quad\left(\widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}\left(\Delta S_{(x, a)}\right) \cap \widetilde{\mathcal{F}}_{k, i-1}\left(S_{(x, a)}^{\prime}\right)\right), \left(\widetilde{\mathcal{F}}_{k, \Delta U_{i-1}^{k}}^{-}\left(\Delta S_{(x, a)}\right) \cap \widetilde{\mathcal{F}}_{k, i-1}^{-}\left(S_{(x, a)}^{\prime}\right)\right)\right) . \end{array}$

至此, 在该框架下, 模糊三支概念认知学习已逐步构建模糊三支对象粒概念空间和模糊三支属性粒概念空间.

为了适配概念认知学习方法中的模糊形式背景构造, 本文提出基于谱分解的对象约简方法, 约简原始样本集.方法的设计思想受到CUR^[22]的启发, 即尽可能从原始数据中选取具有代表性的对象, 并保留其原始属性特征, 而不是通过线性变换生成新的特征表示.与主成分分析等传统降维方法不同, 基于谱分解的对象约简方法不改变原始属性空间, 也不重构新的对象, 而是在保持原始数据表达形式不变的前提下, 从原始对象集上筛选对整体结构贡献较大的样本, 兼顾数据约简、结构保持与结果可解释性.

设某一类别对应的数据子矩阵X_c∈ Rnc×m, 其中, n_c为该类别中的对象数, m为属性维数.首先, 构造其Gram矩阵:

$\boldsymbol{G}_{c}=\boldsymbol{X}_{c}^{\mathrm{T}} \boldsymbol{X}_{c} \in \mathbf{R}^{m \times m} .$

由于G_c为对称半正定矩阵, 可进行特征值分解, 并将特征值按降序排列.记排序后的特征值为

$\lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{m} \geqslant 0 .$

然后, 依据累计能量阈值α 选取前k个主方向, 其中k满足

$\sum_{j=1}^{k} \lambda_{j}\left(\sum_{j=1}^{m} \lambda_{j}\right)^{-1} \geqslant \alpha .$

由此前k个特征向量构成矩阵P_k, 并将原始对象投影到相应的主子空间中, 得到对象的重要性评分.第i个对象在主子空间中的投影能量, 即评分

$s_{i}=\left\|\left(\boldsymbol{X}_{c} \boldsymbol{P}_{k}\right)_{i}\right\|^{2} .$

s_i越大, 说明该对象对保持原始数据主要结构信息的贡献越大, 具有更高的重要性.

在对象筛选阶段, 采用确定性选择与概率性选择结合的混合策略.首先, 按照评分从高到低排序, 直接保留部分高分对象, 确保尽可能不丢失关键结构信息.然后, 对剩余对象按照评分大小进行加权随机抽样, 在突出代表性对象的同时保留一定的数据多样性, 避免样本约简过程过度集中于少数高分对象.设确定性保留高分对象后, 当前类别中剩余对象的索引集合为R_c.记类别c的目标保留总样本数为r_c, 确定性保留的高分对象数量为t, 需要从集合R_c中抽取r_c-t个对象.对于∀ i∈ R_c, 将对象重要性评分s_i, 进行归一化得到抽样概率:

$p_{i}=s_{i}\left(\sum_{j \in R_{c}} s_{j}\right)^{-1} .$

再基于概率p_i迭代执行无放回抽样, 直至选择r_c-t个对象.每选中一个对象, 从R_c中移除该对象索引, 并对剩余对象的抽样概率重新归一化.若剩余对象的评分之和为0, 对剩余对象采用等概率无放回抽样, 即

$p_{i}=\frac{1}{\left|R_{c}\right|} .$

最终, 所选对象仍保持原始属性取值不变, 从而为后续模糊形式背景构造提供更紧凑且更具代表性的数据基础.

总之, 基于谱分解的对象约简方法本质上是一种面向概念认知学习的数据约简策略, 核心目标不是通过特征变换获得新的低维表示, 而是在不改变原始数据形式的前提下, 通过谱分解刻画数据的主要结构方向, 并据此筛选更具代表性的重要对象, 从而提升大规模数据条件下形式背景构造与后续学习过程的可行性与稳定性.基于谱分解的对象约简方法步骤如算法2所示.

算法2 基于谱分解的对象约简方法

输入 数据集M, 目标保留对象总数N_keep,

累计能量阈值α , 确定性保留比例γ

输出 约简后的数据集M_red

初始化 $M_{\text {red }}=\emptyset$

统计各类别样本数n_c, 并按分层原则分配各类别保留对象数r_c(至少为1), 满足$\sum_{c} r_{c}=N_{\text {keep }}$

for each 类别c:

提取该类别对应的数据子矩阵X_c

$\text { if } r_{c} \geqslant\left|\boldsymbol{X}_{c}\right|:$

保留该类别全部对象

else

构造Gram矩阵G_c= XTcX_c

对G_c进行特征值分解, 将特征值按降序排序为

$\lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{m} \geqslant 0$

选取满足$\sum_{j=1}^{k} \lambda_{j}\left(\sum_{j=1}^{m} \lambda_{j}\right)^{-1} \geqslant \alpha$的最小整数k

记前k个特征向量组成的矩阵为P_k

计算投影矩阵 Z_c=X_cP_k

for each 对象x_i∈ X_c:

计算重要性评分s_i=‖ (X_cP_k)_i‖ ²

end for

按评分s_i从大到小排序

确定性保留前t个高分对象(取整), $ t=\left\lfloor\gamma r_{c}\right\rfloor$

令剩余对象索引集合为R_c, 按照p_i进行无放回

加权抽样, 补足其余r_c-t个对象

记该类别最终保留的对象集合为 Xc*

end if

更新$ M_{\text {red }} \leftarrow M_{\text {red }} \cup X_{c}^{* }$

end for

返回M_red

通过基于谱分解的对象约简过程, 可在保持原始属性空间不变的前提下获得更紧凑的样本集合, 为后续模糊形式背景构造和概念空间生成提供数据基础.然而, 即使在对象约简之后, 构建的模糊三支属性粒概念空间中仍可能存在大量相似概念或冗余概念.对模糊三支属性粒概念进行聚类, 旨在依据概念外延的相似性划分候选概念集合, 为后续伪概念的构造限定合理的组合范围, 使相似的概念参与聚合, 从而降低冗余计算.本文主要基于概念外延集合度量概念之间的相似性.

定义14^[23] 在模糊形式背景$ (U, A, \tilde{I})$中, 2个模糊三支粒概念

$ G_{1}=\left(X_{1}, \left(\widetilde{B}_{1}, \widetilde{B}_{1}^{c}\right)\right), G_{2}=\left(X_{2}, \left(\widetilde{B}_{2}, \widetilde{B}_{2}^{c}\right)\right)$

之间的相似度根据对象集合X₁和X₂定义如下:

$ \sigma\left(G_{1}, G_{2}\right)=\left|X_{1} \cap X_{2}\right| /\left|X_{1} \cup X_{2}\right| .$

除了相似度σ (G₁, G₂)以外, 伪概念的构建还需要引入相似度阈值τ .当G₁与G₂的相似度大于等于τ 时, 这2个模糊三支粒概念将纳入用于构建该伪概念的概念集合中.上述方法同时提升计算效率:若X_i⊇X_j, 即G_j为G_i的子概念, 当

$ \sigma\left(G_{i}, G_{j}\right)< \tau, $

对于∀ X_j⊇X_l, 均有

$ \sigma\left(G_{i}, G_{l}\right) \leqslant \sigma\left(G_{i}, G_{j}\right)< \tau .$

因此, 可跳过G_j的进一步子概念, 减少相似度计算开销.

算法3 模糊三支粒概念聚类空间构建算法

输入 模糊三支属性粒概念空间集合AS_A, 参数τ

输出 聚类后的概念集合V

for each ASak∈ AS_A:

初始化$ V_{k}=\emptyset$

for each G_i∈ ASak, G_j∈ ASak:

$ \text { if } X_{i} \supseteq X_{j} \text { : }$

计算σ (G_i, G_j)

end if

if σ (G_i, G_j)≥ τ :

将G_i, G_j加入$ V_{k, i}$

end if

更新$ \gamma_{k} \leftarrow \gamma_{k} \cup \gamma_{k, i}$

end for

$ v \leftarrow v \cup v_{k}$

end for

返回V={V₁, V₂, …, V_n}

本文采用基于基准概念的重叠聚类方式.对于类别k中任意模糊三支属性粒概念G_i, 以 G_i为基准概念, 并初始化聚类V_{k, i}=G_i.对于满足X_i⊇X_j的子概念G_j, 若σ (G_i, G_j)≥ τ , 将G_j加入V_{k, i}.遍历完成后, V_{k, i}构成以G_i为基准的相似概念集合.

由于不同基准概念对应的相似概念范围可能存在交叠, 同一模糊三支属性粒概念允许同时属于多个聚类.本文聚类的目的并非形成互斥的数据划分, 而是为后续伪概念构建确定结构相近的候选概念集合.

算法3给出基于相似度阈值τ 的模糊三支属性粒概念聚类过程.然而, 同一聚类中的不同概念对分类任务的贡献并不完全相同, 因此有必要进一步引入权重机制, 改进伪概念的构建方式.

在完成模糊三支属性粒概念聚类后, 每个聚类均包含若干结构相近的模糊三支概念.本文所称的伪概念, 是指由同一聚类中的若干相似模糊三支属性粒概念按照给定组合规则聚合形成的派生概念表示, 其外延和内涵由参与聚合的概念共同确定, 用于增强相关概念在分类认知过程中的综合表征能力^[10].与单个模糊三支属性粒概念不同, 伪概念反映一组相似概念的联合信息.

为了将这些概念整合为可用于分类的统一表达, 需要进一步构建伪概念.传统伪概念通常采用固定系数对聚类中的概念进行组合, 但这种方式难以反映不同概念在结构层次和信息贡献上的差异.为此, 本文在传统伪概念构建方法的基础上进一步引入权重机制.

定义15 考虑标签k下的子背景(U_k, A, I˜k, D, J_k), 设 ASak为其模糊三支属性粒概念集合.对于任意聚类 Crk⊆ ASak, 设其中包含概念

$ \begin{array}{l} G_{1}^{r}=\left(X_{1}, \left(\widetilde{B}_{1}, \widetilde{B}_{1}^{c}\right)\right), G_{2}^{r}=\left(X_{2}, \left(\widetilde{B}_{2}, \widetilde{B}_{2}^{c}\right)\right), \cdots, \\ G_{m}^{r}=\left(X_{m}, \left(\widetilde{B}_{m}, \widetilde{B}_{m}^{c}\right)\right), \end{array}$

则其伪概念定义如下:

$ \begin{aligned} X^{r}=X_{1} \cup X_{2} \cup \cdots \cup X_{m}, & \\ \widetilde{B}^{r}(a)= & \frac{1}{2^{m-1}}\left(\widetilde{B}_{1}(a)+\widetilde{B}_{2}(a)+2 \widetilde{B}_{3}(a)+\cdots+\right. \\ & \left.2^{m-2} \widetilde{B}_{m}(a)\right), a \in A, \\ \left(\widetilde{B}^{c}\right)^{r}(a)= & \frac{1}{2^{m-1}}\left(\widetilde{B}_{1}^{c}(a)+\widetilde{B}_{2}^{c}(a)+2 \widetilde{B}_{3}^{c}(a)+\cdots+\right. \\ & \left.\quad 2^{m-2} \widetilde{B}_{m}^{c}(a)\right), a \in A . \end{aligned}$

上述伪概念构建方式本质上采用固定系数1/2及其幂次对不同概念进行组合, 虽然能实现概念聚合, 但未充分区分不同概念在局部对象结构和全局层次关系中的信息贡献.为此, 本文提出加权伪概念构建方法, 在伪概念构建过程中同时考虑概念的局部贡献度、层级衰减因子及相对于父概念的层级一致性.具体而言, 通过计算G_{i, n}中的元素X_{i, n}, 可计算有效对象, 这部分体现局部性质, 同时, 通过对比G_{i, n}与其父概念G_{i, n-1}的属性, 可衡量当前概念对上层概念结构信息的保持程度, 反映其在概念层次关系中的全局结构特征, 体现全局性质.

定义16 考虑标签k下的子背景(U_k, A, I˜k, D, J_k), 设ε _k为从该子背景中得到的所有加权伪概念集合.每个加权伪概念 E_{k, i}∈ ε _k由一组概念组成, 即

$ \begin{array}{l} G_{i, 1}=\left(X_{i, 1}, \left(\widetilde{B}_{i, 1}, \widetilde{B}_{i, 1}^{c}\right)\right), \\ G_{i, 2}=\left(X_{i, 2}, \left(\widetilde{B}_{i, 2}, \widetilde{B}_{i, 2}^{c}\right)\right), \\ \vdots \\ G_{i, m}=\left(X_{i, m}, \left(\widetilde{B}_{i, m}, \widetilde{B}_{i, m}^{c}\right)\right) . \end{array}$

这些模糊三支属性粒概念的聚类集合记为V_{k, i}, 而在类别k下所有此类集合构成V_k.对于∀ G_{i, n}∈ V_{k, i}, 在加权伪概念E_{k, i}的讨论中, 仅关注概念G_{i, 1}, G_{i, 2}, …, G_{i, m}.为了简化表示, 这些模糊三支属性粒概念统称为模糊三支概念.模糊三支概念G_{i, n}的权重定义如下:

$ \omega_{i, n}=d_{i, n} \cdot c_{i, n} \cdot u_{i, n} .$

其中:d_{i, n}表示衰减因子, 由模糊三支概念的层级深度及其衰减基数决定; u_{i, n}表示该模糊三支概念与其父概念的层级一致性; c_{i, n}表示该模糊三支概念的贡献度, 取值基于隶属度与非隶属度.三者分别从概念的层级位置、概念间结构关系及概念内部信息三个方面共同确定概念权重.下文将进一步说明这些参数的具体定义及其选取依据.

参数d_{i, n}为概念G_{i, n}的衰减因子.在一个伪概念E_{k, i}中, d_{i, n}由模糊三支概念G_{i, 1}, G_{i, 2}, …, G_{i, m}构成.若对象集合满足

$ X_{i, 1} \supseteq X_{i, 2} \supseteq \cdots \supseteq X_{i, m}, $

则具有对象集X_{i, 1}的模糊三支概念深度为1, 具有对象集X_{i, 2}的模糊三支概念深度为2, 依此类推, 拥有对象集X_{i, m}的模糊三支概念深度为m.

衰减基数用于控制深度对衰减因子的影响.为了使权重保持平衡, 取值既不应过大, 也不应过小.因此, 选择合适的衰减基数十分重要.对于任意模糊三支概念G_{i, n}∈ E_{k, i}, 衰减因子

$ d_{i, n}=\beta^{-d e p t h\left(G_{i, n}\right)}, $

其中, β > 1表示衰减基数, depth(· )表示模糊三支概念G_{i, n}的深度.一般而言, 包含更多对象的模糊三支概念覆盖更广的对象范围, 因此在整体结构表征中具有更强的代表性, 所以在构建伪概念时更重要.然而, 在某些情况下, 一些模糊三支概念虽然仅包含少量对象, 但却包含重要且无冗余的信息.为了解决这一问题, 选择合适的衰减基数, 可有效控制权重的衰减速度.在给出层级深度对应的衰减因子后, 下面进一步刻画概念内部对象对该概念属性信息的贡献程度, 即贡献度c_{i, n}.

事实上, 贡献度c_{i, n}与概念的稳定性相似, 已有研究描述经典形式背景下三支概念的稳定性.类似地, 本文在模糊形式背景下定义三支概念的稳定性.

给定模糊形式背景(U, A, I˜)及模糊三支概念(X, ( B˜, B˜c)), 稳定性

$ \begin{array}{l} \xi\left(\left(X, \left(\widetilde{B}, \widetilde{B}^{c}\right)\right)\right)= \\ \quad \frac{1}{2^{|X|}}\left|\left\{C \subseteq X \mid \widetilde{F}^{\triangleleft}(C)=\left(\widetilde{B}, \widetilde{B}^{c}\right)\right\}\right| . \end{array}$

模糊三支概念的稳定性反映其对某些对象的依赖程度.当部分对象被移除后, 剩余对象仍能保持该模糊三支概念的完整信息.稳定性值表示在删除部分对象后, 该概念属性信息保持不变的概率.

然而, 单个模糊三支概念稳定性的计算时间复杂度为 2X, 计算开销较大.为了避免这一问题, 本文不直接采用该指标, 而是使用一种思想类似但时间复杂度更小的方法.

定义17 对于概念G_{i, n}, 设其对象集X_{i, n}包含 xi, n1, xi, n2, …, xi, nl, 且

$ \widetilde{\mathcal{F}}^{\triangleleft}\left(X_{i, n}\right)=\left(\widetilde{B}_{i, n}, \widetilde{B}_{i, n}^{c}\right) .$

依次对每个对象应用模糊三支概念算子$ \widetilde{F}^{\triangleleft}(\cdot)$, 若存在对象 xi, nj∈ X_{i, n}, 属性a∈ A及

$ \widetilde{\mathcal{F}}^{\triangleleft}\left(x_{i, n}^{j}\right)=\left(\widetilde{B}_{i, n}^{j}, \widetilde{B}_{i, n}^{c j}\right), $

使得

$ \widetilde{B}_{i, n}^{j}(a)=\widetilde{B}_{i, n}(a)$

或

$ \widetilde{B}_{i, n}^{c j}(a)=\widetilde{B}_{i, n}^{c}(a), $

则称 xi, nj为X_{i, n}的有效对象.

所有有效对象构成的集合记为T_{i, n}.在对X_{i, n}中所有对象处理完成后, 贡献度

$ c_{i, n}=\left|\square_{i, n}\right| /\left|X_{i, n}\right| .$

贡献度主要从概念内部对象的角度刻画局部结构信息.与此不同, 层级一致性进一步从当前概念与其父概念之间的关系出发, 刻画当前概念对所在概念层次中共有结构信息即全局结构信息的保持程度.

定义18 设G_{i, n}在加权伪概念E_{k, i}中的父概念为G_{i, n-1}, 且

$ \widetilde{\mathcal{F}}^{\triangleleft}\left(X_{i, n-1}\right)=\left(\widetilde{B}_{i, n-1}, \widetilde{B}_{i, n-1}^{c}\right) .$

对于∀ a∈ A, 定义

$ \begin{array}{l} A_{G_{i, n}}=\left\{a \in A \mid \widetilde{B}_{i, n}(a)=\widetilde{B}_{i, n-1}(a)\right\}, \\ A_{G_{i, n}}^{c}=\left\{a \in A \mid \widetilde{B}_{i, n}^{c}(a)=\widetilde{B}_{i, n-1}^{c}(a)\right\} . \end{array}$

则模糊三支概念的层级一致性为:

$ u_{i, n}=\frac{\left|A_{G_{i, n}}\right|+\left|A_{G_{i, n}}^{c}\right|}{2|A|} .$

层级一致性通过对比当前模糊三支概念与其父概念的属性刻画, 反映当前概念对概念层次里共有结构信息的保持程度.在由父概念向子概念逐层细化的过程中, 若子概念与父概念在隶属度和非隶属度对应的属性刻画上具有较高的一致程度, 说明该子概念在细化过程中仍能较好地保持父概念表征的共有结构信息, 其在当前层级结构中具有较强的代表性.反之, 若二者差异较大, 说明该子概念更多地反映局部变化, 对上层共有结构的保持程度较低.因此, u_{i, n}越大, 表示当前概念与其父概念的层级一致性越高.对于层级中的首个概念G_{i, 1}, 由于不存在父概念, 令u_{i, 1}=1.该指标后续作为乘法权重因子, 取1表示不产生衰减, 从而在权重计算中起到中性作用.对层级一致性较高的概念赋予更高权重, 有助于在融合多个相似概念时更多地保留其共同的层次结构信息, 降低局部结构偏离对伪概念整体表达的影响.

然而, 由于每个模糊三支概念的权重ω _{i, n}由多个因素共同决定, 因此需要对ω _{i, n}进行归一化处理, 生成最终的加权伪概念.

定义19 对于G_{i, n}, 其权重ω _{i, n}由其自身信息d_{i, n}、c_{i, n}和u_{i, n}共同决定.通过归一化处理后, 可得到G_{i, n}的最终权重:

$ \omega_{i, n}^{* }=\omega_{i, n}\left(\sum_{j=1}^{m} \omega_{i, j}\right)^{-1} .$

若分母为0, 则令各概念权重均为 1/m.因此, 将加权伪概念E_{k, i}的对象与属性定义如下:

$ \begin{array}{l} X_{i}^{k}=X_{i, 1} \cup X_{i, 2} \cup \cdots \cup X_{i, m}, \\ \widetilde{B}_{i}^{k}(a)=\omega_{i, 1}^{* } \widetilde{B}_{i, 1}(a)+\omega_{i, 2}^{* } \widetilde{B}_{i, 2}(a)+\cdots+ \\ \omega_{i, m}^{* } \widetilde{B}_{i, m}(a), \\ \left(\widetilde{B}^{c}\right)_{i}^{k}(a)=\omega_{i, 1}^{* } \widetilde{B}_{i, 1}^{c}(a)+\omega_{i, 2}^{* } \widetilde{B}_{i, 2}^{c}(a)+\cdots+ \\ \\ \omega_{i, m}^{* } \widetilde{B}_{i, m}^{c}(a) . \end{array}$

算法4 加权伪概念构建算法

输入 模糊三支属性粒概念集合V

输出 加权伪概念集合ε

for each V_k∈ V:

初始化ε _k=Ø

for each V_{k, i}:

初始化 E_{k, i}

for each G_{i, n}:

计算ω _{i, n}(定义16)

end for

for each G_{i, n}:

计算 ωi, n*(定义19)

计算E_{k, i}

end for

更新ε _k← ε _k∪ E_{k, i}

end for

ε ← ε ∪ ε _k

end for

返回ε

算法4展示在概念聚类之后, 如何通过计算聚类中各概念的权重以构建加权伪概念.因此, 该方法不仅能利用聚类结果降低概念数量, 还能通过权重分配保留不同概念之间的信息差异.

需要指出的是, 上述聚类结果和加权伪概念的构建均受到相似度阈值τ 的影响, 因此有必要进一步讨论τ 的选取问题.

在模糊三支属性粒概念聚类过程中, 相似度阈值τ 直接决定概念聚类结果, 并进一步影响加权伪概念的构建质量.若τ 值过高, 可能导致可合并概念数量不足, 难以有效降低概念空间规模; 若τ 值过低, 可能将差异较大的概念划分到同一聚类中, 影响伪概念的信息表达能力.因此, 有必要基于验证集构建阈值评价准则, 确定较优的相似度阈值.

定义20 定义标签k下的模糊三支粒概念空间

$ C S_{k}=A S_{A}^{k} \cup O S_{U}^{k}, $

对象集合U被划分为训练集U_train、验证集U_val和测试集U_test.对于∀ x_t∈ U_test, x_v∈ U_val, 其隶属度为 B˜t, 非隶属度为 B˜tc.

给定∀ CS_k∈ CS, 其中CS表示所有CS_k集合, 以及任意加权伪概念或模糊三支概念

$ \left(X_{k, j}, \left(\widetilde{B}_{k, j}, \widetilde{B}_{k, j}^{c}\right)\right) \in C S_{k}, $

其与验证对象x_v之间的距离为:

$ D C_{k, j}=\sqrt{\left\|\widetilde{B}_{k, j}-\widetilde{B}_{v}\right\|^{2}+\left\|\widetilde{B}_{k, j}^{c}-\widetilde{B}_{v}^{c}\right\|^{2}} .$

给定阈值τ , 优化后的模糊三支概念空间CS_k记为 CSkτ.函数d(k)表示在阈值τ 下进行聚类后, CSkτ中模糊三支粒概念聚类的数量.设验证集上共有V个对象, 则目标函数

$ \begin{array}{l} K(\tau, d(k))= \\ \quad \min _{d(k), k} \sum_{v=1}^{V} \sqrt{\left\|\widetilde{B}_{k, j}-\widetilde{B}_{v}\right\|^{2}+\left\|\widetilde{B}_{k, j}^{c}-\widetilde{B}_{v}^{c}\right\|^{2}}- \\ \quad \max _{d\left(k^{\prime}\right)} \sum_{k^{\prime} \neq k} \sum_{v=1}^{V} \sqrt{\left\|\widetilde{B}_{k^{\prime}, j}-\widetilde{B}_{v}\right\|^{2}+\left\|\widetilde{B}_{k^{\prime}, j}^{c}-\widetilde{B}_{v}^{c}\right\|^{2}}, \end{array}$

其中j表示类别k下第j个加权伪概念或模糊三支对象粒概念.

根据模糊三支概念与验证集对象x_v之间距离的定义可看出, 目标函数的第1项表示x_v与其真实类别对应的模糊三支概念空间之间的最小距离, 第2项表示x_v与其它类别模糊三支概念空间之间的最大距离.因此, 该目标函数旨在使验证对象尽可能接近其真实类别对应的概念空间, 同时与其它类别的概念空间保持较大区分度.阈值τ 的优化问题可表示为:

$ \begin{array}{l} \tau=\arg \min _{d(k)} K(\tau, d(k)) \in[0, 1], \\ k=1, 2, \cdots, n . \end{array}$

理论上可通过求解上式得到最优阈值 τ .然而, 由于上式难以获得解析解, 因此本文采用网格搜索方法优化τ , 对于FG3WCCL中涉及的其它超参数, 如衰减基数等, 也可采用类似的网格搜索策略进行选择.由于相关超参数的候选范围相对有限, 网格搜索能在可接受的计算成本内获得较优的参数组合, 保证后续分类实验的稳定性.

算法5 测试集上的预测

输入 加权伪概念空间集合ε ,

模糊三支对象粒概念空间测试集U_test

输出 测试集的标签集合Θ

初始化Θ =Ø

for each x_t∈ U_test:

初始化 θ _t=0

for each 类别 k∈ D:

for each OS_x∈ OSUk:

计算DC_{k, j}

end for

for each E_{k, i}∈ ε _k:

计算DC_{k, j}

end for

使用min{DC_{k, j}}的信息更新θ _t

end for

Θ =Θ ∪ θ _t

end for

返回Θ

在完成阈值τ 及相关超参数选择后, 进一步基于测试集评价方法的分类性能.具体而言, 对于任意测试对象x_t∈ U_test, 计算其与各类别模糊三支粒概念空间之间的距离, 并将距离最小的类别作为预测标签.

为了进一步说明FG3WCCL在实际应用中的可行性, 下面从时间复杂度角度分析计算开销.设对象数量N=|U|, 属性数量M=|A|, 类别数量C=|D|,

在算法1中, 构建模糊三支对象粒概念和模糊三支属性粒概念时, 需要围绕对象和属性组合反复计算 S_{(x, a)}、模糊三支概念算子及相应对象集合.由于每次计算通常需要在对象集和属性集上进行扫描, 因此时间复杂度可粗略记为O(N²M²).

在算法2中, 基于谱分解的对象约简方法首先需要对各类别数据子矩阵构造Gram矩阵, 时间复杂度为O(NM²). 然后, 对每个类别的 M× M的Gram矩阵进行特征值分解, 时间复杂度为O(CM³). 最后, 还需要计算对象评分并按照评分排序, 时间复杂度为O(Nlog₂N).因此, 算法2的时间复杂度为

$O\left(N M^{2}+C M^{3}+N \log _{2} N\right) .$

在算法3中, 需要对模糊三支属性粒概念进行相似度聚类.对于每个属性, 同类概念之间需要两两对比, 而每次对比又涉及对象集合的包含关系和交并计算, 因此该部分时间复杂度为O(N³M).

在算法4中, 加权伪概念构建方法需要计算每个概念的衰减因子、贡献度和层级一致性, 并对概念进行加权融合.由于概念数量可由对象和属性组合上界控制, 因此该部分时间复杂度为O(N²M²).

在算法5中, 分类预测需要计算测试对象与各类别下模糊三支粒概念空间之间的距离, 若测试对象数量与训练对象数量同阶, 则该部分时间复杂度可粗略记为O(N²M²).

综上所述, FG3WCCL的总体时间复杂度为

$O\left(N^{3} M+N^{2} M^{2}+C M^{3}+N \log _{2} N\right) .$

本文选择如下15种对比方法.

1)模糊概念认知学习方法:FCLM^[4]、FGC-CL^[5]、ILMPFTC^[6]、DMPWFC^[8]、FRCM(Fuzzy Rule Based Classification Model)^[24]、MA-CLM(Multi-atten-tion Concept-Cognitive Learning Model)^[25].

2)基于模糊相似性的分类方法:CFKNN(Con-densed Fuzzy K-Nearest Neighbor Rule)^[26]、FRNN(Fuzzy-Rough Nearest Neighbor)^[27]、文献[28]方法.

3)经典分类方法:C4.5、NB(Naive Bayes)、LDA(Linear Discriminant Analysis)、C-SVM、NU-SVM、RBFN(Radial Basis Function Network).

基于模糊相似性的分类方法和经典分类方法在KEEL软件平台上运行, 其余方法在Matlab 2019b环境中进行测试.在Firewall、Skin这2个对象相对较多的数据集上使用基于谱分解的对象约简方法进行数据预处理, 即在不显著损失有用信息的前提下, 减少数据集上样本数量, 提升计算效率.为了减少误差并保证结果的公平性, 每种算法均重复运行10次, 给出平均分类准确率和标准差.

FG3WCCL与模糊概念认知学习方法在各数据集上的分类准确率如表2所示, 表中黑体数字表示最优值.由表可知, FG3WCCL在14个数据集上的平均分类准确率为87.95%.相比FCLM提升9.08%, 相比FRCM提升29.12%, 相比DMPWFC提升13.65%, 相比ILMPFTC提升12.32%, 相比FGCCL提升11.10%, 相比MA-CLM提升15.59%.从另一角度来看, 在14个数据集上, FG3WCCL在其中11个数据集上取得最高或并列最高的分类准确率, 表明其具有良好的有效性.仅在Glioma、Fourclass、Fire- wall数据集上未取得最优值.

表2

Table 2

表2(Table 2)

表2 FG3WCCL与模糊概念认知学习方法的分类准确率 Table 2 Classification accuracy of FG3WCCL and fuzzy concept-cognitive learning methods % 数据集 分类准确率 FG3WCCL FCLM FRCM DMPWFC ILMPFTC FGCCL MA-CLM Chemical Composition 100.00± 0.00 100.00± 0.00 59.41± 10.54 100.00± 0.00 100.00± 0.00 99.58± 1.32 98.89± 3.51 Iris 96.67± 2.72 85.67± 5.89 33.00± 9.09 95.39± 3.77 95.21± 4.23 83.33± 4.71 86.00± 5.40 Wine 95.00± 3.15 93.81± 4.64 31.71± 8.02 77.58± 19.18 94.61± 7.29 92.86± 2.75 79.72± 2.64 Seeds 94.29± 1.16 90.48± 2.75 29.29± 4.21 87.72± 5.14 86.06± 8.91 88.33± 4.41 74.76± 4.92 Credit 84.09± 3.40 80.87± 2.09 81.59± 2.64 82.99± 5.22 78.17± 5.04 75.51± 3.78 65.36± 9.32 Breast Cancer Wisconsin 97.29± 0.88 84.08± 3.34 91.80± 2.65 97.07± 1.29 84.86± 5.31 74.90± 5.28 36.14± 10.52 Glioma 80.71± 3.54 69.09± 4.37 81.74± 2.64 74.43± 6.15 67.58± 4.29 72.63± 2.86 74.37± 5.59 Fourclass 74.63± 3.42 55.06± 3.08 62.79± 2.70 58.45± 4.30 60.54± 2.97 44.83± 2.73 98.72± 0.71 Raisin 84.11± 1.57 77.83± 1.49 47.22± 2.50 72.15± 4.57 61.28± 10.14 72.44± 1.86 61.44± 1.58 Mammographic 81.64± 1.16 64.04± 8.77 42.07± 7.30 45.57± 5.90 46.36± 10.53 64.09± 3.98 56.88± 10.66 Titanic 77.95± 0.99 66.94± 1.09 67.82± 1.72 19.00± 1.36 73.48± 5.15 68.39± 1.85 38.11± 20.58 Rice Cammeo Osmancik 90.51± 1.38 86.26± 0.95 57.15± 2.25 89.78± 1.36 58.54± 12.38 85.09± 1.25 58.29± 2.23 Firewall 82.58± 3.56 80.18± 0.59 58.80± 1.59 88.26± 1.60 71.67± 6.68 79.10± 1.62 92.89± 3.61 Skin 91.83± 0.14 69.87± 1.40 79.26± 0.10 51.84± 2.79 80.48± 8.03 74.77± 2.78 91.53± 1.59 平均值 87.95 78.87 58.83 74.30 75.63 76.85 72.36

表2 FG3WCCL与模糊概念认知学习方法的分类准确率 Table 2 Classification accuracy of FG3WCCL and fuzzy concept-cognitive learning methods %

FG3WCCL与基于模糊相似性的分类方法和经典分类方法的分类准确率如表3所示, 表中黑体数字表示最优值.

表3

Table 3

表3(Table 3)

表3 FG3WCCL与基于模糊相似性的分类方法和经典分类方法的分类准确率 Table 3 Classification accuracy of FG3WCCL, fuzzy similarity-based classification methods, and classical classification methods % 数据集 分类准确率 FG3WCCL CFKNN FRNN 文献[28]方法 C4.5 NB LDA C-SVM NU-SVM RBFN Chemical Composition 100.00 (± 0.00) 100.00 (± 0.00) 97.78 (± 4.44) 100.00 (± 0.00) 97.50 (± 5.00) 100.00 (± 0.00) 100.00 (± 0.00) 100.00 (± 0.00) 100.00 (± 0.00) 100.00 (± 0.00) Iris 96.67 (± 2.72) 86.67 (± 7.30) 80.00 (± 5.96) 86.67 (± 10.33) 89.33 (± 3.27) 94.00 (± 8.14) 96.00 (± 3.04) 93.44 (± 3.92) 96.67 (± 4.47) 92.67 (± 5.00) Wine 95.00 (± 3.15) 90.98 (± 2.84) 94.44 (± 0.00) 94.44 (± 3.51) 87.71 (± 5.36) 94.33 (± 2.55) 93.89 (± 2.55) 72.52 (± 27.79) 40.52 (± 4.20) 70.23 (± 5.35) Seeds 94.29 (± 1.16) 84.76 (± 3.56) 87.62 (± 2.33) 85.71 (± 3.01) 89.52 (± 1.90) 89.05 (± 7.98) 90.72 (± 2.65) 88.75 (± 2.87) 92.86 (± 5.32) 82.86 (± 5.30) Credit 84.09 (± 3.40) 83.51 (± 2.51) 83.78 (± 4.01) 82.36 (± 2.46) 81.93 (± 2.69) 82.03 (± 4.50) 44.49 (± 0.66) 81.51 (± 2.59) 57.25 (± 17.76) 83.19 (± 6.52) Breast Cancer Wisconsin 97.29 (± 0.88) 94.56 (± 1.06) 84.24 (± 1.57) 94.56 (± 1.06) 92.00 (± 1.14) 96.99 (± 1.35) 95.89 (± 1.38) 94.21 (± 2.12) 93.99 (± 2.19) 95.42 (± 1.91) Glioma 80.71 (± 3.54) 81.38 (± 2.01) 82.33 (± 1.66) 81.14 (± 2.51) 82.57 (± 1.70) 85.69 (± 4.19) 83.15 (± 3.21) 85.53 (± 8.46) 78.31 (± 3.95) 71.52 (± 5.77) Fourclass 74.63 (± 3.42) 72.16 (± 2.52) 71.81 (± 3.13) 64.39 (± 0.50) 76.10 (± 3.03) 76.34 (± 2.80) 76.109 (± 2.75) 76.10 (± 2.75) 62.14 (± 4.29) 68.31 (± 5.58) Raisin 84.11 (± 1.57) 82.00 (± 1.30) 82.00 (± 1.78) 81.56 (± 1.13) 83.78 (± 2.59) 82.56 (± 3.26) 83.869 (± 2.18) 75.22 (± 24.79) 50.44 (± 0.74) 80.22 (± 3.94) Mammographic 81.64 (± 1.16) 77.75 (± 0.32) 80.20 (± 0.28) 61.81 (± 3.46) 81.21 (± 0.47) 78.51 (± 1.85) 80.28 (± 1.87) 80.89 (± 1.26) 75.98 (± 1.32) 80.75 (± 2.96) Titanic 77.95 (± 0.99) 75.06 (± 2.46) 67.70 (± 0.09) 75.06 (± 2.46) 77.83 (± 1.69) 77.60 (± 2.17) 77.60 (± 2.17) 77.60 (± 2.17) 69.65 (± 13.74) 65.56 (± 15.84) Rice Cammeo Osmancik 90.51 (± 1.38) 89.55 (± 0.47) 90.23 (± 0.27) 90.36 (± 0.31) 90.13 (± 0.69) 90.44 (± 1.13) 90.05 (± 0.96) 78.71 (± 21.29) 77.22 (± 3.60) 86.56 (± 1.79) Firewall 82.58 (± 3.56) 78.33 (± 1.09) 89.04 (± 1.18) 59.29 (± 0.72) 95.82 (± 0.12) 94.60 (± 0.15) 97.23 (± 0.59) 94.69 (± 0.25) 91.04 (± 4.84) 97.04 (± 3.25) Skin 91.83 (± 0.14) 89.62 (± 0.39) 79.25 (± 0.01) 61.03 (± 0.57) 90.56 (± 0.39) 88.48 (± 0.29) 88.56 (± 0.39) 90.56 (± 0.39) 63.61 (± 21.24) 89.99 (± 0.61) 平均值 87.95 84.74 83.60 79.88 86.86 87.90 85.56 84.98 74.98 83.17

表3 FG3WCCL与基于模糊相似性的分类方法和经典分类方法的分类准确率 Table 3 Classification accuracy of FG3WCCL, fuzzy similarity-based classification methods, and classical classification methods %

由表3可见, FG3WCCL的平均分类准确率为87.95%, 为最高值, 并在其中11个数据集上取得最高或并列最高的分类准确率, 进一步验证该方法的有效性.

仅对比分类准确率虽能反映方法在各数据集上的总体表现, 但仍不足以说明不同方法之间的性能差异是否具有统计意义.因此, 本文进一步采用临界差异(Critical Difference, CD)图分析各方法的平均秩.定义显著性水平α =0.05, 基于Friedman检验及相应后续对比得到CD值, 各方法对比结果如图2所示.由图可见, FG3WCCL 在所有对比方法中的平均秩排名第一, 说明其优势并非仅由个别数据集上的偶然结果驱动, 而是在跨数据集对比中表现出较好的稳定性.若两个方法之间的平均秩差超过CD值, 则认为二者在给定置信水平下存在统计显著差异.结合图2可见, FG3WCCL与若干排名较低的方法之间存在明显差距, 进一步支持其在整体分类性能上的优势.

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 各方法的CD图Fig.2 CD diagram of different algorithms

在鲁棒性实验中, 将每个数据集划分为三部分, 即70%的数据用于训练、10%的数据用于验证、20%的数据用于测试.在训练集的属性中加入噪声, 而测试集保持不变.

针对每个数据集, 在0%、5%、10%、15%、20%、25%、30%的数据中加入噪声, 对FG3WCCL及6种模糊概念认知学习方法进行测试.每个数据集在每个噪声水平下的实验均重复运行10次, 并记录其平均结果, 结果如图3所示.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 FG3WCCL与模糊概念认知学习方法在不同噪声等级下的分类准确率Fig.3 Classification accuracy of FG3WCCL and fuzzy concept-cognitive learning methods under1different noise levels

由图3可见, 在大多数情况下, FG3WCCL的分类准确率最高, 表明其对噪声具有较强的鲁棒性, 即使在较高噪声水平下, 仍能保持较高的分类准确率, 仅表现出轻微的性能下降.相比之下, 对比方法的分类准确率表现较不稳定.例如:在Firewall数据集上, MA-CLM在训练集加入噪声后分类准确率显著下降, 说明其在此数据集上的鲁棒性不佳.此外, ILMPFTC在Titanic数据集上的波动较大, 也与其在无噪声数据情况下的表现有较大差异.总之, 模糊概念认知学习方法在一定程度上具有抗噪能力, 而 FG3WCCL在多数噪声条件下表现出较优的分类性能和稳定性.

为了检验FG3WCCL中加权伪概念构造方法的有效性, 设计消融实验, 验证融合概念局部信息与全局信息的优势.针对14个数据集均采用10折交叉验证, 评估方法的分类准确率, 结果如图4所示.在图中, 完整方法是本文提出的加权伪概念构造方法, 即算法4, 等比权重方法采用定义15给出的权重构造方式, 均等权重方法是对构成同一伪概念的各模糊三支概念赋予相同权重.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 不同权重策略的分类准确率Fig.4 Classification accuracy with different weighting strategies

由图4可知, 在所有数据集上, 算法4的分类准确率均最优.尽管由于数据集差异, 不同数据集上完整方法相对于其它两种方法的性能提升幅度存在一定差异, 但总体而言, 完整方法始终保持最优性能.

此外, 从图4中还可观察到, 等比权重方法与均等权重方法在各数据集上的表现差异较小, 说明仅采用单一权重策略难以充分挖掘概念结构信息, 而本文提出的融合策略能更有效地提升分类性能.

为了进一步验证本文提出的基于谱分解的对象约简方法的有效性, 采用随机采样方法进行对比实验.在该实验中, 保持分类模型、参数设置及测试流程不变, 仅将训练集构造过程中的对象筛选策略替换为随机分层采样方法进行对比.实验在Skin数据集上进行, 对象数量为245 057.

首先, 设定训练阶段需要保留的样本总量, 保留样本规模分别设为500、1 000、2 500、5 000、10 000、20 000、40 000、60 000, 并依据各类别在原始数据中的比例, 将该数量分配到不同类别中.然后, 在每个类别内部采用无放回随机抽样的方式选取相应数量的对象, 并合并针对各类别抽取得到的样本, 形成降采样后的训练集.训练集全部用于模型训练, 不再进一步划分.测试集仍由从原始未降采样数据中按类别比例随机抽取20%的样本构成, 保证测试分布的一致性.

为了减少随机抽样带来的偶然性影响, 在每种保留规模下重复进行5次训练样本选取.对于每次训练样本选取, 进一步重复进行5次测试集抽样, 最终以25次结果的平均值和标准差作为评价依据.通过该对比实验, 可在相同样本规模和相同实验流程下, 将基于谱分解的对象约简方法与随机约简方法进行直接对比, 从而更客观地评估本文样本筛选机制的有效性.

两种方法的分类准确率对比如图5所示.

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 2种约简方法的分类准确率Fig.5 Classification accuracy of 2 reduction methods

由图5可看出, 除样本量为10 000和20 000以外, 本文方法在其余样本规模下的分类准确率总体上均高于随机约简方法, 对应误差明显更小.这表明, 相比随机选择方法, 本文方法在多数情形下能更有效地保留对分类任务有用的信息, 从而表现出更优的分类性能和更强的稳定性.尤其是当对象数量较少时, 本文方法仍能维持较高的分类准确率和较低的波动水平, 而随机约简方法在小样本条件下误差明显增大, 说明其结果更容易受到样本选取偶然性的影响, 稳定性相对较弱.

需要指出的是, 在中等样本规模条件下, 本文方法的性能出现一定程度的下降.其可能原因在于, 该方法主要基于数据的整体结构特征进行信息提取, 对于数据中潜在的复杂非线性模式的刻画仍存在一定局限, 可能保留部分对分类不利的冗余信息或忽略某些关键判别特征, 最终导致分类准确率阶段性下降.