[机器学习]-2 经典机器学习算法

一 线性模型

线性模型是机器学习中最基本和最常用的一类模型，假设输出变量是输入变量的线性组合。线性模型在许多实际应用中表现良好，并且为更复杂的模型（如非线性模型、深度学习模型）奠定了理论基础；优点是简单易懂，易于实现和解释，计算复杂度低，适合大规模数据；缺点是不能处理复杂的非线性关系，容易受到异常值的影响，可能出现过拟合或欠拟合，需要正则化处理。

线性模型假设输出y是输入变量 x=[x1,x2,…,xn]的线性组合，加上一个常数项（截距项）和噪声项：y=wTx+b+ϵ，其中：

w=[w1,w2,…,wn]是权重向量；

b是截距（bias）或偏置项；

ϵ是噪声项，通常假设服从正态分布。

1 主要类型

1）线性回归（Linear Regression）：拟合一个线性函数来预测连续目标变量。

模型表达式：y=wTx+b

损失函数：最小化均方误差（MSE），MSE=1/m {∑i=1m(yi−(wTxi+b))2}

优化方法：梯度下降、正规方程、最小二乘法等。

2）逻辑回归（Logistic Regression）：用于分类问题，通过sigmoid函数将线性组合映射到[0,1]之间，表示概率。

模型表达式：y= σ(wTx+b)，σ(z) =1/（1 + e-z）

损失函数：对数似然损失，Loss=−1/m {∑i=1m [yilog(^yi)+(1−yi)log(1−^yi)]}

优化方法：梯度下降、牛顿法等。

3）Ridge回归：在线性回归基础上添加L2正则化，减少过拟合。

模型表达式：y=wTx+b

损失函数：最小化正则化的均方误差，Loss=1/m {∑i=1m [yi−(wTxi+b)]2+ λ∥w∥2}

4）Lasso回归：在线性回归基础上添加L1正则化，实现特征选择。

模型表达式：y=wTx+b

损失函数：最小化正则化的均方误差，Loss=1/m {∑i=1m [yi−(wTxi+b)]2+ λ∥w∥1}

2 建模和训练方法

数据预处理：标准化，将数据进行标准化处理，使得每个特征均值为0，方差为1；特征选择，选择对目标变量有显著影响的特征。

训练过程

   - 初始化参数（权重和截距）；

   - 计算损失函数的梯度；

   - 更新参数：根据梯度和学习率，使用优化算法（如梯度下降）更新参数；

   - 迭代上述过程，直到损失函数收敛或达到最大迭代次数。

二 决策树

决策树是一种用于分类和回归的非参数监督学习方法，以树状结构表示决策过程，通过对特征进行条件判断来预测目标变量。决策树易于理解和解释，结果具有直观的可视化，能够处理数值型和类别型数据和多输出问题，对缺失值不敏感，可以容忍一定程度的缺失数据。但决策树容易过拟合，需剪枝处理；对噪声数据敏感，容易受极端值影响；在处理类别较多的数据集时，树的构建可能会变得复杂且计算量大。

1 决策树的构建

决策树的构建过程通过递归地选择最优特征来分割数据集，使得每次分割能够最大化地减少数据的不纯度或不确定性。

1）特征选择标准

信息增益：基于熵（Entropy）的变化量来选择特征，常用ID3算法。

InfoGain(D, A) = Entropy(D) - ∑v∈Values(A)(∣Dv∣/∣D∣)Entropy(Dv)

信息增益率：修正了信息增益偏好多值特征的问题，常用C4.5算法。

GainRatio(D, A) = InfoGain(D, A) / SplitInfo(D, A)

基尼指数：基于基尼不纯度选择特征，常用CART算法。

Gini(D) = 1 - ∑K=1K (pk)^2

    

2）树的构建过程

2.1）从根节点开始，计算所有特征的选择标准（如信息增益）。

2.2）选择最优特征，根据该特征的不同取值分割数据集。

2.3）为每个子集递归地构建子树，重复步骤1和2，直到满足停止条件。

3）停止条件

   - 所有样本属于同一类别。

   - 特征集为空或没有更多特征可分割。

   - 达到最大树深度或最小样本数。

2 决策树的剪枝

决策树在训练过程中容易过拟合，为了提高泛化能力，需要进行剪枝，分为前剪枝和后剪枝。

1）前剪枝：在构建过程中提前停止树的生长。

   - 设置最大树深度。

   - 设置叶节点的最小样本数。

   - 设置信息增益阈值。

