1.论文简介

• 论文出处：IEEE TRANSACTIONS ON CYBERNETICS（SCI 1区、CCF-B）

• 论文链接

• 暂无代码

• 【摘要】：脑电图（EEG）是一种复杂、微弱、多变量、非线性和非平稳的时间序列，近年来被广泛应用于神经认知障碍诊断和脑机接口开发。由于其特殊性，传统的无监督时间序列学习方法无法很好地解决无标记脑电图的问题。在本文中，我们处理了无标记脑电图时间序列聚类问题，并提出了一种新颖的脑电图聚类算法，我们称之为 mwcEEGc。该算法的思路是将脑电图聚类映射到改进的弗雷切相似性加权脑电图图中的最大加权簇（MWC）搜索。mwcEEGc 考虑了所构建脑电图图中顶点和边的权重，并根据其相似性权重对脑电图进行聚类，而不是计算聚类中心点。据我们所知，这是首次尝试使用 MWC 搜索对未标记的脑电图试验进行聚类。mwcEEGc 在簇内紧凑性和簇间分散性方面都实现了高质量的聚类。通过在 14 个真实世界脑电图数据集上使用标准聚类有效性标准进行详细实验，我们证明了 mwcEEGc 优于 10 种最先进的无监督学习/聚类方法。我们还发现 mwcEEGc 满足聚类的理论特性，如丰富性、一致性和阶次独立性。

2.问题背景

• 脑电图是一种特殊的时间序列数据，它具有复杂、弱、多元、非线性和非平稳的特点，传统的无监督时间序列学习方法不能很好地处理这类数据

3.拟解决的问题

• 如何使用无监督技术处理无标记脑电图数据

4.主要贡献

• 将脑电图聚类问题表述为相似加权脑电图的MWC搜索

• 提出了一种新的算法mwcEEGc，该算法在使用MWC对EEG trials进行聚类时，同时考虑了边的权重和顶点的权重

• mwcEEG满足聚类理论的三个属性:丰富度;一致性;顺序独立性。

5.提出的方法

5.1总体框架

• 脑电图相似性度量：测量两两EEG trails的相关性

• EEG图的构建：形成一个带权无向完全EEG图，包括顶点权值和边权值，其中EEG trails转换为顶点，任意两个顶点之间用边连接。同时，提出了一种基于顶点权值和边权值的改进权值函数

• EEG聚类：根据相似阈值从带权EEG图中搜索群组，使所有群组的总权重最大化。

5.2预备知识

5.2.1Fréchet距离

• Fréchet distance：就是狗绳距离：主人走路径A，狗走路径B，各自走完这两条路径过程中所需要的最短狗绳长度
  

• 具体细节请参考 弗雷切距离

• Similarity Measures为什么选择FD？

1. FD与其它距离度量的优缺点比较
   

2. FD与其他距离度量的EEG聚类对比
   

5.2.2Maximum-Weight Clique

• 最大权重团问题(MWCP)是一种搜索带权图中的clique的技术，从而使顶点和边的权重最大化。

• 给定一个无向加权图 $G=(V,E,\eta ,\mu )$，其中 $V$ 和 $E$ 分别定义顶点集和边集。 η : V → { 0 } ∪ R + \eta: V \rightarrow \{0\} \cup \mathbb{R}^+ η:V→{0}∪R+ 和 μ : E → { 0 } ∪ R + \mu: E \rightarrow \{0\} \cup \mathbb{R}^+ μ:E→{0}∪R+ 分别表示顶点权值和边权值。即为G的总权重

• 定义：设 N n = { 1 , … , n } N_n = \{1, \dots, n\} Nn​={1,…,n}，其中$n=|V|$，且对于边 e i j = { i , j } ∈ E e_{ij} = \{i, j\} \in E eij​={i,j}∈E。当顶点$v_i$或边$e_{ij}$（其中$i,j$分别表示顶点$v_i$和$v_j$）被选入一个clique时，有$v_i=1$，$v_j=1$，$e_{ij}=1$。否则，$v_i=0$，$v_j=0$，$e_{ij}=0$。因此， v i , v j , e i j ∈ { 0 , 1 } v_i, v_j, e_{ij} \in \{0, 1\} vi​,vj​,eij​∈{0,1}。

