7,129
个编辑
更改
跳到导航
跳到搜索
第119行：
第119行： + + 第135行：
第137行： + + 第157行：
第161行： −
→算法
“分配”步骤被称为“期望步骤”，而“更新步骤”是最大化步骤，这使得该算法成为广义期望最大化算法的变体。
“分配”步骤被称为“期望步骤”，而“更新步骤”是最大化步骤，这使得该算法成为广义期望最大化算法的变体。
===变体===
===变体===
* Jenks自然断点优化：使用单变量数据的k-means。
* Jenks自然断点优化：使用单变量数据的k-means。
* [[k-medians clustering]]使用每个维度中的中位数而不是均值，这样可以最大程度地减少<math>L_1</math>规范（出租车的几何形状）。
* [[k-medians clustering]]使用每个维度中的中位数而不是均值，这样可以最大程度地减少<math>L_1</math>规范（出租车的几何形状）。
* [[Minkowski加权k均值 Minkowski weighted k-means]]：自动计算聚类特定的特征权重，支持直观的想法，即一个特征在不同的特征上可能具有不同的相关度。<ref>{{Cite journal |last1=Amorim |first1=R. C. |last2=Mirkin |first2=B. |year=2012 |title=Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in ''k''-Means Clustering |journal=Pattern Recognition |volume=45 |issue=3 |pages=1061–1075 |doi=10.1016/j.patcog.2011.08.012 }}</ref>这些权重还可以用于重新缩放给定的数据集，增加了在预期的群集数下优化群集有效性指标的可能性。<ref>{{Cite journal |last1=Amorim |first1=R. C. |last2=Hennig |first2=C. |year=2015 |title=Recovering the number of clusters in data sets with noise features using feature rescaling factors |journal=Information Sciences |volume=324 |pages=126–145 |arxiv=1602.06989 |doi=10.1016/j.ins.2015.06.039 }}</ref>
* [[Minkowski加权k均值 Minkowski weighted k-means]]：自动计算聚类特定的特征权重，支持直观的想法，即一个特征在不同的特征上可能具有不同的相关度。<ref>{{Cite journal |last1=Amorim |first1=R. C. |last2=Mirkin |first2=B. |year=2012 |title=Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in ''k''-Means Clustering |journal=Pattern Recognition |volume=45 |issue=3 |pages=1061–1075 |doi=10.1016/j.patcog.2011.08.012 }}</ref>这些权重还可以用于重新缩放给定的数据集，增加了在预期的群集数下优化群集有效性指标的可能性。<ref>{{Cite journal |last1=Amorim |first1=R. C. |last2=Hennig |first2=C. |year=2015 |title=Recovering the number of clusters in data sets with noise features using feature rescaling factors |journal=Information Sciences |volume=324 |pages=126–145 |arxiv=1602.06989 |doi=10.1016/j.ins.2015.06.039 }}</ref>
* Mini-batch k-means：针对不适合内存的数据集使用“mini batch”样本。<ref>{{Cite conference |last=Sculley |first=David |date=2010 |title=Web-scale ''k''-means clustering |url=http://dl.acm.org/citation.cfm?id=1772862 |publisher=ACM |pages=1177–1178 |accessdate=2016-12-21 |booktitle=Proceedings of the 19th international conference on World Wide Web }}</ref>
* Mini-batch k-means：针对不适合内存的数据集使用“mini batch”样本。<ref>{{Cite conference |last=Sculley |first=David |date=2010 |title=Web-scale ''k''-means clustering |url=http://dl.acm.org/citation.cfm?id=1772862 |publisher=ACM |pages=1177–1178 |accessdate=2016-12-21 |booktitle=Proceedings of the 19th international conference on World Wide Web }}</ref>
===Hartigan-Wong方法===
===Hartigan-Wong方法===
Hartigan和Wong的方法<ref name="hartigan19792" /> 提供了k-means算法的一种变体，它随着不同的解决方案更新而朝着最小平方和问题的局部最小值发展。该方法是一种局部搜索，只要此过程可以改善目标函数，它就会反复尝试将样本重新放置到其他聚类中。如果无法通过改善目标将任何样本重定位到其他群集中，则该方法将停止（以局部最小值计）。以与经典k-means类似的方式，该方法仍然是一种启发式方法，因为它不一定保证最终解是全局最优的。
Hartigan和Wong的方法<ref name="hartigan19792" /> 提供了k-means算法的一种变体，它随着不同的解决方案更新而朝着最小平方和问题的局部最小值发展。该方法是一种局部搜索，只要此过程可以改善目标函数，它就会反复尝试将样本重新放置到其他聚类中。如果无法通过改善目标将任何样本重定位到其他群集中，则该方法将停止（以局部最小值计）。以与经典k-means类似的方式，该方法仍然是一种启发式方法，因为它不一定保证最终解是全局最优的。
::<math>\Delta(x,n,m) = \frac{ \mid S_n \mid }{ \mid S_n \mid - 1} \cdot \lVert \mu_n - x \rVert^2 -
::<math>\Delta(x,n,m) = \frac{ \mid S_n \mid }{ \mid S_n \mid - 1} \cdot \lVert \mu_n - x \rVert^2 -
\frac{ \mid S_m \mid }{ \mid S_m \mid + 1} \cdot \lVert \mu_m - x \rVert^2</math>。
\frac{ \mid S_m \mid }{ \mid S_m \mid + 1} \cdot \lVert \mu_m - x \rVert^2</math>。
==k-means算法缺点==
==k-means算法缺点==