Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_means/
Documentation version: v5.3.2

# K-Means

## Algorithm introduction

K-Means groups nodes into K clusters by iteratively assigning nodes and updating centroids in embedding space.

Run classic 1D K-Means clustering on Node.rating with deterministic initial centers [0..k-1].

For more information, see [K-Means](https://en.wikipedia.org/wiki/K-means_clustering).

## Data model

To implement the K-Means algorithm in GQL, the following data model is used to create a graph type:

- Entities are represented by nodes of type `Node`, with properties `id` and `rating`.
- Relationships are represented by edges of type `Link`, with property `weight`.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_means/#1_prepare_graph_data).

## Procedure implementation[]()

To compute K-Means results, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created.

For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/k_means/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- `k`: `INT64`. Number of clusters to partition nodes into.
- `max_iter`: `INT64` (default: `20`). Maximum number of assignment-update iterations.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `iter` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current iteration counter.
 | `init_idx` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Index used when sampling initial cluster centers.
 | `changed` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Whether any node changed its cluster assignment in this iteration.
 | `centers` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Flat list of current cluster center coordinates.
 | `next_centers` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Flat list of updated cluster center coordinates being computed.
 | `cluster_sum` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Accumulated coordinate sum for center update in the current cluster.
 | `cluster_cnt` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Count of nodes assigned to the current cluster.
 | `cluster` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node current cluster assignment index.
 | `result_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Output table storing (vertex_id, cluster_id) pairs.

The following steps outline the logic of the procedure:

1. Sample `k` initial cluster centers from node embeddings into `centers`.
2. Assign each node to its nearest center (by Euclidean distance) and update `cluster` for each node.
3. Recompute cluster centers by averaging the embeddings of all assigned nodes into `next_centers`.
4. Repeat until no assignment changes (`changed` is false) or `max_iter` is reached. Return (`vertex_id`, `cluster_id`).

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data[]()

1. 

Create a graph type that matches your data model.

````
'''
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. 

Download these CSV files and save them with their original names in `examples/algorithms/k_means/` under your deployment directory:

  - [k_means_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/k_means/k_means_node.csv): Node data.
  - [k_means_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/k_means/k_means_edge.csv): Edge data.

Preview the CSV files

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 a temporary graph based on the graph type and load the data files into the temporary graph.

````
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: ','
      }
  }
'''

````

After the import succeeds, run this query in the console to check the node count:

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

````

The expected `node_count` is `24`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

### 2. Create a procedure[]()

Create a procedure to implement the K-Means algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/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. Call your procedure[]()

Use `3` clusters and at most `20` iterations. Return each node's cluster assignment and cluster center.

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

````

Returns:

Expand to view results

````
+-----------+------------+--------+--------+
| 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    |
+-----------+------------+--------+--------+

````

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/). Match the exported fields to the returned columns and target properties.