• 现有的求MWCP的方法只考虑了顶点的权值或边的权值，而没有同时考虑两者。当只考虑顶点权值或将边权值转化为顶点权值时，MWCP就相应转化为搜索具有最大基数的完整子图的极大团问题(MCP)。在这种情况下，MWCP可以用二进制模型等效地解释：
  
  其中$n=|V|$，$w_i$为顶点$v_i$的权值；$x_i$是与顶点集$v_i$相关的二进制变量；$E$定义了互补图$G$的边集。

5.3MWCEEGC聚类算法

5.3.1理论基础

• 在刺激特定的大脑活动时，得到大部分相似的脑电图信号的概率大于得到大部分不相似的脑电图信号的概率
• 形式化定义为：刺激大脑活动A，得到相似脑电图的概率为 $p$，则相应得到不同脑电图的概率为 $1-p$。当 $0\le 1-\mathbf{p}\le \mathbf{p}$ 时，激活A n≥2次，设 $p(E_k\ge \frac{n}{2})$ 为得到等于或大于 $k\ge \frac{n}{2}$ 个相似脑电图信号的概率，$p(E_k\le \frac{n}{2})$ 为得到等于或小于 $k\le \frac{n}{2}$ 个相似脑电图信号的概率，则 $p(E_k\ge \frac{n}{2})\ge p(E_k\le \frac{n}{2})$。

5.3.2EEG图的边权

传统FD的改进

• 为什么要改进？传统的FD (CFD)主要度量的是全局趋势，而忽略了局部结构，因此我们可以利用局部趋势对CFD进行改进。
• 如何计算局部趋势？设 $tri=(a_1,\dots ,a_h),trj=(b_1,\dots ,b_l)$ 是 EEG 数据集中的两个 EEG 数据，则 $tri，trj$ 的局部趋势 local tendency 可以由以下公式进行计算：

• 其中，$r$为EEG子序列的长度，$1\le r<o$，其中 o = min ⁡ { h , l } o = \min\{h, l\} o=min{h,l}；$ap+r-ap$在(5)中表示选取$r$个点来测量局部趋势，通常$r=1$，因为$r\ge 2$可能导致忽略长度$\le r$的较小脑电图段的更多局部趋势；$LocT(tri,trj)\in [-1,1]$，其中正值表示两个EEG的局部倾向越相似，值越大表示两个EEG的局部倾向越相似，反之则两个EEG的局部倾向越相反。

改进的相似度计算

• 
  其中 $\delta F(tri,trj)$ 为CFD相似度，$\lambda \in [0,1]$。通常，$\lambda$ 取 $0.5$，以平衡全局相似度和局部趋势。

• 根据局部趋势和全局趋势，将 $n$ 次脑电图试验的归一化相似度构建对角相似度矩阵 $S_{n\times n}$，称为边权矩阵 $\mu$：

CFD和IFD的对比

• 

5.3.3EEG图的顶点权重

• 顶点权重${\eta }_i$定义如下：
  
  当$|\text{Tri}|=1$时，$\eta =0$；${\eta }_i$表示tri对其余trj的排序，即当tri被选入到一个聚类C中，顶点权重最高的trj，可能将其划分到类簇C中。

5.3.4EEG图的权重计算

• 权重矩阵$\text{C}$可表示为：
  
• $\text{C}$中最大的顶点$v_t$可以作为下一潜在候选点加入clique中
  

5.3.5mwcEEGc算法

算法伪代码

算法描述

• 给定一个基于改进的Fréchet相似加权脑电图图 $GW=(V,E,\eta ,\mu )$，其中 η : V → { 0 } ∪ R + \eta: V \rightarrow \{0\} \cup \mathbb{R}^+ η:V→{0}∪R+ 和 μ : E → { 0 } ∪ R + \mu: E \rightarrow \{0\} \cup \mathbb{R}^+ μ:E→{0}∪R+ 分别表示顶点和边的权值。目标是寻找一个族 C = { η 1 , … , η m } C=\{\eta_1,\dots,\eta_m\} C={η1​,…,ηm​}（$m\ge 2$），以最大化：
  ，其基数用正整数$N_1$表示，$N_1\dots N_m$满足
  

