简答题：（40）

1. KNN与k-means异同点（B卷K-means算法伪代码）

KNN与k-means算法的异同点如下：异同点：
1. 解决问题不同：KNN是用于分类和回归问题的监督学习方法，而k-means是用于聚类问题的无监督学习方法。
2. 数据处理方式不同：KNN算法是对数据点进行分类或回归，而k-means算法是对数据点进行聚类。
3. 算法原理不同：KNN方法通过计算数据点之间的距离，来寻找离测试样本最近的K个训练样本进行分类或回归；k-means方法通过迭代计算数据点与聚类中心之间的距离，来不断更新聚类中心，直到聚类中心不再变化，从而达到聚类的目的。

相同点：
1. 都是基于距离度量的算法，都需要计算数据点之间的距离。
2. 都需要确定K值，KNN算法中的K代表要选择几个最近的邻居，而k-means算法中的K代表要分成几个簇。
3. 都需要进行模型选择和评估，根据测试集的效果来确定最终模型的好坏。

以下是B卷中K-means算法的伪代码：
1. 随机选取K个初始聚类中心
2. 将每个数据点分配到距离最近的聚类中心
3. 更新每个聚类的中心点
4. 重复执行第2步和第3步，直到聚类中心不再变化或者达到最大迭代次数

输入：样本数据集 X，簇的个数 k
输出：聚类结果 C，每个样本所属的簇
1. 从数据集中随机选择 k 个样本作为初始的聚类中心点
2. 重复以下步骤直到满足收敛条件：
   a. 对于数据集中的每个样本 x_i：
      - 计算 x_i 与每个聚类中心点的距离，并将样本分配到与之距离最近的聚类中心的簇中
   b. 对于每个簇 c_j：
      - 计算该簇内所有样本的均值作为新的聚类中心点
3. 返回每个样本所属的簇 C

2. 朴素贝叶斯算法流程—处理垃圾邮件（B卷朴素贝叶斯算法在外卖小哥正向评价判断）

朴素贝叶斯是一种基于贝叶斯定理的分类算法，常用于文本分类和垃圾邮件过滤。它的核心思想是假设所有的特征都是相互独立的，然后根据特征的条件概率进行分类。

朴素贝叶斯算法的流程：

输入：训练数据集X，训练数据的标签y，待分类的样本x。
输出：样本x的分类结果。

统计训练数据集中每个类别的先验概率P(Y)：计算每个类别在训练集中的出现频率，并除以训练样本的总数。
计算每个特征的条件概率P(X|Y)：对于每个特征，计算该特征在给定类别下的条件概率。这可以通过将特征值与对应类别的训练样本进行匹配来实现。
计算待分类样本x属于每个类别的后验概率P(Y|X)：使用贝叶斯定理，结合先验概率和条件概率，计算样本x属于每个类别的后验概率。后验概率最大的类别将被认为是样本x的分类结果。
输出：将样本x分配给具有最大后验概率的类别。

需要注意的是，为了避免概率为0的情况，通常会引入平滑技术（如拉普拉斯平滑）来处理。此外，在实际中，朴素贝叶斯算法通常使用对数概率来避免数值下溢。
对于连续特征，朴素贝叶斯算法通常会使用概率密度函数（如高斯分布）对其进行建模，然后使用特征的概率密度函数来计算条件概率。

处理垃圾邮件

当应用于垃圾邮件过滤时，朴素贝叶斯算法的处理流程如下：

数据准备：首先，将已有的邮件数据集分为训练集和测试集。训练集用于学习模型的参数，测试集用于评估模型的性能。
特征提取：从每封邮件中提取特征，常见的特征包括词频、词汇出现的概率等。特征提取过程将邮件转化为特征向量，其中每个特征表示某个单词或词汇的出现与否。
训练模型：使用训练集对朴素贝叶斯模型进行训练。对于每个特征向量，计算其对应的条件概率。
预测分类：对于待分类的新邮件，将其转化为特征向量，并使用训练好的模型计算每个类别（垃圾邮件或正常邮件）的后验概率。选择后验概率较大的类别作为最终的分类结果。
模型评估：使用测试集评估模型的性能，计算准确率、召回率、F1分数等指标来衡量模型的效果。

需要注意的是，在实际应用中，可能需要进行特征选择和特征权重调整，以提高模型的准确性。此外，预处理步骤如去除停用词、词干提取等也可以应用于朴素贝叶斯算法来提高性能。
朴素贝叶斯算法在垃圾邮件过滤中的优势在于其快速、简单且可扩展，同时能够处理大量的特征和样本。它的一个假设是特征之间的独立性，这在实际中可能不成立，但在大多数情况下仍能给出良好的分类结果。

外卖小哥正向评价判断

朴素贝叶斯算法可以应用于外卖小哥正向评价的判断，即根据评价文本判断该评价是正向的还是负向的。
以下是朴素贝叶斯算法在该场景下的处理流程：

数据准备：收集一定数量的评价数据，包括正向评价和负向评价。这些评价应尽可能具有代表性和多样性。
特征提取：从每个评价文本中提取特征，可以使用词袋模型（bag of words）或者词频统计作为特征。对文本进行分词、去除停用词、词干提取等预处理操作。
数据标注：根据评价的标签（正向或负向），为每个评价文本分配正确的标签。这些标签将用于训练模型。
训练模型：使用带有正确标签的评价数据集训练朴素贝叶斯分类模型。模型将使用特征向量和对应的标签学习文本特征与标签之间的关联。
预测分类：对于待分类的新评价，将其转化为特征向量，并使用训练好的模型计算正向评价和负向评价的后验概率。选择后验概率较大的类别作为最终的分类结果。
模型评估：评估模型的性能，可以使用测试集计算分类准确率、召回率、F1分数等指标来评估模型的表现。

需要注意的是，准确的分类结果需要依赖于准确的数据标注和具有代表性的训练数据。此外，对文本特征的选择和预处理也会影响模型的性能。

3. SVM（线性可分，非线性可分的各自的判断数学表达）

SVM（支持向量机）是一种常用的分类和回归算法。在进行分类问题时，SVM的主要目标是找到一个超平面（线性或非线性）来将两个不同的类别分开。线性可分的情况下，SVM的判断数学表达式为：
w^Tx + b ≥ 1, y = +1 (属于正类)
w^Tx + b ≤ -1, y = -1 (属于负类)
这个表达式中，w是超平面的法向量，b是偏移量，x是输入特征向量，y是输出类别。
非线性可分的情况下，SVM使用核函数对原始数据进行映射，将其转换到高维空间，使其变成线性可分的问题。在这种情况下，SVM的判断数学表达式可以写成：
∑(i=1 to m)αiyixi•x + b ≥ 1, y = +1 (属于正类)
∑(i=1 to m)αiyixi•x + b ≤ -1, y = -1 (属于负类)
这里 y 是输出类别，αi 是对应训练样本的拉格朗日乘子，xi 是训练样本的属性向量，m 是样本数量，b 是偏移量，核函数 K(xi, x) 将输入属性映射到其他空间中，其中 x 是输入样本属性向量。
当核函数 K(xi, x) 选用不同的函数形式时，SVM就对应不同的分类器模型，比如线性核、多项式核、高斯核等。

4. Apriori关联规则挖掘、

