具有大方差/接近点的 k-means 成本函数的问题以及如何解决它
The problem of the k-means cost function with large variance / close points and how to fix it
所有 k-means 算法都在尝试以一种或另一种方式找到 k 个点，这样如果您将原始数据集中的任何点映射到它离这 k 个点最近的点，您将最小化平方和到这些点的距离。
这个代价函数的问题：
想象一下 k = 2 的以下 1 维情况（即数字而不是向量）。我们将真实点称为 A 和 B，使得 A = -1 和 B = 1。我们将这些点称为最佳 k-means 算法将 return C 和 D，使得 C 和 D 分别对应于 A 和 B。现在假设我们有一个大型数据集，它是从 A 和 B 周围的点创建的，具有一些正态分布。假设方差足够大，我们预计 A 中的点百分比为正，B 中的点百分比为负，因为这些点将映射到错误的点，这将使 C 和 D 更接近除了 A 和 B 之外，随着方差增加，C 和 D 都接近 0。
这个问题的解决方案？
这个问题对我来说听起来很基础，我确信我能找到一些关于它的信息，但是当我搜索时，我找不到任何关于这个问题的信息。所以我的问题是是否有 paper/algorithm 解决这个问题并试图解决这个问题？即使对于假设数据正态分布或对数据分布有任何其他假设的特殊情况？令我感到奇怪的是，我从来没有在任何地方找到任何关于这个问题的提及。
在大多数情况下，k-means 算法 defined 是一个优化问题，可以最小化每个集群的 within-cluster 方差。
在数据无限方差的情况下，你遇到的问题是k-means算法的解non-uniqueness的问题。由于两个基础分布的 true 方差接近无穷大，k-means 问题公式的最优解集是无穷大的。也就是说，任何一组意味着 returns 完全相同的拟合质量（理论上）。在实践中，k-means 算法将简单地 over-fit 数据中的（有限）噪声和 select 任意一对均值。
简而言之，k-means 问题定义不适合您描述的无限方差情况。请注意，在无限方差的情况下，您遇到的问题比 k-means 没有产生有用的解决方案要大得多。不再保证其他基本属性（例如中心极限定理）。
在有限但大方差的情况下，我们预计 k-means 问题是 ill-conditioned。要了解原因，请在 k-means.
的上下文中考虑中心极限定理 (CLT)
CLT 指出在 k-means 期间计算的均值收敛于均值等于（数据的）真实均值且方差等于 sigma^2 / sqrt(n) 的正态分布，其中 sigma^2 是数据的方差，n 是样本数。随着 sigma^2 接近无穷大，n 必须接近无穷大（二次方）以便有合理的机会准确估计真实均值。
简单地说，您的问题的解决方案是对您的数据进行适当的探索性分析，以确定您的方差有多高，以及您拥有的样本数量是否足以满足预期的方差。如果没有，返回并收集更多数据，或应用不同的技术。
此问题是与 so-called 贝叶斯分类误差相关的普遍现象，这是当 类 的分布重叠时可以达到的最低误差。 （在实践中，分类器比这个理论界限更差。）
这显然意味着在重叠的情况下，无论采用何种方法，都无法避免一定比例的误分类。有大猫小虎
事实上，即使不是无处不在，也是非常普遍的情况。改进它的唯一方法是使用额外的特征进行分类，即增加数据的维度 space。比如除了尺寸还要告诉颜色。
所有 k-means 算法都在尝试以一种或另一种方式找到 k 个点，这样如果您将原始数据集中的任何点映射到它离这 k 个点最近的点，您将最小化平方和到这些点的距离。
这个代价函数的问题：
想象一下 k = 2 的以下 1 维情况（即数字而不是向量）。我们将真实点称为 A 和 B，使得 A = -1 和 B = 1。我们将这些点称为最佳 k-means 算法将 return C 和 D，使得 C 和 D 分别对应于 A 和 B。现在假设我们有一个大型数据集，它是从 A 和 B 周围的点创建的，具有一些正态分布。假设方差足够大，我们预计 A 中的点百分比为正，B 中的点百分比为负，因为这些点将映射到错误的点，这将使 C 和 D 更接近除了 A 和 B 之外，随着方差增加，C 和 D 都接近 0。
这个问题的解决方案？
这个问题对我来说听起来很基础，我确信我能找到一些关于它的信息，但是当我搜索时，我找不到任何关于这个问题的信息。所以我的问题是是否有 paper/algorithm 解决这个问题并试图解决这个问题？即使对于假设数据正态分布或对数据分布有任何其他假设的特殊情况？令我感到奇怪的是，我从来没有在任何地方找到任何关于这个问题的提及。
在大多数情况下，k-means 算法 defined 是一个优化问题，可以最小化每个集群的 within-cluster 方差。
在数据无限方差的情况下，你遇到的问题是k-means算法的解non-uniqueness的问题。由于两个基础分布的 true 方差接近无穷大，k-means 问题公式的最优解集是无穷大的。也就是说，任何一组意味着 returns 完全相同的拟合质量（理论上）。在实践中，k-means 算法将简单地 over-fit 数据中的（有限）噪声和 select 任意一对均值。
简而言之，k-means 问题定义不适合您描述的无限方差情况。请注意，在无限方差的情况下，您遇到的问题比 k-means 没有产生有用的解决方案要大得多。不再保证其他基本属性（例如中心极限定理）。
在有限但大方差的情况下，我们预计 k-means 问题是 ill-conditioned。要了解原因，请在 k-means.
的上下文中考虑中心极限定理 (CLT)CLT 指出在 k-means 期间计算的均值收敛于均值等于（数据的）真实均值且方差等于 sigma^2 / sqrt(n) 的正态分布，其中 sigma^2 是数据的方差，n 是样本数。随着 sigma^2 接近无穷大，n 必须接近无穷大（二次方）以便有合理的机会准确估计真实均值。
简单地说，您的问题的解决方案是对您的数据进行适当的探索性分析，以确定您的方差有多高，以及您拥有的样本数量是否足以满足预期的方差。如果没有，返回并收集更多数据，或应用不同的技术。
此问题是与 so-called 贝叶斯分类误差相关的普遍现象，这是当 类 的分布重叠时可以达到的最低误差。 （在实践中，分类器比这个理论界限更差。）
这显然意味着在重叠的情况下，无论采用何种方法，都无法避免一定比例的误分类。有大猫小虎
事实上，即使不是无处不在，也是非常普遍的情况。改进它的唯一方法是使用额外的特征进行分类，即增加数据的维度 space。比如除了尺寸还要告诉颜色。