线性回归算法

线性回归是一种预测连续数值的监督学习算法。全局梯度下降是线性回归中用来找到损失函数最小值的一种优化算法。

image-20240909004636099

线性回归模型

线性回归模型的目标是找到一个函数，它能够尽可能准确地预测输出值 $y $。对于一个简单的线性模型，我们可以表示为：

$$
h(x) = \theta_0 + \theta_1 x
$$

其中，$h(x)$ 是模型的预测值，$\theta_0$ 是截距项，$\theta_1$ 是斜率，$x$ 是输入特征。

损失函数

为了衡量模型预测值 $h(x)$ 与真实值 $y$ 之间的差距，我们定义损失函数（或代价函数）：

$$
J(\theta_0, \theta_1) = \frac{1}{2m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)})^2
$$

这里，$m$ 是训练样本的数量，$x^{(i)}$ 和 $ y^{(i)}$ 分别是第 $i$ 个训练样本的特征和标签。

梯度下降

梯度下降算法的目标是找到损失函数 $J$ 的最小值。为此，我们需要计算 $J$ 关于每个参数的梯度，然后更新参数：

$$
\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta_0, \theta_1)
$$

其中，$ \alpha$ 是学习率，$\theta_j $ 是参数（$\theta_0$或 $ \theta_1$），$\frac{\partial}{\partial \theta_j} J$ 是损失函数关于参数 $\theta_j $ 的偏导数。

梯度计算

对于线性回归的参数 $\theta_0$ 和 $\theta_1$，梯度可以分别计算为：

$$
\frac{\partial}{\partial \theta_0} J(\theta_0, \theta_1) = \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)})
$$
$$
\frac{\partial}{\partial \theta_1} J(\theta_0, \theta_1) = \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)}) x^{(i)}
$$

参数更新

利用上述梯度，我们可以更新参数：

$$
\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)})
$$

$$
\theta_1 := \theta_1 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)}) x^{(i)}
$$

算法步骤

  1. 初始化参数：选择一个合适的学习率 $\alpha$，随机初始化 $\theta_0$ 和 $\theta_1$。
  2. 迭代更新：重复以下步骤直到收敛：
    • 计算当前参数下的预测值 $h(x)$。
    • 计算损失函数 $J$。
    • 计算 $J$ 关于每个参数的梯度。
    • 使用梯度下降公式更新参数 $\theta_0 $ 和 $\theta_1 $。
  3. 收敛判断：当参数更新的变化非常小或达到预设的迭代次数时，停止迭代。

结论

全局梯度下降是一种简单而强大的优化算法，它通过迭代地最小化损失函数来找到线性回归模型的最佳参数。通过适当选择学习率和初始化参数，全局梯度下降能够高效地收敛到全局最小值。

逻辑回归算法

逻辑回归是一种用于二分类问题的监督学习算法，它预测的是给定输入特征下，某个类别的概率。

image-20240909014112732

逻辑回归模型

image-20240909014011429

逻辑回归模型使用逻辑函数（或称Sigmoid函数）将线性回归的输出映射到0和1之间，公式如下：

$$
h(x) = \sigma(\theta^T x) = \frac{1}{1 + e^{-\theta^T x}}
$$

其中，$\theta^T x$ 是输入特征 $x$ 与参数 $\theta$ 的点积，$\sigma$​ 是Sigmoid函数。

损失函数

假定样本与样本之间相互独立，那么整个样本集(样本总数为$m$)生成的概率即似然函数为:
$$
L(\theta)=\prod_{i=1}^{m}p(y^{(i)}|x^{(i)};\theta )=\prod_{i=1}^{m}{h_\theta (x^{(i)})^{y^{(i)}}(1-h_\theta (x^{(i)})^{(1-{y^{(i)})}}}
$$
逻辑回归的损失函数是交叉熵损失函数，它衡量了模型预测值与真实值之间的差距：
$$
J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} [y^{(i)} \log h(x^{(i)}) + (1 - y^{(i)}) \log (1 - h(x^{(i)}))]
$$

这里，$m$ 是训练样本的数量，$y^{(i)}$ 是第 $i$ 个训练样本的真实标签，$h(x^{(i)})$ 是模型对第 $i$ 个训练样本的预测值。

梯度下降

为了找到损失函数 $J$ 的最小值，我们使用梯度下降算法来更新参数 $\theta$：

$$
\theta := \theta - \alpha \frac{\partial}{\partial \theta} J(\theta)
$$

其中，$\alpha$ 是学习率。

梯度计算

损失函数 $J$ 关于参数 $\theta$ 的梯度可以计算为：

