chinese-whispers v0.2.11
CHINESE-WHISPERS
An Efficient Graph Clustering Algorithm for JavaScript/Node.js
Picture credit: http://www.wikihow.com/Play-Chinese-Whispers
ALGORITHM
Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems
Author: Chris Biemann, University of Leipzig, NLP-Dept. Leipzig, Germany
INSTALL
npm install chinese-whispers
EXAMPLE
Talk is cheap, show me the code!
import { ChineseWhispers } from 'chinese-whispers'
function weightFunc(a, b) {
const dist = Math.abs(a - b)
return 1 / dist
}
const cw = new ChineseWhispers({
weightFunc,
})
const dataList = [
0, 1, 2,
10, 11, 12,
20, 21, 22,
]
const clusterIndicesList = cw.cluster(dataList)
for (const i in clusterIndicesList) {
const clusterIndices = clusterIndicesList[i]
const cluster = clusterIndices.map(j => dataList[j])
console.log('Cluster[' + i + ']: ' + cluster)
}
// Cluster[0]: 0,1,2
// Cluster[1]: 10,11,12
// Cluster[2]: 20,21,22
Source code can be found at: https://github.com/huan/chinese-whispers/blob/master/examples/demo.ts
API
The ChineseWhispers
class is all you need to run the Chinese Whispers Algorithm.
1. constructor(options: ChineseWhisperOptions)
interface ChineseWhispersOptions<T> {
weightFunc: WeightFunc<T>,
epochs?: number,
threshold?: number,
}
options
weightFunc
: a function that takes two data item, calculate the weight between them and return the value.epochs
: how many epoches to run the algorithm, default 15.threshold
: minimum weight required for a edge. default 0.
const nj = require('numjs') // a Javascript implementation of numpy in Python
// calculate the distance between vectors
function weightFunc(v1, v2) {
const njV1 = nj.array(v1)
const njV2 = nj.array(v2)
const l2 = njV1.subtract(njV2)
.pow(2)
.sum()
const dist = Math.sqrt(l2)
return 1 / dist
}
const cw = new ChineseWhispers({
weightFunc,
})
2. cluster(dataList): number[][]
Process dataList
which is an array of data, returns the cluster results as an array, each array item is a cluster, and each cluster is an array which includes the indices of dataList that belongs to this cluster.
const clusterIndicesList = cw.cluster(dataList)
for (const i in clusterIndicesList) {
// get the cluster, which stores the array index dataList
const clusterIndices = clusterIndicesList[i]
// map the array index of dataList to the actual dataList data
const cluster = clusterIndices.map(j => dataList[j])
console.log('Cluster[' + i + ']: ' + cluster)
}
INSPIRATION
The code is heavily inspired by the following implementation:
- facenet chinese whispers(face cluster) in Python - zhly0
- Chinese Whispers Graph Clustering in Python - Alex Loveless
- A Python implementation of Chris Biemann's algorithm for graph clustering
- Implementation of the Chinese Whispers graph clustering algorithm in Java
- Chinese Whispers Graph Clustering Algorithm in Javascript
SEE ALSO
- The meaning and origin of the expression: Chinese whispers
- TensorFlow backed FaceNet implementation for Node.js - Face verification, face recognition and face clustering.
CHANGELOG
v0.3 master
v0.2 Aug 2018
- Upgrade TypeScript to 3.0
- DevOps to npm@next
- Upgrade rollup to 1.0
v0.1 Sep 2017
ChineseWhispers
classcluster()
class method- Unit test cases
- Travis CI & CD(publish to NPM automatically)
AUTHOR
Huan LI \zixia@zixia.net\ (http://linkedin.com/in/zixia)
COPYRIGHT & LICENSE
- Code & Docs © 2017-2019 Huan LI \zixia@zixia.net\
- Code released under the Apache-2.0 License
- Docs released under Creative Commons
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
6 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago
7 years ago