Stochastic Outlier Selection algorithm

type

status

date

slug

summary

🤔算法的输入

SOS是一种无监督的离群值选择算法。因此，SOS只需要一个未标记的数据集，一个未标记的数据集意味着标签“异常”和“正常”是不可用的。因此，SOS不知道领域专家是否认为真实世界的观测结果（对应于数据点）是异常的还是正常的。然而，SOS能够将数据集中的数据点分类为“离群值”或“内点”。

未标记数据集中的数据点数量用n表示.在我们对SOS的描述中，每个数据点都用一个m维的实值特征向量表示因此，一个数据点可以看作是m维欧几里得空间中的一个点。数据集是一个的矩阵。

图4.2中展示了我们描述的SOS使用的示例数据集

数据集中包含6个数据点，每个点有两个维度。矩阵X中的单元格颜色对应着数据点的特征值。数据点的特征被用来度量数据点对之间的差异。数据点和数据点之间的不相似度是一个由非相似度度量计算的非负标量。在我们的描述和实验中，我们使用欧几里德距离作为对数据点之间的不同度量。

距离是对称的且与自身的距离为0，图中绿线长度代表距离，D中颜色亮度也代表距离

将不同度转化为相似矩阵

如上所述，我们使用亲和性来量化从一个数据点到另一个数据的关系。我们对亲和性的定义基于用于降维问题的定义（Hinton和Roweis，2003；Goldberger、Roweis、Hinton和Salakhuddinov，2005；van der Maaten和Hinton，2008）

定义：（Affinity）

设代表数据点之间的距离，那么与之间的亲和度（相似度）可以表示为：

简而言之，(1)表明，在具有平均和方差的高斯分布下，数据点与数据点的亲和力与和的概率密度成正比。图4.3提供了方程4.2的三个方差值的图形比较。方差越小，亲和力衰减得越快。方差越大，相似性影响的亲和性越小。作为一个极端的例子，无论不同性有多高（因为e＝1），无限高的方差都会产生1的亲和性。换句话说，高斯分布变为均匀分布。

SOS只有一个参数，成为困惑参数，用h表示。困惑参数h可以与参数墨最近邻进行比较，有两个重要的区别。首先，因为亲和性平滑衰减，“成为一个邻居”不是一个二进制性质，而是一个平滑性质。事实上，在下一小节中，我们使用随机邻域图将“作为一个邻域”形式化为一个概率性质。其次，与参数k不同，困惑度不被限制为一个整数，但可以是1和n−1之间的任何实数。换句话说，一个数据点可以有最小1和最大n−1有效邻居。因此，困惑可以被解释为对有效邻居数量的平滑测量。因为一个数据点与自身没有关联，即，它从来都不是它自己的邻居，这意味着（我们稍后将看到）只有其他数据点的离群值概率。

每个方差的值是使用自适应方法确定的，这样每个数据点具有相同数量的有效邻居。自适应方法为每个数据点产生不同的方差，导致亲和力是不对称的。精确地说，亲和力和只平等当(1)不同和相等，这总是欧几里得距离但不需要与其他不同的措施，和(2)方差和是相等的，这是很少的，除非两个数据点有同样不同于自己的邻居。作为非对称亲和度的反例，我们提到了Maaten和Hinton（2008）的降维算法，它有意地对称数据点之间的亲和度（即），这样不同的数据点就不是孤立的，而是在低维映射中与其中一个集群连接。然而，SOS的目的是将这些不同的数据点分类为离群值，因此，并不对称亲和性。

图4.4显示了示例数据集中的数据点的方差。六个圆的半径对应于六个数据点的方差（请注意，这些圆并不代表边界）。

利用不同度矩阵和式(1)，我们计算每个数据点与其他每个数据点的亲和性，从而得到亲和性矩阵，与的相似在于它们都是nn的且对角为0，不同之处在于亲和矩阵非对称。

📝基于亲和关系的邻域图

在我们对SOS的描述的其余部分中，我们使用图论，因为

（1）它提供了一个坚实的数学框架来执行具有亲和性的计算，并且

（2）它允许我们推导离群概率。为了使用顶点和有向边显式地建模数据点及其关系（即亲和关系），我们生成了一个随机邻域图（SNG）。

顶点集V与数据集x相关联。因此，每个顶点对应于数据点。在顶点之间生成有向边取决于绑定的概率。因此，我们首先引入(A)绑定概率的概念，然后(B)定义SNG的生成过程。最后，我们引入(C)作为一个SNG的离群值的二进制性质。

A 绑定概率

绑定概率是顶点绑定到顶点的概率，即从到生成一条有向边的概率。我们用‘i→j’来表示从到的有向边。绑定概率与数据点与数据点的亲合力成正比（用∝表示）。

这等价于亲和关系的标准化

同样，是0.通过4.5式得到了绑定概率矩阵

一个顶点的绑定概率B矩阵在形式上是一个概率分布：

如果用图来表示则是许多全连接图，每条边的权值为绑定概率

生成一个随机邻域图

通过引入绑定概率，我们正式地讨论了随机邻域图（SNG），并讨论了SNG的生成过程。我们通过两个假设和四个后续结果来这样做。然后，我们描述了有向边集的生成过程。

定义随机邻域图：随机邻域图（SNG）是一个具有垂直点集合V和有向边缘G集合的图)。设矩阵X是一个包含n个数据点的数据集。对于每个数据点∈X，添加一个顶点到V。

有向边集合是由以下随机绑定过程生成的。设是顶点的绑定分布。让每个顶点独立绑定一个其他的顶点,其中j是从绑定分布中的随机采样。设ij是一条有向边。

通过图4.7来说明。4.7显示了如图所示的绑定矩阵B的示例数据集的三种可能的SNG。

首先，SNG总有n条有向边，因为每个顶点都连接到一个顶点。其次，尽管在给定一个数据集X时，SNG的顶点是固定的，但每个生成的SNG可能是不同的，因为有向边是使用随机绑定过程生成的。第三，每个绑定分布都基于亲和分布，从而反映了数据点之间的关系。第四，SNG没有自循环。第五，顶点独立绑定。第六，顶点出度为1.第七，绑定过程随机，可以有多个顶点绑定到同一个顶点。