算法岗面试常见问题大集合

发表于 | 更新于: | 阅读量 次 | 分类于 | | 热度: ℃ |
字数统计: 7.2k | 阅读时长 ≈ 28

1.参考博客

2.模型过拟合的解决方法

  • L1/L2正则化（原理奥卡姆剃刀）:L2正则化也叫作权重衰减，目标函数中增加所有权重w参数的平方之和，迫使所有w可能趋向0但不为0；L1正则化在损失函数中加入所有权重参数w的绝对值之和，迫使更多的w为0，使特征变得稀疏。
  • Batch Normalization（对神经网络中下一层的输入进行归一化处理，使得输入量的均值为0，方差为1，即通过特征归一化，加速模型的训练）
  • shortcut-connect(使用残差网络Residual network)
  • 数据增强(增加样本的数量)
  • early stopping
  • Dropout：在训练过程中，让神经元以超参数p的概率被激活(也就是说1-p的概率被设置为0)，类似于bagging算法

3.如何解决样本类别的不均衡问题？

  • a.过采样/上采样：增加类别少的样本数量实现样本数量的均衡。具体是通过复制类别上的样本构成多条数据。此方法的缺点是当样本的特征很少时，容易出现过拟合。需要对过采样方法进行改进，改进的方法是：在类别少的样本中加入噪声、干扰数据或通过一定的规则产生新合成的样本，如smote算法。
  • b.欠采样/下采样：减少类别多的样本数量，一般的方法是随机地去掉一些类别多的样本。
  • c.调整正负样本的惩罚权重：对类别少的样本赋予高的权重，对类别多的样本赋予低的权重。
  • d.通过集成学习的方法：每次生成训练集时，使用所有类别少的样本，同时从类别多的样本中随机抽取数据与类别少的样本合并起来，构成一个新的训练集。
  • e.使用特征选择：一般样本不均衡也会导致特征不均衡。但如果类别少的样本量具有一定的规模时，则意味着其特征的分布较为均匀，可以选择出具有显著特征配合参与解决样本不均衡的问题。

4.在神经网络训练过程中，为什么会出现梯度消失的问题？如何防止？

  • 原因：使用了不合适的激活函数，例如sigmoid函数。此时，当神经网络的层数很深时，利用链式求导法则计算梯度时，损失函数的梯度连乘，导致乘积会变得越来越小接近于0，从而神经网络无法学习到新的信息。
  • 解决方法：
    • 预训练加微调
    • 梯度剪切
    • 权重正则化
    • 使用不同的激活函数
    • 使用Batch Normalization
    • 使用残差网络ResNet
    • 使用LSTM网络

5.介绍一下TensorFlow中的计算图

  • TensorFlow是一个通过计算图的形式来表述计算的编程系统，计算图也叫作数据流图。可以把计算图看做是一种有向图，TensorFlow中的每个节点都是计算图上的一个张量Tensor，而节点之间的边描述了计算之间的依赖关系和数学运算。

