K-均值聚类 (K-Means Clustering)

术语表

有向: 有向特征。该算法在有向图上定义良好。
有向: 有向特征。该算法忽略图的方向。
有向: 有向特征。该算法不能在有向图上运行。
无向: 无向特征。该算法在无向图上定义良好。
无向: 无向特征。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法有能力区分不同类型的节点。
异构节点: 异构节点允许。该算法平等对待所有选定的节点，无论其标签如何。
异构关系: 异构关系完全支持。该算法有能力区分不同类型的关系。
异构关系: 异构关系允许。该算法平等对待所有选定的关系，无论其类型如何。
加权关系: 加权特征。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特征。该算法将每个关系视为同等重要，忽略任何关系权重值。
节点属性: 节点属性特征。该算法使用节点属性。

简介

K-Means 聚类是一种用于解决聚类问题的无监督学习算法。它遵循一个简单的程序，即根据参数 k 定义的数量将给定的数据集划分为多个簇。Neo4j GDS 库基于节点属性进行聚类，并通过 nodeProperty 参数传入浮点数组类型的节点属性作为输入。图中的节点随后被定位为 d 维空间中的点（其中 d 是数组属性的长度）。

算法首先选择 k 个初始簇质心，它们是 d 维数组（详见下方章节）。质心充当簇的代表。

然后，图中的所有节点计算它们与每个簇质心的欧几里得距离，并被分配到距离最近的簇中。分配完成后，每个簇会计算分配给它的所有节点（作为点）的平均值，以形成其新的代表质心（作为 d 维数组）。

该过程使用新的质心重复进行，直到结果稳定，即每次迭代中只有少数节点更换簇，或者达到最大迭代次数。

请注意，K-Means 实现会忽略关系，因为它仅关注节点属性。

有关此算法的更多信息，请参阅

https://en.wikipedia.org/wiki/K-means_clustering

初始质心采样

该算法通过从可用节点集中随机采样来选取 k 个质心。有两种不同的采样策略。

均匀 (Uniform): 对于均匀采样 (Uniform Sampling)，每个节点被选为 k 个初始质心之一的概率相同。这是 K-Means 的默认采样器，由 uniform 参数表示。
K-Means++: 这种采样策略改编了著名的 K-means++ 初始化算法^[1] 用于 K-Means。采样过程首先随机均匀选择第一个质心。然后，其余的 k-1 个质心基于加权随机采样逐一选取。也就是说，一个节点被选为下一个质心的概率与其到已选质心的最小距离成正比。因此，距离越大的节点被选为质心的机会越大。这种采样策略试图更均匀地分散初始簇，从而获得更好的最终聚类效果。通过在配置中选择 kmeans++ 作为初始采样器，可以启用此选项。

也可以通过 seedCentroids 参数显式地向算法提供初始质心列表。在这种情况下，即使在配置中更改了 initialSampler 参数，其值也会被忽略。请注意，尽管该算法支持对单个双精度数字进行聚类，但在通过 seedCentroids 参数设定种子时，初始质心必须以数组形式传入，例如 [[1.5],[2.5]]，分别表示以 1.5 和 2.5 进行初始化。

注意事项

为了使 K-Means 正常工作，所有节点的属性数组必须具有相同数量的元素。此外，它们必须只包含数字，且不能包含任何 NaN 值。

语法

各模式下的 K-Means 语法

在命名图上以流模式 (stream mode) 运行 K-Means。

CALL gds.kmeans.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  communityId: Integer,
  distanceFromCentroid: Float,
  silhouette: Float

表 1. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
nodeProperty	字符串	`不适用`	否	对应于浮点数组的节点属性，K-Means 使用它将节点聚类到社区中。
k	整数	`10`	是	所需的簇数量。
maxIterations	整数	`10`	是	K-Means 运行的最大迭代次数。
deltaThreshold	浮点数	`0.05`	是	以百分比形式表示的值，用于确定何时提前停止。如果更换簇的节点数少于 'deltaThreshold * \|nodes\|'，算法将停止。值必须在 0（不含）到 1（含）之间。
numberOfRestarts	整数	`1`	是	使用不同初始中心执行 K-Means 的次数。返回的社区是使平均节点-中心距离最小化的那些社区。
randomSeed	整数	`不适用`	是	用于控制初始质心分配的种子值。
initialSampler	字符串	`"uniform"`	是	用于采样前 `k` 个质心的方法。"uniform" 和 "kmeans++"（均不区分大小写）是有效的输入。
seedCentroids	浮点数列表的列表	`[]`	是	显式提供初始质心的参数。它不能与非默认值的 `numberOfRestarts` 参数同时启用。
computeSilhouette	布尔值	`false`	是	如果设置为 true，则在确定聚类后计算轮廓系数 (silhouette scores)。轮廓系数是衡量节点聚类效果好坏的指标。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
communityId	整数	社区 ID。
distanceFromCentroid	浮点数	节点到其社区质心的距离。
silhouette	浮点数	节点的轮廓系数。