Apriori算法是一个经典的关联规则挖掘算法，用来挖掘数据集中的频繁项集和关联规则。这个算法的基本思路是：先找出数据集中的所有频繁项集，然后由频繁项集生成关联规则。Apriori算法的过程大致可分为两个步骤：1. 找出频繁项集
在第一步中，Apriori算法从单个项开始，依次遍历数据集中的所有项，并统计它们出现的频次。接下来，算法会对频次进行筛选，去掉低频项，只保留出现频率高于阈值的项，生成新的频繁项集。
在继续搜索新的频繁项集时，我们需要对原始项集的组合进行扩展，生成更长的候选项集。具体实现时，我们可以利用频繁项集的性质进行剪枝，例如如果一个项集中有某个子项集是非频繁的，那么这个项集也一定是非频繁的，可以直接剪掉。
这个过程可以持续进行下去，直到不能再生成新的频繁项集为止。

由频繁项集生成关联规则
在第二步中，Apriori算法会利用频繁项集生成关联规则。具体来说，算法会针对每一个频繁项集，生成所有可能的非空子集，逐一计算它们的支持度和置信度，对这些关联规则进行筛选，只保留支持度、置信度高于阈值的规则。
Aprior算法的时间复杂度较高，因为它需要进行大量的数据扫描和组合操作。不过，针对大规模数据集，可以使用优化手段，如FPGrowth算法等来进行更高效的频繁项集挖掘。

5. PCA与LDA

PCA和LDA都是常用的特征提取方法，用于将高维的数据降维到低维表示，以方便分类、聚类等机器学习任务的处理。两者都广泛应用于模式识别、人脸识别、图像处理等领域。下面简要介绍一下它们的主要思想及使用场景。1. PCA (Principal Component Analysis，主成分分析)
PCA是一种通过线性变换将原始数据投影到新的低维空间中的算法。PCA寻找一个线性变换，使得变换后的数据具有最大的方差，从而保留了原始数据的大部分信息。换句话说，PCA主要是用于找到投影后各个特征向量之间相关性最小的主成分，使得经过主成分变换后的数据能够尽量保留原有的特征，并且降维的同时尽量保持数据的信息量不变。通常情况下，PCA中使用的特征选择策略是基于数据的协方差矩阵而提出来的。
所以，PCA适用于无监督降维，也就是没有类别标签，不需要事先知道数据的类别，仅仅需要找到数据中最主要的特征信息进行降维。

2. LDA (Linear Discriminant Analysis，线性判别分析)
LDA是一种有监督降维算法，在PCA的基础上发展而来。LDA 下降后，新的低维度特征的特定类别将具有最佳的判别性，即，最小化特征间的协方差，同时最小化类别内的散度，最大化类别间的间隔（即使类别最大化）。LDA降维的基本思想是在保证信息最大化的同时，最大化样本分类的间隔，即在原始高维数据中找出能够最好地区分不同类别的特征并保留下来，削减其他不相关特征。
因此，LDA适用于有监督降维，数据需要事先知道类别标签。在分类任务中表现较好。
总之，PCA和LDA都是非常有用的特征提取方法，PCA主要用于无监督降维，而LDA主要用于有监督降维。根据实际任务，可以根据需要选择合适的方法。

6. 推荐算法

推荐算法是一种利用机器学习和数据挖掘技术，为用户提供个性化推荐的算法。它根据用户的历史行为、个人兴趣和偏好，以及物品的属性和特征，通过分析和挖掘这些数据，预测用户可能感兴趣的物品，并向用户推荐合适的内容。以下是几种常见的推荐算法：
1. 基于内容的推荐算法: 这种算法通过分析物品的属性和特征，与用户的历史行为进行匹配，为用户推荐具有相似特征的物品。例如，基于文本内容的推荐可以根据物品的文本描述和用户的兴趣，推荐相关的文章或新闻。
2. 协同过滤算法: 协同过滤算法基于用户的行为历史和与其他用户的相似性，推荐那些与用户具有相似兴趣的物品。这种算法可以基于用户行为（用户-物品关系）或物品的特征（物品-物品关系）来进行推荐。例如，基于用户行为的协同过滤可以根据用户的购买历史，向其推荐其他购买过相似物品的用户还购买过的物品。
3. 矩阵分解算法: 矩阵分解算法将用户-物品的关系矩阵分解为两个低维的矩阵，以捕捉隐藏的用户和物品特征。通过学习和预测这些潜在特征，可以进行个性化的推荐。矩阵分解算法在协同过滤中广泛使用，例如基于奇异值分解（SVD）的方法。
4. 深度学习算法: 深度学习在推荐系统中也有广泛应用。通过建立深度神经网络模型，可以从用户和物品的大量特征中学习到更高层次的表示和特征，从而提高推荐的准确性和表现力。

这些算法在实际推荐系统中常常结合使用，根据具体的场景和需求进行调整和优化。推荐算法的发展也是一个不断演进的过程，研究者们一直在探索和提出新的算法来改进推荐效果。

7. Sunday算法

Sunday算法是一种用于字符串匹配的算法，其主要思想是将匹配过程向右移动，直到出现第一个无法匹配的字符。然后根据该字符在模式串中出现的位置，将模式串向右移动一定的距离，使得该字符与文本串中的下一个字符对齐。这样可以减少不必要的比较次数，提高匹配速度。具体实现步骤如下：
1. 预处理模式串中每个字符最右边出现的位置（记为loctab[]）
2. 从左往右匹配文本串和模式串，如果当前字符匹配，则向右移动一位继续匹配
3. 如果当前字符不匹配，则查看文本串中下一个待匹配的字符（记为nextchar），并在模式串中找到nextchar的位置（记为j）。
4. 如果j为0，则将模式串整体向右移动1位，否则将模式串移动j位（即使得nextchar与文本串中的下一个字符对齐）
5. 重复步骤2-4直到匹配成功或者文本串匹配结束。
Sunday算法的时间复杂度为O(n+m)，其中n和m分别为文本串和模式串的长度。由于其简单易实现、效率高等优点，被广泛应用于文本匹配领域。

8. 最短路径

最短路径是图论中的一个经典问题，主要目的是在从图中的某一起点到某一终点的所有路径中找出一条距离最短的路径。这里的距离可以指代多种类型的度量标准，如边权、节点间距离、时间等。最短路径问题可以用多种算法解决，其中Dijkstra算法和Bellman-Ford算法是最为常见的两种。
Dijkstra算法是一种贪心算法，具体思路是从起点开始，不断选择当前距离起点最近的一个节点，并将其加入“已访问”集合中。然后以该节点为中心，更新与其相邻的节点到起点的距离，若更新后的距离比之前的短，则将其加入候选节点集合。最后重复该过程，直到终点被加入“已访问”集合或者所有与起点相连的节点都被访问过。Dijkstra算法可以求解带权有向图或无向图的最短路径，时间复杂度为O(n^2)。
Bellman-Ford算法是一种动态规划算法，通过不断迭代更新各个节点到起点的最短距离，直到收敛为止。具体过程是，首先给所有节点赋初值为正无穷大，起点的值赋为0。然后依次遍历所有边，对每条边(u, v)进行松弛操作：如果起点到u的距离加上(u, v)的权值小于终点到v的距离，则更新v的距离值。Bellman-Ford算法可以处理带负权边的图，时间复杂度为O(nm)，其中n和m分别为图中节点数和边数。

除了上述两种算法，还有Floyd-Warshall算法和SPFA算法等用于解决最短路径问题的算法，根据实际问题的规模和复杂度要求选择合适的算法才能保证算法效率。

