专栏首页YoungGyMMD_5a_Clustering

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 条评论
登录 后参与评论

相关文章

  • MMD_5b_ComputationalAdvertising

    OnlineAlgorithms 与Offline算法的对比 BipartiteMatching 例子 问题描述 一般用于Online场合 贪心算法 描述 算法...

    用户1147754
  • 无损卡尔曼滤波UKF与多传感器融合

    非线性系统状态估计是一大难点。KF(Kalman Filter)只适用于线性系统。EKF(Extended Kalman Filter)利用泰勒展开将非线性系统...

    用户1147754
  • DASI_1_IntroToData

    anecdotal evidence: 用极端的个例去判断整体的信息。例如“我叔叔每天吸三根烟身体很棒”来验证“吸烟对人体没有危害”。

    用户1147754
  • 金融交易 as a Game :深度强化学习方法应用探索

    来自台湾国立交通大学的作者将深度递归Q学习算法应用于量化交易,实现了在较小内存需求下的交易算法,目前这种技术只适用于在一定假设市场条件下的金融交易,在外汇市场上...

    用户7623498
  • 一顿操作猛如虎,仔细一看原地杵:AI这些惹眼进展都是虚的!

    现在的AI看上去越来越智能了,每一代IPhone都不光比上一代 Bigger,还Smarter,能更好识别你的脸、声音和操作习惯。这些都得亏更快的芯片、更多的数...

    大数据文摘
  • 开发转算法,我们应该如何准备(肺腑之言,无广告)

    随着近几年AI和算法岗位越来越热门,很多开发者都选择从开发岗向算法岗转型,但是由于大家对算法岗并不是很熟悉,并且自身对算法岗所需要的技术技能也不是很了解,因此,...

    黄鸿波
  • 牛逼了,原来大神都是这样学算法的...

    我们都知道,程序员是一个典型拼能力的岗位。那些足够优秀的人,本科毕业 3 年就可以年薪 50w+,这样的案例很多,很多就在你的身边。

    GitHubDaily
  • 非计算机专业如何转行AI,找到算法offer?

    目前,各行业都在尝试着用机器学习/深度学习来解决自身行业的需求。在这个过程中,最为稀缺的也是高质量人工智能人才。 这一年我们见证了不断有非计算机专业学生转行人工...

    CDA数据分析师
  • 非计算机专业如何转行AI,找到算法offer?

    【AI科技大本营导读】目前,各行业都在尝试着用机器学习/深度学习来解决自身行业的需求。在这个过程中,最为稀缺的也是高质量人工智能人才。 这一年我们见证了不断有非...

    AI科技大本营
  • 高校大数据工程教学实训平台解决方案

    大数据的出现催生出产业人才缺口瓶颈,在大数据挖掘项目的实施方面,被调查公司普遍缺乏相关的技术能力。75%以上的公司表示在人员和培训方面存在障碍,会大数据挖掘技术...

    数道云大数据

扫码关注云+社区

领取腾讯云代金券