6.K-Means或KNN中，通常使用欧式距离来表示最近的数据点之间的距离，有时候也使用曼哈度距离，对比两者的区别。

  • 欧式距离最常见的是两个或多个点之间的距离表示法，又称为欧几里得距离。也就是通常所说的L2范数，公式如下。欧式距离的缺点是它将样本的不同属性之间的差别等同看待，这一点有时候不能满足实际要求。
  • 曼哈顿距离，也就是欧式空间中的在直角坐标系上两个点所形成的线段对轴产生的投影的距离总和。也就是我们所说的L1距离。例如，坐标(x1,y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离计算公式为：

7.参数模型与非参数模型

  • 参数模型：根据预先设计的规则，例如方差损失最小，进行学习，参数模型例子：回归（线性回归、逻辑回归）模型；最好可以看一下或者直接进行一下相关的推导；根据规则，拥有少部分数据就可以；
  • 非参数模型：不需要事先假设规则，直接挖掘潜在数据中的规则；非参数模型例子：KNN，决策树，挖掘数据潜在的特征，所以比较灵活；

8.生成模型与判别模型

  • 生成模型：根据数据学习联合概率分布P(x,y)，从而计算出条件概率分布P(y|x)作为预测的模型。常用于含有隐变量的模型，例如HMM，朴素贝叶斯算法、高斯混合模型GMM、文档主题生成模型LDA、限制玻尔兹曼机等
  • 判别模型：根据数据直接学习条件概率分布P(x|y)或者决策函数Y=f(X)作为预测模型。例如：逻辑回归、RF、SVM、神经网络、感知机、KNN、CRF等
  • 两者的对比：
    • 使用生成式方法得到的模型，可以还原出模型的联合概率分布，而判别模型不可以；
    • 生成式方法得到的模型收敛速度更快。当样本数增加时，生成式方法得到的模型能更快的收敛到真实模型；
    • 存在隐变量时，只能使用生成模型；
    • 使用判别式方法学习得到的模型，直接面对预测，学习的准确率通常更高，可以简化学习问题。

9.LR和SVM的联系和区别？

  • 联系：
    • LR和SVM都可以处理分类问题，且一般都用于处理线性二分类问题
    • 两个方法都可以增加不同的正则化项，如L1、L2正则化项
  • 区别：
    • LR是参数模型，SVM是非参数模型
    • 从损失函数来看，LR使用的是交叉熵损失函数，SVM使用的hinge损失函数，这两个损失函数的目的都是增加对分类影响较大的样本点的权重，减小与分类关系比较小的数据点的权重。
    • SVM的处理方法只考虑支持向量，也就是只考虑和分类最相关的少数样本点来学习分类器。而逻辑回归通过非线性映射，大大减小了离分离超平面远的样本点权重，相对提升了与分类最相关的样本点的权重。
    • LR模型相对来说简单好理解，一般用于大规模的线性分类。SVM的理解和优化比较复杂，在处理复制非线性分类时，使用核技巧来计算优势明显。
    • LR能做的SVM也能做，但可能准确率是上有问题，但SVM能做的LR做不了。

10.神经网络中参数量parameters和FLOPs计算

  • CNN中的parameters分为两种：W和b，对于某一个卷积层，它的parameters的个数为:其中，$K{h}$是卷积核的高度，$K{w}$是卷积核的宽度,$C{in}$是输入的通道数，$C{out}$是输出的通道数
  • 对于某个全连接层，如果输入的数据有$N{in}$个节点，输出的数据有$N{out}$个节点，它的参数个数为：
  • FLOPs：全称是floating point operations per second，指的是每秒浮点运算次数，即用来衡量硬件的计算性能
  • 对于某个卷积层,它的FLOPs数量是：其中，$num_{params}$表示该层参数的数量，H是输出图片的高，W是输出图片的宽
  • 例题1：假设你的输入是一个300×300的彩色（RGB）图像，而你没有使用卷积神经网络。 如果第一个隐藏层有100个神经元，每个神经元与输入层进行全连接，那么这个隐藏层有多少个参数（包括偏置参数）？
  • A1：因为输入的节点数量是300*300*3,输出的节点数量是100。然后加上偏置项b，因为隐藏层有100个节点，每个节点都有一个偏置，所以b=100。利用上面计算全连接网络的公式，故3*300*300*100+100
  • 例题2：假设你的输入是300×300彩色（RGB）图像，并且你使用卷积层和100个过滤器，每个过滤器都是5×5的大小，请问这个隐藏层有多少个参数（包括偏置参数）？
  • A2：首先，参数和输入的图片大小是没有关系的，无论你给的图像像素有多大，参数值都是不变的，在这个题中，参数值只与过滤器有关。单个过滤器的大小是5*5,由于输入的是RGB图像，所以输入通道数目是3。因此一个过滤器的组成是5*5*3,每一过滤器只有一个偏置项b,因此一个过滤器所拥有的参数是5*5*3+1=76，一共用了100个过滤器，所以隐藏层含有76*100=7600个参数。其实，也就是上面的公式计算CNN的参数量。

11.SVM中常见的几种核函数

  • 线性核函数：内积公式
  • 多项式核函数
  • 高斯核函数
  • 字符串核函数：详见李航统计学习方法

12.逻辑回归与线性回归的联系与区别

  • 联系：逻辑回归和线性回归首先都是广义的线性回归；逻辑回归的模型本质上是一个对数线性回归模型，逻辑回归都是以线性回归为理论支持的。但线性回归模型无法做到sigmoid的非线性形式，sigmoid可以轻松处理0/1分类问题。
  • 区别：
    • 线性模型的优化目标函数是最小二乘，而逻辑回归则是似然函数
    • 线性回归在整个实数域范围内进行预测，敏感度一致；而分类范围，需要在[0,1]。逻辑回归就是一种减小预测范围，将预测值限定为[0,1]间的一种回归模型，因而对于这类问题来说，逻辑回归的鲁棒性比线性回归的要好。

13.XGBoost为什么要用泰勒公式展开，优势在哪?

  • XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准。使用泰勒展开取得二阶倒数形式, 可以在不选定损失函数具体形式的情况下用于算法优化分析.本质上也就把损失函数的选取和模型算法优化和参数选择分开了，这种去耦合增加了XGBoost的适用性。

14.XGBoost如何寻找最优特征？是有放回还是无放回？

  • XGBoost在训练过程中给各个特征的增益评分，最大增益的特征会被选出来作为分裂的依据，从而记忆了每个特征对在模型训练时的重要性。XGBoost属于boosting的集成学习方法，样本是无放回的，因此每轮计算样本不重复。XGBoost支持子采样，即每轮计算不使用全部样本，以减少过拟合。

15.决策树、随机森林RF、Boosting、Adaboost、GBDT、XGBoost的区别？

  • bagging与boosting的区别：
    • bagging方法有放回的采样相同数量样本训练学习器，然后再一起投票。学习器之间不存在强的依赖关系，学习器可以并行训练生成。集成方式一般为投票法。随机森林属于Bagging的代表，放回抽样，每个学习器随机选择部分特征去优化。
    • Boosting方法使用全部样本，依次训练每个学习器，迭代集成。学习器之间不存在强依赖关系，学习器可并行训练生成，集成方式为加权和；Adaboost属于Boosting，采用指数损失函数代替原本分类任务中的0-1损失函数；GBDT属于Boosting的优秀代表，对函数残差近似值进行梯度下降，用CRAT树作为基本的学习器，集成模型为回归模型。XGBoost属于Boosting的集大成者，对函数残差近似值进行梯度下降，迭代时利用二阶梯度信息，集成模型可用于分类也可以用于回归。
  • 决策树的学习过程：从根开始建立树，也就是如何选择特征进行分裂。ID3算法使用信息增益、C4.5使用信息增益比、CART树采用基尼系数计算最优分类点，XGBoost使用二阶泰勒展开系数计算最优分裂点。

16.GBDT与XGBoost的对比，XGBoost的优点

  • 损失函数用泰勒展开二项逼近，而不是像GBDT中用的就是一阶导数
  • 对树的结构进行了正则化约束，防止模型过于复杂，降低了过拟合的可能性
  • 节点的分裂方式不同，GBDT使用的是基尼系数，XGBoost使用的是经过优化推导后的算法(穷举法选择最佳的分裂节点、通过加权分位数方法近似选择最佳的分裂节点、针对稀疏特征的分裂点选择法)

17.L1和L2范数的区别

  • L1 norm:向量中各个元素绝对值之和，也称为稀疏规则算子，L1范数可以使权重稀疏，方便特征提取；L1正则化先验服从拉普拉斯分布
  • L2 norm:向量中各个元素平方和的1/2次方，又称为Frobenius范数，L2范数可以防止过拟合，提升模型的泛化能力；L2正则化先验服从高斯分布

18.阐述Adaboost算法的流程，并写出权重更新的公式

19.LSTM的结构推导，为什么比普通的RNN好？

20.为什么朴素贝叶斯算法如此朴素？

  • 因为它假设所有的特征在数据集中的作用都是同样重要的，而且相互独立的。这个假设在现实中基本上是不存在的，但特征相关性很小的实际情况还很多，岁月这个模型还可以工作的很好。

21.EM算法原理说明

  • 有时候样本的产生和隐含变量有关(隐变量是不能观察的)，而求模型的参数时一般都采用极大似然估计，由于含有隐变量，所以对似然函数的参数求导数是求不出来的，这时候用EM算法来求模型的参数，典型的用法是用在GMM和HMM中。步骤如下：
    • E步：选择一组参数，求出在此参数下隐变量的条件概率值
    • M步：结合E步求出的隐变量的条件概率值，求出似然函数的下界函数(即某个期望函数)最大值。
    • 重复进行上面的两步，直至收敛为止。
  • M步中下界函数的推导过程：

22.GMM算法原理说明

  • EM算法的常用例子是高斯混合模型GMM，每个样本都有可能由K个高斯模型产生，只不过每个高斯模型的产生概率不同，因此每个样本都有对应的高斯分布(K个模型中的一个)，此时的隐变量就是每个样本对应的某个高斯分布。
    • GMM算法的E步(计算每个样本对应每个高斯模型的概率)具体的计算公式为：
    • M步计算公式(计算每个高斯模型的权重，均值，方差3个参数)：

23.KNN算法中K是如何选择的?

  • 如果选择较小的K值，就相当于用较小的邻域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大。换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
  • 如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
  • K=N，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的累，模型过于简单，忽略了训练实例中大量有用信息。
  • 实际中，使用交叉验证的方法选择最优的K的取值。

24.机器学习中，为什么经常需要对数据进行归一化？

  • 归一化能提高梯度下降算法求解的速度
  • 归一化有可能提高精度

25.神经网络中的批量归一化Batch Normalization(BN)原理

26.哪些机器学习算法不需要进行归一化操作？

  • 概率模型不需要做归一化操作，因为它们不关心变量的值，而关心的是变量分布和变量之间的条件概率，如决策树。但是，像Adaboost、SVM、LR、KNN、Kmeans等最优化问题就需要归一化。

27.为什么树形结构不需要归一化？

  • 数值缩放，不影响分裂点位置。因为第一步都是按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会变。对于线性模型，比如说LR，假设有两个特征，一个是(0,1)的，一个是(0,10000)的，这样运用梯度下降时候，损失等高线是一个椭圆的形状，这样想迭代到最优点，就需要很多次迭代，但是如果进行了归一化，那么等高线就是圆形的，那么SGD就会往原点迭代，需要的迭代次数较少。另外，注意树模型是不能进行梯度下降的，因为树模型是阶跃的，阶跃点是不可导的，并且求导没意义，所以树模型（回归树）寻找最优点是通过寻找最优分裂点完成的。

28.一个完整机器学习项目的流程

  • 抽象成数学问题、获取数据、特征预处理与特征选择、训练模型与调优、模型诊断、模型融合、上线运行

29.条件随机场CRF模型相对于HMM模型(隐马尔科夫模型)和MEMM模型(最大熵隐马尔科夫模型)的优势。

  • HMM模型中一个最大的缺点即其输出独立性假设，由于输出独立性假设的缺点导致HMM模型不能考虑上下文的特征，限制了特征的选择。
  • MEMM模型则解决了HMM模型的最大的缺点，可以任意选择特征，但是由于其每一个节点都要进行归一化，所以只能找到局部最优值。同时，也带来了标记偏见的问题即凡是在训练语料库中未出现的情况都被忽略掉了。CRF模型很好的解决了这个问题，它并不在每一节点进行归一化，而是所有特征进行全局归一化，因此可以求出全局的最优值。

30.什么是熵？

  • 熵的定义：离散随机事件的出现概率。一个系统越是有序，信息熵就越低。信息熵可以被认为是系统有序化程度的一个度量。

31.BP反向传播算法推导及python实现

图1.jpg
图2.jpg
图3.jpg

  • python代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    import numpy as np
    import matplotlib.pyplot as plt

    class MLP():
        def __init__(self, name='nn', layer_structure=[], task_model=None, batch_size=1, load_model=None):
            """layer_number : 神经网络的层数
               layer_structure = [输入的特征个数，第1层神经元个数，第2层神经元个数，...，最后一层神经元个数输出层特征个数]，
               如网络层数设为layer_number=3, layer_structure=[20,10,5,1]：输入特征是20个，第一层有10个神经元，第二层5个，第三层1个.
               output_model = 'regression'/'logistic'
            """
            self.name = name
            self.layer_number = len(layer_structure) - 1
            self.layer_structure = layer_structure
            self.task_model = task_model
            self.W = []
            self.B = []
            self.batch_size = batch_size
            self.total_loss = []
            if self.task_model == 'logistic' or self.task_model == 'multi':
                self.total_accuracy = []

            if load_model == None:
                print("Initializing the network from scratch ...")
                for index in range(self.layer_number):
                    self.W.append(np.random.randn(self.layer_structure[index], self.layer_structure[index+1]))
                    self.B.append(np.random.randn(1, self.layer_structure[index+1]))
            else:
                print("Initializing the network from trained model ...")
                for index in range(self.layer_number):
                    self.W.append(np.loadtxt(load_model + self.name + "_layer_" + str(index) + "_W.txt").reshape(self.layer_structure[index], self.layer_structure[index+1]))
                    self.B.append(np.loadtxt(load_model + self.name + "_layer_" + str(index) + "_B.txt").reshape(1, self.layer_structure[index+1]))

        def normal_parameters(self, means, sigmas):
            self.means = means
            self.sigams = sigmas

        def sigmoid(self, x):
            return 1/(1+np.exp(-x))

        def sigmoid_gradient(self, x):
            return self.sigmoid(x)*(1-self.sigmoid(x))

        def softmax(self, x):
            return np.exp(x)/np.sum(np.exp(x), axis = 1, keepdims = True)

        def forward(self, x):
            """
                intput : x = [batch_size, features]
            """
            self.before_activation = []
            self.activations = [x]
            for index in range(self.layer_number):
                if index < self.layer_number - 1:
                    Z = np.dot(self.activations[index], self.W[index]) + self.B[index]
                    self.before_activation.append(Z)
                    self.activations.append(self.sigmoid(Z))
                else:
                    if self.task_model == 'logistic':
                        Z = np.dot(self.activations[index], self.W[index]) + self.B[index]
                        self.before_activation.append(Z)
                        self.activations.append(self.sigmoid(Z))
                    elif self.task_model == 'regression':
                        Z = np.dot(self.activations[index], self.W[index]) + self.B[index]
                        self.before_activation.append(Z)
                        self.activations.append(Z)
                    elif self.task_model == 'multi':
                        Z = np.dot(self.activations[index], self.W[index]) + self.B[index]
                        self.before_activation.append(Z)
                        self.activations.append(self.softmax(Z))

            return self.activations[-1]

        def __call__(self, x):
            return self.forward(x)

        def lossfunction(self, inputs, target):
            if self.task_model == 'regression':
                return(np.mean(np.sum((inputs - target)**2, 1)))
            elif self.task_model == 'logistic':
                return np.mean(np.sum(-target*np.log(inputs+1e-14) - (1-target)*np.log(1-inputs+1e-14), 1))
            elif self.task_model == 'multi':
                return np.mean(np.sum(-target*np.log(inputs+1e-14), 1))

        def back_forward(self, targets=None, loss=None, regularization=False):
            self.dWs = []
            self.dBs = []
            self.dAs = []
            W_reverse = self.W[::-1]
            activations_reverse = self.activations[::-1]
            before_activation_reverse = self.before_activation[::-1]
            # 从最后一层开始往回传播
            for k in range(self.layer_number):
                if(k == 0):
                    if loss == 'MSE' or loss == 'CE' or loss == 'BE':
                        dZ = activations_reverse[k] - targets
                        dW = 1/self.batch_size*np.dot(activations_reverse[k+1].T, dZ)
                        dB = 1/self.batch_size*np.sum(dZ, axis = 0, keepdims = True)
                        dA_before = np.dot(dZ, W_reverse[k].T)
                        self.dWs.append(dW)
                        self.dBs.append(dB)
                        self.dAs.append(dA_before)
                else:
                    dZ = self.dAs[k-1]*self.sigmoid_gradient(before_activation_reverse[k])
                    dW = 1/self.batch_size*np.dot(activations_reverse[k+1].T,dZ)
                    dB = 1/self.batch_size*np.sum(dZ, axis = 0, keepdims = True)
                    dA_before = np.dot(dZ, W_reverse[k].T)
                    self.dWs.append(dW)
                    self.dBs.append(dB)
                    self.dAs.append(dA_before)
            self.dWs = self.dWs[::-1]
            self.dBs = self.dBs[::-1]

        def steps(self, lr=0.001, lr_decay=False):
            for index in range(len(self.dWs)):
                self.W[index] -= lr*self.dWs[index]
                self.B[index] -= lr*self.dBs[index]

        def train(self, train_datas=None, train_targets=None, train_epoch=1, lr=0.001, lr_decay=False, loss='MSE', regularization=False, display=False):
            train_counts = 0
            for epoch in range(train_epoch):
                if epoch == int(train_epoch * 0.7) and lr_decay == True:
                    lr *= 0.1
                train_steps = train_datas.shape[0] // self.batch_size
                for i in range(train_steps):
                    input_data = train_datas[self.batch_size*i : self.batch_size*(i+1), :].reshape(self.batch_size, train_datas.shape[1])
                    targets = train_targets[self.batch_size*i : self.batch_size*(i+1), :].reshape(self.batch_size, train_targets.shape[1])
                    prediction = self.forward(input_data)
                    forward_loss = self.lossfunction(prediction, targets)
                    if self.task_model=='logistic':
                        accuracy = np.sum((prediction>0.6) == targets) / targets.shape[0]
                        self.total_accuracy.append(accuracy)
                    elif self.task_model=='multi':
                        accuracy = np.sum(np.argmax(prediction,1) == np.argmax(targets,1)) / targets.shape[0]
                        self.total_accuracy.append(accuracy)
                    self.total_loss.append(forward_loss)
                    if display:
                        if train_counts % 10 == 0:
                            if self.task_model == 'logistic' or self.task_model == 'multi':
                                print("After " + str(train_counts) + ", loss is ", forward_loss,
                                ", accuracy is ", accuracy)
                            else:
                                print("After " + str(train_counts) + ", loss is ", forward_loss)
                    self.back_forward(targets=targets, loss=loss, regularization=regularization)
                    self.steps(lr=lr, lr_decay=lr_decay)
                    train_counts += 1

        def save_model(self, path):
            print("Saving the " + self.name + " model ...")
            for i in range(self.layer_number):
                np.savetxt(path  + self.name + "_layer_" + str(i) + "_W.txt", self.W[i])
                np.savetxt(path  + self.name + "_layer_" + str(i) + "_B.txt", self.B[i])
            print("Model saved !!!")

32.K_Means算法的原理

  • 聚类算法综述：聚类算法是一种无监督学习算法，它是将相似的对象归到同一个簇中。K均值算法中的K可以理解用户想要聚类成K个不同的簇，K是一个用户可以自行定义的超参数。
  • K均值聚类的优缺点：
    • 优点：容易实现
    • 缺点：可能收敛到局部最小值，在大规模的数据上收敛慢
    • 适用场合：数值型数据
  • K_Means算法的基本流程：
    • 1.随机选择K个点作为起始的聚类中心
    • 2.遍历每个样本，计算每个样本到K个聚类中心的距离，找出”距离”聚类中心最近的样本，并将此样本聚集到离它最近的那一个簇中。注：K_Means算法的性能会受到所选距离计算方法的影响。
    • 3.所有样本都聚集到K个簇完成后，计算K个簇的均值，并将聚类中心移动到K个簇的均值处作为新的聚类中心。
    • 4.重复上述步骤2~3，直到最大迭代次数就停止。
  • K_Means算法的优化(为了克服收敛于局部最小值提出)：如何知道生成的簇比较好？一种用来衡量K_Means算法聚类效果的指标是SSE误差平方和(预测数据与原始数据之间误差的平方和),SSE越小表示样本点越接近于聚类中心点，聚类效果越好。因为对误差取了平方，因此更加重视那些远离聚类中心的点(未理解)。降低SSE值的方法是增加簇的个数，但是簇的个数K在算法一开始运行时就固定了，不能改变。聚类的目标是在保持原有簇数目不变的条件下，提高簇的质量。常用思想是：对生成的簇进行后处理，将具有最大SSE值的簇划分成两个簇。为了保持簇的总数不变，可以将某两个簇进行合并。可以有下面两种方法合并：
    • 1.合并最近的聚类中心：计算所有聚类中心之间的距离，合并距离最近的两个聚类中心点。
    • 2.合并两个使得SSE增加最小的聚类中心：合并两个簇，然后计算总的SSE。必须在所有可能的两个簇上重复上述处理过程，直到找到合并最佳的两个簇。

33.常见的距离函数总结

  • 闵可夫斯基距离：给定样本$\overrightarrow{\mathbf{x}}{i}=\left(x{i, 1}, x{i, 2}, \cdots, x{i, n}\right)^{T}$,$\overrightarrow{\mathbf{x}}{j}=\left(x{j, 1}, x{j, 2}, \cdots, x{j, n}\right)^{T}$，则闵可夫斯基距离定义为：
  • 当p=2时，闵可夫斯基距离就是欧式距离：
  • 当p=1时，闵可夫斯基距离就是曼哈顿距离：

本文标题:算法岗面试常见问题大集合

文章作者:Curry_Coder

发布时间:2019年07月30日 - 22:51:47

最后更新:2019年08月01日 - 15:08:31

原始链接:https://cdlwhm1217096231.github.io/机器学习/算法岗面试常见问题大集合/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------本文结束感谢您的阅读-------------
觉得对您有所帮助，请我喝杯可乐吧!
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多