处理聚类问题常⽤算法-----算法岗⾯试题
●什么是DBSCAN
参考回答：
DBSCAN是⼀种基于密度的空间聚类算法，它不需要定义簇的个数,⽽是将具有⾜够⾼密度的区域划分为簇，并在有噪声的数据中发现任意形状的簇，在此算法中将簇定义为密度相连的点的最⼤集合。
● k-means算法流程
参考回答：
从数据集中随机选择k个聚类样本作为初始的聚类中⼼，然后计算数据集中每个样本到这k个聚类中⼼的距离，并将此样本分到距离最⼩的聚类中⼼所对应的类中。将所有样本归类后，对于每个类别重新计算每个类别的聚类中⼼即每个类中所有样本的质⼼，重复以上操作直到聚类中⼼不变为⽌。
● LDA的原理
参考回答：
LDA是⼀种基于有监督学习的降维⽅式，将数据集在低维度的空间进⾏投影，要使得投影后的同类别的数据点间的距离尽可能的靠近,⽽不同类别间的数据点的距离尽可能的远。
●介绍⼏种机器学习的算法，我就结合我的项⽬经理介绍了些RF, Kmeans等算法。
参考回答：
常见的机器学习算法：
1）. 回归算法：回归算法是试图采⽤对误差的衡量来探索变量之间的关系的⼀类算法。回归算法是统计机器学习的利器。常见的回归算法包括：最⼩⼆乘法（Ordinary Least Square），逻辑回归（Logistic Regression），逐步式回归（Stepwise Regression），多元⾃适应回归样条（Multivariate Adaptive Regression Splines）以及本地散点平滑估计（Locally Estimated Scatterplot Smoothing）。
2）. 基于实例的算法：基于实例的算法常常⽤来对决策问题建⽴模型，这样的模型常常先选取⼀批样本数据，然后根据某些近似性把新数据与样本数据进⾏⽐较。通过这种⽅式来寻最佳的匹配。因此，基于实例的算法常常也被称为“赢家通吃”学习或者“基于记忆的学习”。常见的算法包括 k-Nearest Neighbor(KNN), 学习⽮量量化（Learning Vector Quantization， LVQ），以及⾃组织映射算法（Self-
Organizing Map，SOM）。深度学习的概念源于⼈⼯神经⽹络的研究。含多隐层的多层感知器就是⼀种深度学习结构。深度学习通过组合低层特征形成更加抽象的⾼层表⽰属性类别或特征，以发现数据的分布式特征表⽰。
3）. 决策树学习：决策树算法根据数据的属性采⽤树状结构建⽴决策模型，决策树模型常常⽤来解决分类和回归问题。常见的算法包括：分类及回归树（Classification And Regression Tree，CART），ID3 (Iterative Dichotomiser 3)，C4.5，Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 随机森林（Random Forest），多元⾃适应回归样条（MARS）以及梯度推进机（Gradient Boosting Machine，GBM）。
4）. 贝叶斯⽅法：贝叶斯⽅法算法是基于贝叶斯定理的⼀类算法，主要⽤来解决分类和回归问题。常见算法包括：朴素贝叶斯算法，平均单依赖估计（Averaged One-Dependence Estimators，AODE），以及Bayesian Belief Network（BBN）。
5）. 基于核的算法：基于核的算法中最著名的莫过于⽀持向量机（SVM）了。基于核的算法把输⼊数据映射到⼀个⾼阶的向量空间，在这些⾼阶向量空间⾥，有些分类或者回归问题能够更容易的解决。常见的基于核的算法包括：⽀持向量机（Support Vector Machine，SVM），径向基函数（Radial Basis Function，RBF)，以及线性判别分析（Linear Discriminate Analysis，LDA)等。
6）. 聚类算法：聚类，就像回归⼀样，有时候⼈们描述的是⼀类问题，有时候描述的是⼀类算法。聚类算法通常按照中⼼点或者分层的⽅式对输⼊数据进⾏归并。所以的聚类算法都试图到数据的内在结构，以便按照最⼤的共同点将数据进⾏归类。常见的聚类算法包括 k-Means 算法以及期望最⼤化算法（Expectation Maximization，EM）。
7）. 降低维度算法：像聚类算法⼀样，降低维度算法试图分析数据的内在结构，不过降低维度算法是以⾮监督学习的⽅式试图利⽤较少的信息来归纳或者解释数据。这类算法可以⽤于⾼维数据的可视化或者⽤来简化数据以便监督式学习使⽤。常见的算法包括：主成份分析（Principle Component Analysis，PCA），偏最⼩⼆乘回归（Partial Least Square Regression，PLS），Sammon映射，多维尺度（Multi-Dimensional Scaling, MDS）, 投影追踪（Projection Pursuit）等。
8）. 关联规则学习：关联规则学习通过寻最能够解释数据变量之间关系的规则，来出⼤量多元数据集中有⽤的关联规则。常见算法包括Apriori算法和Eclat算法等。
9）. 集成算法：集成算法⽤⼀些相对较弱的学习模型独⽴地就同样的样本进⾏训练，然后把结果整合起来进⾏整体预测。集成算法的主要难点在于究竟集成哪些独⽴的较弱的学习模型以及如何把学习结果整合起来。这是⼀类⾮常强⼤的算法，同时也⾮常流⾏。常见的算法包括：Boosting，Bootstrapped Aggregation（Bagging），AdaBoost，堆叠泛化（Stacked Generalization，Blending），梯度推进机（Gradient
Boosting Machine, GBM），随机森林（Random Forest）。
10）. ⼈⼯神经⽹络：⼈⼯神经⽹络算法模拟⽣物神经⽹络，是⼀类模式匹配算法。通常⽤于解决分类和回归问题。⼈⼯神经⽹络是机器学习的⼀个庞⼤的分⽀，有⼏百种不同的算法。（其中深度学习就是其中的⼀类算法，我们会单独讨论），重要的⼈⼯神经⽹络算法包括：感知器神经⽹络（Perceptron Neural Network）, 反向传递（Back Propagation），Hopfield⽹络，⾃组织映射（Self-Organizing Map, SOM）。学习⽮量量化（Learning Vector Quantization， LVQ）。
RF：通过对训练数据样本以及属性进⾏有放回的抽样（针对某⼀个属性随机选择样本）这⾥有两种，⼀种是每次都是有放回的采样，有些样本是重复的，组成和原始数据集样本个数⼀样的数据集；另外⼀种是不放回的抽样，抽取出⼤约60%的训练信息。由此⽣成⼀颗CART 树，剩下的样本信息作为袋外数据，⽤来当作验证集计算袋外误差测试模型；把抽取出的样本信息再放回到原数据集中，再重新抽取⼀组训练信息，再以此训练数据集⽣成⼀颗CART树。这样依次⽣成多颗CART树，多颗树组成森林，并且他们的⽣成都是通过随机采样的训练数据⽣成，因此叫随机森林。RF可以⽤于数据的回归，也可以⽤于数据的分类。回归时是由多颗树的预测结果求均值；分类是由多棵树的预测结果进⾏投票。正式由于它的随机性，RF有极强的防⽌过拟合的特性。由于他是由CART组成，因此它的训练数据不需要进⾏归⼀化，因为每课的建⽴过程都是通过选择⼀个能最好的对数据样本进⾏选择的属性来建⽴分叉，因此有以上好处的同时也带来了⼀个缺点，那就是忽略了属性与属性之间的关系。
K-meas：基本K-Means算法的思想很简单，事先确定常数K，常数K意味着最终的聚类类别数，⾸先随机选定初始点为质⼼，并通过计算每⼀个样本与质⼼之间的相似度(这⾥为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质⼼(即为类中⼼)，重复这样的过程，知道质⼼不再改变，最终就确定了每个样本所属的类别以及每个类的质⼼。由于每次都要计算所有的样本与每⼀个质⼼之间的相似度，故在⼤规模的数据集上，K-Means算法的收敛速度⽐较慢。
初始化常数K，随机选取初始点为质⼼
重复计算⼀下过程，直到质⼼不再改变
计算样本与每个质⼼之间的相似度，将样本归类到最相似的类中
重新计算质⼼
输出最终的质⼼以及每个类
● KMeans讲讲，KMeans有什么缺点，K怎么确定
参考回答：
在k-means算法中，⽤质⼼来表⽰cluster；且容易证明k-means算法收敛等同于所有质⼼不再发⽣变化。基本的k-means算法流程如下：
选取k个初始质⼼（作为初始cluster）；
repeat：对每个样本点，计算得到距其最近的质⼼，将其类别标为该质⼼所对应的cluster；重新计算k个cluser对应的质⼼；
until 质⼼不再发⽣变化
k-means存在缺点：
1）k-means是局部最优的，容易受到初始质⼼的影响；⽐如在下图中，因选择初始质⼼不恰当⽽造成次优的聚类结果。
2）同时，k值的选取也会直接影响聚类结果，最优聚类的k值应与样本数据本⾝的结构信息相吻合，⽽这种结构信息是很难去掌握，因此选取最优k值是⾮常困难的。
K值得确定：
法1：(轮廓系数)在实际应⽤中，由于Kmean⼀般作为数据预处理，或者⽤于辅助分聚类贴标签。所以k⼀般不会设置很⼤。可以通过枚举，令k从2到⼀个固定值如10，在每个k值上重复运⾏数次kmeans(避免局部最优解)，并计算当前k的平均轮廓系数，最后选取轮廓系数最⼤的值对应的k作为最终的集数⽬。
法2：(Calinski-Harabasz准则)
其中SSB是类间⽅差，，m为所有点的中⼼点,mi为某类的中⼼点；
SSW是类内⽅差，；
(N-k)/(k-1)是复杂度；
⽐率越⼤，数据分离度越⼤。
● Kmeans
参考回答：
基本K-Means算法的思想很简单，事先确定常数K，常数K意味着最终的聚类类别数，⾸先随机选定初始点为质⼼，并通过计算每⼀个样本
与质⼼之间的相似度(这⾥为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质⼼(即为类中⼼)，重复这样的过程，知道质⼼不再改变，最终就确定了每个样本所属的类别以及每个类的质⼼。由于每次都要计算所有的样本与每⼀个质⼼之间的相似度，故在⼤规模的数据集上，K-Means算法的收敛速度⽐较慢。
初始化常数K，随机选取初始点为质⼼
重复计算⼀下过程，直到质⼼不再改变
计算样本与每个质⼼之间的相似度，将样本归类到最相似的类中
重新计算质⼼
输出最终的质⼼以及每个类
● DBSCAN原理和算法伪代码，与kmeans，OPTICS区别
参考回答：
DBSCAN聚类算法原理
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，它是⼀种基于⾼密度连通区域的、基于密度的聚类算法，能够将具有⾜够⾼密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇。我们总结⼀下DBSCAN聚类算法原理的基本要点：
DBSCAN算法需要选择⼀种距离度量，对于待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度，说明了点与点是否能够聚到同⼀类中。由于DBSCAN算法对⾼维数据定义密度很困难，所以对于⼆维空间中的点，可以使⽤欧⼏⾥德距离来进⾏度量。
DBSCAN算法需要⽤户输⼊2个参数：⼀个参数是半径（Eps），表⽰以给定点P为中⼼的圆形邻域的范围；另⼀个参数是以点P为中⼼的邻域内最少点的数量（MinPts）。如果满⾜：以点P为中⼼、半径为Eps的邻域内的点的个数不少于MinPts，则称点P为核⼼点。
DBSCAN聚类使⽤到⼀个k-距离的概念，k-距离是指：给定数据集P={p(i); i=0,1,…n}，对于任意点P(i)，计算点P(i)到集合D的⼦集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有点之间的距离，距离按照从⼩到⼤的顺序排序，假设排序后的距离集合为D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，则d(k)就被称为k-距离。也就是说，k-距离是点p(i)到所有点（除了p(i)点）之间距离第k近的距离。对待聚类集合中每个点p(i)都计算k-距离，最后得到所有点的k-距离集合E={e(1), e(2), …, e(n)}。
根据经验计算半径Eps：根据得到的所有点的k-距离集合E，对集合E进⾏升序排序后得到k-距离集合E’，
需要拟合⼀条排序后的E’集合中k-距离的变化曲线图，然后绘出曲线，通过观察，将急剧发⽣变化的位置所对应的k-距离的值，确定为半径Eps的值。
根据经验计算最少点的数量MinPts：确定MinPts的⼤⼩，实际上也是确定k-距离中k的值，DBSCAN算法取k=4，则MinPts=4。
另外，如果觉得经验值聚类的结果不满意，可以适当调整Eps和MinPts的值，经过多次迭代计算对⽐，选择最合适的参数值。可以看出，如果MinPts不变，Eps取得值过⼤，会导致⼤多数点都聚到同⼀个簇中，Eps过⼩，会导致已⼀个簇的分裂；如果Eps不变，MinPts的值取得过⼤，会导致同⼀个簇中点被标记为噪声点，MinPts过⼩，会导致发现⼤量的核⼼点。
我们需要知道的是，DBSCAN算法，需要输⼊2个参数，这两个参数的计算都来⾃经验知识。半径Eps的计算依赖于计算k-距离，DBSCAN 取k=4，也就是设置MinPts=4，然后需要根据k-距离曲线，根据经验观察到合适的半径Eps的值，下⾯的算法实现过程中，我们会详细说明。对于算法的实现，⾸先我们概要地描述⼀下实现的过程：
1）解析样本数据⽂件。2）计算每个点与其他所有点之间的欧⼏⾥德距离。3）计算每个点的k-距离值，并对所有点的k-距离集合进⾏升序排序，输出的排序后的k-距离值。4）将所有点的k-距离值，在Excel中⽤散点图显⽰k-距离变化趋势。5）根据散点图确定半径Eps的值。）根据给定MinPts=4，以
及半径Eps的值，计算所有核⼼点，并建⽴核⼼点与到核⼼点距离⼩于半径Eps的点的映射。7）根据得到的核⼼点集合，以及半径Eps的值，计算能够连通的核⼼点，得到噪声点。8）将能够连通的每⼀组核⼼点，以及到核⼼点距离⼩于半径Eps的点，都放到⼀起，形成⼀个簇。9）选择不同的半径Eps，使⽤DBSCAN算法聚类得到的⼀组簇及其噪声点，使⽤散点图对⽐聚类效果。
算法伪代码：
算法描述：
算法：DBSCAN
输⼊：E——半径
MinPts——给定点在E邻域内成为核⼼对象的最⼩邻域点数。
D——集合。
输出：⽬标类簇集合
⽅法：Repeat
1）判断输⼊点是否为核⼼对象
2）出核⼼对象的E邻域中的所有直接密度可达点。
Until 所有输⼊点都判断完毕
Repeat
针对所有核⼼对象的E邻域内所有直接密度可达点到最⼤密度相连对象集合，中间涉及到⼀些密度可达对象的合并。Until 所有核⼼对象的E领域都遍历完毕
DBSCAN和Kmeans的区别：
1)K均值和DBSCAN都是将每个对象指派到单个簇的划分聚类算法，但是K均值⼀般聚类所有对象，⽽DBSCAN丢弃被它识别为噪声的对象。
2)K均值使⽤簇的基于原型的概念，⽽DBSCAN使⽤基于密度的概念。
3)K均值很难处理⾮球形的簇和不同⼤⼩的簇。DBSCAN可以处理不同⼤⼩或形状的簇，并且不太受噪声和离点的影响。当簇具有很不相同的密度时，两种算法的性能都很差。
4)K均值只能⽤于具有明确定义的质⼼（⽐如均值或中位数）的数据。DBSCAN要求密度定义（基于传统的欧⼏⾥得密度概念）对于数据是有意义的。
5)K均值可以⽤于稀疏的⾼维数据，如⽂档数据。DBSCAN通常在这类数据上的性能很差，因为对于⾼维数据，传统的欧⼏⾥得密度定义不能很好处理它们。
6)K均值和DBSCAN的最初版本都是针对欧⼏⾥得数据设计的，但是它们都被扩展，以便处理其他类型的数据。
7)基本K均值算法等价于⼀种统计聚类⽅法（混合模型），假定所有的簇都来⾃球形⾼斯分布，具有不同的均值，但具有相同的协⽅差矩阵。DBSCAN不对数据的分布做任何假定。
8)K均值DBSCAN和都寻使⽤所有属性的簇，即它们都不寻可能只涉及某个属性⼦集的簇。
9)K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。
10)K均值算法的时间复杂度是O(m)，⽽DBSCAN的时间复杂度是O(m^2)，除⾮⽤于诸如低维欧⼏⾥得数据这样的特殊情况。
11)DBSCAN多次运⾏产⽣相同的结果，⽽K均值通常使⽤随机初始化质⼼，不会产⽣相同的结果。
12)DBSCAN⾃动地确定簇个数，对于K均值，簇个数需要作为参数指定。然⽽，DBSCAN必须指定另外两个参数：Eps（邻域半径）和MinPts（最少点数）。
13)K均值聚类可以看作优化问题，即最⼩化每个点到最近质⼼的误差平⽅和，并且可以看作⼀种统计聚类（混合模型）的特例。DBSCAN 不基于任何形式化模型。
DBSCAN与OPTICS的区别：
bootstrappedDBSCAN算法，有两个初始参数E（邻域半径）和minPts(E邻域最⼩点数)需要⽤户⼿动设置输⼊，并且聚类的类簇结果对这两个参数的取值⾮常敏感，不同的取值将产⽣不同的聚类结果，其实这也是⼤多数其他需要初始化参数聚类算法的弊端。
为了克服DBSCAN算法这⼀缺点，提出了OPTICS算法（Ordering Points to identify the clustering structure）。OPTICS并不显⽰的产⽣结果类簇，⽽是为聚类分析⽣成⼀个增⼴的簇排序（⽐如，以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从⼀个⼴泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数E和minPts的DBSCAN算法的聚类结果。
OPTICS两个概念：
核⼼距离：对象p的核⼼距离是指是p成为核⼼对象的最⼩E’。如果p不是核⼼对象，那么p的核⼼距离没有任何意义。
可达距离：对象q到对象p的可达距离是指p的核⼼距离和p与q之间欧⼏⾥得距离之间的较⼤值。如果p不是核⼼对象，p和q之间的可达距离没有意义。
算法描述：OPTICS算法额外存储了每个对象的核⼼距离和可达距离。基于OPTICS产⽣的排序信息来提取类簇。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。