# 异常点检测算法（一）

### （一）基于正态分布的一元离群点检测方法

$\mu=\sum_{i=1}^{n}x_{i}/n,$

$\sigma^{2}=\sum_{i=1}^{n}(x_{i}-\mu)^{2}/n.$

### （二）多元离群点的检测方法

#### （1）基于一元正态分布的离群点检测方法

$\mu_{j}=\sum_{i=1}^{m}x_{i,j}/m$

$\sigma_{j}^{2}=\sum_{i=1}^{m}(x_{i,j}-\mu_{j})^{2}/m$

$p(\vec{x})=\prod_{j=1}^{n} p(x_{j};\mu_{j},\sigma_{j}^{2})=\prod_{j=1}^{n}\frac{1}{\sqrt{2\pi}\sigma_{j}}\exp(-\frac{(x_{j}-\mu_{j})^{2}}{2\sigma_{j}^{2}})$

#### （2）多元高斯分布的异常点检测

$\vec{\mu}=(E(x_{1}),...,E(x_{n}))$

$n\times n$ 的协方差矩阵：

$\Sigma=[Cov(x_{i},x_{j})], i,j \in \{1,...,n\}$

$p(\vec{x})=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}} \exp(-\frac{1}{2}(\vec{x}-\vec{\mu})^{T}\Sigma^{-1}(\vec{x}-\vec{\mu}))$

#### （3）使用 Mahalanobis 距离检测多元离群点

$MDist(a,\overline{a})=\sqrt{(a-\overline{a})^{T}S^{-1}(a-\overline{a})},$

#### （4）使用 $\chi^{2}$ 统计量检测多元离群点

$\chi^{2}=\sum_{i=1}^{n}(a_{i}-E_{i})^{2}/E_{i}.$

# 异常点检测算法（三）Replicator Neural Networks

An outlier is an observation that deviates so much from other observations as as to arouse suspicion that it was generated by a different mechanism.

## RNN 算法的主要思想

$e_{i}=\sum_{j=1}^{6}(x_{i j}-r_{i j})^{2}/6$

$\theta=I_{ki}=\sum_{j=0}^{L_{k-1}}w_{kij}Z_{(k-1)j}$

$S_{k}(\theta)=tanh(a_{k}\theta) \text{ for } k=2 \text{ or } 4,$

$S_{3}(\theta)=\frac{1}{2}$+$\frac{1}{4}\sum_{j=1}^{N-1}tanh(a_{3}(\theta-\frac{j}{N}))$.

## 后向传播算法：

$\bold{x}_{i}=\bold{y}_{i}\in\mathbb{R}^{n} \text{ for all } 1\leq i\leq m$.

$\alpha_{h} = \sum_{i=1}^{n}v_{i h}x_{i} \text{ for all } 1\leq h \leq q.$

$(\alpha_{1},\cdot\cdot\cdot,\alpha_{q})=(x_{1},\cdot\cdot\cdot,x_{n})\begin{bmatrix} v_{11} & ... & v_{1q} \\ ... & ... & ... \\ v_{n1} & ... & v_{nq} \end{bmatrix}.$

$\beta_{j}=\sum_{h=1}^{q}w_{h j}b_{h} \text{ for all } 1\leq j\leq n,$

$(\beta_{1},\cdot\cdot\cdot,\beta_{n})=(b_{1},\cdot\cdot\cdot,b_{q})\begin{bmatrix} w_{11} & ... & w_{1n} \\ ... & ... & ... \\ w_{q1} & ... & w_{qn} \end{bmatrix}.$

$E_{k} =\frac{1}{2}\sum_{j=1}^{n}(\hat{y}_{kj}-y_{kj})^{2},$

$E = \frac{1}{m}\sum_{k=1}^{m}E_{k} = \frac{1}{2m}\sum_{k=1}^{m}\sum_{j=1}^{n}(\hat{y}_{kj}-y_{kj})^{2}$

### 标准 BP 算法：

$v \leftarrow v$+$\Delta v.$

$\Delta w_{hj} = -\eta \frac{\partial E_{k}}{\partial w_{hj}},$

$\frac{\partial E_{k}}{\partial w_{hj}} = \frac{\partial E_{k}}{\partial \hat{y}_{kj}} \cdot \frac{\partial \hat{y}_{kj}}{\partial \beta_{j}} \cdot \frac{\partial \beta_{j}}{\partial w_{hj}}$

$\frac{\partial E_{k}}{\partial w_{hj}} = (\hat{y}_{kj}-y_{kj})\cdot\hat{y}_{kj}\cdot(1-\hat{y}_{kj})\cdot b_{h}$