在命名图上以统计模式 (stats mode) 运行 K-Means。

CALL gds.kmeans.stats(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  communityDistribution: Map,
  centroids: List of List of Float,
  averageDistanceToCentroid: Float,
  averageSilhouette: Float,
  configuration: Map

表 4. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
nodeProperty	字符串	`不适用`	否	对应于浮点数组的节点属性，K-Means 使用它将节点聚类到社区中。
k	整数	`10`	是	所需的簇数量。
maxIterations	整数	`10`	是	K-Means 运行的最大迭代次数。
deltaThreshold	浮点数	`0.05`	是	以百分比形式表示的值，用于确定何时提前停止。如果更换簇的节点数少于 'deltaThreshold * \|nodes\|'，算法将停止。值必须在 0（不含）到 1（含）之间。
numberOfRestarts	整数	`1`	是	使用不同初始中心执行 K-Means 的次数。返回的社区是使平均节点-中心距离最小化的那些社区。
randomSeed	整数	`不适用`	是	用于控制初始质心分配的种子值。
initialSampler	字符串	`"uniform"`	是	用于采样前 `k` 个质心的方法。"uniform" 和 "kmeans++"（均不区分大小写）是有效的输入。
seedCentroids	浮点数列表的列表	`[]`	是	显式提供初始质心的参数。它不能与非默认值的 `numberOfRestarts` 参数同时启用。
computeSilhouette	布尔值	`false`	是	如果设置为 true，则在确定聚类后计算轮廓系数 (silhouette scores)。轮廓系数是衡量节点聚类效果好坏的指标。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
communityDistribution	Map	包含最后一级社区大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数的映射。
centroids	浮点数列表的列表	质心坐标列表。每个项目都是一个包含一个质心坐标的列表。
averageDistanceToCentroid	浮点数	节点与质心之间的平均距离。
averageSilhouette	浮点数	所有节点的平均轮廓系数。
配置	Map	用于运行算法的配置。

在命名图上以变异模式 (mutate mode) 运行 K-Means。

CALL gds.kmeans.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  postProcessingMillis: Integer,
  nodePropertiesWritten: Integer,
  communityDistribution: Map,
  centroids: List of List of Float,
  averageDistanceToCentroid: Float,
  averageSilhouette: Float,
  configuration: Map

表 7. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中用于写入簇的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
nodeProperty	字符串	`不适用`	否	对应于浮点数组的节点属性，K-Means 使用它将节点聚类到社区中。
k	整数	`10`	是	所需的簇数量。
maxIterations	整数	`10`	是	K-Means 运行的最大迭代次数。
deltaThreshold	浮点数	`0.05`	是	以百分比形式表示的值，用于确定何时提前停止。如果更换簇的节点数少于 'deltaThreshold * \|nodes\|'，算法将停止。值必须在 0（不含）到 1（含）之间。
numberOfRestarts	整数	`1`	是	使用不同初始中心执行 K-Means 的次数。返回的社区是使平均节点-中心距离最小化的那些社区。
randomSeed	整数	`不适用`	是	用于控制初始质心分配的种子值。
initialSampler	字符串	`"uniform"`	是	用于采样前 `k` 个质心的方法。"uniform" 和 "kmeans++"（均不区分大小写）是有效的输入。
seedCentroids	浮点数列表的列表	`[]`	是	显式提供初始质心的参数。它不能与非默认值的 `numberOfRestarts` 参数同时启用。
computeSilhouette	布尔值	`false`	是	如果设置为 true，则在确定聚类后计算轮廓系数 (silhouette scores)。轮廓系数是衡量节点聚类效果好坏的指标。

表 9. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
nodePropertiesWritten	整数	添加到投影图中的属性数量。
communityDistribution	Map	包含最后一级社区大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数的映射。
centroids	浮点数列表的列表	质心坐标列表。每个项目都是一个包含一个质心坐标的列表。
averageDistanceToCentroid	浮点数	节点与质心之间的平均距离。
averageSilhouette	浮点数	所有节点的平均轮廓系数。
配置	Map	用于运行算法的配置。

在命名图上以写入模式 (write mode) 运行 K-Means。

CALL gds.kmeans.write(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  postProcessingMillis: Integer,
  nodePropertiesWritten: Integer,
  communityDistribution: Map,
  centroids: List of List of Float,
  averageDistanceToCentroid: Float,
  averageSilhouette: Float,
  configuration: Map

表 10. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中用于写入簇的节点属性。
nodeProperty	字符串	`不适用`	否	对应于浮点数组的节点属性，K-Means 使用它将节点聚类到社区中。
k	整数	`10`	是	所需的簇数量。
maxIterations	整数	`10`	是	K-Means 运行的最大迭代次数。
deltaThreshold	浮点数	`0.05`	是	以百分比形式表示的值，用于确定何时提前停止。如果更换簇的节点数少于 'deltaThreshold * \|nodes\|'，算法将停止。值必须在 0（不含）到 1（含）之间。
numberOfRestarts	整数	`1`	是	使用不同初始中心执行 K-Means 的次数。返回的社区是使平均节点-中心距离最小化的那些社区。
randomSeed	整数	`不适用`	是	用于控制初始质心分配的种子值。
initialSampler	字符串	`"uniform"`	是	用于采样前 `k` 个质心的方法。"uniform" 和 "kmeans++"（均不区分大小写）是有效的输入。
seedCentroids	浮点数列表的列表	`[]`	是	显式提供初始质心的参数。它不能与非默认值的 `numberOfRestarts` 参数同时启用。
computeSilhouette	布尔值	`false`	是	如果设置为 true，则在确定聚类后计算轮廓系数 (silhouette scores)。轮廓系数是衡量节点聚类效果好坏的指标。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	向 Neo4j 数据库添加属性所需的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
nodePropertiesWritten	整数	添加到投影图中的属性数量。
communityDistribution	Map	包含最后一级社区大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数的映射。
centroids	浮点数列表的列表	质心坐标列表。每个项目都是一个包含一个质心坐标的列表。
averageDistanceToCentroid	浮点数	节点与质心之间的平均距离。
averageSilhouette	浮点数	所有节点的平均轮廓系数。
配置	Map	用于运行算法的配置。

示例

以下所有示例应在空数据库中运行。

这些示例将 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行 K-Means 算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指南。我们将在一个包含少量以特定模式连接的节点的小型城市图上进行操作。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图：

CREATE
  (:City {name: 'Surbiton', coordinates: [51.39148, -0.29825]}),
  (:City {name: 'Liverpool', coordinates: [53.41058, -2.97794]}),
  (:City {name: 'Kingston upon Thames', coordinates: [51.41259, -0.2974]}),
  (:City {name: 'Sliven', coordinates: [42.68583, 26.32917]}),
  (:City {name: 'Solna', coordinates: [59.36004, 18.00086]}),
  (:City {name: 'Örkelljunga', coordinates: [56.28338, 13.27773]}),
  (:City {name: 'Malmö', coordinates: [55.60587, 13.00073]}),
  (:City {name: 'Xánthi', coordinates: [41.13488, 24.888]});

该图由分布在三个全球位置的各种 City 节点组成 - 英国、瑞典和欧洲的巴尔干地区。

现在我们可以投影该图并将其存储在图目录中。我们加载带有 coordinates 节点属性的 City 节点标签。

以下语句将投影图并将其存储在图目录中。

MATCH (c:City)
RETURN gds.graph.project(
  'cities',
  c,
  null,
  {
    sourceNodeProperties: c { .coordinates },
    targetNodeProperties: {}
  }
)

在接下来的示例中，我们将演示如何在该图上使用 K-Means 算法来寻找在地理位置上彼此接近的城市社区。

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在这个例子中我们将使用 write 模式。估算算法有助于了解在您的图上运行该算法将产生的内存影响。当您随后在其中一种执行模式下真正运行算法时，系统将执行一次估算。如果估算显示执行超出其内存限制的可能性非常高，则禁止执行。要阅读更多关于此的内容，请参阅自动估算和执行阻塞。

有关 estimate 的更多详细信息，请参阅内存估算。

以下内容将估算运行算法所需的内存

CALL gds.kmeans.write.estimate('cities', {
  writeProperty: 'kmeans',
  nodeProperty: 'coordinates'
})
YIELD nodeCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	bytesMin	bytesMax	requiredMemory
8	33248	54240	"[32 KiB ... 52 KiB]"

流 (Stream)

在 stream 执行模式下，算法返回每个节点的簇。这使我们能够直接检查结果或在 Cypher 中进行后处理，而不会产生任何副作用。

有关 stream 模式的更多详细信息，请参阅流式读取。

以下命令将运行算法并流式传输结果

CALL gds.kmeans.stream('cities', {
  nodeProperty: 'coordinates',
  k: 3,
  randomSeed: 42
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId, name ASC

表 14. 结果
名称 (name)	communityId
"Kingston upon Thames"	0
"Liverpool"	0
"Surbiton"	0
"Sliven"	1
"Xánthi"	1
"Malmö"	2
"Solna"	2
"Örkelljunga"	2

在上面的示例中，我们可以看到城市在地理上被聚类在一起。

统计 (Stats)

在 stats 执行模式下，算法返回包含算法结果摘要的单行数据。此执行模式没有任何副作用。它可用于通过检查 computeMillis 返回项来评估算法性能。在下面的示例中，我们将省略返回的时间。该过程的完整签名可以在语法部分找到。

有关 stats 模式的更多详细信息，请参阅统计。

以下命令将运行算法并以统计和测量值的形式返回结果

CALL gds.kmeans.stats('cities', {
  nodeProperty: 'coordinates',
  k: 3,
  randomSeed: 42
})
YIELD communityDistribution

表 15. 结果
communityDistribution
{max=3, mean=2.6666666666666665, min=2, p1=2, p10=2, p25=2, p5=2, p50=3, p75=3, p90=3, p95=3, p99=3, p999=3}

变异 (Mutate)

mutate 执行模式扩展了 stats 模式，具有一个重要的副作用：使用包含该节点簇的新节点属性更新命名图。新属性的名称使用必需的配置参数 mutateProperty 指定。结果是类似于 stats 的单行摘要，但包含一些额外的指标。当多个算法协同使用时，mutate 模式特别有用。

有关 mutate 模式的更多详细信息，请参阅变更。

以下命令将运行算法并将结果存储在 cities 图中

CALL gds.kmeans.mutate('cities', {
  nodeProperty: 'coordinates',
  k: 3,
  randomSeed: 42,
  mutateProperty: 'kmeans'
})
YIELD communityDistribution

表 16. 结果
communityDistribution
{max=3, mean=2.6666666666666665, min=2, p1=2, p10=2, p25=2, p5=2, p50=3, p75=3, p90=3, p95=3, p99=3, p999=3}

在 mutate 模式下，过程仅返回一行。结果被写入 GDS 内存图，而不是 Neo4j 数据库。

写入 (Write)

write 执行模式扩展了 stats 模式，具有一个重要的副作用：将每个节点的簇作为属性写入 Neo4j 数据库。新属性的名称使用必需的配置参数 writeProperty 指定。结果是类似于 stats 的单行摘要，但包含一些额外的指标。write 模式可以将结果直接持久化到数据库中。

有关 write 模式的更多详细信息，请参阅写入。

以下命令将运行算法并将结果写回 Neo4j

CALL gds.kmeans.write('cities', {
  nodeProperty: 'coordinates',
  k: 3,
  randomSeed: 42,
  writeProperty: 'kmeans'
})
YIELD nodePropertiesWritten

表 17. 结果
nodePropertiesWritten
8

在 write 模式下，过程仅返回一行。结果被写入 Neo4j 数据库，而不是 GDS 内存图。

设置初始质心种子

现在我们来看看设置质心种子对 K-Means 的影响。我们运行 K-Means，并将纽约、阿姆斯特丹和罗马的坐标作为初始种子。

以下命令将运行算法并流式传输结果

CALL gds.kmeans.stream('cities', {
  nodeProperty: 'coordinates',
  k: 3,
  seedCentroids: [[40.712776,-74.005974], [52.370216,4.895168],[41.902782,12.496365]]
})
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY communityId, name ASC

表 18. 结果
名称 (name)	communityId
"Kingston upon Thames"	1
"Liverpool"	1
"Malmö"	1
"Solna"	1
"Surbiton"	1
"Örkelljunga"	1
"Sliven"	2
"Xánthi"	2

请注意，在这种情况下，城市在地理上被聚类为两个簇：一个包含北欧城市，另一个包含南欧城市。另一方面，以纽约作为初始质心的簇在第一阶段并不是任何城市最接近的簇。

1. Arthur, David 和 Sergei Vassilvitskii. "k-means++: The Advantages of Careful Seeding." ACM-SIAM Symposium on Discrete Algorithms (2007).