从k-mean聚类中删除异常值

Question

我有许多包含10个XY坐标的小数据集。我正在使用Matlab（R2012a）和k-means来获取质心。在某些聚类中（如下图所示），由于我的数据集太小，一个离群值会破坏我的质心值。有没有一种简单的方法来排除这些点？据说Matlab有一个“排除离群值”的函数，但我在工具菜单中找不到它。谢谢你的帮助！（是的，我是新手:-)）

- carro

---

我认为你要找的词是“异常值”（http://en.wikipedia.org/wiki/Outlier），而不是“轮廓线”。也许这会帮助你更容易地找到解决方案。 - Medo42

最好提及你正在使用的软件并相应地进行标记。 - kotekzot

抱歉，我不小心写了草稿;（我已经做了很多搜索，但我是Matlab的初学者，到目前为止遇到的代码相当复杂。看了ORC和ODIN，但根据Matlab帮助函数，工具栏中应该有一个叫做“排除异常值”的东西，但我找不到它，我正在使用R2012a版本。 - carro

Answer 1

k-means 对数据集中的异常值非常敏感。原因很简单，即 k-means 尝试优化平方和。因此，大偏差（例如异常值）会得到很大的权重。

如果您有一个带有异常值的嘈杂数据集，则最好使用具有专门噪声处理的算法，例如DBSCAN（密度聚类应用程序与噪声）。请注意首字母缩写中的“N”：Noise。与例如 k-means 但也许其他许多聚类算法不同，DBSCAN 可以决定不聚类低密度区域中的对象。

- Erich Schubert

Answer 2

你正在寻找类似于“异常值去除”的东西，正如其他人所链接的那样，“没有严格的数学定义来说明什么构成了异常值” - http://en.wikipedia.org/wiki/Outlier#Identifying_outliers。

当你进行无监督聚类时，异常值检测变得更加困难，因为你既要学习聚类是什么，又要确定哪些数据点对应于“没有”聚类。

一个简单的定义是将所有与每个其他数据点“远离”的数据点视为异常值。例如，您可以考虑删除与任何其他点的最小距离最大的点：

x = randn(100,2); 
x(101,:) = [10 10];  %a clear outlier
nSamples = size(x,1);

pointToPointDistVec = pdist(x);
pointToPointDist = squareform(pointToPointDistVec);
pointToPointDist = pointToPointDist + diag(inf(nSamples,1)); %remove self-distances; set to inf

smallestDist = min(pointToPointDist,[],2);
[maxSmallestDist,outlierInd] = max(smallestDist);

你可以多次迭代以上步骤以逐步删除点。请注意，这样做将不会删除恰好具有至少一个附近邻居的离群值。如果您阅读了WIKI页面并看到可能更有帮助的算法，请尝试实现它并询问特定方法的问题。

- Pete