TOC
k-平均算法（英文：k-means clustering）源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是：把 n 个点（可以是样本的一次观察或一个实例）划分到 k 个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。这个问题将归结为一个把数据空间划分为 Voronoi cells 的问题。
学习这个算法的前置知识是线性代数领域,你必须了解向量空模型，该算法会将数据转化成一组向量，假设该向量具有 N 维，那么你可以把这个向量看成是在 N 维空间中的一个点，就好比向量 [1,2,3] 可以被看成是三维空间中的一个点。
随后你需要理解如何判断两个向量直接的相似度，我这里给出两种常见的相似度计算方法，这两种方法在结果上是类似的。
向量之间的距离
你可以把两个向量之间的距离看做是多维空间内两个点的距离。
并且向量的距离根据不同的形式可以分为，曼哈顿距离 欧式距离 切比雪夫距离
闵氏距离可以表现上述所有距离，只要改变 P 的取值 就能得出不同的距离 p = 1 为曼哈顿 p = 2 为欧式 p=3 为切比雪夫
距离越小说明两个向量直接更加类似
向量之间的夹角
夹角越小说明两个向量直接更加类似
核心
该算法的主要思想就是先 设立 M 个质心 在该算法的初始启动过程中，这几个质心将会从你的所有数据集合中随机挑选，随后执行核心循环
把数据挨个归类到离它最近的质心中(这里就会用到向量直接的相似度)
重新计算每个质心的位置(新的质心位置是该质心下面所有数据向量的平均值)
重复上述步骤，直到质心移动误差已经达到阈值，结束
文本分类算法介绍
在这里我要还要介绍一下关于一条文本如何转化为一个向量模型做一些介绍
首先我们需要把文本进行一些基本的处理，分解成一个单词组 比如 [what,is,your,name]
这里面中英文的分词算法事实上是非常不一样的，中文的分词算法更为复杂，比较常用的做法是利用隐马尔可夫模型。
接着我们就可以用向量来代表一个文档 比如我们的整个文档库是这样的一个向量 [1,1,1,1,1,1] 他背后会拥有一个映射表 其中的每个维度其实都代表了一个单词 比如 [what,fuck,am,bitch,cool,big]。这时候我们进入一个文档的时候，就能把他和文档集合的向量进行匹配，生成一个维度相同的文档向量，如 “fuck bitch” 可以转化为 0,1,0,1,0,0，1代表该词出现，0代表不出现。
但是这种方式其实没有那么的客观，因为某些关键词因为更加的特定，所以应该具有更加的权重，比如一句话里面
“what is java spring”
这里面 java 与 spring的权重应该需要更高，因为他属于更加特定的词汇。
所以我们可以用IDF来定义单词的权重
其中 N 代表文档的数量 df 代表该词汇在整个文档集合中的出现频率，这样一来，该单词出现频率越低，代表该词的特定程度更高。
实现
const _ = require('loadsh');
// 每一条假设都是一篇文章
const corpus = [
'avatar is fuck game',
'The Java Programer use SpBoot',
'The Java Code is good',
'Do you like fuck game ?',
'do you want play watch dogs game with me?',
];
// 求两个向量之间的距离
function MKD(x, y, p) {
var sum = 0;
for (var i = 0, len = x.length; i < len; i++) {
sum += Math.pow(Math.abs(x[i] - y[i]), p);
}
return Math.sqrt(sum);
}
// 简单英文分词算法
function splitWords(str) {
// 拆分
let lib = str.split(/(,|\s)/).filter(v => v !== ',' && v !== ' ' && v !== '?');
// 去重
return lib.filter((v, i) => lib.indexOf(v) === i);
}
function transform(corpus) {
let corpusLen = corpus.length;
let dict = splitWords(corpus.join());
let result = [];
for (const corpu of corpus) {
let corpuVector = [];
for (const dictWord of dict) {
// 未找到 该纬度的值 = 0
if (corpu.indexOf(dictWord) <= -1) {
corpuVector.push(0);
} else {
// 文档中出现该词的频率
let df = corpus.filter(v => v.indexOf(dictWord)).length / corpus.length;
// 计算 IDF
corpuVector.push(Math.log2(corpusLen / df));
}
}
// 挂载一下原句 方便查看结果
corpuVector._curpu = corpu;
result.push(corpuVector);
}
return result;
}
// 求向量数组的 平均向量
function vectorsAVG(vectors) {
const len = vectors.length;
const latitude = vectors[0].length;
let res = [];
for (let i = 0; i < latitude; i++) {
let sum = 0;
for (let j = 0; j < len; j++) {
sum += vectors[j][i];
}
res.push(sum / len);
}
return res;
}
// 把我们亲爱的样本转换成向量数组 其中每个 item 代表了每个句子的向量
// 向量的纬度等于 所有的句子 去重 去特殊符号 之后 单词个数总和
let vectors = transform(corpus);
/*
这个算法的名称是 K 均值（K-Means）聚类算法，
它让我们可以在一个任意多的数据上，
得到一个事先定好群组数量（K）的聚类结果。
1. 从 N 个数据对象中随机选取 k 个对象作为质心，这里每个群组的质心定义是，群组内所有成员对象的平均值。因为是第一轮，所以第 i 个群组的质心就是第 i 个对象，而且这时候我们只有这一个组员。
2. 对剩余的对象，测量它和每个质心的相似度，并把它归到最近的质心所属的群组。这里我们可以说距离，也可以说相似度，只是两者呈现反比关系。
3. 重新计算已经得到的各个群组的质心。这里质心的计算是关键，如果使用特征向量来表示的数据对象，那么最基本的方法是取群组内成员的特征向量，将它们的平均值作为质心的向量表示
4. 迭代上面的第 2 步和第 3 步，直至新的质心与原质心相等或相差之值小于指定阈值，算法结束。
*/
function KMeans(k, vectors) {
// 初始质心 与 group 对应
const centroids = _.shuffle(vectors).slice(0, k);
let group;
// 初始误差
let thresHolder = 100;
while (thresHolder > 0.001) {
group = new Array(k).fill(1).map(() => []);
// 计算每个目标与与当前所有质心的距离
for (const corpu of vectors) {
let min = Infinity;
let minCentroidIndex = 0;
centroids.forEach((centroid, index) => {
let len = MKD(corpu, centroid, 2);
if (len < min) {
min = len;
minCentroidIndex = index;
}
});
// 把单个 corpu 放置到对应最短欧式距离 group 里
group[minCentroidIndex].push(corpu);
}
// 重新计算每个质❤️
// 为每个 group 的中心点
let maxThresHolder = 0;
for (let i = 0; i < k; i++) {
let temp = centroids[i];
centroids[i] = vectorsAVG(group[i]);
maxThresHolder = Math.max(maxThresHolder, MKD(temp, centroids[i], 2));
}
// 误差为所有质心里面最大的那一个
thresHolder = maxThresHolder;
}
console.log('完成分类');
group.forEach((g, i) => {
console.log(`分类${i}:`);
g.forEach(v => {
console.log(v._curpu);
});
console.log('-------');
});
}
KMeans(2, vectors);
K均值分类属于无监督机器学习算法，简单来说就是无监督机器学习算法的运行结果是未知的，你只能绝对分成几个类，并不能指定每个类的主题。