$$
\frac{\partial}{\partial \theta_j} J(\theta) = \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)}) x_j^{(i)}
$$

参数更新

利用上述梯度，我们可以更新参数：

$$
\theta_j := \theta_j - \alpha \frac{1}{m} \sum_{i=1}^{m} (h(x^{(i)}) - y^{(i)}) x_j^{(i)}
$$

算法步骤

  1. 初始化参数：选择一个合适的学习率 $\alpha$，随机初始化参数 $\theta$。
  2. 迭代更新：重复以下步骤直到收敛：
    • 计算当前参数下的预测值 $h(x)$。
    • 计算损失函数 $J $。
    • 计算 $J$ 关于每个参数的梯度。
    • 使用梯度下降公式更新参数 $\theta$。
  3. 收敛判断：当参数更新的变化非常小或达到预设的迭代次数时，停止迭代。

结论

逻辑回归是一种广泛使用的分类算法，它通过最小化交叉熵损失函数来找到最佳参数。逻辑回归不仅能够给出分类结果，还能给出属于某一类的概率，这在许多应用中非常有用。

KNN 算法 (K-Nearest Neighbors)

K-Nearest Neighbors（KNN）是一种基本的分类与回归方法，通常用于分类任务。KNN算法的核心思想是在特征空间中找到离目标点最近的K个点，根据这些点的标签通过投票或平均来预测目标点的标签。

image-20240909015411448

KNN算法原理

KNN算法不需要训练阶段，它直接根据测试样本的特征和训练样本的标签来进行预测。

算法步骤

  1. 确定K值：选择一个正整数K，K是参与投票的最近邻居的数量。
  2. 距离计算：计算测试样本与每个训练样本之间的距离。常用的距离计算方法包括欧氏距离、曼哈顿距离等。
  3. 寻找最近邻居：找出距离最近的K个训练样本，即最近邻居。
  4. 决策规则：
    • 分类任务：在K个最近邻居中，根据多数投票原则来预测测试样本的类别。
    • 回归任务：计算K个最近邻居的标签值的平均值，作为测试样本的预测值。

距离度量

对于两个样本点 $x$ 和 $y$，欧氏距离的计算公式为：

$$
d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}
$$

其中，$n$ 是特征的数量，$x_i$ 和 $y_i$ 分别是样本点 $x$ 和 $y$ 在第 $i$ 个特征上的值。

选择K值

K值的选择对KNN算法的性能有很大影响。K值较小，模型可能会对噪声数据过于敏感；K值较大，模型可能会过于平滑，无法捕捉数据的细节。通常通过交叉验证来选择最佳的K值。

算法实现

以下是KNN算法的伪代码：

1
2
3
4
5
6
7
8
9
10
11
函数 KNN(train_data, train_labels, test_data, k):
	distances = []
	for train_data 中的每个训练数据点：
	    distance = 计算 test_data 与训练数据点的距离
	    将 (distance, 训练数据点的标签) 添加到 distances 列表中
	将 distances 按照距离进行排序
	neighbors = distances[0:k]
	votes = []
	for neighbors 中的每个邻居：
	    将邻居的标签添加到 votes 列表中
	return votes 中最常见的标签

算法优缺点

优点：

  • 简单有效，易于理解和实现。
  • 对数据的分布没有假设，可以用于非线性数据。
  • 可用于分类和回归任务。

缺点：

  • 计算成本高，尤其是在大数据集上。
  • 需要大量内存来存储训练数据。
  • 对不均匀的特征缩放敏感，可能需要进行特征归一化。

结论

KNN算法是一种直观且易于实现的机器学习方法，适用于各种类型的数据集。尽管它在计算和存储上可能存在一些挑战，但它在许多实际应用中仍然非常有效。

决策树

决策树是一种常用的分类和回归方法，它通过学习简单的决策规则从数据特征中推断出目标值。

image-20240909022248428

决策树原理

决策树通过树状图的形式模拟决策过程，每个内部节点代表一个特征上的判断，每个分支代表判断的结果，每个叶节点代表一个决策结果。

算法步骤

  1. 选择最佳特征：选择一个特征，使得按照该特征分割数据后，产生的子集尽可能“纯”。
  2. 分割数据集：按照选定的特征的不同值，将数据集分割成多个子集。
  3. 递归构建树：对每个子集重复步骤1和2，直到满足停止条件（如所有数据都属于同一类别，或者达到了树的最大深度）。
  4. 剪枝：为了防止过拟合，可能需要对树进行剪枝，移除一些过于具体的判断条件。

