王半仙的学习分享

1 DBSCAN算法概况

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，基于密度的、对噪声鲁棒的空间聚类方法）是一种基于密度的经典聚类算法

2 DBSCAN算法细节

1. 遍历所有样本，寻找关键的核心点（邻域内样本数>=MinPoints）
2. 核心点及其邻域内的样本（包括其他核心点）形成了临时聚类簇
3. 当核心点A属于核心点B的临时聚类簇时，合并两处临时聚类簇
4. 重复以上过程，直至找不到新的可合并临时聚类簇

Read more

本文中大部分算法都可通过R语言的latend包复现

1 GBTM

轨迹分组算法（Group-based trajectory model，GBTM）

• 最早由 Daniel Nagin 于 1999 年在知名心理学方法学杂志「Psychological Methods」开始推展
• 接着由 Bobby Jones 与 Daniel Nagin 于 2001 年发表了 SAS procedure2，于是此方法慢慢

Read more

1 算法概况

谱聚类（spectral clustering）：一种基于图的聚类算法

前置知识：图论基础概念、拉普拉斯矩阵

核心思想：将数据转化为图的形式，距离近的数据间对应的边权重高，距离远的数据间对应的边权重低。之后通过切图的方式，使得不同子图间的边权值和尽可能低，子图内部的边权值和尽可能高，从而达到聚类的目的

2 算法细节

2.1 数据转图

核心思想：把每个样本看作一个节点，然后构建任意两点$(x_i,x_j)$间权重边$w_{ij}$

方法1：$\epsilon-

Read more

1 算法概况

Chinese Whispers（简称CW）算法，是一种无监督的图聚类算法

CW算法运行效率高，但结果存在不确定性，常用于人脸聚类或文本聚类

2 算法步骤

以人脸聚类为例，先进行图的初始化（构建无向加权图）：每个人脸图片为一个节点，不同节点通过计算相似度，然后连接相似度超出指定阈值的节点，并以相似度作为边的权重

算法步骤

1. 对于N个人脸样本，每个样本节点先单独成簇（自成一类）
2. 遍历所有节点，根据每个节点的邻节点所属类别，计算权重累加
3. 修正节点类别，选择最终累加权重最高的类别
4. 如果有多个权重最高的类别，

Read more

1 K-means算法概况

K均值算法（即，k-means clustering），是一种无监督聚类算法

K-means算法属于NP-hard问题，不过存在高效的启发式算法，能快速收敛到一个局部最优解

2 K-means算法细节

算法步骤

1. 对于N个样本，随机选择其中K个，作为最初的质心
2. 遍历所有样本，选择最新的质心进行归类，形成K个簇
3. 根据每个簇的样本重新计算质心（比如求均值）
4. 重复步骤2-3，直到每个簇质心基本不再变化或达到最大迭代次数

算法的收敛过程如下所示：

（图源来自https

Read more