Week 1 An Introduction to Machine Learning(Part A)
摘要：
机器学习是一种从数据中提取模式并用于预测的目标值的方法。它通过分析输入属性与目标变量之间的关系来构建预测模型，并利用此模型对未知数据进行预测。
在构建预测模型的过程中，有监督学习（如线性回归）利用标签数据进行训练，而无监督学习则通过聚类等方式探索数据结构。训练集用于训练模型，而测试集用于评估其泛化能力。欠拟合指模型过于简单导致低性能，在测试集中表现不佳；过拟合则因复杂度过高导致在训练集中表现良好但在测试集中表现差。解决过拟合的方法包括增加正则化或减少特征数量。
选择合适的统计模型需使用交叉验证评估性能，并平衡偏差与方差的 trade-off。不同的评估指标如 RMSE 可用于衡量 K-Nearest Neighbors (KNN) 分类器的表现。
KNN 算法基于距离计算邻居投票结果进行预测，在低维空间表现优异但计算复杂度较高且受异常值影响较大。其核心在于计算样本间的距离并根据邻居类别进行决策。
总结而言，机器学习过程涉及从训练集中提取模式并构建泛化的预测函数；关键概念包括参数设置、泛化能力及避免过拟合或欠拟合；统计建模的选择需通过交叉验证和性能评估来优化结果。
目录
一、什么是机器学习
二、如何学习形成一个模型
三、如何选择一个好的模型
四、K-Nearest Neighbors (KNN) classifier（Tutorial内容）
五、总结
一、什么是机器学习
过程：建立一组属性（通过预处理可获得的一组输入变量）与响应或目标变量之间的映射关系。
改写说明
2、目的：
（1）预测：预测属性变量的任何（可能是新的）值的目标/响应值
（2）推理：理解目标变量随着输入变量的变化而受到影响的方式
3. 机器学习的模型：
（1）线性模型：
（2）非线性模型（多项式模型）
3、重要参数
（1）训练集
（2）测试集
（3）泛化性：评估模型在面对与训练数据存在差异的新样本时的表现能力；构建一个能够有效推广到未曾见过的数据实例的预测系统。
4、有监督学习和无监督学习
(1) 有监督学习：在训练集中，给定对应输入变量的目标变量（lable值给定）
无监督学习：基于所给定的数据集仅提供输入变量的信息。其典型的方法包括聚类和可视化（Clustering or visualization）。
5、回归和分类（Regression and Classification）
（1）回归：目标变量是实值且连续的
（2）分类：目标变量是有限数量的离散类别
6、为未来使用生成模型所需的关键活动
二、如何学习形成一个模型
1、遇到的困难：
（1）需要从有限的数据集中进行泛化；
（2）观察到的（或训练的）数据被噪声破坏：因为有不确定性的存在。
2、模型的类型：
（1)无参模型：参数的数量可以增长为训练集的大小增加（例如 KNN 分类器）
（2）有参模型：无论大小如何，参数都是固定的训练集（例如线性回归）
3、一个多项式模型的例子：
W为多项式的系数向量， M决定了模型的复杂度：
如何确定W：（W能最小化目标值二号预测值之间的误差 ）
对E(W)的多项表达式关于w求偏导数，再令它为0即可求得w：
误差函数：
4、欠拟合和过拟合的情况以及解决方法：
在机器学习中，欠拟合问题通常表现为模型在训练集和测试集上的均方误差（MSE）显著较高。具体而言，在实际最优模型为X²形式时（即非线性关系），若选用X¹形式的线性模型进行拟合，则容易导致欠拟合现象的发生。这表明，在所有其他条件相同的情况下，选择一个过于简单的模型（如线性关系）来拟合本应是非线性的数据分布时，更容易出现欠拟合问题。换言之，在这种情况下无论是训练数据还是测试数据所得到的准确率都会显著较低。
下面这个一般是M太小导致函数太简单而欠拟合
(2) 过拟合：该模型在训练数据集上的均方误差极低，在测试数据集上的均方误差显著提高。当最优拟合曲线由X平方确定时，若所选曲线为X立方或其他更高阶多项式，则容易出现这一现象。这表明随着所选模型复杂度的增加，越易导致过拟合现象。即该模型在训练数据集上的预测精度较高，在独立测试数据集上的表现则明显下降。
下面这个一般是M太大导致函数太复杂而过拟合。
如何解决过拟合问题：增加训练集的size
（3）偏差与方差（bais and variance）
偏差：所选模型与最优模型之间的差距程度（绝对值）被定义为偏差量度，在量化分析中用于衡量我们的建模效果。具体而言：
- 该量度用于衡量我们的模型是否接近最优模型以及两者之间的接近程度。
- 当偏差越大时（即差距程度越高），越容易出现欠拟合现象。
方差是指系统输出结果与真实数据之间的偏离程度越高，则该系统预测结果与最优模型之间的差异即为方差；当该系统的预测误差数值越大时，则该系统出现过拟合现象的可能性随之增加。
(4)偏差与方差的解决办法
- 偏差比较大，则欠拟合。
解决办法：
a、增加特征数据提高拟合程度，避免欠拟合。
b、增加模型的复杂度（增加M的值）提高拟合程度，避免欠拟合。
c、尝试获得更多的特征
d、尝试增加多项式特征（与b差不多）
e、尝试减少正则化程度
- 方差比较大，则过拟合。
解决办法：
通过引入大量数据尤其是大数据资源的应用来优化系统性能，在提升模型在大数据环境下的预测效果的同时有效降低了模型的复杂性并成功避免了过拟合问题与第（2）条所述的方法具有相似性
b、引入正则项（Regularization），计算关于权重参数w的损失函数及其最小值；当权重参数w较小时；能够更好地实现对数据的拟合。
c、尝试减少特征的数量
λ是一个正则化参数，在实际应用中需要通过调参来确定其最优取值。当λ较大时，在损失函数中加入较大的惩罚项pen(w)，从而使得损失函数E(λ)的整体表现发生变化。具体而言，在这种情况下：
（1）模型趋于简单，
（2）训练误差与测试误差均显著上升（出现欠拟合现象）；
而当λ较小时：
（1）模型趋于复杂，
（2）训练误差接近于零，
（3）性能表现优异；
但与此同时，
测试误差接近于一，
导致性能严重下降（出现过拟合现象）。需要注意的是，
随着λ值的增大，
尽管模型变得更为简单，
然而其训练误差与测试误差都会随之上升，
最终导致欠拟合问题。
因此建议选择一个平衡点：
即选取适当的λ值，
使模型既不会出现欠拟合现象，
也不会导致过拟合问题。
通过链接中的链接评估模型泛化能力（其中采用均方根误差作为衡量预测偏差的标准）
三、如何选择一个好的模型
过程：
（1）一种特殊的K-Fold交叉验证实现，在这种情况下子集中包含的数据样本数量等于整个训练集的数量。
（2）在每次迭代过程中，在当前迭代中将一个训练数据点单独分离出来构成独立的验证集，并将剩下的所有样本均用于模型的训练。
（3）循环执行上述步骤共K次，并确保每个样本在各次循环中的验证阶段仅被使用一次。
补充:什么是K重交叉折叠验证（K-Fold cross-validation ）
（1）数据集划分为K个相同大小的互斥子集；
（2）通过分层抽样K个子集保持分布一致性；
（3）K次评估结果的均值，每次用K-1个集合训练，剩下的一个做模型评估。
例子代码实现：
上述例子中共有10个样本，在进行五折交叉验证时对测试集索引进行了查看。所有样本集的并即构成整个样本集合，在每次循环中将其中一个样本作为训练数据、剩余两个作为测试数据使用；然后基于这五组训练-测试划分方案评估模型性能，并计算其平均表现以获得最终结果。
四、K-Nearest Neighbors (KNN) classifier（Tutorial内容 ）
1、KNN中计算距离的方式
（1）欧式距离：（Euclidean仅对连续变量有效）
（2）麦哈顿距离：(Manhattan仅对连续变量有效)
（3）Minkowski距离：仅对连续变量有效
（4）汉明距离(Hamming)：在分类实例中应用该方法具有必要性。当数据集包含数值型和分类型变量时，则需考虑对数值型特征进行归一化处理的问题。
2、K-近邻（KNN）算法的工作流程如下所述：
首先，在计算阶段（step 1），我们度量待分类样本与训练样本集中各个样本之间的欧氏距离；
随后，在选择邻居阶段（step 2），我们确定参数K，并选取与待分类样本距离最近的前K个训练样本；
接着，在投票统计阶段（step 3），我们汇总各邻居对应的类别标签；
最后，在分类决策阶段（step 4），我们将待分类样本归类至得票最高的类别中。
3、KNN算法的时间复杂度
传统的搜索方法需要对全部的数据集进行遍历并评估每个数据点之间的距离,其时间复杂度为O(dN),其中d代表输入样本x的空间维度;
在某些情况下, 通过预处理数据并仅对所需部分进行搜索, 使用k-d树等更为智能的数据存储方式通常会带来显著提升, 并使运行时间达到O(d \log N)水平.
4、KNN算法的模型复杂度
如果所建的模型具有低偏差（bais）和高方差（variance），则该机器学习模型被定义为拥有较高的复杂度。
（1）高偏差和低方差 = 欠拟合模型
（2） 低偏差和高方差 = 过拟合模型（高度复杂的模型）
（3） 低偏差和低方差 = 最佳拟合模型（最佳模型）
（4）训练集上的高准确率与测试集上的低准确率（与基于样例的评估标准相比）= 模型的泛化能力较低= 复杂且过度拟合的模型 = 表明模型具有较高的复杂度。
（5）低训练准确率和低测试准确率（超出样本精度）=高偏差=欠拟合模型
5、KNN算法的优缺点
优点：
（1）算法简单直观，易于应用于回归及多分类任务
（2）该方法不受数据分布假设的限制，并且具有较高的准确率，在处理异常点时展现出较强的鲁棒性
（3）由此可知该方法特别适用于处理具有类别交叉或呈非线性不可分特征的数据集；其核心在于仅依赖周围有限数量的邻近样本进行分类判断而不使用判别类域的方法来判定归属类别。
缺点：
该算法在处理大规模数据时表现出较高的计算复杂度。值得注意的是，在数据规模和属性维度显著提升的情况下（尤其是构建这些数据结构时），该方法的内存占用率也会显著提高
（2）主要依赖于较少的k相邻样本，在样本分布失衡的情况下，稀有类别的预测准确性较低。
（3）采用懒散学习策略，在预测阶段相较于像逻辑回归这样的算法而言速度较慢。当需要进行分类任务时，则需即时完成计算处理。为了确定待分类样本应归属至哪一类别，在训练数据集的基础上需逐一计算其与所有训练样本之间的相似程度，并依据最接近的K个训练样本来进行分类决策
（4）相较于其他方法而言，在考虑不同特征重要性这一点上，KNN并未采取特别措施；每个经过归一化的特征对结果的影响均一致。
（5）相比决策树、逻辑回归模型，KNN模型可解释性弱一些
（6）差异性小，不太适合KNN集成进一步提高性能。
6、KNN算法实现的主要代码（R语言）
投票函数（Majority Vote）：
# define an auxiliary function that calculates the majority votes (or mode!)
majority <- function(x) {
uniqx <- unique(x)
uniqx[which.max(tabulate(match(x, uniqx)))]#统计出现次数最多的lable为最终的预测值
}KNN Classifier：
# KNN function (distance should be one of euclidean, maximum, manhattan, canberra, binary or minkowski)
knn <- function(train.data, train.label, test.data, K=3, distance = 'euclidean'){#采用欧式距离
## count number of train samples
train.len <- nrow(train.data)
## count number of test samples
test.len <- nrow(test.data)
## calculate distances between samples
dist <- as.matrix(dist(rbind(test.data, train.data), method= distance))[1:test.len, (test.len+1):(test.len+train.len)]
## for each test sample...
for (i in 1:test.len){
### ...find its K nearest neighbours from training sampels...
nn <- as.data.frame(sort(dist[i,], index.return = TRUE))[1:K,2]
###... and calculate the predicted labels according to the majority vote
test.label[i]<- (majority(train.label[nn]))
}
## return the class labels as output
return (test.label)
}针对下图有如下的问题：
（1）随着𝐾的增加，KNN分类器的复杂度是增加还是减少？
当K较小时（如K=1），模型的复杂度较高（即模型的容量较大），此时虽然能够显著降低训练误差（因为每个测试样本都能找到最近的邻居来进行预测），但泛化能力随之下降（因为模型过于依赖于有限数量的邻近样本）。相反地，在这种情况下（即当k=1时），算法可能会受到异常或噪声样本的影响（例如图中所示的情况），导致决策边界的位置就会受到影响，并且容易出现过拟合现象：即尽管在某些特定位置上能够获得较高的准确性（如图中所示情况），但整体表现会受到噪声数据的影响而变得不稳定）。在这种情况下（即当k较大时），虽然训练误差可能会有所增加（因为每个测试样本需要考虑更多邻近区域内的信息），但泛化能力却能够得到一定程度的提升：这是因为算法会综合考虑更多不同类别的信息来做出决策。然而，在实际应用中选择合适的k值是一个关键问题：常用的方法是通过网格搜索配合交叉验证来找到一个既能有效减少偏差又不会导致显著增加方差的最佳平衡点。
假设在以下条件下：
\log\left(\frac{1}{K}\right) > -1.35
当上述不等式成立时，在自变量\log\left(\frac{1}{K}\right)增加的过程中（即K值降低到某个程度），对应的\text{training error}会随之减小。
第三部分探讨了参数K^{-1}与测试误差之间的关联。
若log(1/k)值大于-1.35，则随着该值的增加（对应k值减小），testing error值也随之上升。
（4）在KNN分类器复杂性提升的情况下，请阐述训练误差与测试误差变化趋势间的差异。
当K值逐渐减小时，模型的复杂性会增加；同时，在 \log(1/K) 数值上也会随之上升；这种情况下(training error trends)趋向于减小而(testing error trends)则会上升；最终会导致模型出现过拟合现象。（5）请指出模型处于过拟合与欠拟合区域的具体范围，并确定最佳K值是多少？
当取值为左侧区域时（即此时k值较大），模型具有较低的复杂度，并可能导致欠拟合现象发生。
随着log(1/k)值的增大（尤其是当k值较小时），模型具有较高的复杂度，并容易导致过拟合现象。
当training and testing两个图相交时即log(1/k) = -1.4的时候，拟合刚好。
五、总结
机器学习的过程是如何进行的？它是通过训练数据集建立输入属性与目标值之间的映射关系模型，并利用该模型对未知数据进行目标值预测。
机器学习的核心内容包括哪些方面？主要涉及数学基础、算法设计以及数据特征分析与模式识别等关键领域。
(1) 必须设定模型的参数。（2）必须使模型适应训练的目标，并优化其与真实目标值之间的误差函数。（3）在防止过拟合的同时,需注意多个因素包括训练顺序(M值)以及正则化系数(λ值)。
3、如何选择好的统计模型？
(1)使用K重折叠交叉验证
(2)测量训练误差和测试误差