概述

K 均值（k-Means）算法可以将图上所有点分成 k 类，使每个点到自己所属分类质心（几何中心）的距离小于到其它分类的质心的距离。其中，距离最短的评判标准分为两种：1）欧几里得距离，2）余弦相似度。算法的思想可以追溯到 1957 年，术语“K 均值”由 J. MacQueen 于 1967 年提出。K 均值算法在向量量化、聚类分析、特征学习、计算机视觉等领域都有应用，也经常作为其他算法的预处理步骤使用。

算法的相关资料如下：

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

基本概念

欧几里得距离

图中两点的欧几里得距离是用点的 N 个属性构成两个 N 维向量并计算距离。细节可参看章节《数值相似度》，公式如下：

余弦相似度

余弦相似度是用向量空间中两个 N 维向量间夹角的余弦值来表示这两个向量的相似程度。图中两点的余弦相似度是用点的 N 个属性构成两个 N 维向量并计算余弦值。细节可参看章节《数值相似度》，公式如下：

质心

N 维空间中一个对象的质心或几何中心是将该对象分成矩相等的两部分的所有超平面的交点。非正式地说，它是对象中所有点的平均。如果一个对象质量分布平均，质心便是重心。

有限个点总存在质心，可以通过计算这些点的每个坐标分量的算术平均值得到。这个中心是空间中一点到这有限个点距离的平方和的唯一最小值点。

使用欧几里得距离时，节点选择最近质心的计算公式如下，其中 d 为每个质心 m 到当前节点 x 的欧几里得距离，选择这些距离中最小值对应的质心为当前节点 x 的质心：

使用余弦相似度时，节点选择最近质心的计算公式如下，其中 s 为每个质心 m 到当前节点 x 的余弦相似度，选择这些相似度中最大值对应的质心为当前节点 x 的质心：

指定 k 个节点作为起始分类的质心。从第一次迭代开始，为每个节点计算其到每个质心的距离，选择距离最小的质心作为该节点的质心；根据分类结果重新计算各类的质心。如果本次迭代后分类结果的变化符合预设的精度要求，或达到了迭代次数限制也会结束，则迭代结束。

请注意，初始质心的选择会影响最终分类结果；如果有多个初始质心的属性值相同，则仅其中一个质心有效，其余的质心会产生空集。

特殊处理

孤点、不连通图

计算两点的欧几里得距离或余弦相似度理论上不依赖边，无论待计算的节点是否为孤点或是否与质心处于同一个连通分量内，都不影响它们之间欧几里得距离或余弦相似度的计算。

自环边

K 均值的计算与边无关。

有向边

K 均值的计算与边无关。

结果和统计值

沿用上面的例子，指定节点的 property_1、property_2、property_3 三个属性构成向量，使用欧几里得距离作为评判标准，初始时选取 2, 4, 5 三个节点为质心，设置最大迭代次数为 3：

算法结果：将图上所有点分为 3 类，返回 community、ids 两列

算法统计值：无

命令和参数配置

• 命令：algo(k_means)
• params() 参数配置项如下：

示例：依据欧几里得距离对全图进行 K 均值分类，依据属性 property_1、property_2、property_3 分为 3 类，以 UUID = 2,4,5 为起始质心，最大迭代 4 轮

algo(k_means).params({
  start_ids: [2,4,5],
  k: 3,
  distance_type: 1,
  node_schema_property:["property_1", "property_2", "property_3"],
  loop_num: 4
}) as k3 return k3

算法执行

任务回写

1. 文件回写

示例：依据余弦相似度对全图进行 K 均值分类，依据属性 property_1、property_2 分为 3 类，以 UUID = 2,5 为起始质心，最大迭代 3 轮，将算法结果回写至名为 communities 的文件

algo(k_means).params({
  start_ids: [2,4,5],
  k: 3,
  distance_type: 2,
  node_schema_property: ["property_1", "property_2"],
  loop_num: 3
}).write({
  file:{
    filename: "communities"
    }
})

2. 属性回写

算法不支持属性回写。

3. 统计回写

算法无统计值。

直接返回

示例：依据欧几里得距离对全图进行 K 均值分类，依据属性 property_1、property_2、property_3 分为 3 类，以 UUID = 2,4,5 为起始质心，最大迭代 4 轮，将算法结果定义为别名 k3 并返回

algo(k_means).params({
  start_ids: [2,4,5],
  k: 3,
  distance_type: 1,
  node_schema_property:["property_1", "property_2", "property_3"],
  loop_num: 4
}) as k3 return k3

流式返回

示例：依据欧几里得距离对全图进行 K 均值分类，依据属性 property_1、property_2、property_3 分为 3 类，以 UUID = 2,4,5 为起始质心，最大迭代 4 轮，将算法结果定义为别名 k3 并返回

algo(k_means).params({
  start_ids: [2,4,5],
  k: 3,
  distance_type: 1,
  node_schema_property:["property_1", "property_2", "property_3"],
  loop_num: 4
}).stream() as k3
return k3

实时统计

算法无统计值。