概述
K均值(k-Means)算法是一种广泛使用的聚类算法,旨在根据节点的相似性将图中的节点分为k个聚类。该算法将每个节点分配至距离最近的质心所在的聚类。节点和质心之间的距离可以使用不同的度量方法来计算,例如欧几里得距离或余弦相似性。
K均值算法的概念可以追溯至1957年,它在1967年由J. MacQueen正式命名和推广:
- J. MacQueen, Some methods for classification and analysis of multivariate observations (1967)
从那时起,该算法在各个领域都有应用,包括向量量化、聚类分析、特征学习、计算机视觉等。它通常用作其他算法的预处理步骤,或作为数据分析的独立方法来使用。
基本概念
质心
一个N维空间中对象的质心(Centroid)或几何中心是所有N个坐标方向上点的平均位置。
![](https://img.ultipa.cn/draw/draw_366c58b621b74ca4a72dc460710e6d8b.jpg?v='1685586649322')
在K均值这类聚类算法的语境中,质心是指聚类的几何中心。通过将多个节点属性指定为节点特征,质心是汇总了聚类中所有节点特征的代表性点。为了找到聚类的质心,该算法计算该聚类中所有节点每个维度的平均特征值。
K均值算法以k个节点作为初始质心,可以手动指定或由系统随机采样。
距离度量指标
嬴图的K均值算法可以计算节点与质心之间的欧几里得距离或余弦相似度。
聚类迭代
在K均值算法的每次迭代中,先计算图中每个节点到每个聚类质心的距离,然后并将节点分配给与其距离最近的聚类;将所有节点归到聚类中后,通过分配给每个聚类的节点重新计算聚类的质心。
如果聚类结果的变化低于预设的阈值,或达到了迭代次数限制,算法迭代就会结束。
特殊说明
- 适当选择k的值以及使用符合特定场景的距离度量指标对于K均值算法的结果至关重要。初始质心的选择也会影响最终的聚类结果。
- 如果存在两个或多个相同的质心,只有一个质心将生效,其余等效质心的聚类为空。
语法
- 命令:
algo(k_means)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
start_ids | []_uuid |
/ | / | 是 | 指定节点作为初始质心,UUID数组的长度必须等于k ;忽略则由系统进行选取 |
k | int | [1, |V|] | 1 |
否 | 聚类的数量 |
distance_type | int | 1 , 2 |
1 |
是 | 距离度量指标:1 代表欧几里得距离,2 代表余弦相似度 |
node_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 否 | 用作节点特征的至少两个点属性 |
loop_num | int | ≥1 | / | 否 | 迭代的最大次数 |
示例
示例图包含11个节点(忽略边),每个节点有f1、f2和f3属性:
![](https://img.ultipa.cn/draw/draw_010deab95e374a2dbbba4138fa61519c.jpg?v='1685588449840')
文件回写
配置项 |
回写内容 |
---|---|
filename | community :_id ,_id ,... |
algo(k_means).params({
start_ids: [1,2,5],
k: 3,
distance_type: 2,
node_schema_property: ['f1', 'f2', 'f3'],
loop_num: 3
}).write({
file:{
filename: 'communities'
}
})
结果:文件communities
0:I,
1:K,H,G,B,F,
2:J,C,A,E,D,
直接返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | []perCommunity | 聚类及聚类中的节点 | community , uuids |
algo(k_means).params({
start_ids: [1,2,5],
k: 3,
distance_type: 1,
node_schema_property: ['@default.f1', '@default.f2', '@default.f3'],
loop_num: 3
}) as k3
return k3
结果:k3
community | uuids |
---|---|
0 | 11,5,4,2,1, |
1 | 10,9, |
2 | 8,7,6,3, |
流式返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | []perCommunity | 聚类及聚类中的节点 | community , uuids |
algo(k_means).params({
k: 2,
node_schema_property: ['f1', 'f2', 'f3'],
loop_num: 5
}).stream() as c
return c
结果:c
community | uuids |
---|---|
0 | 3,6,8,7, |
1 | 5,9,11,10,4,2,1, |