特征选择

特征选择是决策树算法的核心，常用的方法包括信息增益（ID3算法）、增益率（C4.5算法）和基尼不纯度（CART算法）。

信息增益（ID3算法）

信息增益衡量了特征$T$对于数据集$D$的分类能力，如果有多个属性，则在确定根节点以后，将根节点的分类结果作为整体分类结果，根据同样的算法比较其他属性的信息增益，挑选信息增益最大的属性作为第二个划分的节点。计算公式为：
$$
\text{Gain}(D, T) = \text{Entropy}(D) - \sum_{v \in \text{values}(T)} \frac{|D_v|}{|D|} \text{Entropy}(D_v)
$$

其中，$ \text{Entropy}(D) $ 是数据集$D$的熵，$ D_v $ 是特征$T$取值为$v$时的数据集。

增益率（C4.5算法）

增益率是信息增益与特征的固有信息（即分裂信息）的比值，在ID3算法中，显然属性的取值越多，信息增益越大。为了避免属性取值个数的影响， C4.5算法从候选划分中找出信息增益高于平均水平的属性，再从中选出信息增益率（用信息增益除以该属性本身的固有值Intrinsic value）最高的分类作为分裂规则。计算公式为：
$$
\text{GainRatio}(D, T) = \frac{\text{Gain}(D, T)}{\text{SplitInfo}(D, T)}
$$

基尼不纯度（CART算法）

基尼不纯度衡量了数据集的不纯度，计算公式为：

$$
\text{Gini}(D) = 1 - \sum_{j=1}^{m} p_j^2
$$

其中，$ p_j $ 是数据集中第$j$个类别的比例。选择Gini系数减少最快的分裂规则，最小化不纯度。

剪枝

为了防止过拟合，决策树算法通常会在构建树之后进行剪枝。剪枝的方法包括预剪枝（在构建树的过程中提前停止树的生长）和后剪枝（先让树完全生长，然后自底向上评估是否需要剪枝）。

算法优缺点

优点：

  • 易于理解和解释。
  • 不需要假设数据的分布。
  • 可以处理数值型和类别型数据。
  • 可以处理多输出问题。

缺点：

  • 容易过拟合，特别是在决策树很深的情况下。
  • 对于某些数据集，构建的决策树可能不稳定。

结论

决策树是一种强大的非线性学习算法，它通过递归地选择最佳特征来构建模型。通过适当的剪枝策略，可以有效地控制决策树的复杂度，从而提高模型的泛化能力。

K-means算法

K-means是一种广泛使用的聚类算法，用于将数据点划分为K个预先指定的簇。

image-20240909024525351

K-means算法原理

K-means算法的目标是最小化簇内距离的平方和，即每个点到其簇中心的距离。算法通过迭代地移动簇中心（称为质心）来实现这一目标。

算法步骤

  1. 初始化：随机选择K个数据点作为初始质心。
  2. 分配：将每个数据点分配给最近的质心，形成K个簇。
  3. 更新：重新计算每个簇的质心，即计算簇中所有点的均值。
  4. 迭代：重复步骤2和3，直到质心的位置不再显著变化或达到预定的迭代次数。

质心更新

质心是簇中所有点的均值，计算公式为：

$$
\mu_j^{(new)} = \frac{1}{|C_j|} \sum_{x \in C_j} x
$$

其中，$ \mu_j^{(new)} $ 是第 $ j $ 个簇的新质心，$ C_j $ 是第 $ j $ 个簇中的点集，$ |C_j| $ 是簇中点的数量。

距离度量

K-means算法通常使用欧氏距离来衡量数据点之间的距离，计算公式为：

$$
d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}
$$

其中，$ x $ 和 $ y $ 是两个数据点，$ n $ 是特征的数量。

算法优缺点

优点：

  • 算法简单，易于实现。
  • 计算效率较高，尤其是在数据维度不是特别高的情况下。
  • 可以用于大规模数据集。

缺点：

  • 需要预先指定簇的数量K。
  • 对初始质心的选择敏感，可能导致局部最优解。
  • 对离群点敏感，离群点可能会对质心的位置产生较大影响。

算法实现

以下是K-means算法的伪代码：

1
2
3
4
5
6
7
8
函数 K-means(D, K):
	初始化质心 C = {c1, c2, ..., cK}
	while(质心显著变化)
	for D 中的每个点 x：
	    将 x 分配给最近的质心所在的簇
	for每个簇 Cj：
	    重新计算簇 Cj 的质心 μj	
	return 最终的簇集合

选择K值