2）后剪枝：先构建一棵完整的决策树，然后回溯剪枝。

代价复杂度剪枝：通过最小化损失函数选择最优子树，Loss(T)=∑t∈T [Loss(t)+α∣T∣]

交叉验证剪枝：通过交叉验证评估子树的性能，选择最优子树。

3 决策树的实现

以Python的Scikit-Learn库为例，介绍决策树的实现过程。

1）导入库和数据

   from sklearn.datasets import load_iris

   from sklearn.model_selection import train_test_split

   from sklearn.tree import DecisionTreeClassifier

   # 加载数据集

   iris = load_iris()

   X = iris.data

   y = iris.target

   # 划分训练集和测试集

   X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

  

2）构建和训练决策树模型

   # 构建决策树分类器

   clf = DecisionTreeClassifier(criterion='gini', max_depth=3, random_state=42)

   # 训练模型

   clf.fit(X_train, y_train)

   

3）模型评估

   from sklearn.metrics import accuracy_score, confusion_matrix, classification_report

   # 预测

   y_pred = clf.predict(X_test)

   # 评估

   print("Accuracy:", accuracy_score(y_test, y_pred))

   print("Confusion Matrix:\n", confusion_matrix(y_test, y_pred))

   print("Classification Report:\n", classification_report(y_test, y_pred))

 4）决策树可视化

   from sklearn.tree import export_graphviz

   import graphviz

   # 导出决策树结构

   dot_data = export_graphviz(clf, out_file=None,

                              feature_names=iris.feature_names,  

                              class_names=iris.target_names,  

                              filled=True, rounded=True,  

                              special_characters=True)  

   graph = graphviz.Source(dot_data)  

   graph.render("iris")  # 保存为文件

   graph.view()  # 显示决策树

  

三 支持向量机SVM

支持向量机（Support Vector Machine）是一种用于分类和回归的监督学习算法，通过寻找最佳分离超平面来实现数据分类，具有很高的分类性能，特别适用于小样本、高维度的数据。但SVM对缺失数据较为敏感，计算复杂度较高，训练时间较长，需要选择合适的核函数和参数较为复杂，需要调参。

1 基本概念

1）支持向量：离分离超平面最近的样本点，这些点对决策边界起决定作用。

2）超平面：在特征空间中将不同类别样本分开的决策边界。

3）间隔：支持向量到超平面的距离，SVM通过最大化间隔来提高分类器的泛化能力。

2 线性SVM

1）线性可分数据：当数据集是线性可分的，SVM试图找到能够将数据分开的最佳超平面。

目标：最大化间隔2/ ∥W∥

约束条件：yi (w⋅xi +b)≥1，∀i

优化问题：minw,b (1/2) ∥W∥2

2）线性不可分数据：对于线性不可分数据，SVM引入松弛变量ξi允许某些样本点违背约束条件。

优化问题：minw,b,ξ (1/2) ∥W∥2 + C∑i=1n ξi ，其中C 是惩罚参数，控制误差项对优化目标的影响。在以下约束条件下：yi (w⋅xi +b) ≥ 1−ξi​，ξi ≥ 0，∀i。

3 非线性SVM

对于非线性可分数据，SVM通过核函数（Kernel Function）将数据映射到高维空间，使其在高维空间中线性可分。

1）核函数：将输入数据映射到高维特征空间的函数，常用的核函数包括：

线性核：K(xi, xj) = xi⋅xj​

多项式核：K(xi, xj) = (xi⋅xj +c)d

高斯径向基函数核：K(xi, xj) = exp(−γ∥xi-xj∥2)

sigmoid 核：K(xi, xj) = tanh(αxi⋅xj +c)

2）优化问题：通过核函数将优化问题从原始空间转到高维特征空间。

目标：minα (1/2)∑i=1n∑j=1nαiαj yiyj K(xi, xj) − ∑i=1nαi​

在以下约束条件下：∑i=1nαiyi = 0, 0≤αi≤C,∀i

4 SVM的多类分类

SVM本质上是二分类器，处理多类分类问题时，常用以下策略：一对多（One-vs-Rest, OvR），将一个类别与其他所有类别进行二分类，构建多个二分类器；一对一（One-vs-One, OvO），将每两个类别进行二分类，构建K(K-1)/2个二分类器（K为类别数）。

5 SVM的实现

以Python的Scikit-Learn库为例，介绍SVM的实现过程。