9. 背包问题

背包问题是一个经典的组合优化问题，主要涉及在给定容量的情况下，如何选择一些物品放入背包中，使得在重量限制下价值最大化。背包问题通常分为两种类型：0/1背包和完全背包。
在0/1背包问题中，每个物品只能选择放入或不放入背包中，不能分成多个部分。因此可将问题转化为一个二进制决策问题，有一个固定容量的背包和n个物品，第i个物品的重量为wi，价值为vi，问在不超过背包容量的情况下，如何选择物品使得总价值最大。

解决0/1背包问题的经典算法是动态规划算法，其基本思路是利用子问题的最优解推导出整个问题的最优解。
具体实现时可建立一个二维数组dp，其中dp[i][j]表示前i个物品在不超过j的容量下能够达到的最大价值。对于第i个物品，有两种选择：放入背包或不放入背包。如果选择放入，则需要考虑第i个物品占据j容量的贡献变化；如果选择不放入，则需要使用前i-1个物品达到容量j的最大价值。根据这两种选择，可得到状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)。

完全背包问题则允许每种物品在背包中存在无限个，因此可将问题转化为一个组合问题。即有一个固定容量的背包和n个物品，第i个物品的重量为wi，价值为vi，问在不超过背包容量的情况下，如何选择物品使得总价值最大。

解决完全背包问题的经典算法同样是动态规划算法。但是相比0/1背包，需要修改状态转移方程： dp[i][j] = max(dp[i-1][j-kwi]+kvi) (0 <= k <= maxj/wi)。
其中k表示第i个物品选取的个数，最大值由物品的数量和容量限制决定。这是因为对于每个物品，可以选择0个或多个，因此需要在每个阶段找到最大的k，使得能够放入背包的数量最大。

10. 距离的度量方法

折叠

1. 欧氏距离(Euclidean Distance)

欧氏距离是最容易直观理解的距离度量方法，我们小学、初中和高中接触到的两个点在空间中的距离一般都是指欧氏距离。

二维平面上点a(x1,y1)与b(x2,y2)间的欧氏距离:

三维空间点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离:

n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的欧氏距离（两个n维向量）：

2. 曼哈顿距离(Manhattan Distance)

顾名思义，在曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。

二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离：

n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)的曼哈顿距离：

Python计算曼哈顿距离：

3. 切比雪夫距离 (Chebyshev Distance)
国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？这个距离就叫切比雪夫距离。
二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离：

n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)的切比雪夫距离：

4. 闵可夫斯基距离(Minkowski Distance)

闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。

闵氏距离定义：
两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

其中p是一个变参数：
当p=1时，就是曼哈顿距离；
当p=2时，就是欧氏距离；
当p→∞时，就是切比雪夫距离。
因此，根据变参数的不同，闵氏距离可以表示某一类/种的距离。

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
e.g. 二维样本(身高[单位:cm],体重[单位:kg]),现有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c的闵氏距离。但实际上身高的10cm并不能和体重的10kg划等号。
闵氏距离的缺点：
(1)将各个分量的量纲(scale)，也就是“单位”相同的看待了;
(2)未考虑各个分量的分布（期望，方差等）可能是不同的。

5. 标准化欧氏距离 (Standardized Euclidean Distance)

定义：标准化欧氏距离是针对欧氏距离的缺点而作的一种改进。标准欧氏距离的思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。假设样本集X的均值(mean)为m，标准差(standard deviation)为s，X的“标准化变量”表示为：

标准化欧氏距离公式：

如果将方差的倒数看成一个权重，也可称之为加权欧氏距离(Weighted Euclidean distance)。

6. 马氏距离(Mahalanobis Distance)

马氏距离的引出：

上图有两个正态分布的总体，它们的均值分别为a和b，但方差不一样，则图中的A点离哪个总体更近？或者说A有更大的概率属于谁？显然，A离左边的更近，A属于左边总体的概率更大，尽管A与a的欧式距离远一些。这就是马氏距离的直观解释。

概念：马氏距离是基于样本分布的一种距离。物理意义就是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解。再对所有主成分分解轴做归一化，形成新的坐标轴。由这些坐标轴张成的空间就是规范化的主成分空间。

定义：有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到μ的马氏距离表示为：

向量Xi与Xj之间的马氏距离定义为：

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布），则Xi与Xj之间的马氏距离等于他们的欧氏距离：

若协方差矩阵是对角矩阵，则就是标准化欧氏距离。

欧式距离&马氏距离：

期末复习简易版 - 图19
期末复习简易版 - 图20

马氏距离的特点：
量纲无关，排除变量之间的相关性的干扰；
马氏距离的计算是建立在总体样本的基础上的，如果拿同样的两个样本，放入两个不同的总体中，最后计算得出的两个样本间的马氏距离通常是不相同的，除非这两个总体的协方差矩阵碰巧相同；
计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在，这种情况下，用欧式距离计算即可。

7. 余弦距离(Cosine Distance)

几何中，夹角余弦可用来衡量两个向量方向的差异；机器学习中，借用这一概念来衡量样本向量之间的差异。

二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：

两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦为：

即：

夹角余弦取值范围为[-1,1]。余弦越大表示两个向量的夹角越小，余弦越小表示两向量的夹角越大。当两个向量的方向重合时余弦取最大值1，当两个向量的方向完全相反余弦取最小值-1。

8. 汉明距离(Hamming Distance)

定义：两个等长字符串s1与s2的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。例如:
汉明重量：是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。因此，如果向量空间中的元素a和b之间的汉明距离等于它们汉明重量的差a-b。
应用：汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。比如在信息编码过程中，为了增强容错性，应使得编码间的最小汉明距离尽可能大。但是，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离等算法。

数据处理与智能决策-第一次作业-翁修林-物联12002-202004071

二．算法设计（与简答题可能会交替）（30分）

1. 排序算法设计

冒泡排序

