算法目的

提出问题

• 现实中，一个对象可能存在多个身份，属于多个类别。比如，一个研究者会研究多个领域，在聚类时，不能单纯说其只属于某一个领域。如下图，重叠的部分就是即研究计算机也研究石油的研究者。
  
• 一般聚类是解决静态数据的聚类，数据集没有变过，但是现实世界中，很多数据是动态的，随着时间变化而更新，所以存在增量聚类问题，将新的数据聚类，就会更新已有的聚类信息。

解决方法

• 重叠聚类
• 增量聚类
• 三支决策
• 树

思路分析

重叠聚类

重叠聚类：采用两个集合表示形式表示一个类，

$\underline{C_{i}}$Ci​​表示下边界，图中粉色部分。

$\overline{C_{k}}$Ck​​表示上边界，图中蓝色部分+粉色部分。

他们之间有这样一个关系：

$\underline{C_{i}}$Ci​​表示正域，POS ，即图中粉色中心域，这里面的对象肯定属于这个类别。

$\overline{C_{k}}-\underline{C_{k}}$Ck​​−Ck​​表示边界域 BND，即蓝色部分，这部分里面的对象可能属于也可能不属于这个类别（不确定）。

$U-\overline{C_{k}}$U−Ck​​表示负域，即图中空白区域，，与此类别无关的其他对象。


当不管是正域还是边界域和其他类别的正域或边界域有交集的，就是有重叠的部分，即存在属于多个类别的对象。用这样的形式表示重叠聚类。

增量聚类

首先根据初始数据聚类，建立搜索树，然后计算增量与初始聚类代表点的相似度来更新聚类。

所提算法

静态重叠聚类

计算代表点

1. 计算样本之间的距离，得到距离矩阵。
2. 根据阈值挑选近邻样本，近邻样本多的点作为代表点的几何中心。
3. 删除距离矩阵中该中心点的邻近点所在行。
4. 重复2、3步，直到选择完所有点。

例1：

初始数据
距离矩阵

选出两两距离<1.5最多的点，$x_{9}$x9​作为第一个代表点$r_{1}$r1​的集合中心点，$cover(r_{1})=\{x_{2},x_{3},x_{5},x_{6},x_{7},x_{8},x_{9}\}$cover(r1​)={x2​,x3​,x5​,x6​,x7​,x8​,x9​}，删除$x_{2},x_{3},x_{5},x_{6},x_{7},x_{8},x_{9}$x2​,x3​,x5​,x6​,x7​,x8​,x9​所在的行，得到table3：

在比较$x_{1},x_{4},x_{10}$x1​,x4​,x10​中谁邻居数最多，发现是$x_{1}$x1​最多，则把$x_{1}$x1​作为$r_{2}$r2​的几何中心点，得到$cover(r_{2})=\{x_{1},x_{2},x_{3},x_{5},x_{10}\}$cover(r2​)={x1​,x2​,x3​,x5​,x10​}，删除邻居所在行$x_{1},x_{10}$x1​,x10​，只剩一个行元素$x_{4}$x4​，同理得到$cover(r_{3})=\{x_{4}\}$cover(r3​)={x4​}。代表点计算完毕。

构建无向图

根据此公式，计算两个代表区域（$cover()$cover()）的相似度，设定两个阈值$\alpha、\beta$α、β 当$SimilarityRR(r_{i},r_{j})\geq\alpha$SimilarityRR(ri​,rj​)≥α则在这两个代表区域之间画一条强链接实线，当$\beta<SimilarityRR(r_{i},r_{j})<\alpha$β<SimilarityRR(ri​,rj​)<α，则两个代表区域之间画弱连接虚线。
形成无向图

聚类

搜索上述无向图，其中的由强链接构成的强连通子图就是一类，对于每个这样的子图，与其对应的对象形成一个簇的正区域。然后连接它的弱连接区域作为该类的边界域。