1）导入库和数据

   from sklearn.datasets import load_iris

   from sklearn.model_selection import train_test_split

   from sklearn.svm import SVC

   # 加载数据集

   iris = load_iris()

   X = iris.data

   y = iris.target

   # 划分训练集和测试集

   X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

  2）构建和训练SVM模型

   # 构建支持向量分类器

   clf = SVC(kernel='rbf', C=1, gamma='scale')

   # 训练模型

   clf.fit(X_train, y_train)

  

3）模型评估

   from sklearn.metrics import accuracy_score, confusion_matrix, classification_report

   # 预测

   y_pred = clf.predict(X_test)

   # 评估

   print("Accuracy:", accuracy_score(y_test, y_pred))

   print("Confusion Matrix:\n", confusion_matrix(y_test, y_pred))

   print("Classification Report:\n", classification_report(y_test, y_pred))

   

4）参数调优

   from sklearn.model_selection import GridSearchCV

   # 参数网格

   param_grid = {'C': [0.1, 1, 10], 'gamma': ['scale', 'auto', 0.1, 1, 10], 'kernel': ['rbf', 'poly', 'sigmoid']}

   # 网格搜索

   grid = GridSearchCV(SVC(), param_grid, refit=True, verbose=3)

   grid.fit(X_train, y_train)

   # 最佳参数

   print("Best Parameters:", grid.best_params_)

   # 使用最佳参数预测

   grid_predictions = grid.predict(X_test)

   # 评估

   print("Grid Search Accuracy:", accuracy_score(y_test, grid_predictions))

四 K近邻学习（K-Nearest Neighbors, KNN）

K近邻算法是一种基本且直观的机器学习算法，广泛用于分类和回归问题。KNN算法基于“相似的样本具有相似的特征”这一假设，给定一个待分类样本，通过计算它与训练集中所有样本的距离，找到最近的K个样本（邻居），然后根据这K个样本的标签进行投票，决定待分类样本的类别。在回归问题中，KNN通过计算最近K个样本标签的平均值来预测。

KNN算法思想简单，容易理解和实现，不需要对训练数据进行显式学习，直接对新数据进行预测。但预测时需要计算所有样本的距离，导致计算开销大，尤其是在数据量大时；而且对K值敏感，K值的选择对算法性能影响较大，K值过小容易过拟合，K值过大容易欠拟合；此外在高维数据中，距离计算可能会失去意义（维度灾难）。

1 算法步骤

1）选择K值：选择参数K，即选取的最近邻居的数量。

2）计算距离：计算待分类样本与训练集中每个样本之间的距离。常用的距离度量包括欧氏距离、曼哈顿距离、余弦相似度等。

3）找最近的K个邻居：根据计算的距离，找到距离待分类样本最近的K个训练样本。

4）投票决策：分类问题，对这K个邻居的标签进行投票，选择出现次数最多的标签作为预测结果；回归问题，计算这K个邻居的标签的平均值，作为预测结果。

2 KNN的距离度量

1）欧氏距离（Euclidean Distance）：两点间的直线距离。

2）曼哈顿距离（Manhattan Distance）：两点在各坐标轴上的绝对距离之和。

d(xi,xj) =∑m=1 n​∣xim−xjm∣

3）余弦相似度（Cosine Similarity）：两向量之间的余弦值，用于度量方向的相似性。

Cosine Similarity(xi,xj) = (xi ⋅xj )/ (∥xi∥∥xj∥)​

3 KNN的实现

以Python中的Scikit-Learn库为例，展示KNN在分类和回归中的实现。

1）分类问题

from sklearn.datasets import load_iris

from sklearn.model_selection import train_test_split

from sklearn.neighbors import KNeighborsClassifier

from sklearn.metrics import accuracy_score

# 加载数据集

iris = load_iris()

X = iris.data

y = iris.target

# 划分训练集和测试集

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 构建KNN分类模型

knn_classifier = KNeighborsClassifier(n_neighbors=3)

# 训练模型

knn_classifier.fit(X_train, y_train)

# 预测结果

y_pred = knn_classifier.predict(X_test)

# 评估模型

accuracy = accuracy_score(y_test, y_pred)

print(f"Accuracy: {accuracy:.2f}")

2）回归问题

from sklearn.datasets import load_boston

from sklearn.model_selection import train_test_split

from sklearn.neighbors import KNeighborsRegressor

from sklearn.metrics import mean_squared_error

# 加载数据集

boston = load_boston()

