Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/k_means/
Documentation version: v5.3.2

# K-Means

本文介绍 K-Means 算法，并演示如何用 GQL 实现该算法。

## 算法介绍

K-Means 通过迭代分配与更新中心将点划分为 K 个簇。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见 [K-Means](https://zh.wikipedia.org/wiki/K-%E5%B9%B3%E5%9D%87%E7%AE%97%E6%B3%95)。

## 数据模型

为了在 GQL 中实现 K-Means 算法，使用以下数据模型创建图类型：

- 实体由类型为`Node`的点表示，点属性包括`id`和`rating`。
- 实体间关系由类型为`Link`的边表示，边属性包括`weight`。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/k_means/#1_prepare_graph_data)。

## 过程实现[]()

为了计算 K-Means 结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/k_means/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

- `k`：`INT64`类型。 将点划分为的簇数。
- `max_iter`：`INT64`类型，默认值`20`。 分配更新迭代的最大次数。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `iter` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前迭代次数。
 | `init_idx` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 初始化聚类中心时的采样索引。
 | `changed` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 本轮迭代中是否有点更改了所属簇。
 | `centers` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前聚类中心坐标的平铺列表。
 | `next_centers` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 正在计算的更新后聚类中心坐标列表。
 | `cluster_sum` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前簇的坐标之和，用于更新聚类中心。
 | `cluster_cnt` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 分配到当前簇的点数量。
 | `cluster` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点当前的簇分配索引。
 | `result_table` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 存储 (vertex_id, cluster_id) 结果对的输出表。

以下步骤概述了该过程的逻辑：

1. 从点嵌入中采样`k`个初始聚类中心存入`centers`。
2. 将每个点分配到欧氏距离最近的聚类中心，更新每点的`cluster`。
3. 对每个簇内所有点的嵌入取均值，更新`next_centers`。
4. 重复执行直至无点更换簇（`changed`为 false）或达到`max_iter`。返回（`vertex_id`、`cluster_id`）。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建一个与数据模型匹配的图类型。

````
'''
CREATE GRAPH TYPE IF NOT EXISTS k_means_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/k_means/`：

  - [k_means_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/k_means/k_means_node.csv)：点数据。
  - [k_means_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/k_means/k_means_edge.csv)：边数据。

查看 CSV 内容

k_means_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

k_means_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

基于图类型创建临时图，并将数据文件加载到临时图中。

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #k_means_graph TYPED k_means_graph_type

````

````
'''
USE #k_means_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/k_means/k_means_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/k_means/k_means_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

````
'''
USE #k_means_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

`node_count`应为`24`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现 K-Means 算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/k_means/#procedure_implement)。 

````
'''
CREATE OR REPLACE PROCEDURE k_means(
  k INT64,
  max_iter INT64 DEFAULT 20
)
RETURNS (vertex_id INT64, cluster_id INT64, rating INT64, center DOUBLE)
COMMENT "Run classic 1D K-Means clustering on Node.rating with deterministic initial centers [0..k-1]."
AS {
  VALUE iter INT64 = 0
  VALUE init_idx INT64 = 0
  VALUE changed OrAgg = true
  VALUE centers ListAgg<DOUBLE>
  VALUE next_centers ListAgg<DOUBLE>
  VALUE cluster_sum SumAgg<DOUBLE> = 0.0
  VALUE cluster_cnt SumAgg<INT64> = 0

  NODE VALUE cluster SumAgg<INT64> = 0

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    cluster_id INT64,
    rating INT64,
    center DOUBLE
  }

  IF k <= 0 THEN {
    FINISH
  }

  WHILE init_idx < k THEN {
    SET @centers += CAST(init_idx AS DOUBLE)
    SET init_idx = init_idx + 1
  }

  WHILE @changed AND iter < max_iter THEN {
    VALUE cid INT64 = 1
    VALUE new_center DOUBLE = 0.0

    SET @changed = false

    MATCH (n)
    PER NODE (n) {
      VALUE idx INT64 = 0
      VALUE best_idx INT64 = 0
      VALUE best_dist DOUBLE = 1000000000.0
      VALUE dist DOUBLE = 0.0
      VALUE center_value DOUBLE = 0.0
      VALUE rating_value DOUBLE = CAST(n.rating AS DOUBLE)

      WHILE idx < k THEN {
        IF idx < @centers.size() THEN {
          SET center_value = @centers[idx]
        }
        ELSE {
          SET center_value = CAST(idx AS DOUBLE)
        }

        SET dist = abs(rating_value - center_value)

        IF dist < best_dist THEN {
          SET best_dist = dist
          SET best_idx = idx
        }

        SET idx = idx + 1
      }

      IF n.@cluster <> best_idx + 1 THEN {
        SET @changed += true
      }

      SET n.@cluster = best_idx + 1
    }

    SET @next_centers.clear()

    WHILE cid <= k THEN {
      SET @cluster_sum = 0.0
      SET @cluster_cnt = 0

      MATCH (n)
      WHERE n.@cluster = cid
      PER NODE (n) {
        SET @cluster_sum += CAST(n.rating AS DOUBLE)
        SET @cluster_cnt += 1
      }

      IF @cluster_cnt > 0 THEN {
        SET new_center = @cluster_sum / CAST(@cluster_cnt AS DOUBLE)
      }
      ELSEIF cid - 1 < @centers.size() THEN {
        SET new_center = @centers[cid - 1]
      }
      ELSE {
        SET new_center = CAST(cid - 1 AS DOUBLE)
      }

      SET @next_centers += new_center
      SET cid = cid + 1
    }

    SET @centers = @next_centers
    SET iter = iter + 1
  }

  MATCH (n)
  PER NODE (n) {
    VALUE center_value DOUBLE = 0.0

    IF n.@cluster > 0 AND n.@cluster - 1 < @centers.size() THEN {
      SET center_value = @centers[n.@cluster - 1]
    }

    EXPORT n.id, n.@cluster, CAST(n.rating AS INT64), center_value INTO result_table
  }

  FOR r IN result_table
  RETURN
    r.vertex_id AS vertex_id,
    r.cluster_id AS cluster_id,
    r.rating AS rating,
    r.center AS center
  ORDER BY vertex_id ASC
}
'''

````

### 3. 调用过程[]()

将聚类数量设为`3`、最大迭代次数设为`20`，返回各点的聚类归属和聚类中心。

````
USE #k_means_graph CALL k_means(3, 20) RETURN vertex_id, cluster_id, rating, center

````

返回：

展开查看返回

````
+-----------+------------+--------+--------+
| vertex_id | cluster_id | rating | center |
+-----------+------------+--------+--------+
| 1         | 1          | 0      | 0.0    |
| 2         | 3          | 2      | 2.0    |
| 3         | 2          | 1      | 1.0    |
| 4         | 1          | 0      | 0.0    |
| 5         | 1          | 0      | 0.0    |
| 6         | 3          | 2      | 2.0    |
| 7         | 2          | 1      | 1.0    |
| 8         | 3          | 2      | 2.0    |
| 9         | 1          | 0      | 0.0    |
| 10        | 2          | 1      | 1.0    |
| 11        | 1          | 0      | 0.0    |
| 12        | 3          | 2      | 2.0    |
| 13        | 2          | 1      | 1.0    |
| 14        | 2          | 1      | 1.0    |
| 15        | 1          | 0      | 0.0    |
| 16        | 3          | 2      | 2.0    |
| 17        | 1          | 0      | 0.0    |
| 18        | 2          | 1      | 1.0    |
| 19        | 3          | 2      | 2.0    |
| 20        | 1          | 0      | 0.0    |
| 21        | 3          | 2      | 2.0    |
| 22        | 2          | 1      | 1.0    |
| 23        | 1          | 0      | 0.0    |
| 24        | 2          | 1      | 1.0    |
+-----------+------------+--------+--------+

````

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。