第八章-聚类算法与异常检测.md

WEEK 8

[TOC]

前言

无监督学习：聚类，异常检测anomaly detection

推荐系统-商业，广告

强化学习：电子游戏

聚类-clustering

聚类的介绍

非监督学习的一种，之前也提过，但是不给y的标签了，让机器自己分类

让机器自己寻找结构，可以将其分成簇-clusters

宇宙中的星系

k-means均值聚类算法

找到簇质心-cluster centroids

Step0.随机找两个点-簇质心

Step1.历遍所有点，按照距离远近的划分为两个簇

Step2.移动簇质心，然后重复Step1

然后再依次重复下去

最后到稳定收敛就可以了

实际上就是每个簇应该有一个质心，只不过是通过这种方式来从外围步步迭代到质心

k-means代码实现

质心的维数与数据集每个数据的维数相同，k个就代表你刚开始放了k个质心点

• Step 1

$$ 这里就是要找离x^{(i)}最近的k值(u_k点)，min_k{||x^{(i)}-u_k||}，这里是二范数(距离空间的距离) $$

• Step 2

  计算质心位置

边界情况：如果出现0个点距离近，那么可以去掉这个点，k=k-1，或者直接再随机分点

其实只要不是同一个点，就会自动分成两个簇（不然全在垂直平分线上）

即使区分不那么明显，也可以起到一定的价值作用

代价函数-distortion function

distortion-失真or畸变，index-返回值函数

中间那一项算的是中点（质心）（余弦定理）

至于这里为什么要找质心，我们可以稍微一想

$$ 我们假设簇中心坐标为p_0 = (x_1,x_2,x_3,\dots ,x_n)\\ 假设所有的样本点为{p_m = (x_1^{(m)},x_2^{(m)},x_3^{(m)},\dots,x_n^{(m)})}\\ 那么求最短距离就是min \sum_{i=1}^m||p_0 - p_i||^2\\ 展开来，就有\sum_{i=1}^m||p_0 - p_i||^2 = \sum_{i=1}^m[(x_1-x_1^{(i)})^2+(x_2-x_2^{(i)})^2+(x_3-x_3^{(i)})^2+\dots+(x_n-x_n^{(i)})^2]\\ =\sum_{i=1}^m(x_1-x_1^{(i)})^2+\sum_{i=1}^m(x_2-x_2^{(i)})^2+\sum_{i=1}^m(x_3-x_3^{(i)})^2+\dots+\sum_{i=1}^m(x_n-x_n^{(i)})^2\\ 从这里也可以看出来，其实不过多少维的数据集，x_i与x_j之间都是相互独立的(都是整体的一个基向量)整体的最小值即研究\\ \sum_{k=1}^m(x-x_k)^2的最小值(一维直线上的点平方和最小)\\ 记函数为f(x) = \sum_{k=1}^m(x-x_k)^2 = mx^2-2\sum_{k=1}^mx_kx+\sum_{k=1}^mx_k^2\\ 可见，是一个二次函数，开口向上，最小值为x = \frac{\sum_{k=1}^mx_k}{m}时，即质心位置 $$

k-means 初始化

可以直接挑某几个点作为初始迭代点

但有时会导致局部最优值

最佳的还是从上述的题目中挑出来代价函数J最小的情况

方法就是初始化的所有尝试中选择J最小的先

集群数量的选择

因为是无监督学习，所以没法给出一个很具体的正确答案方向，即没法告知优化方向

选择k值的一种方法-肘部法则-elbow method

很多时候也是看实际上的利用价值，以及图像的压缩

异常检测-Anomaly detection

异常检测介绍

异常检测通过观察正常事件的未标记数据集，从而学会检测异常或者在异常事件发生时告知

测试集是否与训练集相似？（有点儿像数理统计）

很像假设检验-接受H0与拒绝H0

高斯正态分布-Gaussian distribution

也叫bell shaped distribution（钟型分布）

实际上要是只考虑单个的正态分布信息，怎么综合考量成了一个问题

上式实际上是极大似然估计，统计学多用无偏估计

嘎嘎，远古课件限时返厂

异常检测算法

基于事件的独立性，我们可以得到向量的概率值为基向量概率乘积

嘎嘎，数学知识普及：

概率过小就是异常现象，即小概率事件

这里实际上是假设各个特征独立，所以直接相乘就是分布函数，但是一般会是多元正态分布

异常检测的设计与评估

实际上之事告诉了一个划分标准，并没有告诉数据集里哪些坏哪些好

数据倾斜是如何改正修改

实际上这里已经很想0.1分类监督学习了

选择技巧

监督学习vs异常检测

• 监督学习：数据错的跟对的都很多
• 异常检测：数据大部分都很正常

例子：Fraud-金融诈骗：有很多的方法，每年每月都有很多新的诈骗形式，异常检测就可以找到与之前不同的异类。Spam-垃圾邮件：但是监督学习是学习之前的不好的案例，然后接着找不好的。In short：异常检测能检测出新错误（新情况），监督学习是根据之前的给你分类（只是搬运工）。

一个关注过去，一个着眼未来

特征的选择

异常检测肯定得好好选，要不然有一个不是高斯分布，会影响整个的分布

尝试去转化一些特征的分布(数据的预处理)

上面是几种不同的转换（有的ln会出现0，我们+0.000001加小值即可）

记得对cv与test数据集也转换

出现一些判断错误时，可以单看同一概率下其余数据的具体特征，添加或者删除某些不正常的点

如果正常是大-大，小-小，那么可以建立一个新的特征是二者的比-就会出现异常值