$g_{j}=-\frac{\partial E_{k}}{\partial \beta_{j}}=-\frac{\partial E_{k}}{\partial \hat{y}_{kj}}\cdot \frac{\hat{y}_{kj}}{\partial \beta_{j}}$

$g_{j}=\hat{y}_{kj}\cdot(1-\hat{y}_{kj})\cdot(y_{kj}-\hat{y}_{kj})$

$\Delta \theta_{j}=-\eta\cdot\frac{\partial E_{k}}{\partial \theta_{j}}, \Delta v_{ih}=-\eta\cdot\frac{\partial E_{k}}{\partial v_{ih}}, \Delta \gamma_{h}=-\eta\cdot\frac{\partial E_{k}}{\partial \gamma_{h}}$.

$\frac{\partial E_{k}}{\partial \theta_{j}}=\frac{\partial E_{k}}{\partial \hat{y}_{kj}}\cdot\frac{\partial\hat{y}_{kj}}{\partial\theta_{j}}=(\hat{y}_{kj}-y_{kj})\cdot(-1)\cdot f^{'}(\beta_{j}-\theta_{j})=(y_{kj}-\hat{y}_{kj})\cdot\hat{y}_{kj}\cdot(1-\hat{y}_{kj})=g_{j}$

$\frac{\partial E_{k}}{\partial v_{ih}}=\frac{\partial E_{k}}{\partial\alpha_{h}}\cdot\frac{\partial\alpha_{h}}{\partial v_{ih}}=\frac{\partial E_{k}}{\partial b_{h}}\cdot\frac{\partial b_{h}}{\partial \alpha_{h}}\cdot\frac{\partial\alpha_{h}}{\partial v_{ih}}$

$\frac{\partial \alpha_{h}}{\partial v_{ih}}=x_{ki}$

$\frac{\partial b_{h}}{\partial\alpha_{h}}=f^{'}(\alpha_{h}-\gamma_{h})=f(\alpha_{h}-\gamma_{h})\cdot(1-f(\alpha_{h}-\gamma_{h}))=b_{h}\cdot(1-b_{h})$

$\frac{\partial E_{k}}{\partial b_{h}}=\sum_{j=1}^{n}\frac{\partial E_{k}}{\partial \beta_{j}}\cdot\frac{\partial \beta_{j}}{\partial b_{h}}=\sum_{j=1}^{n}(-g_{j})\cdot w_{hj}$

$\Delta v_{ih}=\eta(\sum_{j=1}^{n}g_{j}w_{hj})\cdot b_{h}\cdot (1-b_{h})x_{ki} = \eta e_{h}x_{ki},$ 其中 $e_{h}=-\partial E_{k}/\partial\alpha_{h}=(\sum_{j=1}^{n}g_{j}w_{hj})\cdot b_{h}\cdot(1-b_{h}).$

$\Delta \gamma_{h}=(-\eta)\cdot\frac{\partial E_{k}}{\partial\gamma_{h}}=(-\eta)\cdot\frac{\partial E_{k}}{\partial b_{h}}\cdot\frac{\partial b_{h}}{\partial\gamma_{h}}=\eta\cdot(\sum_{j=1}^{n}g_{j}w_{hj})\cdot(-1)\cdot f^{'}(\alpha_{h}-\gamma_{h})=(-\eta)\cdot(\sum_{j=1}^{n}g_{j}w_{hj})\cdot b_{h}\cdot(1-b_{h})=(-\eta)\cdot e_{h} .$

$\Delta w_{hj}=\eta g_{j}b_{h} \text{ for all } 1\leq j\leq n, 1\leq h \leq q,$

$\Delta \theta_{j}=-\eta g_{j} \text{ for all } 1\leq j\leq n,$

$\Delta v_{ih}=\eta e_{h}x_{ki} \text{ for all } 1\leq i\leq n, 1\leq h\leq q,$

$\Delta \gamma_{h}=-\eta e_{h} \text{ for all } 1\leq h\leq q,$

1. 在 (0,1) 范围内随机神经网络中的所有连接权重和阈值
2. repeat
for all $(\bold{x}_{k},\bold{y}_{k})$ do

end for
3. 达到停止条件

### 累积 BP 算法：

BP 算法的目的是最小化训练集上的累计误差 $E=\sum_{k=1}^{m}E_{k}/m,$ 其中 m 是训练集合中样本的个数。不过，标准的 BP 算法每次仅针对一个训练样例更新连接权重和阈值，也就是说，标准 BP 算法的更新规则是基于单个的 $E_{k}$ 推导而得到的。通过类似的计算方法可以推导出累计误差的最小化更新规则，那就得到了累计误差逆传播（accumulate error backpropagation）算法。标准 BP 算法需要进行更多次的迭代，并且参数的更新速度快，累积 BP 算法必须扫描一次训练集合才会进行一次参数的更新，而且累计误差下降到一定的程度以后 ，进一步下降就会明显变慢，此时标准 BP 算法往往会更快的得到较好的解，尤其是训练集合大的时候。

## 训练方法：

（1）把数据集合的每一列都进行归一化；

（2）选择 70% 的数据集合作为训练集合，30% 的数据集合作为验证集合。或者 训练集合 : 验证集合 = 8 : 2，这个需要根据情况而定。

（3）随机生成一个三层的神经网络结构，里面的权重都是随机生成，范围在 [0,1] 内。输入层的数据和输出层的数据保持一致，并且神经网络中间层的节点个数是输入层的一半。

（4）使用后向传播算法（back-propagation）来训练模型。为了防止神经网络的过拟合，通常有两种策略来防止这个问题。（i）第一种策略是“早停”（early stopping）：当训练集合的误差降低，但是验证集合的误差增加时，则停止训练，同时返回具有最小验证集合误差的神经网络；（ii）第二种策略是“正则化”（regularization）：基本思想是在误差目标函数中增加一个用于描述网络复杂度的部分，例如链接权和阀值的平方和。

## 参考文献：

[1] Anomaly Detection Using Replicator Neural Networks Trained on Examples of One Class, Hoang Anh Dau, Vic Ciesielski, Andy Song

[2] Replicator Neural Networks for Outlier Modeling in Segmental Speech Recognition, Laszlo Toth and Gabor Gosztolya

[3] Outlier Detection Using Replicator Neural Networks, Simon Hawkins, Honxing He, Graham Williams and Rohan Baxter

# 聚类算法（一）

### K-均值（K-Means）聚类算法

K 均值聚类算法是用来发现给定数据集的 K 个簇的一种无监督学习算法，簇的个数是由人工给定的，每个簇使用质心（Centroid）和相应的半径（Radius）来描述。需要量化的误差指标有误差平方和（sum of squared error）等。

K-均值算法是一种启发式的算法。它会渐近地提高聚类的质量，达到局部的最优解，但是就是因为这样，才容易陷入局部最优解，而没有达到全局最优解，所有有人提出了二分 K-均值算法。启发式的聚类算法很适合发现中小规模的簇，对于大数据集合，从计算量来说成本则会很高。K-均值算法也有着自己的不足之处，通过下面算法可以发现 K-均值算法对离群点特别敏感，离群点的存在会直接影响着 K-均值算法的效果。

K 均值算法的流程是这样的。首先，随机确定 K 个初始点作为质心。然后将数据集中的每个点分配到每一个簇中，具体来讲，为每一个数据点找距离其最近的质心，并将其分配给该质心所对应的簇。这一步完成之后，每个簇的质心更新为该簇所有点的平均值。

K-Means 的伪代码：

创建K个点作为初始的质心（经常是随机选择数据点中的K个点，而不是平面上随机的K个点）

对数据集中每个数据点

对每个质心，计算质心与数据点之间的距离

将数据点分配到距离其最近的簇

对每一个簇，计算簇中所有点的均值并将均值作为质心

### 效果评估：

SSE 指的是 Sum of Squared Error（误差平方和）越小表示数据点越接近它们的质心，聚类的效果也就越好。质心使用 c[i] 表示，质心 c[i] 所包含的对象集合使用 C[i] 表示。如果用 p 表示 C[i] 中的某个对象，dist(p,c[i]) 表示的就是对象和质心 c[i] 的距离。那么误差平方和则定义为

$E=\sum_{i=1}^{K}\sum_{p \in C[i]} dist(p, c[i])^{2}$

### 二分 K 均值聚类（Bisecting K-Means）

将所有的点看成一个簇

对于每一个簇

计算总误差

在给定的簇上面进行2均值聚类

计算将该簇一分为二之后的总误差（指的是这两个簇的误差与其他剩余集的误差之和）

选择使得总误差最小的那个簇进行划分操作

# KL散度（Kullback-Leibler Divergence）

### KL 散度的数学定义：

$D_{KL}(P||Q)=\sum_{i}P(i)\log_{2}(P(i)/Q(i)).$

$D_{KL}(P||Q)=\int_{X}p(x)\log_{2}(p(x)/q(x))dx,$

### KL 散度的基本性质：

（1）KL 散度总是非负的，并且只有 $P(x)=Q(x)$ 几乎处处成立的时候，才会有

$D_{KL}(P||Q)=0.$

$D_{KL}(P||Q)=-E_{P}(\log_{2}(q(x)/p(x)))$

$\geq -log_{2}(E_{p}(q(x)/p(x)))=-log_{2}(\int_{X}q(x)dx)=0.$

（2）如果 $P_{1}, P_{2}$ 是独立分布，并且联合分布是 $P(x,y)=P_{1}(x)P_{2}(y),$ $Q_{1},Q_{2}$ 是独立分布并且联合分布是 $Q(x,y)=Q_{1}(x)Q_{2}(y),$ 那么

$D_{KL}(P||Q)=D_{KL}(P_{1}||Q_{1})$ + $D_{KL}(P_{2}||Q_{2}).$

（3）如果定义分布 $P$$Q$ 的交叉墒是

$H(P,Q)=-\int_{X}p(x)\log_{2}q(x)dx,$

$H(P)=-\int_{X}p(x)\log_{2}p(x)dx,$

（4）KL 散度是两个概率分布 $P$$Q$ 差别的非对称性的度量。 KL 散度是用来度量使用基于 $Q$ 的编码来编码来自 $P$ 的样本平均所需的额外的位元数。典型情况下， $P$ 表示数据的真实分布，$Q$ 表示数据的理论分布，模型分布，或 $P$ 的近似分布。

（5）从KL散度的定义可以得出

$D_{KL}(P||Q)\neq D_{KL}(Q||P),$

$DS_{KL}(P,Q)=(D_{KL}(P||Q)$ + $D_{KL}(Q||P))/2.$

### 简单例子：

$D_{KL}(P||Q)$

$=0.1*\log_{2}(0.1/0.4)$ + $0.2*\log_{2}(0.2/0.3)$ + $0.3*\log_{2}(0.3/0.2)$ + $0.4*\log_{2}(0.4/0.1).$

# 线性模型

### 一维输入变量

$f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(x).$

$f_{\theta+\theta^{'}}(x)=f_{\theta}(x)+f_{\theta^{'}}(x),$

$f_{\alpha \theta}(x)=\alpha f_{\theta}(x).$

Weierstrass第一逼近定理：假设$f(x)$是闭区间$[a,b]$上的连续函数，对于任意的$\epsilon>0$，则存在多项式$P(x)$使得对于所有的$x\in [a,b]$，有$|f(x)-P(x)|<\epsilon$。

$\phi_{j}(x)=x^{j-1}$

$\phi(x)=(1,x,x^{2},\cdot\cdot\cdot, x^{b-1})^{T}.$

$\phi_{0}(x)=1,\phi_{2j-1}(x)=\sin(jx),\phi_{2j}(x)=\cos(jx),$ 其中$j\geq 1.$

### 高维输入变量

$f_{\theta}(\textbf{x})=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(\textbf{x})={\theta}^{T}\phi(\textbf{x}).$

$f_{\theta}(x)=\sum_{j_{1}=1}^{b^{'}}\cdot\cdot\cdot\sum_{j_{d}=1}^{b^{'}}\theta_{j_{1},\cdot\cdot\cdot,j_{d}}\phi_{j_{1}}(x^{(1)})\cdot\cdot\cdot \phi_{j_{d}}(x^{(d)}).$

$f_{\theta}(x)=\sum_{k=1}^{d}\sum_{j=1}^{b^{'}}\theta_{k,j}\phi_{j}(x^{(k)}).$

### 核模型

$K(\mathbf{x},\mathbf{c})=\exp(-||\mathbf{x}-\mathbf{c}||_{2}^{2}/(2h^{2})),$

$f_{\theta}(\mathbf{x})=\sum_{j=1}^{n}\theta_{j}\cdot K(\mathbf{x},\mathbf{x}_{j}).$

# 层级模型

$f_{\theta}(\mathbf{x})=\sum_{j=1}^{b}\alpha_{j}\cdot\phi(\mathbf{x};\mathbf{\beta}_{j}).$

$\phi(\mathbf{x};\beta)=1/(1+\exp(-\mathbf{x}^{T}\omega-\gamma)),$ 其中$\beta=(\omega^{T},\gamma)^{T}$

$\phi(\mathbf{x};\beta)=\exp(-||\mathbf{x}-\mathbf{c}||_{2}^{2}/(2h^{2})),$ 其中$\beta=(\mathbf{c}^{T},h)^{T}.$