全屏网站怎么做,如何进行网站备案,黄石网站建设哪家好,有注入漏洞的网站源码前言
俗话说#xff1a;“物以类聚#xff0c;人以群分”#xff0c;在自然科学和社会科学中#xff0c;存在着大量的分类问题。所谓类#xff0c;通俗地说#xff0c;就是指相似元素的集合。
而对于分类问题#xff0c;我们通常不会提供x与y这样的映射关系#xff0…前言
俗话说“物以类聚人以群分”在自然科学和社会科学中存在着大量的分类问题。所谓类通俗地说就是指相似元素的集合。
而对于分类问题我们通常不会提供x与y这样的映射关系对于这种用机器自动找出其中规律并进行分类的问题我们称为聚类。
聚类在实际的应用中亦是非常广泛的如市场细分Market segmentation、社交圈分析social network analysis、集群计算organize computing clusters、天体数据分析astronomical data analysis
K均值(K-means)
在聚类分析中我们希望能有一种算法能够自动的将相同元素分为紧密关系的子集或簇K均值算法K-means为最广泛的一种算法。k-means是硬分类一个点只能分到一个类。
接下来我们会以图解的形式讲解该算法。
假设我们有9个点我们要把九个点分为三类
首先我们在图中随机选择三个点 把距离这三个点最近的其他点归为一类 取当前类的所有点的均值作为中心点 更新距离中心点最近的点 再次计算被分类点的均值作为新的中心点 再次更新距离中心点最近的点 计算中心点 当所有的点无法再更新到其他分类时算法结束此时继续迭代聚类中心将不会再做改变。
k-means算法输入有两个部分K聚类的个数number of clusters训练集 x ( 1 ) , x ( 2 ) , . . . , x ( m ) x^{(1)},x^{(2)},...,x^{(m)} x(1),x(2),...,x(m)
随机初始化K个聚类中心 μ 1 , μ 2 , . . . , μ k \mu_1,\mu_2,...,\mu_k μ1,μ2,...,μk重复以下迭代
for i1:m c ( i ) c^{(i)} c(i)从1到K的所有聚类中心索引index中最接近于 x ( i ) x^{(i)} x(i)的索引即 c ( i ) m i n k ∣ ∣ x ( i ) − μ k ∣ ∣ 2 c^{(i)}min_k||x^{(i)}−\mu_k||^2 c(i)mink∣∣x(i)−μk∣∣2
for k1:K
μ k \mu_k μk对于接近于聚类k点处平均值即 μ k 1 n ∑ n x ( i ) \mu_k \frac{1}{n} \sum_{n} x^{(i)} μkn1n∑x(i)
但是k-means也有其缺点例如我们有9个点初始点我们选择了图中的这三个 根据前面的算法我们最终的结果是这样的 显然这并不是我们期望的结果算法最终陷入到了局部最优解中。
最远点初始化
从上面的问题就可以发现其实k-means算法的关键就是找到合理的初始化点初始化点的位置会影响到最终的结果好坏。这里我们介绍一种优化方案最远初始化。
首先我们还是随机选一个点例如图中的红点 接下来我们要选择一个距离红点最远的点图中绿点 最后再选一个距离红点第二远的点图中黑点 初始化完成后根据前面提到的算法完成分类 但是该算法还是有一些问题对于绿点如果是噪声的话我们最终把噪声分成了一类这也并不是我们想要的结果,那么怎么解决这个问题呢
K-means
对于噪声我们知道都是一些很少量的数据那么在我们选择点的时候我门要给所有的点一个权重例如上面的绿点虽然距离最远但是只有一个点其权重较小而对于(0,1)与(0,-1)附近的点很多其权重就大。例如我们设绿点的权重是1/10(0,1)与(0,-1)的点权重是1/30但是其数量很多假设有10个点那么权重就可以理解为多个点的和那就是1/3所以最终初始化的点会选择(0,1)与(0,-1)附近噪声问题也就解决了。 K-means算法首先需要选择k个点每次要计算其余n各点的距离假设每个点的维度是d那么最终的时间复杂度是 O ( n k d ) O(nkd) O(nkd)可见其算法是线性的效率很高。
K值的选择
对于K值的选择我们可以考虑使用交叉验证根据损失函数来选择最优的K J ∑ i 1 n m i n k ∣ ∣ x ( i ) − μ k ∣ ∣ 2 J \sum_{i1}^n min_k||x^{(i)}−\mu_k||^2 Ji1∑nmink∣∣x(i)−μk∣∣2
损失函数最终会有一个拐点根据这个拐点我们就能选择最佳的K值
