·338· 智能系统学报 第9卷 a,e=,(2）=2A,a e Cok(4 为元素所得的集K,叫做以co,C1,…,c。为顶点的抽 i=1 象复形，如果满足以下2个条件： 则a,:C,(K)→Cg-1(K)是群同态。这里的a,即为 1)由单个元素c,所组成的子集属于K,这里i= q维边缘算子或边缘同态。其实，边缘同态是几何 0,1,…,9； 上概念的代数化，是用来反映图形的边界关系的。 2)若A是K的元，则A的子集也是K的元。 在此基础上，定义出一个单纯链复形C,(K)= 抽象复形K中的元A叫做抽象单形，它的维数 {C,(K),a,}。C.(K)即是一串g维（整数）链群 是其顶点数减1。A的子集叫做A的面。K的维数 C,(K)和一串边缘同态a,:C,(K→C,-1(K),排成 是K中诸单形的最大维数。显然，每个单纯复形K 一个序列： 都自然地决定一个抽象复形K。实际上，K的每个 →0→C,C-1()）- 单形(aa…a,)规定K的一个抽象单形 (5)》 (cc,)。这样规定的K,显然是一个抽象复形， →C,(K)C,(K60 且称K为K的一个几何实现。 满足条件对每个维数q都有0,0，+1=0，也就是说“2 2邻域同调学习算法 次边缘为零”。 定义3单纯复形K的g维闭链群和边缘链群 设G=(V(G),E(G))是一个简单连通图。显 依次为 然，一个简单连通图就是一个单纯复形，根据上述定 Z,(K)=Keri。={z9∈C,(K);a,z=0}(6) 义即可以看成是有限个单形的集合，V(G)= B,(K)=Im0,+1= {ao,a1,…,a-1}表示图G的a。个顶点的集合也 {beC,(K);3c*1∈C,+1(K),使ac*1=b'} 就是图G中所有0维单形的集合，E(G)表示顶点 之间的所有连接边的集合。令X和F分别是G的 (7) 一个顶点子集和边子集，就以G一X表示G去掉X Z,(K)的元”叫做q维闭链，B,(K)的元b9叫做q 中的点及其关联边而得的图，G-F表示G去掉F 维边缘链。 中的边而得到的图。设a是G的任意一个顶点，以 这里B,(K)CZ(K),而且作为自由群 N(a)表示a的邻域，那么N(X)表示X中所有点 C,(K)的子群，它们也都是自由的。Z,(K)是描述有 邻域的并，即N(X)=U,N(a)。 可能成为边的图形，B,(K)是描述真的是边的图形。 基于此，可以构造出一幅给定图形G的领域复 那么“有可能成为边，又不真是边”这一事实，用群论 形N(G),N(G)是以G的顶点为顶点，以G中具有 的语言来表达，就应该是：在有可能成为边的 公共邻接点的子集为单形的一个抽象复形。根据抽 Z(K)中，模真是边的部分B(K)。这样就有商群： 象复形的概念，可以看出任意的抽象复形都可以在 H (K)=Z (K)/B (K)Kerd/Imd+ 欧氏空间实现25]。因此邻域复形在欧氏空间中是 H,(K)叫做单纯复形K的g维（单纯）同调群。 有其相对应的单纯复形的，这里仍以N(G)记邻域 同调群H(K)中的元素为Z,(K)中元素的模 复形所对应的单纯复形。除非特殊说明，二者不加 B(K)的等价类，因此，由单纯复形K上q维闭链” 以区别，统称为G的邻域复形。下文中的N(G)即 所决定的模B(K)的等价类是z+B,(K),记作 指邻域复形在欧氏空间中所对应的单纯复形。 [z],称其为z”的q维同调类，并且Hn(K)= 由于构造出的任意图形的邻域复形N(G)可以 {[z];z”∈Z,(K)}。同一同调类中的元号和号 看成是单纯复形，那么可以将N(G)剖分成有限个 称为同调的，记作月~号或-号~0。 单形，根据定义2可表示为N(G)= 由定义2可以看出单纯复形是由简单的图 {A;9=0,1,…,dim(N(G)),i=1,2,…,a};对 形一单形构成的。那么有了一个单纯复形之后， 每个单形取定一个指向并记为σ！，根据定义1，每 由此出发也可构成相应的新复形。其实仔细观察单 个单形σ？都可以根据顶点坐标线性表示出来：再由 纯复形的定义就会发现，单纯复形实际上完全由其 式(1)将q维单形线性组合就能得出N(G)的q维 顶点和顶点构成的子集组（单形）所决定，当然这时 链，这些g维链组成的自由交换群即为N(G)的q 顶点的子集组要适合某种条件。据此，定义4给出 维链群C,(W(G))。再通过计算同调群，就可以得 了抽象复形的定义，该定义则为本文算法中提到的 出2个图形之间的一种同调关系。设有2个图G、 构造邻域复形提供了理论基础。 H,如果N(G)和N(H)的各阶同调群分别同构，就 定义4以有限个元素c0,c1,…,c,的子集做 称G和H是邻域同调的，记为G≥H。∂ｑ ｃ ｑ ＝ ∂ｑ ∑ αｑ ｉ ＝ １ λｉσ ｑ ( ｉ ) ＝ ∑ αｑ ｉ ＝ １ λｉ∂σ ｑ ｉ ∈ Ｃｑ－１Ｋ （４） 则 ∂ｑ：Ｃｑ (Ｋ) → Ｃｑ－１ (Ｋ) 是群同态。 这里的 ∂ｑ 即为 ｑ 维边缘算子或边缘同态。 其实，边缘同态是几何 上概念的代数化，是用来反映图形的边界关系的。 在此基础上，定义出一个单纯链复形 Ｃ∗ (Ｋ) ＝ Ｃｑ (Ｋ) ，∂ｑ { } 。 Ｃ∗ (Ｋ) 即是一串 ｑ 维（整数） 链群 Ｃｑ (Ｋ) 和一串边缘同态 ∂ｑ：Ｃｑ (Ｋ) → Ｃｑ－１ (Ｋ) ，排成 一个序列： … → ０ → Ｃｑ (Ｋ) ∂ｑ→ Ｃｑ－１ (Ｋ) ∂ｑ－１→ … → Ｃ１ (Ｋ) ∂１→ Ｃ０ (Ｋ) ∂０→ ０ （５） 满足条件对每个维数 ｑ 都有 ∂ｑ∂ｑ＋１ ＝ ０，也就是说“２ 次边缘为零”。 定义 ３ 单纯复形 Ｋ 的 ｑ 维闭链群和边缘链群 依次为 Ｚｑ (Ｋ) ＝ Ｋｅｒ∂ｑ ＝ ｚ ｑ ∈ Ｃｑ (Ｋ) ；∂ｑ ｚ ｑ { ＝ ０} （６） Ｂｑ (Ｋ) ＝ Ｉｍ∂ｑ＋１ ＝ ｂ ｑ ∈ Ｃｑ (Ｋ) ；∃ｃ ｑ＋１ ∈ Ｃｑ＋１ (Ｋ) ， 使 ∂ｃ ｑ＋１ ＝ ｂ ｑ { } （７） Ｚｑ (Ｋ) 的元 ｚ ｑ 叫做 ｑ 维闭链， Ｂｑ (Ｋ) 的元 ｂ ｑ 叫做 ｑ 维边缘链。 这 里 Ｂｑ (Ｋ) ⊂ Ｚｑ (Ｋ) ， 而 且 作 为 自 由 群 Ｃｑ (Ｋ) 的子群，它们也都是自由的。 Ｚｑ (Ｋ) 是描述有 可能成为边的图形， Ｂｑ (Ｋ) 是描述真的是边的图形。 那么“有可能成为边，又不真是边”这一事实，用群论 的语 言 来 表 达， 就 应 该 是： 在 有 可 能 成 为 边 的 Ｚｑ (Ｋ) 中，模真是边的部分 Ｂｑ (Ｋ) 。 这样就有商群： Ｈｑ (Ｋ) ＝ Ｚｑ (Ｋ) ／ Ｂｑ (Ｋ) ＝ Ｋｅｒ∂ｑ ／ Ｉｍ∂ｑ＋１ Ｈｑ (Ｋ) 叫做单纯复形 Ｋ 的 ｑ 维（单纯）同调群。 同调群 Ｈｑ (Ｋ) 中的元素为 Ｚｑ (Ｋ) 中元素的模 Ｂｑ (Ｋ) 的等价类，因此，由单纯复形 Ｋ 上 ｑ 维闭链 ｚ ｑ 所决定的模 Ｂｑ (Ｋ) 的等价类是 ｚ ｑ ＋ Ｂｑ (Ｋ) ，记作 ｚ ｑ [ ] ， 称 其 为 ｚ ｑ 的 ｑ 维 同 调 类， 并 且 Ｈｑ (Ｋ) ＝ ｚ ｑ [ ] ；ｚ { ｑ ∈ Ｚｑ (Ｋ) } 。 同一同调类中的元 ｚ ｑ １ 和 ｚ ｑ ２ 称为同调的，记作 ｚ ｑ １ ～ ｚ ｑ ２ 或 ｚ ｑ １ － ｚ ｑ ２ ～ ０。 由定义 ２ 可以看出单纯复形是由简单的图 形———单形构成的。 那么有了一个单纯复形之后， 由此出发也可构成相应的新复形。 其实仔细观察单 纯复形的定义就会发现，单纯复形实际上完全由其 顶点和顶点构成的子集组（单形）所决定，当然这时 顶点的子集组要适合某种条件。 据此，定义 ４ 给出 了抽象复形的定义，该定义则为本文算法中提到的 构造邻域复形提供了理论基础。 定义 ４ 以有限个元素 ｃ０ ，ｃ１ ，…，ｃｑ 的子集做 为元素所得的集 Ｋ，叫做以 ｃ０ ，ｃ１ ，…，ｃｑ 为顶点的抽 象复形，如果满足以下 ２ 个条件： １）由单个元素 ｃｉ 所组成的子集属于 Ｋ，这里 ｉ ＝ ０，１，…，ｑ ； ２）若 Ａ 是 Ｋ 的元，则 Ａ 的子集也是 Ｋ 的元。 抽象复形 Ｋ 中的元 Ａ 叫做抽象单形，它的维数 是其顶点数减 １。 Ａ 的子集叫做 Ａ 的面。 Ｋ 的维数 是 Ｋ 中诸单形的最大维数。 显然，每个单纯复形 Ｋ 都自然地决定一个抽象复形 Ｋ。 实际上， Ｋ 的每个 单 形 ａ０ ａ１…ａｑ ( ) 规 定 Ｋ 的 一 个 抽 象 单 形 ｃ０ ｃ１…ｃｑ ( ) 。 这样规定的 Ｋ，显然是一个抽象复形， 且称 Ｋ 为 Ｋ 的一个几何实现。 ２ 邻域同调学习算法 设 Ｇ ＝ (Ｖ(Ｇ) ，Ｅ(Ｇ) ) 是一个简单连通图。 显 然，一个简单连通图就是一个单纯复形，根据上述定 义即 可 以 看 成 是 有 限 个 单 形 的 集 合， Ｖ(Ｇ) ＝ ａ０ ，ａ１ ，…，ａα０ －１ { } 表示图 Ｇ 的 α０ 个顶点的集合也 就是图 Ｇ 中所有 ０ 维单形的集合， Ｅ(Ｇ) 表示顶点 之间的所有连接边的集合。 令 Ｘ 和 Ｆ 分别是 Ｇ 的 一个顶点子集和边子集，就以 Ｇ － Ｘ 表示 Ｇ 去掉 Ｘ 中的点及其关联边而得的图， Ｇ － Ｆ 表示 Ｇ 去掉 Ｆ 中的边而得到的图。 设 ａ 是 Ｇ 的任意一个顶点，以 Ｎ(ａ) 表示 ａ 的邻域，那么 Ｎ(Ｘ) 表示 Ｘ 中所有点 邻域的并，即 Ｎ(Ｘ) ＝∪ａ∈Ｘ Ｎ(ａ) 。 基于此，可以构造出一幅给定图形 Ｇ 的领域复 形 Ｎ(Ｇ) ， Ｎ(Ｇ) 是以 Ｇ 的顶点为顶点，以 Ｇ 中具有 公共邻接点的子集为单形的一个抽象复形。 根据抽 象复形的概念，可以看出任意的抽象复形都可以在 欧氏空间实现［２ ５ ］ 。 因此邻域复形在欧氏空间中是 有其相对应的单纯复形的，这里仍以 Ｎ(Ｇ) 记邻域 复形所对应的单纯复形。 除非特殊说明，二者不加 以区别，统称为 Ｇ 的邻域复形。 下文中的 Ｎ(Ｇ) 即 指邻域复形在欧氏空间中所对应的单纯复形。 由于构造出的任意图形的邻域复形 Ｎ(Ｇ) 可以 看成是单纯复形，那么可以将 Ｎ(Ｇ) 剖分成有限个 单 形， 根 据 定 义 ２ 可 表 示 为 Ｎ(Ｇ) ＝ Ａ ｑ ｉ ；ｑ ＝ ０，１，…，ｄｉｍ(Ｎ(Ｇ) ) ，ｉ ＝ １，２，…，αｑ { } ； 对 每个单形取定一个指向并记为 σ ｑ ｉ ，根据定义 １，每 个单形 σ ｑ ｉ 都可以根据顶点坐标线性表示出来；再由 式（１）将 ｑ 维单形线性组合就能得出 Ｎ(Ｇ) 的 ｑ 维 链，这些 ｑ 维链组成的自由交换群即为 Ｎ(Ｇ) 的 ｑ 维链群 Ｃｑ (Ｎ(Ｇ) ) 。 再通过计算同调群，就可以得 出 ２ 个图形之间的一种同调关系。 设有 ２ 个图 Ｇ 、 Ｈ ，如果 Ｎ(Ｇ) 和 Ｎ(Ｈ) 的各阶同调群分别同构，就 称 Ｇ 和 Ｈ 是邻域同调的，记为 Ｇ ≃ Ｎ Ｈ 。 ·３３８· 智 能 系 统 学 报 第 ９ 卷