概述

K均值（k-Means）算法是一种广泛使用的聚类算法，旨在根据节点的相似性将图中的节点分为k个聚类。该算法将每个节点分配至距离最近的质心所在的聚类。节点和质心之间的距离可以使用不同的度量方法来计算，例如欧几里得距离或余弦相似性。

K均值算法的概念可以追溯至1957年，它在1967年由J. MacQueen正式命名和推广：

• J. MacQueen, Some methods for classification and analysis of multivariate observations (1967)

从那时起，该算法在各个领域都有应用，包括向量量化、聚类分析、特征学习、计算机视觉等。它通常用作其他算法的预处理步骤，或作为数据分析的独立方法来使用。

基本概念

质心

一个N维空间中对象的质心（Centroid）或几何中心是所有N个坐标方向上点的平均位置。

在K均值这类聚类算法的语境中，质心是指聚类的几何中心。通过将多个节点属性指定为节点特征，质心是汇总了聚类中所有节点特征的代表性点。为了找到聚类的质心，该算法计算该聚类中所有节点每个维度的平均特征值。

K均值算法以k个节点作为初始质心，可以手动指定或由系统随机采样。

距离度量指标

嬴图的K均值算法可以计算节点与质心之间的欧几里得距离或余弦相似度。

聚类迭代

在K均值算法的每次迭代中，先计算图中每个节点到每个聚类质心的距离，然后并将节点分配给与其距离最近的聚类；将所有节点归到聚类中后，通过分配给每个聚类的节点重新计算聚类的质心。

如果聚类结果的变化低于预设的阈值，或达到了迭代次数限制，算法迭代就会结束。

特殊说明

• 适当选择k的值以及使用符合特定场景的距离度量指标对于K均值算法的结果至关重要。初始质心的选择也会影响最终的聚类结果。
• 如果存在两个或多个相同的质心，只有一个质心将生效，其余等效质心的聚类为空。

语法

• 命令：algo(k_means)
• 参数：

示例

示例图包含11个节点（忽略边），每个节点有f1、f2和f3属性：

文件回写

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,

直接返回

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

流式返回

algo(k_means).params({
  k: 2,
  node_schema_property: ['f1', 'f2', 'f3'],
  loop_num: 5
}).stream() as c
return c

结果：c