clustering聚类分析内容摘要：
标准 • 通常是 NPHard • 多项式算法 并非精确的最优解，而是相对优的解或者局部的最优解 算法一 • 判断标准： kcenter criterion 最小化任意点到所分的类中心的最大距离 • 基本思想： 存在 k个半径为 r的球体覆盖所有点 存在最大距离为 r的划分 算法一 • 步骤 每次选取一个未被覆盖的 数据 点作为一个类的中心，作半径为 r的球体，覆盖某些点。 重复 k次得到 k个类。 算法一 • 不靠谱。 有点 …… • 但是： 若存在最大距离为 r/2的划分，这个算法一定能找到最大距离不超过 r的划分。 证明：反证法 假设无法找到最大距离为 r的划分 至少一个点不在 k个半径为 r的球体中 存在 k+1个点两两的距离大于 r k个半径为 r/2的球体无法覆盖这 k+1个点 不存在最大距离为 r/2的划分（矛盾） 类中心 • 要求类中心必须是数据点 类的划分有限，可穷举 • 类中心可以是空间中的任意点（使距离函数最小的点） 结果精确 • 某。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。