选择K值是K-means算法中的一个关键问题。常用的方法包括：

  • 肘部法则：随着K值的增加，簇内距离的平方和会减少，选择减少幅度突然变小的点作为K值。
  • 轮廓系数：衡量簇内距离和簇间距离的比例，选择轮廓系数最大的K值。

结论

K-means算法是一种简单有效的聚类方法，适用于各种数据集。通过适当的初始化和K值选择，可以有效地发现数据中的簇结构。

支持向量机算法 (SVM)

支持向量机是一种强大的分类技术，用于解决数据分类和回归问题。SVM的目标是找到最优的决策边界，即最大化两个类别之间的边界。

image-20240909030138320

SVM算法原理

SVM通过在特征空间中寻找最大间隔超平面来区分不同的类别。支持向量是距离决策边界最近的那些数据点，它们决定了最大间隔超平面的位置。

线性可分SVM

对于线性可分的数据，SVM的目标是最大化两个类别之间的间隔。间隔定义为最近的数据点（支持向量）到决策边界的距离。

优化问题

线性SVM的优化问题可以表示为：

$$
\min_{\mathbf{w}, b} \frac{1}{2} |\mathbf{w}|^2
$$

$$
\text{subject to } y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, ; \text{for all } i
$$

其中，$ \mathbf{w} $ 是超平面的法向量，$ b $ 是偏置项，$ \mathbf{x}_i $ 是特征向量，$ y_i $ 是对应的标签（+1或-1）。

核技巧

对于非线性可分的数据，SVM使用核技巧将数据映射到高维空间，在这个空间中寻找最优超平面。

常用核函数

  • 线性核：$ K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i \cdot \mathbf{x}_j $
  • 多项式核：$ K(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \mathbf{x}_i \cdot \mathbf{x}_j + r)^d $
  • **径向基函数 (RBF)**：$ K(\mathbf{x}_i, \mathbf{x}_j) = e^{-\gamma |\mathbf{x}_i - \mathbf{x}_j|^2} $
  • Sigmoid核：$ K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \mathbf{x}_i \cdot \mathbf{x}_j + r) $

软间隔SVM

软间隔SVM通过引入松弛变量来处理数据中的噪声和重叠，允许某些数据点违反间隔规则。

优化问题

软间隔SVM的优化问题可以表示为：

$$
\min_{\mathbf{w}, b, \xi} \frac{1}{2} |\mathbf{w}|^2 + C \sum_{i=1}^n \xi_i
$$

$$
\text{subject to } y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i, ; \text{for all } i
$$
$$
\text{and } \xi_i \geq 0, ; \text{for all } i
$$

其中，$ \xi_i $ 是松弛变量，$ C $ 是正则化参数，控制间隔违规的惩罚强度。

算法步骤

  1. 选择核函数和参数：根据数据的特性选择合适的核函数和参数。
  2. 构建并求解优化问题：使用拉格朗日乘子法构建对偶问题，并求解得到拉格朗日乘子。
  3. 计算决策函数：根据求解得到的拉格朗日乘子和支持向量计算决策函数。
  4. 预测新数据：使用决策函数对新数据进行分类。

算法优缺点

优点：

  • 在高维空间表现良好，尤其是在文本分类等应用中。
  • 能够处理非线性问题。
  • 泛化能力强。

缺点：

  • 对大规模数据集的训练效率较低。
  • 核函数和参数选择对结果影响较大。

结论

SVM是一种强大的分类算法，通过最大化类别间的间隔来提高分类的准确性。核技巧的使用使得SVM能够有效地处理非线性可分的数据。尽管SVM在参数选择和大规模数据处理上存在挑战，但它在许多领域仍然是首选的分类方法。

集成算法与随机森林

集成算法是一种机器学习方法，它通过组合多个不同的学习算法或数据子集来提高模型的泛化能力和性能。

image-20240909074059913

集成算法原理

集成算法通过组合多个基学习器来构建一个强大的模型，这些基学习器可以是同质的（相同类型的学习器）或异质的（不同类型的学习器）。集成算法通常分为三类：Bagging、Boosting和Stacking。

Bagging

Bagging（Bootstrap Aggregating）是一种并行集成方法，它通过对原始数据集进行多次重采样来训练多个基学习器，然后通过平均或投票的方式来提高模型的泛化能力。随机森林是集成算法的一种，属于Bagging方法，它通过构建多个决策树并将它们的结果进行投票或平均，以得到最终的预测。

image-20240909074447354