X = boston.data

y = boston.target

# 划分训练集和测试集

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 构建KNN回归模型

knn_regressor = KNeighborsRegressor(n_neighbors=3)

# 训练模型

knn_regressor.fit(X_train, y_train)

# 预测结果

y_pred = knn_regressor.predict(X_test)

# 评估模型

mse = mean_squared_error(y_test, y_pred)

print(f"Mean Squared Error: {mse:.2f}")

五 聚类

聚类是一种常见的无监督学习方法，其目的是将数据集中的样本划分为若干组，使得同一组内的样本相似度尽可能高，而不同组间的样本相似度尽可能低。聚类广泛应用于数据分析、模式识别、图像处理等领域。

1 基本概念

1）样本：数据集中的一个数据点。

2）簇（Cluster）：一组相似的数据点。

3）相似度度量：衡量数据点之间相似程度的标准，常用的相似度度量包括欧氏距离、曼哈顿距离、余弦相似度等。

2 常见的聚类算法

1）K均值（K-Means）

原理：将数据集分为K个簇，使得每个数据点属于距离最近的簇中心（质心）。这种算法简单快速，适用于大规模数据集；但需要预先指定 K ，对初始值敏感，容易陷入局部最优，不能处理非球形分布的簇。

步骤：

1.1）随机选择K个初始质心。

1.2）分配每个数据点到最近的质心，形成 $K$ 个簇。

1.3）重新计算每个簇的质心。

1.4）重复步骤 2 和 3，直到质心不再变化或达到最大迭代次数。

2）层次聚类

原理：通过层次结构将数据点聚类，不需要预先指定簇的数量，可以通过树状图可视化；但计算复杂度高，不适合大规模数据集，无法撤销合并操作。

步骤：

2.1）每个数据点自成一簇。

2.2）迭代地合并最近的两个簇，直到所有数据点合并到一个簇或达到指定簇数量。

3）DBSCAN（Density-Based Spatial Clustering of Applications with Noise）   

原理：基于数据点的密度分布进行聚类，可以发现任意形状的簇，并能识别噪声点，不需要预先指定簇数量；但对于不同密度的簇效果较差，参数ε和 MinPts 较难确定。

步骤：

3.1）指定半径ε和最小点数 MinPts。

3.2）从一个点出发，如果在半径ε内的点数大于等于 MinPts，则将这些点归为一个簇。

3.3）对新加入簇的点，重复步骤 2，直到不再有新的点加入。

4）均值漂移

原理：通过数据点密度梯度上升找到簇的质心，可以发现任意形状的簇，不需要指定簇数量。缺点是计算复杂度高，不适合大规模数据集

步骤：

4.1）对每个数据点计算其密度梯度的方向，并沿该方向移动。

4.2）重复步骤 1，直到所有数据点收敛到质心。

5）高斯混合模型

原理：假设数据由多个高斯分布组成，通过期望最大化（EM）算法估计每个高斯分布的参数。

步骤：

5.1）初始化每个高斯分布的参数。

5.2）计算每个数据点属于每个高斯分布的概率（E步）。

5.3）根据概率重新估计高斯分布的参数（M步）。

5.4）重复步骤 2 和 3，直到参数收敛。

3 评估指标

1）轮廓系数

   - 衡量聚类结果的紧密度和分离度。

   - 取值范围：[-1, 1]，值越大表示聚类效果越好。

2）互信息

   - 衡量聚类结果与真实标签之间的互信息。

   - 值越大表示聚类结果与真实标签越一致。

3）调整兰德指数

   - 衡量聚类结果与真实标签的一致性。

   - 取值范围：[-1, 1]，值越大表示聚类效果越好。

4）DB指数（Davies-Bouldin Index）

   - 衡量聚类结果的紧密度和分离度。

   - 值越小表示聚类效果越好。

4 聚类算法的实现

以Python的Scikit-Learn库为例，介绍K均值聚类实现过程。

   from sklearn.cluster import KMeans

   import numpy as np

   # 生成样本数据

   X = np.array([[1, 2], [1, 4], [1, 0],

                 [4, 2], [4, 4], [4, 0]])

   # 构建KMeans模型

   kmeans = KMeans(n_clusters=2, random_state=0)

   # 训练模型

   kmeans.fit(X)

   # 预测簇标签

   labels = kmeans.predict(X)

   print("Labels:", labels)

   # 簇中心

   print("Cluster Centers:", kmeans.cluster_centers_)