npm package: @jrc03c/tf-k-means
Description: This library implements the K-means algorithm in [TensorFlow.js](https://www.tensorflow.org/js). Note that it is a fresh rewrite of [willfind/tf-kmeans](https://github.com/willfind/tf-kmeans), which should be considered to be deprecated.
Author: jrc03c
Latest version: 0.0.10

# Intro

This library implements the K-means algorithm in [TensorFlow.js](https://www.tensorflow.org/js). Note that it is a fresh rewrite of [willfind/tf-kmeans](https://github.com/willfind/tf-kmeans), which should be considered to be deprecated.

# Installation

```bash
npm install --save @jrc03c/tf-k-means
```

# Usage

## Clustering the data

The model's API follows the [scikit-learn](https://scikit-learn.org/) conventions of having `fit`, `predict`, and `score` methods.

```js
import { KMeansMeta } from "@jrc03c/tf-k-means"

const x = getDataSomehow()

const model = new KMeansMeta({
  finalMaxIterations: 100,
  finalMaxRestarts: 50,
  finalMaxTime: 1000,
  initialization: KMeansMeta.Initialization.PLUS_PLUS,
  ks: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
  maxIterations: 50,
  maxRestarts: 25,
  maxTime: 3000,
  method: KMeansMeta.Method.SILHOUETTE,
  testSize: 0.25,
  tolerance: 1e-4,
})

model.fit(x, progress => {
  console.log("k-means progress:", (progress * 100).toFixed(2) + "%")
})

const labels = model.predict(x)
const score = model.score(x)
```

## Visualizing the data

I've included a [t-SNE](https://en.wikipedia.org/wiki/T-distributed_stochastic_neighbor_embedding) model for visualization purposes. It allows you to project data down into 2 (or 3 or however many) dimensions.

To continue the example above, we'd stack the data points (`x`) and the model's learned centroids (i.e., cluster centers) and project them all at once down into (e.g.) 2 dimensions.

```js
import { TSNE } from "@jrc03c/tf-k-means"
import * as tf from "@tensorflow/tfjs"

const stacked = tf.stack([x, model.centroids])

const projector = new TSNE({
  dimensions: 2,
  learningRate: 100,
  maxIterations: 1000,
  maxTime: 2000,
  perplexity: 30,
})

const projected = projector
  .fitTransform(stacked, progress => {
    console.log("t-sne progress:", (progress * 100).toFixed(2) + "%")
  })
  .arraySync()

const xProjected = projected.slice(0, x.shape[0])
const centroidsProjected = projected.slice(x.shape[0])

// then visualize!
```

# Demo

The `/demo` folder contains a full example. Run the demo using:

```bash
npm run demo
```

And then visit http://localhost:1234 in your browser.

# Caveats

I tried to implement a time limit for each model's `fit` method (or `fitTransform` in the case of the t-SNE model) using the `maxTime` and `finalMaxTime` properties described below. However, some operations are just so large and synchronous and uninterruptible that the time constraint simply can't be honored. Thus the time limits are more like suggestions or approximations rather than hard boundaries. I may add some functionality in the future that would move parts of the `fit` methods into Web Workers. Then they _would_ be cancellable at any time, regardless of whether or not the program was in the middle of executing a large synchronous operation.

# API

> **NOTE:** In the documentation that follows, I refer to the K-means objective function — the within-cluster sum of squared errors — as "WCSSE".

## Models

### `KMeansMeta`

#### Properties

##### `Initialization` (static)

An object with this definition:

```js
{
  PLUS_PLUS: "PLUS_PLUS",
  RANDOM: "RANDOM",
}
```

##### `centroids`

A 2-dimensional `tf.Tensor` representing the centroids learned by the final model fitted at the end of the `fit` method (after the best K-value has been determined). The default is `null`.

##### `finalMaxIterations`

A non-negative integer representing the maximum number of iterations allowed for the final model fitted at the end of the `fit` method. The default is `100`.

##### `finalMaxRestarts`

A non-negative integer representing the maximum number of restarts allowed for the final model fitted at the end of the `fit` method. The default is `50`.

##### `finalMaxTime`

A non-negative float representing the maximum amount of time in milliseconds allowed for the final model fitted at the end of the `fit` method. The default is `1000`.

##### `fittedModel`

A `KMeans` instance representing the final model fitted at the end of the `fit` method. The default is `null`.

##### `initialization`

A string representing the method to use for initializing centroids at the beginning of each restart of a `KMeans` model. Can either be `"RANDOM"` or `"PLUS_PLUS"`. (**NOTE:** These can be accessed as static properties on the class. For example: `KMeansMeta.Initialization.PLUS_PLUS`) The default is `"PLUS_PLUS"`.

##### `k`

A non-negative integer representing the number of clusters learned by the final model fitted at the end of the `fit` method. The default is `0`.

##### `ks`

A 1-dimensional array of non-negative integers representing K-values to test during the `fit` method. The default is `[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]`.

##### `maxIterations`

A non-negative integer representing the maximum number of iterations allowed for each `KMeans` instance used to find the best K-value in the `fit` method. The default is `50`.

##### `maxRestarts`

A non-negative integer representing the maximum number of restarts allowed for each `KMeans` instance used to find the best K-value in the `fit` method. The default is `25`.

##### `maxTime`

A non-negative float representing the maximum amount of time in milliseconds allowed across _all_ `KMeans` instances used to find the best K-value in the `fit` method. (In other words, _all_ of the K-values must be tested before `maxTime` has elapsed.) The default is `3000`.

##### `method`

A string representing the method used to determine the best K-value. Can either be `"ELBOW"` or `"SILHOUETTE"`. (**NOTE:** These can be accessed as static properties on the class. For example: `KMeansMeta.Method.SILHOUETTE`) The default is `"SILHOUETTE"`.

##### `shouldNormalizeInputData`

A boolean representing whether or not data should be normalized when passed into the `fit`, `predict`, and `score` methods. "Normalized" in this context means scaling and centering each column of data to have a mean of 0 and a standard deviation of 1. The default is `true`.

##### `testSize`

A float between 0 and 1 representing the fraction of the data to set aside for testing the validity of each `KMeans` instance during the `fit` method. The default is `0.25`.

##### `timedOut`

A boolean representing whether or not any of the `KMeans` instances ran out of time while trying to run their `fit` methods. The default is `false`.

##### `tolerance`

A float representing the maximum difference between two consecutive WCSSE scores required to allow a `KMeans` instance to skip the remainder of its iterations during its `fit` method. The default is `0.0001`.

#### Methods

##### `constructor(options)`

Accepts an `options` object with these properties, all of which correspond to properties of the same names on the instance:

```js
{
  finalMaxIterations: 100,
  finalMaxRestarts: 50,
  finalMaxTime: 1000,
  fittedModel: null,
  initialization: KMeansMeta.Initialization.PLUS_PLUS,
  ks: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
  maxIterations: 50,
  maxRestarts: 25,
  maxTime: 3000,
  method: KMeansMeta.Method.SILHOUETTE,
  shouldNormalizeInputData: true,
  testSize: 0.25,
  tolerance: 1e-4
}
```

##### `destroy()`

Calls the `fittedModel.destroy()` method, which disposes of any relevant TensorFlow tensors or variables stored in memory. Returns the `KMeansMeta` instance.

##### `fit(x, fn)`

Accepts a 2-dimensional array or tensor, `x`, and a callback function, `fn`. Determines the best K-value from `ks` and then fits a final `KMeans` model, which it stores as the `fittedModel` value. The callback function, `fn`, which receives a float between 0 and 1, can be used to track the progress of the fitting process. Returns the `KMeansMeta` instance.

##### `predict(x)`

Accepts a 2-dimensional tensor array or tensor, `x`. Returns a 1-dimensional `tf.Tensor` of non-negative integers representing the indices into `centroids` to which each data point in `x` is assigned.

##### `printReport(x, centroidsTrue, labelsTrue, fn)`

Accepts a 2-dimensional array or tensor, `x`; another 2-dimensional array or tensor, `centroidsTrue`; a 1-dimensional array or tensor, `labelsTrue`; and a callback function `fn`. Calls the `fit` method using `x`, sorts the learned `centroids` so that they best align with `centroidsTrue`, predicts some labels using the `predict` method, scores the accuracy of those predictions, and then prints a report to the command line or the browser console. Returns the `KMeansMeta` instance.

##### `score(x)`

Accepts a 2-dimensional tensor, `x`. Returns a float representing the WCSSE.

<hr>

### `KMeans`

#### Properties

##### `centroids`

A 2-dimensional `tf.Tensor` representing the centroids learned during the `fit` method. The default is `null`.

##### `initialization`

A string representing the method to use for initializing centroids at the beginning of each restart. Can either be `"RANDOM"` or `"PLUS_PLUS"`. (**NOTE:** These can be accessed as static properties on the class. For example: `KMeans.Initialization.PLUS_PLUS`) The default is `"PLUS_PLUS"`.

##### `k`

A non-negative integer representing the number of clusters into which to group the data during the `fit` method. The default is `0`.

##### `maxIterations`

A non-negative integer representing the maximum number of iterations allowed within each restart in the `fit` method. The default is `100`.

##### `maxRestarts`

A non-negative integer representing the maximum number of restarts allowed in the `fit` method. The default is `50`.

##### `maxTime`

A non-negative float representing the maximum amount of time in milliseconds allowed for the model to complete its `fit` method. The default is `3000`.

##### `scaler`

A `StandardScaler` instance. The default is `null`.

##### `shouldNormalizeInputData`

A boolean representing whether or not data should be normalized when passed into the `fit`, `predict`, and `score` methods. "Normalized" in this context means scaling and centering each column of data to have a mean of 0 and a standard deviation of 1. The default is `true`.

##### `timedOut`

A boolean representing whether or not the model ran out of time while trying to run its `fit` method. The default is `false`.

##### `tolerance`

A float representing the maximum difference between two consecutive WCSSE scores required to allow the model to skip the remainder of its iterations during its `fit` method. The default is `0.0001`.

#### Methods

##### `constructor(options)`

Accepts an `options` object with these properties, all of which correspond to properties of the same names on the instance:

```js
{
  centroids: null,
  initialization: KMeans.Initialization.PLUS_PLUS,
  k: 0,
  maxIterations: 100,
  maxRestarts: 50,
  maxTime: 3000,
  shouldNormalizeInputData: true,
  tolerance: 1e-4
}
```

##### `destroy()`

Disposes of any relevant TensorFlow tensors or variables stored in memory. Returns the `KMeans` instance.

##### `fit(x, fn)`

Accepts a 2-dimensional array or tensor, `x`, and a callback function, `fn`. Finds the centroids that best represent the data. The callback function, `fn`, which receives a float between 0 and 1, can be used to track the progress of the fitting process. Returns the `KMeans` instance.

##### `initializeCentroids(x)`

Accepts a 2-dimensional array or tensor, `x`. Returns a 2-dimensional `tf.Tensor` representing a new set of centroids to be used at the beginning of a restart in the `fit` method.

##### `initializeCentroidsPlusPlus(x)`

Accepts a 2-dimensional array or tensor, `x`. Returns a 2-dimensional `tf.Tensor` representing a new set of centroids selected using the K-means++ algorithm to be used at the beginning of a restart in the `fit` method.

##### `initializeCentroidsRandom(x)`

Accepts a 2-dimensional array or tensor, `x`. Returns a 2-dimensional `tf.Tensor` representing a new set of randomly-selected centroids to be used at the beginning of a restart in the `fit` method.

##### `predict(x)`

Accepts a 2-dimensional array or tensor, `x`. Returns a 1-dimensional `tf.Tensor` of non-negative integers representing the indices into `centroids` to which each data point in `x` is assigned.

##### `printReport(x, centroidsTrue, labelsTrue, fn)`

Accepts a 2-dimensional array or tensor, `x`; another 2-dimensional array or tensor, `centroidsTrue`; a 1-dimensional array or tensor, `labelsTrue`; and a callback function `fn`. Calls the `fit` method using `x`, sorts the learned `centroids` so that they best align with `centroidsTrue`, predicts some labels using the `predict` method, scores the accuracy of those predictions, and then prints a report to the command line or the browser console. Returns the `KMeans` instance.

##### `score(x)`

Accepts a 2-dimensional tensor, `x`. Returns a float representing the WCSSE.

<hr>

### `TSNE`

#### Properties

##### `dimensions`

A non-negative integer representing the number of dimensions into which to project the data. The default is `2`.

##### `learningRate`

A non-negative float representing the learning step size. The default is `100`.

##### `maxIterations`

A non-negative integer representing the maximum number of iterations allowed for the `fitTransform` method. The default is `1000`.

##### `maxTime`

A non-negative float representing the maximum amount of time in milliseconds allowed for the model to complete its `fitTransform` method.

##### `perplexity`

According to [Wikipedia](https://en.wikipedia.org/wiki/Perplexity), perplexity is "a measure of uncertainty in the value of a sample from a discrete probability distribution". According to [Andrej Karpathy's t-SNE library](https://github.com/karpathy/tsnejs), which is the library on top of which this library's t-SNE model is built, perplexity is "roughly how many neighbors each point influences". The default is `30`.

##### `timedOut`

A boolean representing whether or not the model ran out of time while trying to run its `fitTransform` method. The default is `false`.

#### Methods

##### `constructor(options)`

Accepts an `options` object with these properties, all of which correspond to properties of the same names on the instance:

```js
{
  dimensions: 2,
  learningRate: 100,
  maxIterations: 1000,
  maxTime: 2000,
  perplexity: 30,
}
```

##### `fitTransform(x, fn)`

Accepts a 2-dimensional tensor or array, `x`, and a callback function, `fn`. Projects the data in `x` down into the desired number of dimensions. The callback function, `fn`, which receives a float between 0 and 1, can be used to track the progress of the fitting and transforming process. Returns a 2-dimensional `tf.Tensor` representing the projected data.

<hr>

## Helper classes & functions

### `accuracy(a, b)`

Accepts two 1-dimensional tensors or arrays, `a` and `b`. Returns a float between 0 and 1 representing how many of the values in `a` match their corresponding values in `b`.

### `computeParameters(x)`

Accepts a 2-dimensional tensor or array, `x`. Returns an object with these properties:

```js
{
  finalMaxIterations: ...,
  finalMaxRestarts: ...,
  maxIterations: ...,
  maxRestarts: ...,
  testSize: ...,
}
```

This function can be used to help estimate parameters to pass into `KMeansMeta` based on the shape of `x`.

### `getMemoryStatus()`

Returns an object with these properties:

```js
{
  tensorCount: tf.memory().numTensors,
  variableCount: Object.keys(tf.engine().state.registeredVariables).length,
}
```

### `pairwiseDistances(a, b)`

Accepts two 2-dimensional tensors or arrays, `a` and `b`. Returns a 2-dimensional `tf.Tensor` representing all of the pair-wise distances between all of the rows of `a` and all of the rows of `b`.

### `rSquared(xtrue, xpred)`

Accepts two tensors or arrays with the same shapes, `xtrue` and `xpred`. Returns a float value representing an R^2 score less than or equal to 1.

### `silhouette(distances, labels)`

Accepts a 2-dimensional tensor or array, `distances` (which represents pair-wise distances among all points in a dataset), and a 1-dimensional tensor or array, `labels`. Returns a float value between -1 and 1 representing, on average, how much better each data point matches its assigned cluster than its next-best cluster. Higher scores are better.

### `sortByColumn(x, j)`

Accepts a 2-dimensional tensor or array, `x`, and a non-negative integer, `j` (which represents the column number of `x` by which to sort the dataset). Returns a 2-dimensional `tf.Tensor` sorted by column `j`.

### `sortCentroids(ctrue, cpred)`

Accepts two 2-dimensional tensors or arrays, `ctrue` and `cpred`. Returns a 2-dimensional `tf.Tensor` with the same shape as `cpred`.

<hr>

### `StandardScaler`

#### Properties

##### `means`

A 1-dimensional `tf.Tensor` representing the average value of each column of a dataset. The default is `null`.

##### `stdevs`

A 1-dimensional `tf.Tensor` representing the standard deviation of each column of a dataset. The default is `null`.

#### Methods

##### `fit(x)`

Accepts a 2-dimensional tensor or array, `x`. Finds and stores the means and standard deviations of each column of `x` as `means` and `stdevs` respectively. Returns the `StandardScaler` instance.

##### `transform(x1, x2, x3, ...)`

Accepts any number of 2-dimensional tensors or arrays. Returns the same number of 2-dimensional `tf.Tensor` instances, all of which have been scaled and centered such that each column has a mean of 0 and a standard deviation of 1.

##### `untransform(x1, x2, x3, ...)`

Accepts any number of 2-dimensional tensors or arrays. Returns the same number of 2-dimensional `tf.Tensor` instances, all of which have been scaled and translated using the stored `means` and `stdevs`.