注明：
原理部分的内容均来自周志华的西瓜书，真正的大师之作。
其他内容来自开源包文档、开源电子书、ipynb文档等。

# 半监督聚类 （semi-supervised clustering）

聚类是一种典型的无监督学习任务，然而在现实聚类任务中我们往往能获得一些额外的监督信息，于是可以通过半监督聚类来利用额外监督信息以获得更好的聚类效果。

聚类任务中获得额外监督信息大致有两种类型：

• 样本约束：

  必连 (must-link): 指的是样本必属于同一个簇

  勿连 (cannot-link): 样本必不属于同一个簇

• 样本标签：

  监督信息来自少量带有标签的样本

## 约束$k$均值算法 (pseudo-code)

约束$k$均值算法 (Constrained k-means) 是利用第一类监督信息的代表。给定样本集 $D={x_1, x_2, \ldots, x_m}$ 以及 “必连” 关系集合 $\cal{M}$ 和 “勿连” 关系集合 $\cal{C}$ ，$(x_i, x_j) \in \cal{M}$ 表示 $x_i, x_j$ 必属于同簇，$(x_i, x_j) \in \cal{C}$ 表示 $x_i, x_j$ 必不属于同簇。该算法是 $k$-means 算法的扩展，它在聚类过程中要确保样本的约束得到满足，否则返回错误提示，算法如下：

输入： 样本集 $D = {x_1, x_2, \ldots, x_m}$;

​ 必连约束集合 $\cal{M}$ ;

​ 勿连约束集合 $\cal{C}$ ;

注明：
原理部分的内容均来自周志华的西瓜书，真正的大师之作。
其他内容来自开源包文档、开源电子书、ipynb文档等。

# 原型聚类

原型¹聚类也称为 “基于原型的聚类(prototype-based clustering)”，此类算法假设聚类结构能够通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。

## $k$ 均值聚类算法

给定样本集 $D = {x_1, \ldots, x_m }$ ，“$k$ 均值($k$-means)” 算法针对聚类所得簇划分 $\mathcal{C} = {C_1, \ldots, C_k }$ 最小化平方误差 $$ \tag{9.24} E = \sum^k_{i=1} \sum_{x \in C_i} ||x - \mu_i||^2_2 , $$ 其中，$\mu_i = {1 \over |C_i|} \sum_{x \in C_i} x$ 是簇 $C_i$ 的均值向量。直观来看，式(9.24)在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，$E$ 值越小则簇内样本相似度越高。

最小化式(9.24)并不容易，找到它的最优解需考察样本集 $D$ 的所有可能簇划分，这是一个 NP 难问题² 。因此，$k$ 均值算法采用了贪心策略，通过迭代优化来近似求解式(9.24)。算法流程如下，其中第1行对均值向量进行初始化，在第4-8行与第9-16行依次对当前簇划分及均值向量迭代更新，若迭代更新后聚类结果保持不变，则在第18行将当前的簇划分结果返回。

k 均值算法流程

输入：样本集 $D = {x_1, \ldots, x_m }$ ；

## Deep Forest

• online paper, follow the link to all the details.

In this paper, we extend our preliminary study which proposes the gcForest (multi-Grained Cascade Forest) approach for constructing deep forest, a non-NN style deep model. This is a novel decision tree ensemble, with a cascade structure which enables representation learning by forests. Its representational learning ability can be further enhanced by multi-grained scanning, potentially enabling gcForest to be contextual or structural aware. The cascade levels can be automatically determined such that the model complexity can be determined in a data-dependent way rather than manually designed before training; this enables gcForest to work well even on small-scale data, and enables users to control training costs according to computational resource available. Moreover, the gcForest has much fewer hyper-parameters than DNNs. Even better news is that its performance is quite robust to hyper-parameter settings; our experiments show that in most cases, it is able to get excellent performance by using the default setting, even across different data from different domains.

## Tree-based models

# Part-I: Theorist views

基本术语和符号约定

一般地，令 $D = {x_1, x_2, \ldots, x_m }$ 表示包含 $m$ 个示例的数据集，每个示例由 $d$ 个属性描述，则每个示例 $x_i = (x_{i1}, x_{i2}, \ldots, x_{id})$ 是 $d$ 维样本空间 $\mathcal{X}$ 的一个向量¹，$x_i \in \mathcal{X}$, 其中 $x_{ij}$ 是 $x_i$ 在第 $j$ 个属性上的取值， $d$ 称为样本 $x_i$ 的“维数”（dimensionality）。

要建立一个关于“预测(prediction)”的模型，单有示例数据（也称为样本，sample）还不行，我们还需要获得训练样本的“结果”信息，例如，一个描述西瓜的记录“（（色泽=青绿；根蒂=蜷缩；敲声=浊响），好瓜）”。这里，关于示例结果的信息，例如 “好瓜” ，称为 “标记(label)”；拥有了标记信息的示例，则称之为 “样例(example)"。

一般地，用 $(x_i, y_i)$ 表示第 $i$ 个样例，其中 $y_i \in \mathcal{Y}$ 是示例 $x_i$ 的标记， $\mathcal{Y}$ 是所有标记的集合，亦称“标记空间(label space)”或“输出空间”。

如果我们想要预测的是离散值，例如 “好瓜” “坏瓜”，此类学习任务称为 “分类(classification)”；如果要预测的是连续值， 例如西瓜的成熟度0.9，0.4，此类学习任务称为 “回归(regression)”。二分类(binary classification)任务中，通常令 $\mathcal{Y} = {-1, +1 }$ 或 $\mathcal{Y} = {0, 1 }$；对于多分类(multi-class classification), $|\mathcal{Y}| > 2$；对回归任务，$\mathcal{Y} = \R$，$\R$ 为实数集。