Bagging算法，又称为装袋算法，最初由Leo Breiman于1996年提出，是并行式集成学习的典型代表。Bagging算法主要是从数据层面上设计，使用自助采样法随机有放回地对样本进行采样，构建出样本量相等的相互独立的样本数据集，在同一算法中训练出不同的模型。Bagging算法的集成策略也很简单，对于分类问题，一般通过投票法，以多数模型预测结果为最终结果。而对于回归问题，一般采用算术平均法，对所有模型的预测结果做算术平均得到最终结果。

Boosting

Boosting是一种串行集成方法，它通过逐步增加基学习器的权重来纠正前一个学习器的错误，从而提高模型的性能。

image-20240909074153521

随机森林算法

随机森林是一种基于决策树的集成学习方法，它通过构建多个决策树并结合它们的预测结果来提高整体模型的性能。

随机森林的构造步骤

  1. 一个样本容量为N的样本，从原始数据集中使用自助采样法（bootstrap sampling）抽取样本，有放回的抽取N次，每次抽取1个，最终形成了N个样本。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。
  2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
  3. 决策树形成过程中每个节点都要按照步骤2来分裂。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
  4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。

随机森林的优缺点

优点：

  • 准确性高，能够有效处理非线性问题。
  • 能够处理大量样本和特征。
  • 不需要特征选择，可以处理高维数据。
  • 能够评估特征的重要性。

缺点：

  • 模型可能会相对复杂，需要较多的计算资源。
  • 预测过程可能较慢，尤其是在有大量树的森林中。
  • 模型的可解释性不如单个决策树。

随机森林的应用

随机森林在金融、医疗、市场营销、推荐系统、生态保护和制造业等多个领域都有广泛的应用。

结论

集成算法通过组合多个学习器来提高模型的性能，而随机森林作为其中的一种方法，通过构建多个决策树并结合它们的预测结果，能够有效地处理过拟合问题，提高模型的泛化能力。尽管存在一些缺点，如计算资源消耗大和模型复杂度高，但随机森林仍然是一个强大且实用的机器学习工具。

主成分分析（PCA）算法

主成分分析（PCA）是一种统计方法，用于通过正交变换将一组可能相关的变量转换为一组线性不相关的变量，这组变量称为主成分。PCA广泛用于数据降维和提取数据中的关键特征。

image-20240909080150048

PCA算法原理

PCA的目标是找到数据中方差最大的方向，并将其作为新坐标轴的方向。这些新坐标轴被称为主成分，它们是原始数据集的线性组合。

算法步骤

  1. 标准化数据：将数据集中的每个特征进行标准化处理，使其均值为0，方差为1。
  2. 计算协方差矩阵：计算数据的协方差矩阵，以确定数据中变量之间的相关性。
  3. 计算特征值和特征向量：计算协方差矩阵的特征值和对应的特征向量。
  4. 选择主成分：根据特征值的大小，选择最重要的K个特征向量，这些向量代表了数据中方差最大的方向。
  5. 构造新特征空间：将原始数据投影到选定的特征向量上，构造新的特征空间。

数学表达

假设有一个数据集 $ X $，其协方差矩阵为 $ \Sigma $，$ \Sigma $ 的特征值为 $ \lambda_1, \lambda_2, …, \lambda_n $，对应的特征向量为 $ v_1, v_2, …, v_n $。则PCA的目标是：

$$
\Sigma v = \lambda v
$$

其中，$ v $ 是特征向量，$ \lambda $ 是对应的特征值。

算法优缺点

优点：

  • 减少了数据的维度，提高了计算效率。
  • 剔除了数据中的噪声和冗余信息。
  • 有助于可视化高维数据。

缺点：

  • 可能会丢失一些重要信息，因为降维会舍弃一些特征。
  • 对于非线性问题，PCA可能不是最佳选择。

算法实现

以下是PCA算法的伪代码：

1
2
3
4
5
6
7
function PCA(X, K):
	标准化数据 X
	计算协方差矩阵 Σ
	计算 Σ 的特征值和特征向量
	选择最大的 K 个特征值对应的特征向量
	构造特征向量矩阵 P
	return X * P

PCA的应用

PCA在许多领域都有应用，包括：

  • 图像压缩：通过降维减少图像存储所需的空间。
  • 人脸识别：通过降维提高识别算法的效率。
  • 金融分析：通过降维分析股票市场数据。

结论

PCA是一种有效的数据降维技术，它通过提取数据中最重要的特征来简化数据结构。虽然PCA在处理线性关系方面表现出色，但在面对非线性问题时可能需要其他技术。尽管存在局限性，PCA仍然是数据分析和预处理中不可或缺的工具。