k 均值聚类
目标：将数据划分为两个或更多集群。
k 均值聚类背后的想法是获取一堆数据并确定数据中是否存在任何自然聚类（相关对象组）。
k-Means算法是一种所谓的无监督学习算法。我们事先不知道数据中存在什么模式——它没有正式的分类——但我们想看看是否可以以某种方式将数据分组。
例如，您可以使用 k-Means 来查找图像中最突出的 3 种颜色，方法是告诉它根据颜色值将像素分为 3 个簇。或者，您可以使用它将相关新闻文章分组在一起，而无需事先决定使用哪些类别。该算法将自动找出最好的组。
k-Means 中的“k”是一个数字。该算法假设数据中有k 个中心，各种数据元素分散在这些中心周围。最接近这些所谓质心的数据被分类或分组在一起。
k-Means 不会告诉您每个特定数据组的分类器是什么。将新闻文章分组后，并没有说第 1 组是关于科学的，第 2 组是关于名人的，第 3 组是关于即将到来的选举等。你只知道相关的新闻报道现在在一起，但不一定知道是什么这种关系意味着。k-Means 仅有助于尝试查找可能存在的聚类。
算法
k-Means 算法的核心实际上非常简单。
首先，我们选择k 个随机数据点作为初始质心。然后，我们重复以下两个步骤，直到找到集群：
- 对于每个数据点，找到它最接近的质心。我们将每个点分配给最近的质心。
- 将质心更新为其最近数据点的均值（即平均值）。我们移动质心，使其真正位于簇的中心。
我们需要多次重复此操作，因为移动质心会改变属于它的数据点。这个过程会反复进行，直到一切稳定下来。那就是我们达到“收敛”的时候，即质心不再移动的时候。
k 均值所需的一些参数：
- k：这是尝试定位的质心数。如果您想对新闻文章进行分组，则这是要查找的组数。
- 收敛距离：如果在特定的更新步骤后所有质心移动的距离小于此距离，则我们完成。
- 距离函数：计算数据点距质心的距离，以找到它们最接近的质心。有许多距离函数可以使用，但最常见的是欧几里得距离函数就足够了（你知道，毕达哥拉斯）。但这通常会导致在更高维度上无法达到收敛。
让我们看一个例子。
良好的集群
第一个示例显示 k-Means 查找所有三个簇。在所有这些示例中，圆圈代表数据点，星形代表质心。
在第一次迭代中，我们随机选择三个数据点并将质心放在它们上面。然后在随后的每次迭代中，我们找出哪些数据点最接近这些质心，并将质心移动到这些数据点的平均位置。重复此过程，直到达到平衡并且质心停止移动。
初始质心的选择是偶然的！我们发现了左下簇（用红色表示），并且在中心和左上簇上表现得很好。
注意：这些示例旨在展示 k 均值和查找聚类的确切性质。这些例子中的簇很容易被人眼识别：我们看到左下角有一个，右上角有一个，中间也可能有一个。然而，在实践中，数据可能有很多维度，并且可能无法可视化。在这种情况下，k-Means 比人眼更擅长这项工作！
不好的聚类
接下来的两个示例强调了 k 均值的不可预测性以及它并不总是能找到最佳聚类。
正如您在本示例中所看到的，最初的质心彼此都有点太接近，而蓝色的质心并没有到达一个好的位置。通过调整收敛距离，我们应该能够改善质心与数据的拟合。
在这个例子中，蓝色星团永远无法真正与红色星团分离，因此卡在了那里。
改善不良聚类
在这些“糟糕”聚类的例子中，算法陷入了局部最优。它确实找到了集群，但它们并不是划分数据的最佳方式。为了增加成功的机会，您可以多次运行该算法，每次都使用不同的点作为初始质心。您选择能提供最佳结果的聚类。
要计算聚类的“好”程度，您需要找到每个数据点与其聚类的距离，并将所有这些距离相加。这个数字越低越好！这意味着每个簇实际上位于一组数据点的中心，并且所有簇的大小大致相同并且间隔均匀。
代码
这就是 Swift 中的算法的样子。该points数组包含作为对象的输入数据Vector。输出是Vector表示找到的簇的对象数组。
func kMeans(numCenters: Int, convergeDistance: Double, points: \[Vector\]) \-> \[Vector\] {
// Randomly take k objects from the input data to make the initial centroids.
var centers \= reservoirSample(points, k: numCenters)
// This loop repeats until we've reached convergence, i.e. when the centroids
// have moved less than convergeDistance since the last iteration.
var centerMoveDist \= 0.0
repeat {
// In each iteration of the loop, we move the centroids to a new position.
// The newCenters array contains those new positions.
let zeros \= \[Double\](count: points\[0\].length, repeatedValue: 0)
var newCenters \= \[Vector\](count: numCenters, repeatedValue: Vector(zeros))
// We keep track of how many data points belong to each centroid, so we
// can calculate the average later.
var counts \= \[Double\](count: numCenters, repeatedValue: 0)
// For each data point, find the centroid that it is closest to. We also
// add up the data points that belong to that centroid, in order to compute
// that average.
for p in points {
let c \= indexOfNearestCenter(p, centers: centers)
newCenters\[c\] += p
counts\[c\] += 1
}
// Take the average of all the data points that belong to each centroid.
// This moves the centroid to a new position.
for idx in 0..<numCenters {
newCenters\[idx\] /= counts\[idx\]
}
// Find out how far each centroid moved since the last iteration. If it's
// only a small distance, then we're done.
centerMoveDist \= 0.0
for idx in 0..<numCenters {
centerMoveDist += centers\[idx\].distanceTo(newCenters\[idx\])
}
centers \= newCenters
} while centerMoveDist \> convergeDistance
return centers
}注意：KMeans.swift中的代码比上面的列表稍微高级一些。它还为集群分配标签，并有一些其他技巧。一探究竟！
表现
k-Means 被归类为 NP-Hard 类型的问题。这意味着几乎不可能找到最佳解决方案。初始质心的选择对生成的簇的最终结果有很大影响。即使在二维空间中，找到精确的解决方案也是不可能的。
从上面的步骤可以看出，复杂性实际上并没有那么糟糕——它通常被认为是O(kndi)的量级，其中k是质心的数量，n是d维向量的数量，并且i是收敛的迭代次数。
数据量对 k 均值的运行时间具有线性影响，但调整您希望质心收敛的程度会对迭代次数产生很大影响。作为一般规则，k与向量的数量相比应该相对较小。
通常，随着添加更多数据，某些点可能位于两个质心之间的边界，因此这些质心将继续来回反弹，并且需要调整收敛距离以防止这种情况发生。
评论已关闭