网网站站建建站站,自已做网站,教育局门户网站建设目的,双云官方网站目录
1.层次分析法#xff08;结合某些属性及个人倾向#xff0c;做出某种决定#xff09;
1.1 粗浅理解 1.2 算法过程
1.2.1 构造判断矩阵
1.2.2 计算权重向量
1.2.3 计算最大特征根
1.2.4 计算C.I.值 1.2.5 求解C.R.值 1.2.6 判断一致性
1.2.7 计算总得分
2 神经网…目录
1.层次分析法结合某些属性及个人倾向做出某种决定
1.1 粗浅理解 1.2 算法过程
1.2.1 构造判断矩阵
1.2.2 计算权重向量
1.2.3 计算最大特征根
1.2.4 计算C.I.值 1.2.5 求解C.R.值 1.2.6 判断一致性
1.2.7 计算总得分
2 神经网络正向流通反向反馈调整系数预测结果
2.1 粗浅理解
2.2 算法过程
2.2.1 划分数据集
2.2.2 前向传播及反向调整系数利用梯度下降法
编辑 编辑 3 决策树通过若干属性并进行合理排序最快做出分类
3.1 粗浅理解
3.2 算法过程
3.2.1 随机分配属性顺序计算熵值
3.2.2 条件熵的计算
3.2.3 根据不同的评选方法得出最优决策树
3.2.4 连续值处理
3.2.5 剪枝处理
3.2.6 补充K折交叉验证
3.2.7 补充过拟合和欠拟合
4 拟合与插值回归预测
5 时间序列预测体现时间连续性
5.1 粗浅理解
5.2 常见方法
5.2.1 朴素预测法Naive Forecast)
5.2.2 简单平均法(Simple Average
5.3.3 移动平均法(Moving Average
5.2.4 加权移动平均(Weighted Moving Average)
5.2.5 简单指数平滑法 (Simple Exponential Smoothing)
5.2.6 霍尔特线性趋势法
5.2.7 Holt-Winters方法三次指数平滑
6 K-MeansK-均值聚类算法无需分割数据即可分类
6.1 粗浅理解
6.2 算法过程
6.2.1 选定质心
6.2.2 分配点
6.2.3 评价
7 KNN算法K近邻算法
7.1 粗浅理解
7.2 有关距离的介绍
7.2.1 欧氏距离(Euclidean Distance)
7.2.2 曼哈顿距离(Manhattan Distance)
7.2.3 切比雪夫距离 (Chebyshev Distance)
7.2.4 闵可夫斯基距离(Minkowski Distance)
7.2.5 “连续属性”和“离散属性”的距离计算
7.3 算法过程 1.层次分析法结合某些属性及个人倾向做出某种决定
1.1 粗浅理解
举一个例子我们想选择一个旅游地对于不用的旅游地有不同属性而且我们对于不同的属性也有不同的倾向比如旅游地有景点和旅途两个属性每个旅游地的属性好坏不同而且我们可能在选择旅游地时更倾向于景点或旅途这样得出的决策就会更符合自身实际 层次分析法就是将一个决策事件分解为目标层例如选择旅游地准则层影响决策的因素例如景点、旅途等以及方案层指的是方案例如去某地旅游
层次分析法大致有如下过程 1.2 算法过程
1.2.1 构造判断矩阵
构造判断矩阵就是通过各要素之间相互两两比较并确定各准则层对目标层的权重。
简单地说就是把准则层的指标进行两两判断通常我们使用Santy的1-9标度方法给出。 初始表格如下每个属性对于自身的重要性为1 如果我们认为属性2比属性1明显重要那么 以此类推当我们填完这个表格判断矩阵A就构造出来了
1.2.2 计算权重向量
简单来说就是将判断矩阵A的列向量归一化然后求行和得出矩阵后再归一化这时我们得到一个n行1列的权重向量矩阵W
1.2.3 计算最大特征根
根据公式 1.2.4 计算C.I.值
根据公式 1.2.5 求解C.R.值
根据公式 其中R.I.值我们可以查表得知 1.2.6 判断一致性
C.R.0.1 时表明判断矩阵 A 的一致性程度被认为在容许的范围内此时可用 A 的特征向量开展权向量计算若 C.R.≥0.1, 说明我们在构建判断矩阵时出现了逻辑错误这个时候我们需要对判断矩阵 A 进行修正。
1.2.7 计算总得分
利用权重及得分矩阵来计算最后得分最高的即为决策方案
2 神经网络正向流通反向反馈调整系数预测结果
2.1 粗浅理解 设计一个神经网络时输入层与输出层的节点数往往是固定的中间层则可以自由指定神经网络结构图中的拓扑与箭头代表着预测过程时数据的流向跟训练时的数据流有一定的区别结构图里的关键不是圆圈代表“神经元”而是连接线代表“神经元”之间的连接。每个连接线对应一个不同的权重其值称为权值这是需要训练得到的。 大致过程
2.2 算法过程
2.2.1 划分数据集
大部分用来做训练集训练模型小部分用来做验证集和测试集证明模型的完备性可以没有验证集只不过准确度会稍差一点
2.2.2 前向传播及反向调整系数利用梯度下降法 注这里的S函数是激活函数 3 决策树通过若干属性并进行合理排序最快做出分类
3.1 粗浅理解
决策树Decision Tree是一种分类和回归方法是基于各种情况发生的所需条件构成决策树以实现期望最大化的一种图解法。由于这种决策分支画成图形很像一棵树的枝干故称决策树。它的运行机制非常通俗易懂因此被誉为机器学习中最“友好”的算法。下面通过一个简单的例子来阐述它的执行流程。假设根据大量数据含 3 个指标天气、温度、风速构建了一棵“可预测学校会不会举办运动会”的决策树如下图所示。 接下来当我们拿到某个数据时就能做出对应预测。
在对任意数据进行预测时都需要从决策树的根结点开始一步步走到叶子结点执行决策的过程。如对下表中的第一条数据 [ 阴天寒冷强 ] 首先从根结点出发判断 “天气” 取值而该数据的 “天气” 属性取值为 “阴天”从决策树可知此时可直接输出决策结果为 “举行”。这时无论其他属性取值为什么都不需要再执行任何决策类似于 “短路” 现象。 决策树的组成 决策树由结点和有向边组成。结点有两种类型内部结点圆和叶结点矩形。其中内部结点表示一个特征属性叶结点表示一个类别。而有向边则对应其所属内部结点的可选项属性的取值范围。 在用决策树进行分类时首先从根结点出发对实例在该结点的对应属性进行测试接着会根据测试结果将实例分配到其子结点然后在子结点继续执行这一流程如此递归地对实例进行测试并分配直至到达叶结点最终该实例将被分类到叶结点所指示的结果中。
但是对于每一个属性做出决定的先后顺序没有进行解释
3.2 算法过程
3.2.1 随机分配属性顺序计算熵值
构建决策树的实质是对特征进行层次选择而衡量特征选择的合理性指标则是熵。为便于说明下面先给出熵的定义设 是取值在有限范围内的一个离散随机变量其概率密度为 3.2.2 条件熵的计算
根据熵的定义在构建决策树时我们可采用一种很简单的思路来进行“熵减”每当要选出一个内部结点时考虑样本中的所有“尚未被使用”特征并基于该特征的取值对样本数据进行划分。即有 对于每个特征都可以算出“该特征各项取值对运动会举办与否”的影响而衡量各特征谁最合适的准则即是熵。为此引入条件熵。
我们将“天气”特征展开以分别求解各取值对应集合的熵。实际上该式的计算正是在求条件熵。条件熵 ( | ) 表示在已知随机变量 的条件下随机变量 的不确定性。它的数学定义是若设随机变量 (, ) 其联合概率密度为 则定义条件熵 ( | ) 在给定 的条件下 的条件概率分布对 的数学期望即 3.2.3 根据不同的评选方法得出最优决策树
1、信息增益 ID3 算法选用的评估标准
信息增益 (, ) 表示某特征 使得数据集 的不确定性减少程度定义为集合 的熵与在给定特征 的条件下 的条件熵 ( | ) 之差即 2、信息增益率 C4.5 算法选用的评估标准 以信息增益作为划分数据集的特征时其偏向于选择取值较多的特征。比如当在学校举办运动会的历史数据中加入一个新特征 “编号” 时该特征将成为最优特征。因为给定 “编号” 就一定知道那天是否举行过运动会因此 “编号” 的信息增益很高。
但实际我们知道“编号” 对于类别的划分并没有实际意义。故此引入信息增益率。
信息增益率 (, ) 定义为其信息增益 (, ) 与数据集 在特征 上值的熵 () 之比即 3、基尼系数 CART 算法选用的评估标准 从前面的讨论不难看出无论是 ID3 还是 C4.5 都是基于信息论的熵模型出发而得均涉及了大量对数运算。能不能简化模型同时又不至于完全丢失熵模型的优点呢分类回归树Classification and Regression TreeCART便是答案它通过使用基尼系数来代替信息增益率从而避免复杂的对数运算。基尼系数代表了模型的不纯度基尼系数越小则不纯度越低特征越好。注这一点和信息增益率恰好相反。
在分类问题中假设有 个类别且第 个类别的概率为 则基尼系数为 对于给定数据集 假设有 个类别且第 个类别的数量为 则该数据集的基尼系数为 由于基尼系数 () 表示集合 的不确定性则基尼系数 (, ) 表示 “基于指定特征 进行划分后集合 的不确定性”。该值越大就表示数据集 的不确定性越大也就说明以该特征 进行划分越容易分乱。
4、基尼增益
同信息增益一样如果将数据集 的基尼系数减去数据集 根据特征 进行划分后得到的基尼系数 就得到基尼增益系数。显然采用越好的特征进行划分得到的基尼增益也越大。基于前面各特征对数据集的划分可得到其对应的基尼增益。
步骤一先算出初始数据集合 D 的基尼系数
步骤二计算基尼系数计算基尼增益率 可见基尼增益在处理诸如 “编号” 这一类特征时仍然会认为其是最优特征此时可采取类似信息增益率的方式选用基尼增益率 。但对常规特征而言其评估的合理性还是较优的。
5、基尼增益率
基尼增益率 (, ) 定义为其尼基增益 (, ) 与数据集 在特征 上的取值个数之比即 容易看出基尼增益率考虑了特征本身的基尼系数此时当某特征取值类别较多时 (, ) 式中的分母也会增大从而降低了 “偏向取值较多的特征” 这一影响。
从上面的结果可以看出基尼增益率能明显降低取值较多的特征偏好现象从而更合理地评估各特征在划分数据集时取得的效果。
3.2.4 连续值处理
在前面的数据集中各项特征以及标签均为离散型数据但有时处理的数据对象可能会含有连续性数值为了解决这一问题我们可以对数据进行离散化处理。此时可把连续取值的数据值域划分为多个区间并将每个区间视为该特征的一个取值如此就完成了从连续性数据到离散性数据的转变。
对于一些有意义的连续值我们可以通过实际情况来进行划分归类比如温度 对于一些无意义的连续值
626572868996102116118120125169187211218 3.2.5 剪枝处理
对于决策树而言当你不断向下划分以构建一棵足够大的决策树时直到所有叶子结点熵值均为 0理论上就能将近乎所有数据全部区分开。所以决策树的过拟合风险非常大。为此需要对其进行剪枝处理。
常用的剪枝策略主要有两个
预剪枝构建决策树的同时进行剪枝处理更常用 后剪枝构建决策树后再进行剪枝处理。 预剪枝策略可以通过限制树的深度、叶子结点个数、叶子结点含样本数以及信息增量来完成。
这里只讨论预剪枝
1、限制决策树的深度
下图展示了通过限制树的深度以防止决策树出现过拟合风险的情况。 2、限制决策树中叶子结点的个数
下图展示了通过限制决策树中叶子结点的个数以防止决策树出现过拟合风险的情况。 3、限制决策树中叶子结点包含的样本个数
下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。 4、限制决策树的最低信息增益
下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。
3.2.6 补充K折交叉验证 交叉验证是在机器学习建立模型和验证模型参数时常用的办法一般被用于评估一个机器学习模型的表现。更多的情况下我们也用交叉验证来进行模型选择(model selection)。 交叉验证顾名思义就是重复的使用数据把得到的样本数据进行切分组合为不同的训练集和测试集用训练集来训练模型用测试集来评估模型预测的好坏。在此基础上可以得到多组不同的训练集和测试集某次训练集中的某样本在下次可能成为测试集中的样本即所谓“交叉”。 那么什么时候才需要交叉验证呢交叉验证用在数据不是很充足的时候。如果数据样本量小于一万条我们就会采用交叉验证来训练优化选择模型。如果样本大于一万条的话我们一般随机的把数据分成三份一份为训练集Training Set一份为验证集Validation Set最后一份为测试集Test Set。用训练集来训练模型用验证集来评估模型预测的好坏和选择模型及其对应的参数。把最终得到的模型再用于测试集最终决定使用哪个模型以及对应参数。 k折交叉验证 k-Folder Cross Validation经常会用到的。 k折交叉验证先将数据集 D随机划分为 k个大小相同的互斥子集即 每次随机的选择 k-1份作为训练集剩下的1份做测试集。当这一轮完成后重新随机选择 k份来训练数据。若干轮小于 k 之后选择损失函数评估最优的模型和参数。注意交叉验证法评估结果的稳定性和保真性在很大程度上取决于 k取值。
步骤 1、首先随机地将数据集切分为 k 个互不相交的大小相同的子集 2、然后将 k-1 个子集当成训练集训练模型剩下的 (held out) 一个子集当测试集测试模型 3、将上一步对可能的 k 种选择重复进行 (每次挑一个不同的子集做测试集) 4、这样就训练了 k 个模型每个模型都在相应的测试集上计算测试误差得到了 k 个测试误差对这 k 次的测试误差取平均便得到一个交叉验证误差。这便是交叉验证的过程。
k折交叉验证最大的优点
所有数据都会参与到训练和预测中有效避免过拟合充分体现了交叉的思想。 交叉验证可能存在 bias 或者 variance。如果我们提高切分的数量 kvariance 会上升但 bias 可能会下降。相反得如果降低 kbias 可能会上升但 variance 会下降。bias-variance tradeoff 是一个有趣的问题我们希望模型的 bias 和 variance 都很低但有时候做不到只好权衡利弊选取他们二者的平衡点。通常使用10折交叉验证当然这也取决于训练数据的样本数量。 3.2.7 补充过拟合和欠拟合 • 欠拟合Underfitting是指模型不能获取数据集的主要信息在训练集及测试集上的表示都十分糟糕。 • 过拟合Overfitting是指模型不仅获取了数据集的信息还提取了噪声数据的信息是的模型在训练集有非常好的表现但在测试集上的表现及其糟糕。
4 拟合与插值回归预测
问题的引入 已经测得海洋的某深度的及其对应的水温 如何根据这些已有的数据如何估计其他深度比如600,700,800米处的水温我们很自然想到深度和水温之间是否存在某种函数关系。 函数的表达式可能无法给出只能通过实验或者观察得到有限数量的数据点那么如何通过数据点得到其他的点函数值 插值的概念
在实际问题中一个函数yf(x)往往是通过实验观察到的仅已知函数f(x)在某个区间[a,b]上一系列点的值 当需要这些节点 之间的某点x的函数值时常用较为简单的满足一定的条件的函数()去代替真实的难以得出的()插值法是一种常用的方法其插值函数满足 拟合的概念
拟合也是有限个数据点求近似函数。但是拟合只要求整体上逼近而不要求一定满足上面的条件即不要求拟合得到的曲线一定过数据点但是要求在某种意义上这些点的总偏差最小。 其中样本点较少时泛指样本点小于30个采用插值方法主要有拉格朗日插值算法、牛顿插值、双线性内插和双三次插值 当样本点较多时泛指样本点大于30个则采用拟合函数
5 时间序列预测体现时间连续性
5.1 粗浅理解
时间序列通俗的字面含义为一系列历史时间的序列集合。比如2013年到2022年我国全国总人口数依次记录下来就构成了一个序列长度为10的时间序列。
专业领域里时间序列定义为一个随机过程是按时间顺序排列的一组随机变量的序列集记为。并用 或者 表示该随机序列的N有序观测值。
5.2 常见方法
5.2.1 朴素预测法Naive Forecast) 如果数据集在一段时间内都很稳定我们想预测第二天的价格可以取前面一天的价格预测第二天的值。这种假设第一个预测点和上一个观察点相等的预测方法就叫朴素法即 5.2.2 简单平均法(Simple Average 这种方法预测的期望值等于所有先前观测点的平均值称为简单平均法。。
物品价格会随机上涨和下跌平均价格会保持一致。我们经常会遇到一些数据集虽然在一定时期内出现小幅变动但每个时间段的平均值确实保持不变。这种情况下我们可以认为第二天的价格大致和过去的平均价格值一致。这种将预期值等同于之前所有观测点的平均值的预测方法就叫简单平均法。即 由图可见这种方法并没有提高结果的准确度。因此可以推断出当每个时间段的平均值保持不变时这种方法效果最好。 5.3.3 移动平均法(Moving Average
移动平均法也叫滑动平均法取前面n个点的平均值作为预测值 从图表中我们可以推断出过去的观测值在这段时间里有很大幅度的上涨。如果使用简单平均法我们必须使用所有历史数据的平均值但是使用所有数据得出的结果并不正确。
因此作为改进我们只取最近几个时期的平均价格。显然这里的想法是只有最近的价值才重要。这种利用时间窗计算平均值的预测技术称为移动平均法。移动平均值的计算有时包括一个大小为n的“滑动窗口”。
计算移动平均值涉及到一个有时被称为“滑动窗口”的大小值p。使用简单的移动平均模型我们可以根据之前数值的固定有限数p的平均值预测某个时序中的下一个值。这样对于所有的 ip
利用一个简单的移动平均模型我们预测一个时间序列中的下一个值是基于先前值的固定有限个数“p”的平均值。因此对于所有ip 5.2.4 加权移动平均(Weighted Moving Average) 加权移动平均法是对移动平均法的一个改进。在如上所述的移动平均法中我们对过去的n个观测值进行了同等的加权。但我们可能会遇到这样的情况过去“n”的每一个观察结果都会以不同的方式影响预测。这种对过去观测值进行不同加权的技术称为加权移动平均法。
加权移动平均法其实还是一种移动平均法只是“滑动窗口期”内的值被赋予不同的权重通常来讲最近时间点的值越重要。即
这种方法并非选择一个窗口期的值而是需要一列权重值相加后为1。例如如果我们选择[0.40, 0.25, 0.20, 0.15]作为权值我们会为最近的4个时间点分别赋给40%25%20%和15%的权重。 5.2.5 简单指数平滑法 (Simple Exponential Smoothing) 我们注意到简单平均法和加权移动平均法在选取时间点的思路上存在较大的差异简单平均法将过去数据一个不漏地全部加以同等利用移动平均法则不考虑较远期的数据并在加权移动平均法中给予近期更大的权重。我们就需要在这两种方法之间取一个折中的方法在将所有数据考虑在内的同时也能给数据赋予不同非权重。
指数平滑法相比更早时期内的观测值越近的观测值会被赋予更大的权重而时间越久远的权重越小。它通过加权平均值计算出预测值其中权重随着观测值从早期到晚期的变化呈指数级下降最小的权重和最早的观测值相关 5.2.6 霍尔特线性趋势法 Holts线性趋势模型霍尔特线性趋势法该方法考虑了数据集的趋势即序列的增加或减少性质。
尽管这些方法中的每一种都可以应用趋势简单平均法会假设最后两点之间的趋势保持不变或者我们可以平均所有点之间的所有斜率以获得平均趋势使用移动趋势平均值或应用指数平滑。
但我们需要一种无需任何假设就能准确绘制趋势图的方法。这种考虑数据集趋势的方法称为霍尔特线性趋势法或者霍尔特指数平滑法。 5.2.7 Holt-Winters方法三次指数平滑
霍尔特-温特Holt-Winters方法有的地方也叫三次指数平滑法。Holt-Winters 方法在 Holt模型基础上引入了 Winters 周期项也叫做季节项可以用来处理月度数据周期 12、季度数据周期 4、星期数据周期 7等时间序列中的固定周期的波动行为。引入多个 Winters 项还可以处理多种周期并存的情况。
当一个序列在每个固定的时间间隔中都出现某种重复的模式就称之具有季节性特征而这样的一个时间间隔称为一个季节性特征。
例如酒店的预订量在周末较高工作日较低并且每年都在增加 表明存在一个一周的季节性和增长趋势。
这里只介绍简单的预测模型
6 K-MeansK-均值聚类算法无需分割数据即可分类
6.1 粗浅理解
聚类简单来说就是将一个庞杂数据集中具有相似特征的数据自动归类到一起称为一个簇簇内的对象越相似聚类的效果越好。它是一种无监督的学习(Unsupervised Learning)方法,不需要预先标注好的训练集。聚类与分类最大的区别就是分类的目标事先已知例如猫狗识别你在分类之前已经预先知道要将它分为猫、狗两个种类而在你聚类之前你对你的目标是未知的同样以动物为例对于一个动物集来说你并不清楚这个数据集内部有多少种类的动物你能做的只是利用聚类方法将它自动按照特征分为多类然后人为给出这个聚类结果的定义即簇识别。例如你将一个动物集分为了三簇类然后通过观察这三类动物的特征你为每一个簇起一个名字如大象、狗、猫等这就是聚类的基本思想。
至于“相似”这一概念是利用距离这个评价标准来衡量的我们通过计算对象与对象之间的距离远近来判断它们是否属于同一类别即是否是同一个簇。至于距离如何计算科学家们提出了许多种距离的计算方法其中欧式距离是最为简单和常用的除此之外还有曼哈顿距离和余弦相似性距离等。
我们常用的是 对于x点坐标为(x1,x2,x3,...,xn)和 y点坐标为(y1,y2,y3,...,yn)两者的欧式距离为: K-Means 是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值 是因为它可以发现 K 个不同的簇, 且每个簇的中心采用簇中所含值的均值计算而成. 簇个数 K 是用户指定的, 每一个簇通过其质心centroid, 即簇中所有点的中心来描述. 聚类与分类算法的最大区别在于, 分类的目标类别已知, 而聚类的目标类别是未知的.
优点:
1.属于无监督学习无须准备训练集 2.原理简单实现起来较为容易 3.结果可解释性较好 缺点:
1.需手动设置k值。 在算法开始预测之前我们需要手动设置k值即估计数据大概的类别个数不合理的k值会使结果缺乏解释性 2.可能收敛到局部最小值, 在大规模数据集上收敛较慢 3.对于异常点、离群点敏感
几个名词 1.簇: 所有数据的点集合簇中的对象是相似的。 2.质心: 簇中所有点的中心计算所有点的均值而来. 3.SSE: Sum of Sqared Error误差平方和, 它被用来评估模型的好坏SSE 值越小表示越接近它们的质心. 聚类效果越好。由于对误差取了平方因此更加注重那些远离中心的点一般为边界点或离群点 6.2 算法过程
6.2.1 选定质心 随机确定 K 个初始点作为质心不必是数据中的点
6.2.2 分配点
将数据集中的每个点分配到一个簇中, 具体来讲, 就是为每个点找到距其最近上面提到的欧氏距离的质心, 并将其分配该质心所对应的簇. 这一步完成之后, 每个簇的质心更新为该簇所有点的平均值.
重复上述过程直到数据集中的所有点都距离它所对应的质心最近时结束
6.2.3 评价
k-means算法因为手动选取k值和初始化随机质心的缘故每一次的结果不会完全一样而且由于手动选取k值我们需要知道我们选取的k值是否合理聚类效果好不好那么如何来评价某一次的聚类效果呢也许将它们画在图上直接观察是最好的办法但现实是我们的数据不会仅仅只有两个特征一般来说都有十几个特征而观察十几维的空间对我们来说是一个无法完成的任务。因此我们需要一个公式来帮助我们判断聚类的性能这个公式就是SSE (Sum of Squared Error, 误差平方和 它其实就是每一个点到其簇内质心的距离的平方值的总和这个数值对应kmeans函数中clusterAssment矩阵的第一列之和。 SSE值越小表示数据点越接近于它们的质心聚类效果也越好。 因为对误差取了平方因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。 7 KNN算法K近邻算法
7.1 粗浅理解
根据你的“邻居”来推断出你的类别
K Nearest Neighbor算法⼜叫KNN算法这个算法是机器学习⾥⾯⼀个⽐较经典的算法 总体来说KNN算法是相对⽐ 较容易理解的算法 如果⼀个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的⼤多数属于某⼀个类别则该样本也属于这个 类别。 7.2 有关距离的介绍
7.2.1 欧氏距离(Euclidean Distance)
这里不再赘述
7.2.2 曼哈顿距离(Manhattan Distance)
在曼哈顿街区要从⼀个⼗字路⼝开⻋到另⼀个⼗字路⼝驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是 “曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance) 7.2.3 切比雪夫距离 (Chebyshev Distance)
国际象棋中国王可以直⾏、横⾏、斜⾏所以国王⾛⼀步可以移动到相邻8个⽅格中的任意⼀个。国王从格⼦(x1,y1) ⾛到格⼦(x2,y2)最少需要多少步这个距离就叫切⽐雪夫距离。 7.2.4 闵可夫斯基距离(Minkowski Distance)
闵⽒距离不是⼀种距离⽽是⼀组距离的定义是对多个距离度量公式的概括性的表述。 两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为 根据p的不同闵⽒距离可以表示某⼀类/种的距离
小结
闵氏距离包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点: e.g. ⼆维样本(身高[单位:cm],体重[单位:kg]),现有三个样本a(180,50)b(190,50)c(180,60)。 a与b的闵氏距离无论是曼哈顿距离、欧氏距离或切比雪夫距离等于a与c的闵氏距离。但实际上身⾼的10cm并不能 和体重的10kg划等号。 闵氏距离的缺点 (1)将各个分量的量纲(scale)也就是“单位”相同的看待了; (2)未考虑各个分量的分布期望方差等可能是不同的
7.2.5 “连续属性”和“离散属性”的距离计算 我们常将属性划分为 “连续属性” (continuous attribute)和 “离散属性” (categorical attribute)前者在定义域上有⽆穷多个 可能的取值后者在定义域上是有限个取值.
若属性值之间存在序关系则可以将其转化为连续值例如身⾼属性“⾼”“中等”“矮”可转化为{1, 0.5, 0}。 闵可夫斯基距离可以⽤于有序属性。 若属性值之间不存在序关系则通常将其转化为向量的形式例如性别属性“男”“⼥”可转化为{1,0 0,1}。
7.3 算法过程
略