• 总的权重矩阵$w_{ij}$计算如下：
  
  其中 δ = { δ 0 = 1 , δ 1 , . . . , δ m − 1 , δ m = 0 } \delta = \{\delta_0 = 1, \delta_1, . . . , \delta_{m-1}, \delta_m = 0\} δ={δ0​=1,δ1​,...,δm−1​,δm​=0}，且为降序序列

• （11）式可以等价写为：
  
  

• 搜索m个簇需要$m-1$个阈值；顶点${\mathbf{v}}_{\mathbf{t}}$加入clique $C$需要同时满足两个条件：
  
  
  但是实际上，一旦$\delta$被设定，只要满足条件1，就可以将$vt$加到$C$上

算法动态演示

• 

5.3.6算法复杂度分析

• mwcEEGc算法复杂度由改进的Fréchet-based相似度计算和EEG聚类两部分组成，$$O\left(\max \{n^2\cdot l^2\cdot \frac{\log \log l}{\log \log l},m{n}^3\right\})$$

6.实验

6.1数据集

• 数据集：14个脑电图数据集，包括慢皮层电位(SCPs)、心理意象脑电图(EEG)、运动意象脑电图(EEG)和手部运动脑电图(EEG)等
  

• 数据集下载链接

6.2预处理

1. z归一化
2. 删除放松期、空闲期和准备期的非目标和非特异性脑电图
3. 去除原始标记

6.3参数设置

• 阈值δ根据脑电图相似度的离散概率分布d(δ)进行设置，
  

• δ根据公式（15）进行设置
  

6.2实验结果

• EEG聚类性能分析
  

• 相似性度量的影响分析
  

• 执行时间
  

• 聚类算法所满足的聚类特性比较
  

7.结论

• 本文提出的mwcEEGc通过将EEG映射到改进的Fréchet相似加权EEG图中最大权重的搜索团来对EEG trials进行聚类，同时考虑了顶点权值和边权值，且不需要计算聚类质心

• 在14个脑电信号数据集上，针对6个聚类评价标准与10种最先进的聚类方法进行了实验比较，证明了mwcEEGc的优越性。

• mwcEEGc在理论上满足四个关键聚类属性中的三个:1)丰富度;2)一致性;3)顺序无关性，而这十条基线只满足一个:比例不变性。

• 本文中的mwcEEGc对所有EEG信号通道一视同仁，在未来的工作中，mwcEEGc聚类对事件相关通道或脑电信号通道选择的权重更大

8.个人观点

• 本文主要探讨了针对EEG数据集的聚类方法mwcEEGc。EEG数据具有一系列独特特性，如较弱的数据强度、高复杂性和振荡性等，这使得传统的基于特征选择、距离、形状和shapelets的方法在该领域效果不佳。然而，尽管传统方法在EEG数据上的表现有限，mwcEEGc依然在这一特定类型的数据集上取得了一定的成功。

• 在度量方式方面，本文提出了使用FD（Fused Distance）作为新的距离度量标准，并与传统的ED、DTW等度量方式进行了比较。FD的引入被认为是本文的一大创新点，它展示了对传统方法的改进和扩展。此外，mwcEEGc通过将EEG聚类问题映射到最大权重团的搜索（MWC），并在构建的EEG图中考虑顶点和边的权值来解决问题。这一过程的核心在于最大化权重的搜索过程，其中的关键参数δ直接影响着聚类的划分和性能。

• 综上所述，mwcEEGc的创新之处在于其将EEG数据聚类问题转化为MWC搜索，并引入了FD度量方式，这不仅在理论上有利于满足某些聚类属性，而且在实际应用中也提升了算法的适应性和效能。然而，尽管mwcEEGc在该领域表现出色，但其与深度学习方法的比较尚不明确，因此其相对于其他深度学习算法的优越性仍有待进一步验证。

9.Reference

• 弗雷切距离

• 最大权重算法