MMD_5a_Clustering

聚类概述

定义

距离的定义

计算聚类过程中点和cluster的距离,有以下几种方式:

算法的分类

启发式算法

概述

启发式算法有两种方法,从下而上或者从上而下。 以从下而上为例,一开始每一个obes就是一个cluster,然后根据距离,不断地结合两个更近的cluster到一个cluster,达到一定的收敛条件后停止。

KEY POINTS

如何代表cluster

如何决定距离远近

没有欧氏距离怎么办

终止条件

总结

K-MEANS算法

特点

  1. 假设欧氏距离,也就是欧式空间是存在的
  2. 一开始必须确定k
  3. 初始集群先随机选择centroid点,个数等于k(朴素的方法是随机选择,但是容易产生距离太近属于一个cluster的点,影响分类结果)。

过程

首先先选择k个初始点当做群的中心,然后数据集中的所有点根据与群中心的远近划分属于哪个群。然后在根据群的性质取群的中心点,然后再次划分所有点属于的群,不断往复,直到群的中心不发生变化,达到稳定的状态停止。

KEY-POINTS

选择k

策略是:多选择几个k,看看average distance to centroid如何变化。 理论上,随着k的增加,这个值应该越变越小,但是减少的幅度也越来越小,我们需要的就是那个拐点。

选择初始点

初始点的选择很有学问,不能够太近都属于一个cluster,这样的话其他的cluster就发现不了。 所以,应该让点越分散越好。

复杂度

BFR算法

大数据集的难题

前面讨论的启发式算法的复杂度是O(n3)O(n^3),使用priority queue的话能减低到O(n2logn)O(n^2logn)。 KMEANS的复杂度是KNKN,但是收敛很慢,也不适用于大数据集。

因此,我们需要一种算法,能够处理数据量很大的分类问题。

概述

BFR(Bradley-Fayyad-Reina)算法,是KMEANS的变种,适用于大数据的分类(数据量只能在disk中存储,不可能全部放在memory里)。

这个算法的基础是一个很重要的假设:

assumes each cluster is normally distributed around a centroid in Euclidean space.

假设

假设的存在,使得每个cluster长得都像下图这样:

  1. axis-aligned
  2. normal distribution among each cluster in each dimension

算法

概述

三类点

DS点的更新与数据特征

整个流程

细节

怎么判断点离群中心是不是够近以加入DS

怎么判断2个CS是不是应该合成一个

CURE算法

其他算法的限制

步骤1

核心思想就是先用一些样本训练出大概的样子,并且用4个数据很好地用样本代替了总体。

步骤2

总结

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海说

动态规划算法

动态规划过程:每一次决策依赖于当前的状态,即下一状态的产生取决于当前状态。一个决策序列就是在变化的状态中产生的,这种多阶段最优化问题的求解过程就是动态规则过程。...

1950
来自专栏人工智能

机器学习的第一步:先学会这6种常用算法

【IT168 资讯】机器学习领域不乏算法,但众多的算法中什么是最重要的?哪种是最适合您使用的?哪些又是互补的?使用选定资源的最佳顺序是什么?今天笔者就带大家一起...

18310
来自专栏灯塔大数据

每周学点大数据 | No.35缩图法(二)

No.35期 缩图法(二) Mr. 王:现在我们一步一步来分析。首先,每加入一条边,都会构成一个新的连通分量,或者在已有的连通分量上增加一个点,这意味着每一...

3339
来自专栏磐创AI技术团队的专栏

一个完整的机器学习项目在Python中的演练(三)

1191
来自专栏技术沉淀

02 Learning to Answer Yes/No

从最简单最基础的二分类问题出发,演示一个简单机器学习算法PLA的完整过程,见详细课件。

562
来自专栏专知

【干货】理解深度学习中的矩阵运算

【导读】本文是作者Nikhil B撰写的“Terence Parr和Jeremy Howard的深度学习的矩阵运算”笔记。我们知道,深度学习是基于线性代数和微积...

4424
来自专栏数据结构与算法

圆的反演变换

挺神奇的东西,网上没有多少资料,我也不是太懂,代码什么的都没写过,那就抄一下百度百科吧

1172
来自专栏AI研习社

Must Know! 数据科学家们必须知道的 5 种聚类算法

聚类是一种关于数据点分组的机器学习技术。给出一组数据点,我们可以使用聚类算法将每个数据点分类到特定的组中。理论上,同一组中的数据点应具有相似的属性或特征,而不同...

3828
来自专栏机器学习算法原理与实践

用tensorflow学习贝叶斯个性化排序(BPR)

    在贝叶斯个性化排序(BPR)算法小结中,我们对贝叶斯个性化排序(Bayesian Personalized Ranking, 以下简称BPR)的原理做了...

1522
来自专栏数据科学学习手札

(数据科学学习手札09)系统聚类算法Python与R的比较

上一篇笔者以自己编写代码的方式实现了重心法下的系统聚类(又称层次聚类)算法,通过与Scipy和R中各自自带的系统聚类方法进行比较,显然这些权威的快捷方法更为高效...

2958

扫码关注云+社区