基于tensorflow gpu的k-means++实现
kmeanstf的Python项目详细描述
kmeanstf
基于tensorflow gpu的k-means++实现
快速启动
要将k-means++与gpu支持结合使用，请执行以下操作：
pip安装kmeanstf
（需要TensorFlow GPU，至少1.14或2.0b版）
执行以下测试程序以生成上述图形。
importtensorflowastfimportmatplotlib.pyplotaspltfromkmeanstfimportKMeansTF# create data setX=tf.random.normal([50000,2])# create kmeanstf objectkm=KMeansTF(n_clusters=100,n_init=1)# adaptkm.fit(X)# plot result (optional)m=10000# max number of data points to displayfig,ax=plt.subplots(figsize=(8,8))ax.scatter(X[:m,0],X[:m,1],s=1)ax.scatter(km.cluster_centers_[:,0],km.cluster_centers_[:,1],s=8,c="r")plt.show()
什么是k-意思？
k-means-a.k.a.劳埃德算法-也许是最著名的聚类方法。它将k个质心（平均值）定位在给定的数据集上，以表示/聚集数据集。
从质心的一些初始位置开始，执行一些所谓的"劳埃德迭代"，直到满足停止标准。一个Lloyd迭代包含以下两个步骤：
- 为每个质心确定该质心最近的数据点子集
- 将每个质心移动到其相关数据子集的平均值（因此命名为"k-means"）
结果表明，每次lloyd迭代都会使所有数据点的欧氏平方距离之和减小到它们各自最近的质心或保持不变，在这种情况下，算法已经收敛。
最终的距离之和很大程度上取决于初始质心位置。一个共同的目标是找到一组距离和很小的质心（参见下面的示例）。
K-平均数++
2006年，提出了一种特殊的初始化方法，该方法产生了可证明良好（但通常仍然是次优）的结果：k-means++。可以将k-means++的核心描述为在给定数据点远离已定位质心的区域中对质心的顺序定位。据说k-means++在随机初始化的情况下比k-means生成更好的解决方案，而且需要更少的lloyd迭代。
可能由于其良好的效果，k-means++被选为在流行的机器学习的scikit learn python库中实现k-means的默认初始化方法。
为什么是KMeanstf？
大数据集和大量质心的k-均值在计算上是昂贵的（慢！）。由于可移植性的原因，scikit learn不支持使用GPU（https://scikit learn.org/stable/faq.html；是否添加GPU支持）。因此，我们在这里提供了一个基于tensorflow的k-means（和k-means++初始化）的实现，并在可用的情况下使用gpu。k-means++初始化是一个从k-means++的scikit learn实现到tensorflow（使用tensorflow矩阵操作而不是由scikit学习）。基于tensorflow的lloyd迭代实现借鉴了以下几个方面 shawn simister的要点https://gist.github.com/narphorium/d06b7ed234287e319f18并将大数据集拆分为给定大小的子集，以及自动为给定gpu找到合适的大小如果默认大小出现内存错误。
请注意：只有scikit learn kmeans类的一个子集在kmeanstf中实现，特别是fit（），predict（）和fit_predict（）方法。例如，没有稀疏矩阵的处理，没有小批量版本，没有样本权重。对于这些功能，请使用scikit learn。如果您想在大型数据集的GPU上执行标准K-Means（K-Means++），则使用KMeansTF最有意义。
加速
在配备nvidia gtx-1060 6mb显卡的linux机器（ubuntu 18.04 lts）上，我们观察到较大数据集（n>；200k点）的速度提高了7-10。示例：对于n=10_（100万）二维向量和k=100质心的数据集，30个Lloyd迭代的执行时间为6.34秒a.o.t.scikit learn的执行时间为62.17秒（这是9.81的加速）
在下面，您可以看到针对不同的数据集大小值测量的加速值n和针对2d数据的质心数k。对于更大的数据集，速度也更高。然而，对于小数据集，kmeanstf实际上通常比scikit learn kmeans慢。这可能是由tensorflow的启动时间引起的。有人可能会说，这并不那么相关，但也可能表明KMEanstf实现的改进潜力。
为什么这么快？
三行代码似乎来自shawn simister（https://twitter.com/narphorium/status/668234313662525440？lang=en）是tensorflow k-means实现的核心：
expanded_vectors=tf.expand_dims(samples,0)#[1,n,d]expanded_centroids=tf.expand_dims(centroids,1)# [k,1,d]distances=tf.reduce_sum(tf.square(tf.subtract(expanded_vectors,expanded_centroids)),2)#[k,n]
因此samples是包含n维向量的[n，d]张量。
质心是包含k维向量（质心）的[k，d]张量。
前两行分别将尺寸1添加到位置0和1的采样和质心中
第三行包含内部语句
tf.subtract(expanded_vectors,expanded_centroids)#[k,n,d]
这利用了"广播"，一种在tensorflow和numpy中的操作，它在应用要求张量具有相同形状的算术操作之前对齐张量的形状。在这种情况下，[1，n，d]-张量展开的_向量通过沿维度0堆叠k样本的拷贝而转换为形状[k，n，d]。[k，1，d]张量扩展的质心通过沿尺寸1叠加n个质心副本，转换为形状[k，n，d]。
这使得计算所有n数据向量和所有k质心的元素相互距离成为可能。加上外部的tf.square和tf.reduce和运算，我们有一个张量语句，它完成4个嵌套的常规循环。
纯粹的优雅！
非常适合在gpu上运行（如果它有足够的内存，因为k*n*d可能非常大）。为了不使gpu存储器成为一个限制因素，kmeanstf中的实现能够将这个张量沿着n维度分割成多个片段，每个片段都适合gpu。请参见下面的参数最大内存。
KMeanstf类
请注意：该接口设计为sklearn.cluster.kmeans的子集
当前异常：参数最大内存（见下文）
参数
n磁盘簇：int，可选，默认值：8
要形成的簇数以及要生成的质心数。
init:{'k-means++'、'random'或ndarray}
初始化方法，默认为"k-means++"：
"k-means++"：以智能方式为k-means聚类选择初始聚类中心，以加快收敛速度。
"随机"：从初始质心的数据中随机选择k个观测值（行）。
如果通过了ndarray，它应该是形状（n_簇，n_特征）并给出初始中心。
n初始：int，默认：10
使用不同质心种子运行k-means算法的时间数。最终的结果将是n_init连续运行在惯性方面的最佳输出。
最大值：int，默认值：300
一次运行的k-means算法的最大迭代次数。
公差：浮动，默认值：1e-4
宣布收敛的惯性相对公差
详细：int，默认：0 如果较大的0输出消息以分析算法的工作情况
最大内存：int，默认值：1300000000 （sklearn中没有等价物）k-均值计算中使用的最大张量的字节大小。默认值适用于NVIDIA GTX-1060。如果指定的值太大而发生内存错误，则会自动尝试（并打印）一系列递减值，直到找到给定GPU的工作值。该值随后应用作_ax_mem参数。为了不超过这个临界值，大数据集应分成分数。
属性
群集中心阵列，[n群集，n功能]
簇中心的坐标。
惯性：浮子
样本与其最近簇中心的平方距离之和。
n_iter_u:int
运行的迭代次数。
方法
适合（自我，X）
计算k-均值聚类。
拟合预测（self，x）
计算聚类中心并预测每个样本的聚类指数。
参数 X：待聚类和预测的数据，形状=[N_样本，N_特征]
返回： 标签：数组，形状[n_samples，]
每个样本所属簇的索引
预测（自我，x）
预测每个样本的聚类指数。
参数 x：待预测数据，形状=[n_样本，n_特征]
返回： 标签：数组，形状[n_samples，]
每个样本所属簇的索引
需要进一步改进的地方
- 改善较小数据集的时间行为
- 直接根据当前GPU的物理特性确定合适的最大内存值
- 启用多个GPU
- 启用TPU的使用（KMeanstf对带GPU的COLAB有效，但对TPU无效）
欢迎提出反馈和请求。
欢迎加入QQ群-->： 979659372
