没有合适的资源?快使用搜索试试~ 我知道了~
k-中心点:一种基于代表对象的技术.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 86 浏览量
2022-07-11
12:52:53
上传
评论
收藏 413KB PDF 举报
温馨提示
试读
3页
k-中心点:一种基于代表对象的技术.pdf 学习资料 复习资料 教学资源
资源推荐
资源详情
资源评论
k-中心点:一种基于代表对象的技术
本文摘选自:数据挖掘: 概念与技术(原书第 3 版).
Jiawei Han, Micheline Kamber, Jian Pei 著; 范明, 孟小峰译. 机械工业出版社
摘要:如何修改 k-均值算法,降低它对离群点的敏感性?可以不采用簇中对象的均值作为参
照点,而是挑选实际对象来代表簇,每个簇使用一个代表对象。其余的每个对象被分配到与其
最为相似的代表性对象所在的簇中。于是,划分方法基于最小化所有对象与其对应的代表对象
之间的相异度之和的原则来进行划分。k-中心点聚类通过最小化绝对误差,把 n 个对象划分到 k
个簇中。
关键词:聚类;k-均值;k-中心点;代表对象
k-均值算法对离群点敏感,因为这种对象远离大多数数据,因此分配到一个簇时,它们可能严重地扭
曲簇的均值。这不经意间影响了其他对象到簇的分配。正如在例 1 中所观察到的,“k-均值:一种基于形
心的技术”小节(1)式平方误差函数的使用更是严重恶化了这一影响。
例 1 k-均值的缺点。考虑一维空间的 7 个点,它们的值分别为 l、2、3、8、9、10 和 25。直观地,通
过视觉观察,我们猜想这些点划分成簇{1,2,3}和{8,9,10},其中点 25 被排除,因为它看上去是一个
离群点。K-均值如何划分这些值?如果我们以 k=2 和“k-均值:一种基于形心的技术”小节(1)式使用 k-均
值,划分{{1,2,3},{8,9,10,25}}具有簇内变差(1-2)
2
+(2-2)
2
+(3-2)
2
+(8-13)
2
+(9-13)
2
+(10-13)
2
+(25-
13)
2
=196 。 其 中 , 簇 {1 , 2 , 3} 的 均 值 为 2 , 簇 {8 , 9 , 10 , 25} 的 均 值 为 13 。把 这一 划 分 与 划 分
{{1,2,3,8},{9,10,25}}比较,后者的簇内变差为(1-3.5)
2
+(2-3.5)
2
+(3-3.5)
2
+(8-3.5)
2
+(9-14.67)
2
+(10-
14.67)
2
+(25-14.67)
2
=189.67。其中,簇{1,2,3,8}的均值为 3.5,簇{9,10,25}的均值为 14.67。后一个
划分具有最小簇内变差,因此,由于离群点 25 的缘故,k-均值方法把 8 分配到不同于 9 和 10 所在的簇。
此外,第二个簇中心为 14.67,显著地偏离簇中的所有成员。
"如何修改 k-均值算法,降低它对离群点的敏感性?"我们可以不采用簇中对象的均值作为参照点,而
是挑选实际对象来代表簇,每个簇使用一个代表对象。其余的每个对象被分配到与其最为相似的代表性
对象所在的簇中。于是,划分方法基于最小化所有对象 p 与其对应的代表对象之间的相异度之和的原则
来进行划分。确切地说,使用了一个绝对误差标准(absolute-error criterion),其定义如下:
(1)
其中,E 是数据集中所有对象 p 与 C
i
的代表对象 o
i
的绝对误差之和。这是 k-中心点(k-medoids)方法的基础。
k-中心点聚类通过最小化该绝对误差((1)式),把 n 个对象划分到 k 个簇中。
当 k=1 时,我们可以在 O(n
2
)时间内找出准确的中位数。然而,当 k 是一般的正整数时,k-中心点问
题是 NP-困难的。
围绕中心点划分(Partitioning Around Medoids,PAM)算法(图 2)是 k-中心点聚类的一种流行的实现。它
用迭代、贪心的方法处理该问题。与 k 均值算法一样,初始代表对象(称做种子)任意选取。我们考虑用一
个非代表对象替换一个代表对象是否能够提高聚类质量。尝试所有可能的替换。继续用其他对象替换代
表对象的迭代过程,直到结果聚类的质量不可能被任何替换提高。质量用对象与其簇中代表对象的平均
相异度的代价函数度量。
1 / 3
k-中心点:一种基于代表对象的技术
资源评论
努力搬砖的小王
- 粉丝: 16
- 资源: 7706
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功