// 输入：待排序数组arr，数组长度n
BubbleSort(arr, n) {
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            // 比较相邻元素，如果前一个元素大于后一个元素，则交换位置
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

快速排序

// 输入：待排序数组arr，起始索引low，结束索引high
QuickSort(arr, low, high) {
    if (low < high) {
        // 分区操作，返回基准值的索引
        pivotIndex = Partition(arr, low, high);
        // 对基准值左边的子数组进行快速排序
        QuickSort(arr, low, pivotIndex - 1);
        // 对基准值右边的子数组进行快速排序
        QuickSort(arr, pivotIndex + 1, high);
    }
}
// 分区操作函数
Partition(arr, low, high) {
    // 选择基准值为数组的第一个元素
    pivot = arr[low];
    left = low;
    right = high;
    while (left < right) {
        // 从右往左找到第一个小于基准值的元素
        while (arr[right] >= pivot && left < right) {
            right--;
        }
        if (left < right) {
            arr[left] = arr[right];
            left++;
        }
        // 从左往右找到第一个大于基准值的元素
        while (arr[left] <= pivot && left < right) {
            left++;
        }
        if (left < right) {
            arr[right] = arr[left];
            right--;
        }
    }
    // 将基准值放入最终位置
    arr[left] = pivot;
    return left;
}

直接插入排序

// 输入：待排序数组arr，数组长度n
InsertionSort(arr, n) {
    for (i = 1; i < n; i++) {
        key = arr[i]; // 当前待插入的元素
        j = i - 1;
        // 将大于key的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key; // 将key插入到正确的位置
    }
}

希尔排序

// 输入：待排序数组arr，数组长度n
ShellSort(arr, n) {
    // 定义增量序列
    h = 1;
    while (h < n/3) {
        h = 3 * h + 1;
    }
    // 按照增量序列进行排序
    while (h >= 1) {
        for (i = h; i < n; i++) {
            key = arr[i]; // 当前待插入的元素
            j = i - h;
            // 将大于key的元素后移
            while (j >= 0 && arr[j] > key) {
                arr[j+h] = arr[j];
                j -= h;
            }
            arr[j+h] = key; // 将key插入到正确的位置
        }
        h = h / 3; // 缩小增量
    }
}

选择排序

// 输入：待排序数组arr，数组长度n
SelectionSort(arr, n) {
    for (i = 0; i < n-1; i++) {
        minIndex = i; // 默认将当前索引设置为最小元素的索引
        // 在未排序部分寻找最小元素的索引
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小元素与当前位置进行交换
        tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
}

堆排序

// 输入：待排序数组arr，数组长度n
HeapSort(arr, n) {
    // 构建初始堆
    for (i = n/2 - 1; i >= 0; i--) {
        Heapify(arr, n, i);
    }
    // 依次取出堆顶元素，调整堆
    for (i = n-1; i > 0; i--) {
        // 将堆顶元素与当前最后一个元素交换
        tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        // 调整堆
        Heapify(arr, i, 0);
    }
}
// 调整堆
Heapify(arr, n, root) {
    largest = root; // 默认将当前根节点设置为最大元素的索引
    left = 2 * root + 1; // 左子节点的索引
    right = 2 * root + 2; // 右子节点的索引
    // 在根节点、左子节点和右子节点中找到最大元素的索引
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大元素的索引不是根节点，则交换根节点和最大元素的位置，并继续调整子树
    if (largest != root) {
        tmp = arr[root];
        arr[root] = arr[largest];
        arr[largest] = tmp;
        Heapify(arr, n, largest);
    }
}

归并排序

// 归并排序的伪代码
// 归并排序函数，输入：待排序数组arr，数组长度n
MergeSort(arr, n) {
    if (n <= 1) {
        return; // 当数组长度小于等于1时，直接返回，不需要进行排序
    }
    // 计算中间索引
    mid = n / 2;
    // 创建临时数组，用于存放分割后的子数组
    leftArray[mid];
    rightArray[n - mid];
    // 将原数组按照中间索引分割为两个子数组
    for (i = 0; i < mid; i++) {
        leftArray[i] = arr[i];
    }
    for (i = mid; i < n; i++) {
        rightArray[i - mid] = arr[i];
    }
    // 递归调用归并排序函数对左半部分和右半部分进行排序
    MergeSort(leftArray, mid);
    MergeSort(rightArray, n - mid);
    // 合并排好序的左半部分和右半部分
    Merge(arr, leftArray, mid, rightArray, n - mid);
}
// 合并两个子数组的函数
Merge(arr, leftArray, leftSize, rightArray, rightSize) {
    i = 0; // leftArray的索引
    j = 0; // rightArray的索引
    k = 0; // arr的索引
    // 依次比较leftArray和rightArray中的元素，将较小的元素放入arr
    while (i < leftSize && j < rightSize) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }
    // 将leftArray中剩余的元素复制到arr中
    while (i < leftSize) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }
    // 将rightArray中剩余的元素复制到arr中
    while (j < rightSize) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

2. 优化算法设计

单目标优化算法和多目标优化算法是解决优化问题的两种不同方法。单目标优化算法旨在寻找一个最优解，使目标函数的值最小或最大化。这种算法只优化一个特定的目标函数，无论是最小化还是最大化。
常见的单目标优化算法包括：

梯度下降法（Gradient Descent）：通过计算目标函数的梯度来更新参数，以寻找目标函数的最优解。
遗传算法（Genetic Algorithm）：模拟自然进化的过程，通过选择、交叉和变异等操作来搜索最优解。
粒子群优化（Particle Swarm Optimization）：模拟鸟群寻找食物的行为，通过不断调整粒子的位置和速度来搜索最优解。
蚁群算法（Ant Colony Optimization）：模拟蚂蚁在搜索食物过程中释放信息素的行为，通过信息素的累积和挥发来搜索最优解。

而多目标优化算法则是在考虑多个目标函数的情况下寻找一组解，以形成一种称为“帕累托前沿”的解集合。这个解集合是在不利影响其他目标函数的情况下，无法再进一步改善任何目标的解。

常见的多目标优化算法包括：

NSGA-II（Non-Dominated Sorting Genetic Algorithm II）：通过非支配排序、拥挤度距离等指标来搜索帕累托前沿。
MOEA/D（Multi-Objective Evolutionary Algorithm based on Decomposition）：将多目标优化问题分解为多个子问题，并通过解的交叉和变异来搜索帕累托前沿。
SPEA2（Strength Pareto Evolutionary Algorithm 2）：利用解的支配关系和拥挤度距离来保持搜索空间的多样性，并搜索帕累托前沿。
MOPSO（Multi-Objective Particle Swarm Optimization）：将粒子群优化算法扩展到多目标优化问题，通过适应度值和轨迹的更新来搜索帕累托前沿。

这两种类型的优化算法在解决不同类型的问题时具有不同的优势和适应性。单目标优化算法适用于目标明确的问题，而多目标优化算法适用于需要平衡多个目标指标的问题。

3. 常见的深度学习模型及优缺点

常见的深度学习模型以及它们的优缺点如下：1. 卷积神经网络（Convolutional Neural Networks，CNN）：
- 优点：适用于图像和视频处理任务，具有自动提取特征的能力，能够处理平移不变性，参数共享可减少模型复杂度。
- 缺点：对于大规模数据和较复杂的图像结构，模型可能需要更多的时间和计算资源进行训练。

循环神经网络（Recurrent Neural Networks，RNN）：
- 优点：适用于序列数据处理任务，能够建模时序关系和上下文信息。
- 缺点：处理长期依赖关系时存在梯度消失和梯度爆炸问题，限制了其在长序列任务中的表现。
长短时记忆网络（Long Short-Term Memory，LSTM）：
- 优点：是RNN的一种改进，能够更好地处理长期依赖关系，避免梯度消失和梯度爆炸的问题。
- 缺点：相对于标准RNN，LSTM模型具有更多的参数，需要更多的计算资源和时间进行训练。
生成对抗网络（Generative Adversarial Networks，GAN）：
- 优点：通过生成器和判别器的对抗训练，能够生成逼真的样本，适用于图像、语音、文本生成等领域。
- 缺点：训练GAN需要较长的时间，且模型的训练过程不稳定，可能会出现模式崩溃和模式塌陷的问题。
转移学习（Transfer Learning）：
- 优点：能够利用在一个任务上学到的知识和参数来加速和改善在相关任务上的性能；减少对大量标注数据的需求。
- 缺点：对于两个任务之间差异较大的情况，转移学习效果可能会受到限制。

这些深度学习模型在不同的任务和领域中有着广泛的应用。每个模型都有其独特的优点和缺点，选择合适的模型要根据具体问题和数据情况。进一步了解每个模型的详细原理和实践指导，可以参考相关的学术论文、教材和在线资源。

4. 常见的分类器及其数学基础

常见的分类器及其对应的数学基础如下：

逻辑回归（Logistic Regression）：
- 数学基础：逻辑回归使用了逻辑函数（sigmoid函数），该函数将输入特征的线性组合映射到一个概率值（0到1之间）。通过最大似然估计或最小化损失函数的方式，在训练过程中优化模型参数。
支持向量机（Support Vector Machines，SVM）：
- 数学基础：SVM的核心思想是通过在高维空间中找到最优的分离超平面来进行分类。使用核函数将输入特征映射到高维空间，在此空间中寻找能够最大化正负样本间隔（间隔最大化）的超平面。
决策树（Decision Trees）：
- 数学基础：决策树算法使用基于信息增益、基尼系数等准则的分裂判定条件，通过对特征进行递归划分，构建一棵树形结构用于分类。决策树的划分过程通过计算特征的纯度来确定最佳划分。
随机森林（Random Forest）：
- 数学基础：随机森林是基于决策树的集成学习方法。它运用随机特征选择和随机样本抽样的技术，构建多个决策树，并通过投票或平均的方式进行分类预测。
朴素贝叶斯（Naive Bayes）：
- 数学基础：朴素贝叶斯分类器基于贝叶斯定理和特征之间的独立性假设。它通过计算样本在给定类别下的条件概率，并选择最大概率的类别作为预测结果。
K近邻算法（K-Nearest Neighbors，KNN）：
- 数学基础：KNN基于样本之间的距离进行分类。它计算测试样本与训练集中最近的k个样本的类别，并使用多数投票的方式确定测试样本的类别。

这些分类器都有其数学基础和算法原理，理解这些数学基础可以帮助我们更好地理解和使用这些模型。深入学习这些算法的数学基础将有助于对它们的工作原理和特点有更深入的理解。

5. 递归与非递归的转换

递归和非递归是两种不同的编程或问题解决方法。在递归中，问题被划分为较小的子问题，而在非递归中，问题通过迭代的方式解决。在某些情况下，递归可能更简洁和直观，而非递归则更高效。递归转换为非递归通常可以通过使用栈或队列来实现。以下是一种通用的递归与非递归转换的方法：

将递归函数中递归调用的参数和局部变量放入栈或队列中。
使用循环来模拟递归的执行过程。
在每次循环迭代中，从栈或队列中获取参数和局部变量。
将子问题的计算结果存储在需要的地方，以供后续的计算使用。
循环终止条件通常是栈或队列为空，即没有更多的子问题需要解决。

通过这种转换，可以将递归函数转换为非递归的迭代形式，从而实现递归调用的效果。

需要注意的是，并非所有的递归函数都可以简单地转换为非递归形式。有些复杂的递归问题可能需要其他的解决思路，例如动态规划或分治策略。

在实际编程中，递归和非递归的选择通常基于问题的复杂性、效率需求以及程序的可读性。递归可以使代码更简洁和易于理解，但在处理大规模问题时可能会导致栈溢出或效率低下。非递归则可以规避这些问题，但可能需要更多的代码和辅助数据结构。

因此，在将递归转换为非递归时，需要权衡使用递归或非递归的优缺点，并根据具体问题和应用场景做出合适的选择。

6. 优化，单目标与多目标评价函数设计

在机器学习和优化问题中，评价函数被用来衡量模型或优化算法的性能。评价函数分为单目标和多目标评价函数。单目标评价函数设计时，我们关注一个主要的目标或指标，并将其最大化或最小化。常见的单目标评价函数设计包括：

损失函数（Loss Function）：用于衡量模型在训练数据上的误差，例如均方误差（Mean Squared Error，MSE）或交叉熵（Cross-Entropy）损失函数。
准确率（Accuracy）：用于衡量分类模型在测试数据上的分类准确率。
R-Squared（R²）：用于衡量回归模型对目标变量的解释程度。
对数似然（Log-Likelihood）：用于衡量概率模型对观测数据的拟合程度。

多目标评价函数设计考虑到多个目标或指标，并通常涉及它们之间的权衡或折衷关系。常见的多目标评价函数设计方法包括：

加权函数法（Weighted Sum Method）：将每个目标函数乘以一个权重并求和，这种方法假定所有目标函数具有相同的重要性。
线性规划法（Linear Programming Method）：通过线性规划模型，将多个目标函数约束到一组可行解，选择满足优化目标的最优解。
Pareto前沿（Pareto Front）：Pareto前沿是指在多个目标函数之间没有一个可以在所有目标上优于其他解的解集。通过比较不同目标函数之间的权衡，找到Pareto前沿上的最优解。

在评价函数的设计过程中，需要考虑问题的特点、优化目标的关联性、数据的可用性等因素。重要的是根据具体问题和需求选择或设计适合的评价函数，并在优化过程中对其进行迭代和改进。

三，填空题（10分），选择题（20分）

1. 监督学习与无监督学习

监督学习和无监督学习是机器学习中两种基本的学习范式。监督学习是通过给定的输入数据和相应的标签或目标值来进行训练的。在监督学习中，我们知道要解决的问题以及正确的答案是什么，因此可以训练一个模型来学习输入与输出之间的映射关系。常见的监督学习任务包括分类（将实例分到不同的类别）和回归（预测数值型目标变量）。监督学习的训练过程通常包括构建模型、定义损失函数和使用优化算法来最小化损失函数。

无监督学习则是在没有标签或目标值的情况下学习数据的结构和模式。无监督学习的目标是发现数据中的隐藏结构或关系，或者对数据进行聚类或降维。常见的无监督学习任务包括聚类（将相似的实例分到一组）和降维（减少特征的数量或维度）。无监督学习的训练过程通常包括构建模型、定义相似度或距离度量，并使用算法来聚类、建模或降维数据。

监督学习和无监督学习在应用和方法上有所不同。监督学习通常需要有标注的数据和先验知识，可以用于训练和评估模型。而无监督学习不需要标签，只依赖于数据本身的统计特性或结构。因此，监督学习通常可以解决更具体和明确定义的问题，而无监督学习则更适用于探索性分析、数据预处理和特征抽取等任务。

在实际应用中，监督学习和无监督学习经常结合使用。例如，可以使用无监督学习进行数据降维，然后使用监督学习算法对降维后的数据进行分类。或者使用无监督学习进行聚类，然后使用监督学习将新的数据点分配到聚类中。这种结合使用可以提高模型的性能和处理的效率。

2. 背包问题

背包问题是一个经典的组合优化问题，涉及如何在给定容量的背包中选择一些物品，以使得它们的总价值最大化，同时保持其总重量不超过背包的容量。背包问题有两种常见的形式：0-1背包问题和分数背包问题。

0-1背包问题（0-1 Knapsack Problem）：在0-1背包问题中，每个物品要么完全放入背包，要么完全不放入背包。也就是说，每个物品的选择是二进制的（0或1）。问题的目标是选择一组物品，使得它们的总价值最大化，同时总重量不超过背包的容量。
分数背包问题（Fractional Knapsack Problem）：在分数背包问题中，每个物品可以选择放入背包的一部分。这意味着每个物品的选择是一个0到1之间的实数，表示放入的物品的比例。问题的目标是选择一组物品，使得它们的总价值最大化，同时总重量不超过背包的容量。

解决背包问题的常见方法是动态规划。动态规划算法通过构建一个二维表格，根据不同的物品和背包容量进行递推计算，最终得到最优解。对于0-1背包问题，动态规划算法可以使用一个表格来表示选择每个物品和不同背包容量下的最大总价值。而对于分数背包问题，动态规划算法可以使用一个表格来表示物品的单位价值和放入的比例，然后按照单位价值的降序选择物品。

此外，背包问题也可以通过贪心算法和回溯算法进行解决。贪心算法每次选择当前看起来最优的策略，而回溯算法则是通过尝试所有可能的组合来找到最优解。然而，贪心算法只适用于分数背包问题，对于0-1背包问题不一定能得到最优解，而回溯算法在背包容量较大时可能会有指数级的时间复杂度。

背包问题在组合优化和动态规划领域有广泛的应用，例如资源分配、作业调度和投资组合优化等。

3. 分支限界法

分支限界法是解决优化问题的一种算法策略，可以应用于背包问题等组合优化问题。它通过将问题分解为一系列子问题，并使用启发式的方式逐步搜索可能的解空间来找到最优解。具体而言，分支限界法首先确定一个上界（或下界），该上界表示问题的最优解的可能取值范围。然后，从问题的初始状态开始，生成一个候选解，并进行评估。根据评估的结果，可以进一步展开（分支）候选解空间，并对子问题进行求解。在求解子问题时，可能会应用剪枝操作，即通过某些规则或条件来判断某些子问题的解不会是最优解，从而避免继续搜索这些子问题。

分支限界法通过不断生成候选解、评估和分支的过程，在解空间中逐步收敛，直到找到问题的最优解或确定无解。因为每次扩展子问题时，分支限界法能够剪去一些明显不是最优解的子问题，所以它能够在搜索过程中减少搜索空间，提高求解速度。

在背包问题中，分支限界法可以根据当前背包的剩余容量和价值上界，选择一个物品进行添加或不添加，从而生成子问题，并计算出子问题的解空间。通过不断分支、评估和剪枝，可以逐步搜索可能的解空间，并找到最优解。

需要强调的是，实际应用中，分支限界法的性能高度依赖于剪枝条件的设置和启发式规则的选择。不同的问题可能需要设计不同的剪枝策略，以在搜索空间中更有效地寻找最优解。

4. 聚类算法（层次，密度，网格）

聚类算法是一类常用的无监督学习算法，用于将相似的数据样本分组成具有相似特征的簇。层次聚类、密度聚类和网格聚类是三种常见的聚类算法。

1. 层次聚类（Hierarchical Clustering）：层次聚类是一种基于树形结构的聚类方法，可分为自上而下的凝聚层次聚类和自下而上的分裂层次聚类。
  - 凝聚层次聚类从每个样本开始，逐步合并最相似的簇，直到所有样本都合并为一个簇。通过计算簇间的相似度来确定合并的次序。
  - 分裂层次聚类从一个包含所有样本的簇开始，逐步将簇分裂为更小的簇，直到每个样本成为一个独立簇。通过计算簇内的相似度来确定分裂的方式。
1. 密度聚类（Density-based Clustering）：密度聚类算法将簇定义为高密度区域中的数据点，并且将低密度区域的数据点视为噪声或边界点。
  - DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是最常用的密度聚类算法。它通过确定样本的密度和邻域关系来识别核心样本、邻域样本和噪声。
1. 网格聚类（Grid-based Clustering）：网格聚类算法将数据空间划分为规则的网格单元，并在每个单元中进行聚类。
  - STING（Statistical Information Grid）和CLIQUE（CLustering InQUEst）是两个常见的网格聚类算法，它们通过统计信息和关联规则来进行聚类。

这些聚类算法各有优劣，适用于不同的数据分布和应用场景。选择合适的聚类算法需要考虑数据的特征以及聚类目标。

5. A*算法

A算法是一种基于启发式搜索的路径规划算法，用于在图形或网络中找到最短路径。它通过评估每个节点的代价函数（启发式函数），结合节点的实际代价和启发式估计，来选择下一个要扩展的节点，以尽可能快地达到目标节点。具体而言，A算法在搜索过程中维护两个重要的值。第一个值是G值，表示从起始节点到当前节点的实际代价。第二个值是H值，即启发式函数估计的从当前节点到目标节点的代价。

A*算法的搜索过程可以概括为以下步骤：

创建一个优先级队列（通常使用最小堆），将起始节点加入队列，并将其G值设置为0。
从队列中选取代价最低的节点进行扩展，即选择F值（F = G + H）最小的节点。
对于选中的节点，计算其子节点的G值和H值，并将子节点加入队列。
重复步骤2和3，直到找到目标节点或队列为空。

A*算法的优势在于利用启发式函数的估计，可以在搜索过程中有针对性地选择扩展节点，从而减少搜索的时间和空间复杂度。它在解决路径规划等问题时表现出色，尤其在图形或网络较大的情况下。

需要注意的是，A算法的性能高度依赖于所选择的启发式函数。一个良好的启发式函数应该能够提供准确的估计值，以便A算法能够尽可能地接近最优解。但有时可能会存在启发式函数引起的误导，导致找到的路径并非最短路径。因此，在使用A*算法时，选择合适的启发式函数是非常重要的。

6. 哈希算法

哈希算法（Hashing）是一种将输入数据（称为“键”或“消息”）通过哈希函数转换为固定长度的输出值（称为哈希值或散列值）的算法。它主要用于数据的索引、加密、校验等应用。哈希算法的特点是将任意长度的输入数据转换为固定长度的哈希值。无论输入数据的大小如何，生成的哈希值长度是固定的。这个固定长度通常较短，例如32位或64位，使得哈希值占用的空间相对较小。此外，相同的输入数据将始终生成相同的哈希值，而不同的输入数据很难生成相同的哈希值（即哈希冲突的概率非常低）。

哈希算法具有以下几个重要的特性：

一致性：相同的输入将始终生成相同的哈希值。
定长输出：无论输入数据的大小如何，哈希值的长度是固定的。
高效性：计算哈希值的过程应该是高效的，不受输入数据大小的影响。
碰撞概率低：不同的输入数据生成相同哈希值的概率应该非常低。

哈希算法的应用非常广泛。其中一些主要应用包括：

数据索引：哈希算法可以将键映射到索引，以快速查找和访问数据。
数据校验：通过比较哈希值，可以验证数据的完整性，确保数据在传输或存储过程中没有被篡改。
加密和安全：哈希算法可用于对密码进行哈希，以存储和验证用户凭据，以及生成数字签名和消息认证码等安全功能。

常见的哈希算法包括MD5、SHA-1、SHA-256等，它们在不同的安全性和性能要求下被广泛使用。需要注意的是，随着计算能力的提升，一些传统的哈希算法可能会面临安全性问题，因此在使用时应根据具体需求选择适当的哈希算法。

7. 线性回归

线性回归是一种用于建立和预测连续数值输出的机器学习算法。它建立一个线性关系的数学模型，将输入特征与输出变量之间的关系建模为一个线性方程。具体来说，线性回归使用输入特征的线性组合来预测输出变量的值。对于简单线性回归，只有一个输入特征，模型的线性方程可以表示为：y = mx + b。其中，y是输出变量的预测值，x是输入特征的值，m是斜率（表示特征对输出变量的影响），b是截距（表示在输入特征为0时的预测输出值）。

线性回归的目标是找到最佳的斜率和截距值，使得模型预测的值与真实的输出值之间的差异最小化。这通常通过最小化平方误差来实现，即使得预测值和实际值的差的平方和最小。这一方法称为最小二乘法。

线性回归可用于以下场景：

数据分析和预测：通过对输入特征和输出变量之间的线性关系建模，可以预测未来的观测值，或分析变量之间的关系。
特征选择：线性回归可以用于评估每个特征对输出变量的影响，并选择对模型预测能力最有贡献的特征。
解释变量：线性回归可以提供每个特征的系数，这些系数表示了特征对输出变量的影响程度。

要训练线性回归模型，通常使用最小二乘法（例如正规方程）或优化算法（例如梯度下降法）来最小化预测值和实际值之间的差异。在训练完成后，可以使用模型进行预测，提供输入特征的值，即可得到输出变量的预测值。

线性回归是一种简单但强大的机器学习算法，它在各种领域和问题中都有广泛的应用，如经济学、社会科学、金融预测等。

8. 支持度与置信度计算

支持度（Support）和置信度（Confidence）是关联规则中常用的两个度量指标。支持度衡量的是一个关联规则在数据集中出现的频率，表示给定条件的事件发生的概率。它可以被定义为关联规则中同时出现的项集在数据集中出现的频率。支持度可以帮助我们找到频繁项集，即在数据集中经常同时出现的项集。

支持度的计算公式为：
Support(A→B) = P(A∪B)
其中，A和B分别表示关联规则的前项和后项。P(A∪B)表示同时包含A和B的事务的概率。

置信度衡量的是关联规则的准确性，即在前项出现的条件下，后项出现的概率。它可以被定义为给定前项的条件下同时出现的项集在数据集中出现的频率。置信度可以帮助我们评估关联规则的可靠性和相关性。

置信度的计算公式为：
Confidence(A→B) = P(B|A) = P(A∪B) / P(A)
其中，P(B|A)表示在前项A发生的条件下后项B发生的概率。P(A∪B)表示同时包含A和B的事务的概率，P(A)表示前项A出现的概率。

以购物篮分析为例，假设我们有一个超市的交易数据集，包含了许多购物篮的记录。我们想要计算一条关联规则 “牛奶→面包” 的支持度和置信度。

假设数据集中有100个购物篮，其中有50个购物篮同时包含了牛奶和面包，那么该关联规则的支持度为：
Support(牛奶→面包) = 50 / 100 = 0.5

假设有60个购物篮中有牛奶，其中有50个购物篮同时包含了牛奶和面包，那么该关联规则的置信度为：
Confidence(牛奶→面包) = 50 / 60 ≈ 0.83

支持度和置信度是关联规则中常用的度量指标，可用于评估关联规则的重要性和准确性。高支持度的规则表示在数据集中经常同时出现，而高置信度的规则表示在给定条件下具有较高的可靠性。

9. 数据清洗方法

数据清洗是数据预处理的重要步骤，目的是去除无效、错误或冗余的数据，使数据适合于后续的分析和建模。以下是一些常用的数据清洗方法：

处理缺失值：检测和处理数据中的缺失值是数据清洗的关键步骤。可以通过删除包含缺失值的行、使用默认值填充缺失值、通过插值方法填充缺失值或使用机器学习算法预测缺失值来处理缺失值。
处理重复值：检测和处理数据中的重复值是消除冗余数据的重要步骤。可以通过删除重复的行或使用合适的数据去重技术（如哈希算法、RemoveDuplicates函数等）来处理重复值。
异常值处理：检测和处理数据中的异常值可以避免它们对分析和建模的影响。可以使用统计方法（如3σ原则）或基于模型的方法（如聚类、回归等）来识别和处理异常值，可以选择删除、替换或使用插值方法进行异常值的处理。
数据类型转换：将数据转换为正确的数据类型有助于提高数据的一致性和可用性。例如，将文本字符串转换为数值类型、将日期时间转换为日期时间对象、将分类变量转换为数值编码等。
处理不一致的数据：数据可能存在不一致的情况，如大小写混用、拼写错误等。通过进行统一化，如转换为小写字母、使用拼写检查等，可以提高数据的一致性。
特殊字符处理：数据中可能存在特殊字符、符号或噪声，如不可打印字符、换行符等。可以使用正则表达式或字符串处理方法将这些特殊字符进行处理或删除。
数据格式统一：数据的格式应该一致，如日期格式、货币格式、单位格式等。可以使用日期函数、格式化方法或字符串操作来统一数据的格式。
处理不完整的数据：某些情况下，数据可能不完整，例如有些字段没有填写。可以根据领域知识，使用默认值或其他补全方式来填充不完整的数据。
特征标准化：在某些情况下，数据的特征可能具有不同的尺度或范围。通过标准化或归一化等方法，可以将所有的特征转换为相同的尺度，以便在后续的分析中比较和处理。

这些是常见的数据清洗方法，具体方法的选择取决于数据的特征和问题的需求。同时，进行数据清洗时，应该根据领域知识，理解数据背后的含义，并与数据的所有者和使用者进行充分的沟通和协商。

10. 常见数据决策算法

以下是一些常见的数据决策算法：

决策树（Decision Tree）：决策树是一种基于树状结构的分类和回归算法。它通过对数据集进行递归的二分划分，构建一棵树形结构来进行决策。决策树易于理解和解释，并且可以处理各种类型的数据。常用的决策树算法包括ID3、C4.5和CART等。
随机森林（Random Forest）：随机森林是一种集成学习算法，通过在训练集上训练多棵决策树并综合它们的预测结果来进行决策。每棵决策树由随机选择的特征子集进行训练，通过投票或平均的方式来得出最终的决策结果。随机森林具有较高的准确性和鲁棒性，并且对于大型数据集和高维数据有较好的适应性。
朴素贝叶斯（Naive Bayes）：朴素贝叶斯是一种基于贝叶斯定理的分类算法。它假设特征之间是独立的，并使用贝叶斯公式来计算给定特征的条件概率，从而进行分类。朴素贝叶斯算法具有简单快速、适用于高维数据和对缺失数据不敏感等优点。
逻辑回归（Logistic Regression）：逻辑回归是一种广义线性模型，用于解决二分类问题。它使用逻辑函数将输入特征映射到一个概率值，并根据概率值进行分类决策。逻辑回归具有可解释性强、训练和预测速度快的特点。
支持向量机（Support Vector Machines，SVM）：支持向量机是一种在高维空间中进行分类和回归的有监督学习算法。它通过找到一个最优的超平面（或者更一般地，一个最优的分割超平面）来进行分类。支持向量机具有对高维数据处理能力强、泛化能力好的特点。
K最近邻（K-Nearest Neighbors，KNN）：K最近邻是一种基于实例的分类算法，它根据与待分类实例最近的K个训练实例的标签进行决策。KNN可以处理多分类问题，并且对于训练数据分布不规则的情况也适用。
强化学习（Reinforcement Learning）：强化学习是一种机器学习方法，用于训练智能体从与环境的交互中学习如何做出决策。强化学习的目标是通过最大化累积奖励来找到最优的决策策略。

这些算法都是常见的数据决策算法，在不同的问题和数据集上可能具有不同的表现。选择适当的算法要根据具体的问题描述、数据特征以及算法的优缺点进行综合考虑。

11. 大数据特点

大数据的特点常常被总结为4V，即数据的体量（Volume）、多样性（Variety）、速度（Velocity）和价值（Value）。

体量（Volume）：体量指的是大数据的规模或大小。大数据通常以TB、PB甚至EB级别的数据量出现。与传统规模的数据相比，大数据的庞大体量需要使用特殊的技术和工具来存储、处理和分析。
多样性（Variety）：多样性指的是大数据的来源和形式的多样性。大数据来自各种不同的源头，例如结构化数据（如传统数据库中的表格数据）、半结构化数据（如XML文件、日志文件）和非结构化数据（如文本、图像、音视频等）。这种多样性要求在处理和分析大数据时具备处理不同格式和类型数据的能力。
速度（Velocity）：速度指的是大数据的生成和处理速度。大数据往往是实时或近实时产生的，例如社交媒体平台上的实时数据流、物联网设备产生的传感器数据等。这要求对大数据进行快速、及时的处理和分析，以便能够实时获取有用的信息和见解。
价值（Value）：价值指的是大数据中蕴含的潜在商业价值和洞察力。大数据分析的主要目标是从大量的数据中提取有价值的信息、发现新的趋势、预测未来的趋势，并为决策和创新提供支持。通过深入分析和挖掘大数据，可以发现隐藏在数据中的机会和价值。

这些4V特点使得大数据的处理和分析变得更加具有挑战性。企业和组织需要使用大数据技术和工具，如分布式计算、机器学习和人工智能等，来充分利用大数据的潜力，为业务决策和创新提供支持。

12. 稀疏与特征提取方法

稀疏性和特征提取是机器学习中处理高维数据和减少冗余的常用方法和技术。下面介绍一些常见的稀疏性处理和特征提取方法：稀疏性处理方法：

L1正则化（L1 Regularization）：通过在模型的损失函数中添加L1范数惩罚项，使得模型倾向于选择少数非零的特征，从而实现稀疏性。L1正则化可以应用于线性回归、逻辑回归等模型中。
L2正则化（L2 Regularization）：与L1正则化类似，但L2正则化倾向于让特征的系数趋近于零而非完全等于零。L2正则化一般通过在损失函数中添加L2范数惩罚项实现，能有效降低特征的权重，实现稀疏性。
Elastic Net：Elastic Net是L1正则化和L2正则化的组合，既能够选择重要的特征，也能够对特征进行缩减，同时兼顾了L1和L2正则化的优点。
基于树模型的特征选择：通过决策树、随机森林等树模型，可以计算特征的重要性，然后选择重要特征。树模型中的特征重要性可以通过基尼系数、信息熵等指标进行衡量。

特征提取方法：

主成分分析（Principal Component Analysis，PCA）：PCA是一种常用的降维方法，能够将高维数据转换为低维空间的主成分。主成分是原始特征的线性组合，能够尽可能保留原始数据的信息。
线性判别分析（Linear Discriminant Analysis，LDA）：LDA是一种有监督的线性降维方法，旨在最大化类内散度同时最小化类间散度。LDA能够保持不同类别之间的分离性，有助于提取重要特征。
非负矩阵分解（Non-negative Matrix Factorization，NMF）：NMF是一种无监督的特征提取方法，将非负矩阵分解为两个非负矩阵的乘积。NMF能够提取数据的隐含结构，对于非负数据和文本数据等有较好的效果。
字典学习（Dictionary Learning）：通过学习数据的字典（稀疏表示）和对应的编码，可以提取具有判别性的特征表示。字典学习可以通过迭代优化的方式来学习数据的字典和编码矩阵。

这些方法和技术根据不同问题和数据类型的特点，可以选择合适的稀疏性处理和特征提取方法来优化模型性能。在实际应用中，也可以根据具体情况选择多种方法的组合，以达到更好的效果。

13. 最短路径问题

老师PPT**Dijkstra算法
当所有 wij ≥0 时，本算法是用来求给定点vs到任一个点vj 最短路的公认的最好方法。
事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到 vi的最短路。
最短路的子路也是最短路。

Ford算法

Floyd算法**

14. 回溯

回溯（Backtracking）是一种常用的算法技巧，特别适用于解决组合优化问题、搜索问题和满足约束条件的问题。回溯算法通过递归的方式，尝试在问题的解空间中搜索所有可能的解，并在搜索的过程中根据问题的约束条件进行剪枝，减少无效的搜索路径，从而找到问题的解。回溯算法的一般步骤如下：

定义问题的状态：将问题的解表示为一个状态或状态集合。
定义状态转移函数：根据问题的约束条件，定义状态转移函数，表示在当前状态下，如何转移到下一个状态。
定义终止条件：根据问题的要求定义终止条件，当满足终止条件时，得到问题的一个解或最优解。
进行回溯搜索：在当前状态下，按照状态转移函数生成下一个状态，并进行剪枝操作来减少无效的搜索路径。然后，递归地对下一个状态进行搜索，直到满足终止条件。

回溯算法的关键在于状态的回退。当搜索到某个状态时，如果发现该状态不满足问题的约束条件，或者已经搜索过该状态，就需要回退到之前的状态，并继续搜索其他可能的路径。通过不断地回退和探索，最终可以找到问题的解或最优解。

回溯算法的时间复杂度通常很高，因为它需要搜索整个状态空间。为了提高算法的效率，可以采用一些优化技巧，例如剪枝操作、启发式搜索、动态规划等。

回溯算法在很多经典问题中都有应用，比如八皇后问题、0/1背包问题、图的哈密顿回路等。对于具体的问题，需要根据其特点来设计相应的状态表示和状态转移函数，并合理选择回溯的搜索策略。

15. 属性量纲转换

属性量纲转换是指将具有不同量纲（单位）的属性进行转换，使它们具有相同的量纲。这是在机器学习和数据分析中常用的一项预处理技术，用于处理具有不同度量单位的属性或特征值，以确保它们在模型训练过程中能够被正确处理。常见的属性量纲转换方法包括：

标准化（Standardization）：
标准化是将属性数据转换为均值为0、方差为1的标准正态分布。具体而言，对于每个属性，通过减去属性的均值，然后除以属性的标准差，可以实现标准化。标准化能够消除不同属性之间的量纲差异，使得属性具有可比性。
归一化（Normalization）：
归一化是将属性数据缩放到一个固定的范围，通常是0到1之间。归一化方法常用的有最大最小归一化和Z-Score归一化两种。最大最小归一化将属性值映射到指定的最小值和最大值之间，Z-Score归一化则将属性值转换为符合标准正态分布的形式，使得均值为0、方差为1。
对数转换（Log Transformation）：
对数转换是一种常用的非线性转换方法，特别适合用于处理偏态分布的数据。对数转换通过取属性值的对数来减小数据中的极端值，使得数据更符合正态分布。对数转换可以应用于属性的原始值，也可以应用于标准化或归一化后的值。
区间缩放（Scaling）：
区间缩放是将属性数据按比例缩放到一个区间，通常是[-1, 1]或[0, 1]区间。区间缩放可以通过简单的线性变换来实现，即对属性值进行线性映射。

属性量纲转换的选择应该根据数据的分布特征和预测模型的要求来确定。一般来说，线性模型（如线性回归、逻辑回归）对于标准化或归一化后的数据比较敏感，而树模型（如决策树、随机森林）对于原始数据或区间缩放后的数据更为适应。因此，在进行属性量纲转换时需要仔细考虑数据的性质和所使用算法的要求，以获得更好的模型性能。

期末复习简易版