宝山做手机网站建设,wordpress金币插件,网站大全官网,佛山网页设计制作K-means面试题
1. 聚类算法#xff08;clustering Algorithms#xff09;介绍
聚类是一种无监督学习—对大量未知标注的数据集#xff0c;按数据的内在相似性将数据集划分为多个类别#xff0c;使类别内的数据相似度较大而类别间的数据相似度较小。
聚类算法可以分为原型…
K-means面试题
1. 聚类算法clustering Algorithms介绍
聚类是一种无监督学习—对大量未知标注的数据集按数据的内在相似性将数据集划分为多个类别使类别内的数据相似度较大而类别间的数据相似度较小。
聚类算法可以分为原型聚类k均值算法K-means、学习向量量化、Learning Vector Quantization -LVQ、高斯混合聚类Mixture-of-Gaussian密度聚类DBSCAN层次聚类AGNES等。
2. kmeans原理详解
K-means是一种常见的聚类算法也叫k均值或k平均。通过迭代的方式每次迭代都将数据集中的各个点划分到距离它最近的簇内这里的距离即数据点到簇中心的距离。
kmean步骤
随机初始化k个簇中心坐标计算数据集内所有点到k个簇中心的距离并将数据点划分近最近的簇更新簇中心坐标为当前簇内节点的坐标平均值重复2、3步骤直到簇中心坐标不再改变收敛了
3. 优缺点及改进算法
优点效率高、适用于大规模数据集
缺点改进描述k值的确定ISODATA当属于某个簇的样本数过少时把这个簇去除当属于某个簇的样本数过多、分散程度较大时把这个簇分为两个子簇对奇异点敏感k-median中位数代替平均值作为簇中心只能找到球状群GMM以高斯分布考虑簇内数据点的分布分群结果不稳定K-means初始的聚类中心之间的相互距离要尽可能的远
4. k值的选取
K-means算法要求事先知道数据集能分为几群主要有两种方法定义k。 手肘法通过绘制k和损失函数的关系图选拐点处的k值。 经验选取人工据经验先定几个k多次随机初始化中心选经验上最适合的。
通常都是以经验选取因为实际操作中拐点不明显且手肘法效率不高。
5. K-means算法中初始点的选择对最终结果的影响
K-means选择的初始点不同获得的最终分类结果也可能不同随机选择的中心会导致K-means陷入局部最优解。
6. 为什么在计算K-means之前要将数据点在各维度上归一化
因为数据点各维度的量级不同。 举个例子最近正好做完基于RFM模型的会员分群每个会员分别有R最近一次购买距今的时长、F来店消费的频率和M购买金额。如果这是一家奢侈品商店你会发现M的量级可能几万元远大于F可能平均10次以下如果不归一化就算K-means相当于F这个特征完全无效。如果我希望能把常客与其他顾客区别开来不归一化就做不到。
7. K-means不适用哪些数据
数据特征极强相关的数据集因为会很难收敛损失函数是非凸函数一般要用kernal K-means将数据点映射到更高维度再分群。数据集可分出来的簇密度不一或有很多离群值outliers这时候考虑使用密度聚类。
8. K-means 中常用的距离度量
K-means中比较常用的距离度量是欧几里得距离和余弦相似度。
9. K-means是否会一直陷入选择质心的循环停不下来为什么迭代次数后会收敛
从K-means的第三步我们可以看出每回迭代都会用簇内点的平均值去更新簇中心所以最终簇内的平方误差和SSE, sum of squared error一定最小。 平方误差和的公式如下 L ( X ) ∑ i 1 k ∑ j ∈ C i ( x i j − x i ˉ ) 2 L(X) \sum_{i1}^{k}{\sum_{j\in C_i}{(x_{ij}-\bar{x_i})^2}} L(X)i1∑kj∈Ci∑(xij−xiˉ)2
10. 聚类和分类区别
产生的结果相同将数据进行分类聚类事先没有给出标签无监督学习
11. 如何对K-means聚类效果进行评估
回到聚类的定义我们希望得到簇内数据相似度尽可能地大而簇间相似度尽可能地小。常见的评估方式
名称公式含义如何比较sum of squares within clusters(SSW) ∑ i 1 K ∥ x i − c l i ∥ 2 \sum_{i1}^{K}{ \parallel x_i-c_{l_i} \parallel ^2} ∑i1K∥xi−cli∥2所有簇内差异之和越小越好sum of squares between clusters(SSB) ∑ i 1 K n i ∥ c i − x ˉ ∥ 2 \sum_{i1}^{K}{n_i \parallel c_i-\bar{x} \parallel ^2} ∑i1Kni∥ci−xˉ∥2簇心与簇内均值差异的加权和越大越好Calinski-Harabasz S S B K − 1 S S W N − K \frac{\frac{SSB}{K-1}}{\frac{SSW}{N-K}} N−KSSWK−1SSB簇间距离和簇内距离之比除数是惩罚项因为SSW下降地比较快越大越好BallHall S S W K \frac{SSW}{K} KSSW几乎同SSW越小越好Dunn’s index min i 1 M min j i 1 M d ( c i , c j ) max k 1 M d i a m ( c k ) \frac{\min_{i1}^M{\min_{ji1}^M{d(c_i, c_j)}}}{\max_{k1}^M{diam(c_k)}} maxk1Mdiam(ck)mini1Mminji1Md(ci,cj) w h e r e d ( c i , c j ) min x ∈ c i , x ′ ∈ c j ∥ x − x ′ ∥ 2 a n d where d(c_i, c_j)\min_{x \in c_i, x \in c_j}{\parallel x-x \parallel}^2 and whered(ci,cj)minx∈ci,x′∈cj∥x−x′∥2and d i a m ( c k ) max x , x ′ ∈ c k ∥ x − x ′ ∥ 2 diam(c_k)\max_{x, x \in c_k}{\parallel x-x \parallel}^2 diam(ck)maxx,x′∈ck∥x−x′∥2本质上也是簇间距离和簇内距离之比越大越好
另一个常见的方法是画图将不同簇的数据点用不同颜色表示。这么做的好处是最直观缺点是无法处理高维的数据它最多能展示三维的数据集。 如果维数不多也可以做一定的降维处理PCA后再画图但会损失一定的信息量。
聚类算法几乎没有统一的评估指标可能还需要根据聚类目标想评估方式如对会员作分群以后我想检查分得的群体之间是否确实有差异这时候可以用MANOVA计算当p值小于0.01说明分群合理。
12. K-means中空聚类的处理
如果所有的点在指派步骤都未分配到某个簇就会得到空簇。如果这种情况发生则需要某种策略来选择一个替补质心否则的话平方误差将会偏大。一种方法是选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。另一种方法是从具有最大SEE的簇中选择一个替补的质心。这将分裂簇并降低聚类的总SEE。如果有多个空簇则该过程重复多次。另外编程实现时要注意空簇可能导致的程序bug。
参考资料
Mann A K, Kaur N. Review paper on clustering techniques[J]. Global Journal of Computer Science and Technology, 2013.https://blog.csdn.net/hua111hua/article/details/86556322REZAEI M. Clustering validation[J].
