采用EM算法求解的模型有哪些,为什么不用牛顿法或梯度下降法？
EM的求解原理:
因为在求解一个含有隐变量的概率模型时,目标是极大化观测数据关于参数的对数似然,而极大化的主要困难是还有未观测数据并有包含和的对数,而EM通过迭代,不断求解下界极大化,而逐步求解对数似然函数极大化.
用EM算法求解的模型有哪些？
用EM算法的模型一般有GMM或者协同过滤,k-means也属于EM.
EM与k-means
k-means原理
注意：k-means在运行之前需要进行归一化处理.不然可能会因为样本在某些维度上过大导致距离计算失效.
假设给定一个数据集X=$\{x_1,x_2,…,x_N\}$,和类的个数K.我们的每个类都用一个中心点$\mu_k$表示.每个数据集都应该被归为某一个类,那么我们定义$r_{nk}$:如果$x_n$属于类k,则$r_{nk}$=1;如果$x_n$不属于类k,则$r_{nk}$=0.那么我们就可以定义一个误差函数J:
误差函数直观上理解为每个数据点离自己类的中心点的距离之和.我们的目标就是min J.我们发现,J中$r_{nk}$和$\mu_k$都是未知的,直接求导的话,没有闭式解.所以换一个方法.就是k-means算法
k-means算法分为两步:
- 假设各个类的中心$\mu_k$已知,那么所有$r_{nk}$都可求出,计算方法采用最近邻原则,即
- 假设所有$r_{nk}$都已知,将J对$\mu_k$求导等于零,那么:那么容易得到$\mu_k$的闭式解:
通俗讲,k-means第一步是给每个数据点分类,分类方法采用最近邻原则;第二步根据分类的结果,将中心点重新计算,计算方式为类中所有点的中心点.
k-means是最简单的EM算法,其也分为两步:(1)Expectation(2)Maximization
第一步计算$r_{nk}$其实是计算Expectation的一步,$r_{nk}$可以看作是$x_n$属于各个类的概率,只不过它们取值只有0和1,但也符合概率的定义.那么$x_n$的误差期望就是:$\sum_kr_{nk}||x_n-\mu_k||^2$.那么所有点的误差期望之和为:
我们可以发现,这其实就是k-means算法中的J.
EM算法第二步就是对求得的期望求最值.那么在k-means算法中,第二步对J求导等于0其实就是在求最值,这也正好对应EM的第二步.所以我们可以看到,其实k-means就是EM算法的一种。
一个隐藏条件：我们知道用平方和来计算误差其实就是隐性假设原始数据服从高斯分布,那么用EM算法和高斯分布也能推导出k-means.
为什么不用牛顿法或梯度下降法?
由于求和的项数随着隐变量的数目指数上升,会给梯度计算带来麻烦.EM算法是一种非梯度化优化算法.
描述什么是K-means算法?请列出步骤,以及分析优缺点
k-means是一种广泛使用的聚类算法,它是基于相似性的无监督算法,通过比较样本之间的相似性,将较为相似的样本划分在同一个类别中。
步骤1：初始化常数k,随机初始化k个聚类
步骤2:重复计算样本到每个聚类中心的相似度,将样本划分到最相似的类别中,然后计算出每个类别样本的均值,作为每个类别的聚类中心
步骤3:输出最终的聚类中心和样本所属的类别
优缺点:
- K-means简单易于实现,且解释性好
- 但是聚类中心的个数K需要事先给定,对效果的影响较大.可以用K-means++来解决这个问题
- K-means受初始随机化影响.
K-means++
K-means++选择初始聚类中心的基本思想是：初始的聚类中心之间的相互距离要尽可能远.
- 从输入的数据点集合中选择一个点作为第一个聚类中心
- 对于数据集中的每一个点x,计算他与最近聚类中心(指已选择的聚类中心)的距离$D(x)$
- 选择一个新的数据点作为新的聚类中心,选择的原则是D(x)较大的点,被选作为聚类中心的概率大
- 重复2,3直到k个聚类中心被选出来
- 利用k个初始的聚类中心来运行标准的k-means算法
DBSCAN
DBSCAN是一种具有噪声的基于密度的聚类方法.和K-means这些一般只适用于凸样本集的聚类相比,DBSCAN既可以适用于凸样本集,也可以适用于非凸样本集.
DBSCAN密度定义:基于一组邻域来描述样本的紧密程度,参数$(\epsilon,Minpts)$,其中$\epsilon$描述了某一样本的邻域距离阈值,Minpts描述了某一样本的距离为$\epsilon$的邻域的样本个数的阈值
假设样本集D=$(x_1,x_2,…,x_m)$,则DBSCAN具体的密度描述定义如下:
(1)$\epsilon$邻域:对于$x_j$∈D,其$\epsilon$-邻域包含样本集D中与$x_j$的距离不大于$\epsilon$的子样本集,即$N_{\epsilon}(x_j)=\{x_i∈D|distance(x_i,x_j)≤\epsilon \}$,这个子样本集的个数记为$|N_{\epsilon}(x_j)|$
(2)核心对象:对于任一样本$x_j$∈D,如果$\epsilon$-邻域对应的$N_{\epsilon}$(x_j)至少包含MinPts个样本,即如果$|N_{\epsilon}(x_j)|≥Minpts$,则$x_j$是核心对象.
(3)密度直达:如果$x_i$位于$x_j$的$\epsilon$-邻域中,且$x_j$是核心对象,则称$x_i$由$x_j$密度直达。注意反之不一定成立,即此时不能说$x_j$由$x_i$密度直达,除非且$x_i$也是核心对象.(这是不对称性)
(4)密度可达:对于$x_i$和$x_j$,如果存在样本序列$p_1,p_2,…,p_T$满足$p_1=x_i$,$p_T=x_j$,且$p_{t+1}$由$p_t$密度直达,则称$x_j$由$x_i$密度可达.也就是说,密度可达满足传递性.此时序列中的传递样本$p_1,p_2,…,p_{T-1}$均为核心对象,因为只有核心对象才能是其他样本密度直达。注意密度可达不满足对称性,因为密度直达不满足对称性(因为最后一个样本$p_{T}$不一定是核心对象).
(5)密度相连:对于$x_i$和$x_j$,如果存在核心对象样本$x_k$,使得$x_i$和$x_j$均由$x_k$密度可达,则称$x_i$和$x_j$密度相连.注意密度相连关系是满足对称性的.
DBSCAN聚类思想:由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者一个簇.
怎样找到簇样本集合?
任意选择选择一个没有类别的核心对象作为种子,然后找到所有这个核心对象能够密度可达的样本集合,即为一个聚类簇.接着选择另一个没有类别的核心对象去寻找密度可达的样本的样本集合,这样就得到另一个聚类簇.直到运行到所有核心对象都有类别为止.
还有一些小问题要解决:
(1)一些异常样本点或者说少量有利于簇外的样本点,这些点不在任何一个核心对象周围.DBSCAN将这些点标记为噪音点
(2)距离的度量问题:如何计算某样本和核心对象样本的距离.一般采用最近邻思想
(3) 某些样本可能到两个核心对象的距离都小于$\epsilon$,但是两个核心对象又不是密度直达,又不属于同一个聚类簇,那么怎么界定这个样本的类别呢?一般来说,此时DBSCAN采用先来后到的原则,先进性聚类的类别簇会标记该样本为它的类别,也就是说DBSCAB算法是个不完全稳定的算法.
优缺点：
优点:
(1)聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类
(2)与K-means比较起来,不需要输入要划分的聚类个数
(3)聚类簇的形状没有偏倚
(4)可以在需要时输入过滤噪声的参数
缺点:
(1)当数据量增大时,要求较大的内存支持I/O消耗也很大
(2)当空间聚类密度不均匀、聚类间距差很大时,聚类质量很差,因为这种情况参数$MinPts$和$\epsilon$选取困难.
(3)算法聚类效果依赖于距离公式选取,实际应用中常用欧式距离,对高维数据会导致维度灾难.
当我们拿到数据进行建模时,如何选择更合适的算法？
机器学习
- 先看是分类问题还是回归问题(分类先从常用的分类模型里选择)
- 其次看数据特征的数据类型,然后做一些初步的数据统计,比如是否数据均衡,大致的数据分布是 怎么样的(不同类别的分布)
- 然后判断用哪个比较合适一些,是树模型还是其他的分类模型
- 最后查看kaggle有没有相似的案例,别人做的方法有没有值得子集学习的地方
深度学习
对于深度学习算法选择也是看任务目标选择合适的模型,图像类首选cnn及各种cnn的变种,时间顺序相关的选择rnn,生成类的选择VAE或GAN,有明确规则的选择RL
什么式特征提取,解释一下特征提取与特征选择的区别
特征选择:choosing only the most import features or the other methods of dimensionality reduction 数据不变,特征量减少(Filter,Wrapper,Embedded)
特征提取:constructing new features from the existing data 数据转换特征量减少(PCA,LDA,TF-IDF,Word2vec,CountVectorizer)
特征提取和特征选择都是属于降维,前者通过对原始特征的一系列变换生成新的特征空间,而特征选择并不改变原始特征.