Components of Machine Learning

K-means Clustering

Components

1. 最优化目标函数

   $$W(C)=\sum_{l=1}^{k}\sum_{C(i)=l}\Vert x_i-\bar x_l\Vert^2$$

2. 簇中心的位置

   $$n_l=\sum_{i=1}^{n}\mathbb{I}(C(i)=l)$$

3. 最优分划

   $$C^*=\arg\min_{C}W(C)$$

Algorithm

1. 给定簇中心$\ m_1,m_2,..,m_k$，将样本点分配到离它最近的簇中心，得到一步最优分划$\ C$。

   $$\min_{C}\sum_{l=1}^{k}\sum_{C(i)=l}\Vert x_i-m_l\Vert^2,\quad \text{given}\ m_1,m_2,..,m_k$$

2. 给定每个样本点对应的簇（标签）

   $$\min_{m_1,m_2,...,m_k}\sum_{l=1}^{k}\sum_{C(i)=l}\Vert x_i-\bar x_l\Vert^2, \quad\text{given}\ C$$

3. 更新簇中心的位置

   $$m_l=\frac{1}{n_l}\sum_{c(i)=l}x_i,\quad l=1,2,..,k$$

k 的选取

ave. diag

Apriori

$D=\{t_1,t_2,…,t_n\},\quad t_i\subseteq I$。以下两个概念是十分自然的。

支持度

支持度衡量了一个项目的基本价值，我们只关心在项目集中发生次数较多的项目。

$$\sup(X)=\frac{\abs{X}}{\abs{D}}\quad\rightarrow\text{min-sup}$$

1. $X\subseteq Y,\ \sup(X)\ge\sup(Y)$
2. $X\subseteq Y$，$X\ $不是频繁项目集$\ \Rightarrow Y\ $不是频繁项目集
3. $X\subseteq Y$，$Y\ $是频繁项目集$\ \Rightarrow X\ $是频繁项目集

置信度

在超过支持度阈值的那些项目集（频繁项目集）的基础上，置信度衡量了一个潜在关系的价值，只有支持度合格，并且关联关系有一定可靠程度的关系才是有价值的。

$$conf(Y|X)=\frac{\sup(X\cap Y)}{\sup(X)}\quad\rightarrow\text{min-conf}$$ $$conf(Y|X)=conf(R)=conf(X\Rightarrow Y)$$

Algorithm

找到所有超过支持度阈值的频繁项目集是困难的，这将要求我们多次扫描数据库。我们的算法思想也非常直接，最简单的想法就是利用支持度的逆单调性筛查出一些非频繁项目集而不必再浪费时间对它们进行扫描和检验。

DBSCAN

$D=\{x_1,x_2,…,x_n\},\quad(\epsilon,MinPts)$

Components

1. $\epsilon-$领域

   $$N_{\epsilon}(x_j)=\{x_i\in D\ |\ d(x_i,x_j)\le\epsilon\}$$

2. 核心对象（core object）

   $$x_j:\abs{N_{\epsilon}(x_j)}\ge MinPts$$

3. 密度直达（directly density-reachable）

   $$x_j\ \text{core object.}\ x_i\in N_{\epsilon}(x_j)$$

4. 密度可达（density-reachable）

   $$x_i=p_1,\ x_j=p_n,\ p_{i+1}\text{由}p_i \text{密度直达}$$

5. 密度相连（density-connected）

1. 簇

2. 连接性：$x_i\in C,x_j\in C\Rightarrow x_i\ $与$\ x_j\ $密度相连

3. 最大性：$x_i\in C, x_j\ $由$\ x_i\ $密度可达$\ \Rightarrow\ x_j\in C$

   $$X=\{x'\in D\ |\ x'\text{由}x\text{密度可达},\ x\text{是核心对象}\}$$

密度直达的核心对象主干+密度可达分支

SVM