一种基于改进KNN的大数据离群点检测算法

最近邻点法最近邻点法（KNN）是一种基于数据距离度量的机器学习算法。

它是监督学习算法中最简单和最常用的算法之一。

其基本思想是通过测量不同特征之间的距离，将一个未知样本标记为与距离最近的已知样本相同的类别。

KNN算法可以用来分类或回归，常用于分类问题。

KNN分类器的工作原理如下：给定一组已分类的样本数据，将一个新的样本与已有样本数据进行比较，找到与新样本最接近的K个样本（K是一个既定的数目），并将新样本分配给这K个样本中最普遍的类别。

KNN算法的核心是进行距离度量。

KNN算法中距离度量方法的种类很多，例如欧氏距离、曼哈顿距离、马氏距离等。

其中欧氏距离最为常用。

KNN算法的距离度量可以通过计算每个特征的差异来实现，也可以使用其他方法进行度量。

距离度量完成后，KNN算法开始确定K值。

通常情况下，较小的K值能够产生较小的误差，而较大的K值则能更好地抵御噪声。

但是，较大的K值会使算法更加耗时，并且可能使一些例子中的极端离群值对算法产生负面影响。

KNN算法是一种简单而有效的算法，但需要注意以下几点：1.选择合适的K值：过大或过小的K值都可能导致算法的失效。

2.特征归一化：由于不同特征的度量单位和尺度不同，在距离度量时可能会对结果造成很大的影响。

为了使算法更加准确，应该对所有特征进行归一化处理。

3.算法的分类速度比较慢：当样本数据量很大时，KNN算法的计算量会非常庞大。

因此，在处理大量数据时，KNN算法可能会变得非常缓慢。

总的来说，KNN算法在数据量不大、特征数量较少的情况下，非常适合进行分类问题的处理，并且对于数据本身的特征分布不作限定，因此具有比较好的适应性。

但是，由于距离度量方法和K值的选择等问题，需要谨慎使用。

• 57•为了更好的应对复杂情况的离群点检测，本文提出了一种基于集成方法的离群点检测算法。

本算法采用两种集成方式的级联模式，第一阶段的集成方式采用并列集成的方式，KNN、iFores、DBSCAN作为基分类器，进行模型融合得到第一阶段的分类结果。

第二阶段采用序列集成的方式，根据第一阶段得到的权重对数据进行权重值调整，进而实现数据集再分布，再用残差逼近的方式得到最终的离群点检测结果。

通过实验结果对比，由于本算法达到了方差和偏差的平衡，检测效果明显优于常见的离群点检测算法。

Hawkins给出的离群点定义为：离群点是数据集中与众不同的数据点，其表现与其他点如此不同，以至于使人怀疑这些数据这些数据并非随机的偏差，而是由另外一种完全不同的机制所产生的。

常见的离群点检测算法有：基于统计的、基于聚类的、基于密度的、基于距离的、基于深度的离群点检测算法等。

本文基于集成学习方法提出了一种新的离群点检测模型，以间隔森林iForest、局部离群点检测LOF、基于密度的DBSCAN为基分类器，第一阶段用bagging方式集成；第二阶段用boosting方式集成，通过级联的方式得到最终分类结果。

1 相关研究已有的基于密度的离群点检测算法通过与周围邻居点密度的差距大小来判断离群点，常见的有LOF(Local Outlier Factor)、COF(Connectivity based Outlier Factor)。

基于距离的离群点检测算法是通过给定一数据邻域范围，若邻域内包含数据太少，我们则判定该数据为离群点，比较有代表性的有Nested-loop方法、Cell-based 方法。

基于深度的离群点检测算法是根据定义深度方式来计算深度值，以深度值的大小来进行分层，在浅层的数据比处在深层的数据是离群点的可能性更大。

基于聚类的离群点检测算法是先将所有数据进行聚类，然后找出不包含于任何聚类中心的数据或者将聚类密度非常低的小簇的数据作为离群点数据，有代表性的如DBSCAN、CLARANS。

LOF（Local Outlier Factor）算法是一种用于检测局部离群点的算法。

它通过比较数据点与其邻居之间的距离来检测局部离群点，从而能够更准确地识别出真正的离群点。

下面是对LOF 算法公式的解释：
LOF算法的基本思想是通过比较数据点与其邻居之间的距离来确定其离群程度。

在算法中，首先需要定义一个邻居集合，通常使用最近邻（k-nearest neighbors，kNN）算法来确定邻居集合。

然后，对于每个数据点，计算其与邻居集合中所有数据点之间的距离，并使用这些距离来计算其局部离群因子。

具体来说，对于数据点x，LOF算法的公式可以表示为：LOF(x) = exp(-γ* min(kNN(x)))其中，kNN(x)是x在邻居集合中的最近邻点的数量，γ是一个控制算法鲁棒性的超参数。

通过调整γ的值，LOF算法可以适应不同的数据集和场景。

值得注意的是，LOF算法并不只是基于单个数据点的离群程度进行评估，而是通过对数据集中的所有数据点进行评估，并利用其局部邻居之间的距离来识别局部离群点。

因此，LOF算法能够更全面地检测出离群程度较高的数据点，从而有助于提高检测结果的准确性。

综上所述，LOF算法通过比较数据点与其邻居之间的距离来计算其局部离群因子，并利用该因子来识别局部离群点。

该算法能够更全面地检测出离群程度较高的数据点，具有较高的准确性和鲁棒性。

在实际应用中，LOF算法可以应用于各种领域的数据挖掘和机器学习任务中，如社交网络分析、异常检测、推荐系统等。

类似knn的算法在机器学习领域中，有很多类似于KNN（K-最近邻）的算法可以用于分类和回归任务。

下面将介绍其中几个主要的算法。

1. KD树（KD-Tree）KD树是一种在k维空间中对数据点进行结构化组织的数据结构。

它通过递归地将数据集分割为以数据点为中心的超矩形，从而快速进行最近邻。

相比于KNN算法，KD树能够减少计算距离的次数，提高效率。

2.LOF（局部异常因子）LOF算法是一种基于密度的离群点检测算法。

它通过计算每个数据点到其邻近点的局部可达密度，来识别异常点。

与KNN算法相比，LOF算法不仅考虑数据点之间的距离，还考虑了密度差异。

这使得LOF算法对于非球形簇或不同密度的数据集更具鲁棒性。

3. K-Means（K-均值）K-Means算法是一种聚类算法，它将数据集划分为K个簇，使得每个数据点都属于与之最近的簇的中心。

K-Means算法通过迭代优化簇的中心位置来最小化数据点到簇中心的平方距离。

与KNN算法相似，K-Means也利用数据点之间的距离来度量相似性。

4. 决策树（Decision Tree）决策树是一种用于分类和回归任务的非参数监督学习算法。

它通过基于特征的条件来逐步划分数据集，并生成一棵树状结构。

决策树可以根据特征的不同分割数据，类似于KNN算法中的最近邻。

不同的划分策略和剪枝技术可以改善决策树的预测性能。

5. 贝叶斯分类器（Bayesian Classifier）贝叶斯分类器是一种基于贝叶斯定理的统计分类方法。

它假设各个特征之间是相互独立的，并通过计算后验概率来确定数据点的类别。

与KNN算法类似，贝叶斯分类器也利用了数据点之间的距离，但是它还考虑了特征之间的关联性。

6.SVM（支持向量机）支持向量机是一种广泛应用于分类和回归任务的监督学习算法。

它通过找到能够最大程度地划分不同类别之间的间隔的超平面，从而进行分类。

SVM算法利用一些支持向量来表示数据点，这些支持向量是离超平面最近的数据点。

离群点算法全文共四篇示例，供读者参考第一篇示例：离群点（Outlier）是指数据集中与其他数据点明显不同的数据点。

离群点算法是指一系列用来检测和识别离群点的技术和方法。

在数据分析和机器学习中，离群点算法可以有效地识别异常数据点，帮助我们更准确地进行数据分析和建模。

离群点算法主要分为基于统计学的方法、基于聚类的方法和基于密度的方法等多种类型。

每种类型的算法都有其独特的优缺点和适用范围。

在实际应用中，我们可以根据具体的数据集和需求选择合适的算法进行离群点检测。

一种常用的离群点算法是基于统计学的方法，其中最常见的是Z 分数（Z-score）方法。

Z分数是一种标准化的统计量，表示数据点与平均值的偏离程度。

通过计算数据点的Z分数，我们可以判断数据点是否为离群点。

一般来说，Z分数绝对值大于3的数据点可以被认为是离群点。

除了Z分数方法外，还有一些其他基于统计学的离群点算法，如Tukey的箱线图（Boxplot）、Grubbs检验等。

这些方法都可以有效地检测离群点，但在实际应用中需要根据具体情况选择最合适的方法。

另一种常用的离群点算法是基于聚类的方法，其中LOF（Local Outlier Factor）算法是一种常见的基于聚类的离群点算法。

LOF算法通过计算数据点周围邻近点的密度来判断数据点是否为离群点。

密度较低的数据点很可能是离群点。

通过计算LOF值，我们可以对数据点进行离群点判断。

基于密度的离群点算法也是一种常用的方法，其中DBSCAN （Density-Based Spatial Clustering of Applications with Noise）算法是一种典型的基于密度的离群点算法。

DBSCAN算法通过将数据点分为核心点、边界点和噪声点来判断数据点是否为离群点。

在DBSCAN算法中，噪声点通常被认为是离群点。

离群点算法在数据分析和机器学习中扮演着重要的角色。

通过识别和处理离群点，我们可以得到更准确的数据分析结果，提高模型的准确性和稳定性。

knn算法的用法一、引言K近邻算法（K-NearestNeighbors，简称KNN）是一种基于实例的学习算法，它广泛用于分类和回归问题。

KNN算法以其简单、直观且易于理解的特点，在许多领域得到了广泛应用。

本文将详细介绍KNN算法的原理、应用场景、参数设置以及优缺点，帮助读者更好地理解和应用该算法。

二、KNN算法原理KNN算法的基本思想是通过比较待分类项与已知样本集中的每个样本的距离，找出与待分类项距离最近的K个样本。

根据这K个样本的类别，对待分类项进行预测。

最终，待分类项的类别是由这K个样本中最常见的类别决定。

三、KNN算法的应用场景KNN算法适用于以下场景：1.分类问题：KNN算法可以应用于各种分类问题，如文本分类、图像分类、生物信息学中的基因分类等。

2.回归问题：KNN算法也可以应用于回归问题，如房价预测、股票价格预测等。

3.异常检测：通过比较待分类项与已知样本集的距离，KNN算法可以用于异常检测，识别出与正常样本显著不同的数据点。

四、KNN算法参数设置KNN算法的参数包括：1.K值：确定近邻数，影响算法的准确度和计算复杂度。

过小的K 值可能会导致漏检，而过大的K值可能会导致误检。

需要根据实际问题进行尝试和调整。

2.距离度量方法：KNN算法支持多种距离度量方法，如欧氏距离、曼哈顿距离等。

选择合适的距离度量方法对于算法的性能至关重要。

3.权重策略：在计算待分类项的近邻时，不同的样本可能具有不同的权重。

常见的权重策略包括按照样本出现次数加权、按照距离加权等。

合适的权重策略可以提高算法的准确度和鲁棒性。

五、KNN算法优缺点优点：1.简单易实现：KNN算法实现简单，易于理解和应用。

2.对异常值和噪声具有鲁棒性：KNN算法对异常值和噪声具有较强的鲁棒性，可以有效地处理这些问题。

3.无需大量的参数调优：与其他机器学习算法相比，KNN算法的参数较少，无需进行复杂的参数调优。

缺点：1.对大数据处理能力有限：KNN算法的计算复杂度较高，尤其是在大规模数据集上，处理速度较慢。

基于改进粒子群算法优化CNN-LSTM神经网络的传染病预测刘彩云;聂伟;孟金葆;张涛【期刊名称】《湖州师范学院学报》【年(卷),期】2024(46)4【摘要】针对新型传染病发展趋势的预测精度问题,提出一种改进粒子群(PSO)算法优化卷积神经网络(CNN)与长短期记忆神经网络(LSTM)相结合的预测模型.首先,将原始粒子群优化算法中最优惯性权重的调整方式由迭代次数的线性关系转变为非线性关系,并对学习因子进行线性更新,以寻找最优参数,从而更准确地模拟粒子群的社会学习能力,进而平衡算法的全局优化能力,提高收敛速度;其次,以发酵时间较长的新型冠状肺炎为研究对象,构建CNN-LSTM神经网络预测模型,利用CNN层提取其特征信息后降维作为LSTM层输入,并通过预测模块实现对研究对象的指标训练和预测,从而提高模型的预测精度;最后,与原始LSTM模型的预测误差,如均方根误差(RMSE)、平均绝对误差(MAE)、均方误差(MSE)等指标进行对比.研究结果表明,在训练集上,与原始LSTM模型相比,经过改进的PSO算法优化CNN-LSTM组合神经网络模型,其在RMSE、MAE和MSE三个指标上分别降低了73.0%、62.3%、92.7%;在测试集上,这3个指标分别降低了23.0%、29.8%、40.7%.这说明该模型具有更小的误差和较好的预测效果.该研究结果可为实现传染病传播趋势的精准预测提供新的思路和方法.【总页数】12页(P37-48)【作者】刘彩云;聂伟;孟金葆;张涛【作者单位】铜陵学院数学与计算机学院;铜陵职业技术学院信息工程系【正文语种】中文【中图分类】TP39【相关文献】1.一种基于改进粒子群算法优化BP神经网络的预测方法2.基于改进的粒子群算法优化反向传播神经网络的热舒适度预测模型3.基于改进粒子群算法优化小波神经网络的\r短时交通流预测4.基于改进粒子群算法优化BP神经网络的甜菜产量预测方法5.基于改进粒子群算法优化模糊神经网络的炉膛结渣预测研究因版权原因，仅展示原文概要，查看原文内容请购买。

基于改进KNN算法的城轨进站客流实时预测郇宁;谢俏;叶红霞;姚恩建【摘要】针对实时进站客流数据的高维数、多噪声、波动频繁等特征,本文提出一种基于改进K最近邻(K-nearest-neighbor,KNN)算法的城轨进站客流实时预测方法.首先,通过对分时客流数据的相关性分析,确定表征客流特征的状态向量;其次,结合数据特性改进近邻样本的模式匹配过程,利用关键点法去除原始序列中的噪声扰动,并引入动态时间规整算法实现考虑序列形态的相似性度量;再次,根据样本间流量差异引入距离权重和趋势系数,推演未来时段的进站量,实现滚动的实时预测;最后,依托广州地铁客流数据仓库对预测模型进行精度分析.结果表明,对于全网159个站点,5 min粒度下全天分时进站量预测的平均绝对百分比误差的均值为11.6％,能够为路网状态监控提供可靠的数据支撑.【期刊名称】《交通运输系统工程与信息》【年(卷),期】2018(018)005【总页数】8页(P121-128)【关键词】城市交通;实时预测;K近邻;进站客流;动态时间规整【作者】郇宁;谢俏;叶红霞;姚恩建【作者单位】北京交通大学城市交通复杂系统理论与技术教育部重点实验室,北京100044;广州地铁集团有限公司,广州510030;广州地铁集团有限公司,广州510030;北京交通大学城市交通复杂系统理论与技术教育部重点实验室,北京100044【正文语种】中文【中图分类】U268.60 引言随着城市轨道交通网络化运营规模不断扩大，准确地掌握客流分布状况成为提高客运组织水平的重要前提.高精度、小粒度的实时进站量预测能够帮助管理者及时掌握网络客流演化态势，为客运组织提供重要的决策依据.针对客流预测问题，国内外学者对短期和中长期的需求预测关注较多.蔡昌俊[1]通过构建乘积ARIMA模型，消除趋势性特征影响，推演客流长期变化规律.姚恩建等[2]考虑车站可达性指标，建立新线接入后既有站的进出站量预测模型.光志瑞[3]针对节假日客流中动态特征的非线性序列，分析了制约预测精度的关键因素.徐瑞华等[4]提出了站台—列车客流交互模型，为断面客流等精细化指标预测提供了理论基础.包磊[5]通过灰色模型和马尔科夫链预测线路客运量等宏观指标.此类研究普遍针对客流周期性变化，旨在为运力配置提供测算依据，而对实时运算逻辑和效率约束等因素关注较少，难以适应动态增量的数据环境.近年来，非参数回归模型凭借其灵活性和强大的数据处理能力，在实时预测领域应用广泛.Davis G.A.[6]于1991年将非参数回归模型应用到交通流量预测中，并系统地梳理了相关基础理论.宫晓燕等[7]针对基于动态聚类和散列函数的数据组织方式，提出了基于密集度的变K搜索算法.张涛等[8]分析了K最近邻(K-nearest-neighbor,KNN)算法中状态向量等关键因素对精度的影响.谢俏等[9]将KNN算法应用于城轨车站的进出站量实时预测问题，考虑了客流的时间关联性，取得良好的预测效果.目前，同类研究所提出的模型普遍针对15 min或1 h粒度的客流数据，由于采样时间跨度较大，样本的数值型特征相对明显，因而对实时数据中噪声扰动等因素考虑不足，其预测机制也往往难以适用于现实环境.此外，在传统KNN算法的模式匹配过程中，普遍采用基于欧式距离的“点对点”度量方法，当序列中波峰、波谷在时间轴上产生偏移时，造成误差显著升高.本文以5 min粒度的实时进站量数据为研究对象，结合序列降维拟合技术和动态时间规整算法，改进传统KNN算法的模式匹配环节，在规避噪声扰动的同时，实现考虑序列形态的样本匹配；在回归预测阶段，引入距离权重和趋势系数以顺应客流的自然增长规律；最后，通过精度分析论证了方法的可行性与有效性.1 城轨进站客流变化规律分析深入分析客流变化规律是客流预测的重要前提.其一，进站客流规律受周边土地性质等环境因素影响明显，以广州地铁线网中区域跨度较大的3号线为例，随机选择某日的分时进站量进行横向对比，如图1所示.由图1可知，5 min粒度下的进站量波动较强，并且站点的客流规模与峰值分布存在差异.因此，考虑以车站为基本单元组建历史样本库.在数据条件不足的情况下，可结合聚类等手段，选择与本站客流规律相近的同类站点扩充样本.其二，客流规律受双休日、节假日安排等因素影响明显，以位于中心商务区的珠江新城站为例，对不同日期进行纵向对比，如图2所示.图1 广州地铁3号线站点分时进站量对比图Fig.1 Entrance passenger flow of stations in Guangzhou Metro Line 3图2 珠江新城站分时进站量变化图Fig.2 Entrance passenger flow of Zhujiang New Town station among certain days可见，珠江新城站基本不存在早高峰，但具有傍晚通勤和晚间出行带来的双高峰特征.图2中：(a)、(d)、(e)、(f)分别对应不同星期数的工作日，客流规律较为相近；(b)、(c)为双休日，傍晚通勤高峰明显弱于工作日；(g)虽为周六，但受端午节调休影响，规律与工作日一致；(h)、(i)为端午假期，晨间客流进一步衰减，存在晚间高峰强于傍晚高峰的特殊现象.基于此，将预测场景初步划分为工作日、双休日、节假日3类.2 城轨进站客流实时预测模型结合进站客流数据特性，构建基于改进KNN算法的实时预测模型.首先，确定状态向量选取规则以合理描述样本特征；其次，为解决“点对点”欧氏距离匹配适用性差的问题，提出改进的模式匹配方法，实现考虑序列形态的精准匹配；最后，根据近邻样本与预测目标的差异引入距离权重和趋势系数，给出一般化的预测算法.2.1 状态向量选取考虑到进站客流具有较强的时间关联性，故选择与当前邻近的m个时段的进站量构成状态向量，用于描述样本特征.通过计算历史分时进站量的自相关系数推算m 值，公式为[9]式中：为站点i于x日分时进站量滞后q个时段的自相关系数；分别为站点i于x 日时段n、n+q的进站量；为站点i于x日分时进站量的均值；N为有效时段数. 以2016—2017年全网的分时进站量数据为对象，将每日每站216条(6:00-24:00)分时进站量视为1个序列样本.根据式(1)和式(2)计算自相关系数.当≥0.5时，通常认为序列中相邻的q个时段相关性显著[9].统计符合该条件的样本比例，结果如表1所示.表1 广州地铁分时进站客流自相关性统计表Table 1 Self correlation feature of entrance passenger flow in Guangzhou metro(%)场景节假日94.34 92.74 92.01 91.48 90.25 88.82 85.61 81.89 76.28 68.71 8 142阶数q 1234567891 0样本量工作日99.09 98.73 98.64 98.34 97.56 96.61 94.51 90.53 86.33 71.46 71 562双休日97.17 96.01 95.79 95.20 94.17 92.87 90.84 87.14 82.11 65.46 29 373表1结果显示，5 min粒度下的进站客流时间关联性明显.综合考虑样本分布及实际预测的精度表现，确定若样本总量的85%以上满足≥0.5，则认为邻近的前q个时段具有较强相关性，进而确定工作日、双休日、节假日对应的m值为9、8、7，并以此作为状态向量选取依据.2.2 基于关键点的序列表示方法考虑到进站量序列中离群点较多且波动频繁，若直接进行处理不仅会降低实时运算效率，而且影响预测效果.所以，在模式匹配之前，采用关键点法(Key Point Segmentation,KPS)对序列进行降维拟合处理，寻找关键极值点(Key Extreme Point,KEP)和关键转折点(Key Turning Point,KTP)对序列进行抽象化表示.首先，设置极值保持时段阈值K0，筛选KEP以去除序列中的过多细节；其次，利用夹角法描述序列转折趋势，通过转折角度阈值θ0筛选KTP，如图3所示.对于图3中的子序列(xi-1,xi,xi+1)，通过计算转折角的余弦值量化转折程度，公式为[10]式中：；由于研究序列为等长序列，令序列间隔Δt统一为1.图3 KTP选取指标计算示意图Fig.3 Illustration of parameter calculation for KTP selection定义序列压缩比C和拟合优度R2评价降噪拟合算法的有效性.压缩比用于描述对序列的剪裁能力，低压缩比意味着低的计算成本，但过低亦会造成信息损失；拟合优度用于描述对序列的还原程度，值越接近1，表示拟合效果越好.公式为式中：N0为原始序列的维数；NKP为关键点集的元素数；yi和分别为序列点的原始值和拟合值；为原始序列的均值.随机选取部分日期进行测试，指标如图4所示.确定参数K0取2，θ0取90°时，能够在获得较高拟合优度时，取得良好的压缩比.2.3 基于动态时间规整的相似性度量方法模式匹配是KNN算法的核心步骤，指寻找特征空间中K个最邻近样本的过程.对于时间序列这一研究对象，通常采用序列间相似性度量实现.针对序列样本在时间轴上的偏移、扭曲等现象，采用动态时间规整(Dynamic Time Warping,DTW)算法对非等长序列进行相似性度量，适当扩张或压缩局部特征，进而得到更好的形态度量效果，如图5所示.图4 KPS序列表示方法指标统计图Fig.4 Evaluation index for KPS algorithm图5 DTW相似性度量示意图Fig.5 Diagram of similarity measurement with DTW algorithm对于序列A=(a1,…,ai,…,am)和B=(b1,…,bj,…,bn)，构建m×n的距离矩阵Dm×n，DTW的目的在于寻找一条通过若干格点的路径P=(p1,…,pk,…,pK)，使得其全局代价最小，即令累积距离C满足条件式中：pk为该路径元素在矩阵中的位置，即表示ai和bj间的匹配关系.一般而言，序列间存在多条路径，但有效路径P应满足边界性、连续性和单调性约束[11].采用动态规划方法构造一个代价矩阵γm×n，即序列间DTW距离，公式为式中：D(i,j)为ai和bj间的距离，3种匹配方式如图6所示.图6 子序列匹配方式示意图Fig.6 Illustration of matching patterns for subsequences2.4 预测算法以每个预测节点可获取的最新时段进站量为对象，通过调整K值对该时段进行迭代预测，取预测误差最小的K值作为应用值.同时，为顺应客流的自然增长规律，引入距离权重与趋势系数以修正预测结果.若匹配所得近邻日期为{z1,z2,…,zk}，预测值的计算公式为式中：为站点i于预测日T时段t的分时进站量预测值；为近邻zk的预测权重值为近邻zk与预测日T间的匹配距离，即DTW距离；为站点i预测日客流与近邻zk的趋势系数；为站点i于预测日T时段t的前l时段的分时进站量；V为站点i 的近邻zk对应时段t的前l时段的分时进站量.3 精度分析依托广州地铁客流数据仓库对预测模型进行精度分析，以站点的全天分时平均绝对百分比误差ET和累积全天平均绝对百分比误差ED为评价指标，公式为式中：分别为站点i于预测日T时段t的分时进站量的预测值与实际值.首先，测试模型于不同时间粒度下的预测效果，结果如表2所示.表2 不同时间粒度下的预测误差Table 2 Forecast error under different granularities(%)预测日期2017/12/23 2017/12/24 2017/12/25 2017/12/26 2017/12/30 2017/12/31场景双休5 min日2.33日2.24日2.08日2.41假期2.73假期2.54双休工作工作元旦元旦全网平均ET全网平均ED 15 min 1.23 1.19 1.02 1.19 1.39 1.31 1 h 0.92 0.81 0.74 0.87 1.03 0.95 5 min 11.34 11.79 10.78 11.90 12.23 11.61 15 min 9.89 9.22 8.39 9.48 10.46 9.57 1 h 6.97 7.15 6.53 6.78 8.27 7.49与本文预测模式较为相近的文献[9]中，15 min粒度下全网平均ET为12.4%，证明本文提出的方法具有更强的时效性与准确性.在后续分析中，默认采用5 min时间粒度.其次，对比KNN算法改进前后预测效果.具体分为以下4类：方法(i)为“逐点欧式距离匹配+近邻距离加权”的传统模式，方法(ii)为“KPS-DTW+近邻距离加权”的模式，方法(iii)为“逐点欧式距离匹配+近邻距离加权-趋势系数”的模式，方法(iv)为“KPS-DTW+近邻距离加权-趋势系数”的改进模式.结果如表3所示.表3 不同方法下的预测误差Table 3 Forecast error with differentalgorithms(%)（iv）2.39 11.61指标全网平均ED全网平均ET（i）3.27 16.72（ii）2.73 12.54（iii）3.02 15.38由表3可知，匹配模式的改进对预测精度有较大提升，趋势系数的引入也具有良好的效果.然后，从线路层面进行分析，结果如表4所示.表4 不同线路的预测误差Table 4 Forecast error of each line线路1号线2号线3号线3北线4号线5号线6号线7号线8号线广佛线站数16 24 16 13 1624 29 9 13 22站点5 min平均进站量/人次264.507.26公204.598.19269.877.67体247.469.07体73.0714.94 184.7510.26 127.1914.02海23.8523.87广142.4613.48 65.4416.07平均ET/%最低ET站点园前（5.18%）昌岗（6.62%）育西路（4.85%）育西路（4.85%）车陂（8.76%）潭村（8.29%）珠广场（7.60%）州南站（7.15%）昌岗（6.62%）沙园（9.09%）由表4可知，客流量较大的站点往往预测精度更优.以7号线的谢村站为例，每日约90个时段的进站量小于5人次，致使该站误差较高，但在应用中可忽略此类影响.此外，以客流规律不同的4个典型车站为例，随机选择某日的完整预测结果进行展示，如图7～图10所示.图7 珠江新城站预测样本图Fig.7 Forecasting sample of Zhujiang New Town station图8 东晓南站预测样本图Fig.8 Forecasting sample of Dongxiaonan station可以看出，该方法在不同类型车站的预测中均表现出良好的效果，基本不存在局部偏离现象.最后，探究模型在不同数据条件下的适用性问题.依据2017年长期的实时预测记录，对不同时期历史数据在预测中发挥的实际效用进行分析，统计其被成功匹配为近邻的频率，结果如图11所示.图9 杨箕站预测样本图Fig.9 Forecasting sample of Yangji station图10 长寿路站预测样本图Fig.10 Forecasting sample of Changshou Road station图11 历史样本选取频率分布直方图Fig.11 Frequency distribution histogramof sample selection从图11可知，实际被匹配的样本中，九成以上处于预测日期前一年内.因此，为保证预测准确性，历史数据库应尽量覆盖近一年的客流数据.对于节假日等特殊场景，则需结合实际情况提供更长时限的同类场景历史样本.4 结论针对小粒度客流数据的高维数、多噪声等特征，本文提出一种基于改进KNN算法的实时进站客流预测方法.其一，通过KPS序列表示法实现序列的降维表示，当拟合优度达0.8时，平均压缩比为62.4%，可在充分保留特征的同时规避细节扰动；其二，采用DTW算法解决不同维数序列间的相似性度量问题，可容忍小粒度客流数据中的偏移、拉伸现象，优化匹配逻辑；其三，在真实的动态数据环境中开展精度检测，5 min粒度下全网站点全天分时进站量预测的平均绝对百分比误差的均值为11.6%，并给出了历史样本库构建的参考规则.综上，该模型具有较好的可行性与有效性，能够为路网状态监控提供可靠的数据支撑.【相关文献】[1]蔡昌俊.新线接入条件下城轨路网客流预测理论与方法研究[D].北京:北京交通大学,2014.[CAI C J.Passenger flow forecasting theory and method for urban rail transit network after the opening of new lines[D].Beijing:Beijing Jiaotong University,2004.][2]姚恩建,程欣,刘莎莎,等.基于可达性的城轨既有站进出站客流预测[J].铁道学报,2016,38(1):1-7.[YAO E J,CHENG X,LIU S S,et al.Accessibility based forecast on passenger flow entering and departing existing urban railway stations[J].Journal of the China Railway Society,2016,38(1):1-7.][3]光志瑞.城市轨道交通节假日客流预测研究[J].交通工程,2017,17(3):27-35.[GUANG Z R.Short-term passenger flow forecast at urban railway stations during holiday[J].Journal of Transportation Engineering,2017,17(3):27-35.][4]徐瑞华,徐永实.城市轨道交通线路客流分布的实时预测方法[J].同济大学学报(自然科学版),2011,39(6):857-861.[XU R H,XU Y S.Real-time forecast of passenger flow distribution on urban rail transit line[J].Journal of Tongji University(Natural Science),2011,39(6):857-861.][5]包磊.城市轨道交通客流量实时预测模型[J].城市轨道交通研究,2017,20(5):104-106,111.[BAO L.Real-time forecast of passenger flow volume in urban rail transit[J].Urban Mass Transit,2017,20(5):104-106,111.][6]DAVIS G A,NIHAN N L.Nonparametric regression and short-term freeway traffic forecasting[J].Journal of Transportation Engineering,1991,117(2):178-188.[7]宫晓燕,汤淑明.基于非参数回归的短时交通流量预测与事件检测综合算法[J].中国公路学报,2003,16(1):82-86.[GONG X Y,TANG S M.Integrated traffic flow forecasting and traffic incident detection algorithm based on non-parametric regression[J].China Journal of Highway and Transport,2003,16(1):82-86.][8]张涛,陈先,谢美萍,等.基于K近邻非参数回归的短时交通流预测方法[J].系统工程理论与实践,2010,30(2):376-384.[ZHANG T,CHEN X,XIE M P,et al.KNN based nonparametric regression method for shortterm traffic flow forecasting[J].Systems Engineering-Theory&Practice,2010,30(2):376-384.][9]谢俏,李斌斌,何建涛,等.基于非参数回归的城轨实时进出站客流预测[J].都市快轨交通,2017,30(2):32-36,41.[XIE Q,LI B B,HE J T,et al.Nonparametric regression model based real-time forecast for urban railway stations’entrance and exit passenger flow[J].Urban Rapid Rail Transit,2017,30(2):32-36,41.][10]黄晓琴.交通客流时间序列数据的聚类挖掘研究[D].成都:电子科技大学,2015.[HUANG XQ.Research on clustering mining for passenger flow time series[D].Chengdu:University of Electronic Science and Technology of China,2015.][11]徐波,于劲松,李行善.基于路径约束的动态时间规整方法研究[J].系统工程与电子技术,2004(1):103-105.[XU B,YU J S,LI X S.Research of dynamic time warping approach based on path constraint[J].Systems Engineering and Electronics,2004(1):103-105.]。

KNN算法介绍与参数调优K近邻法(k-nearest neighbors,KNN)是一种很基本的机器学习方法了，在我们平常的生活中也会不自主的应用。

比如，我们判断一个人的人品，只需要观察他来往最密切的几个人的人品好坏就可以得出了。

这里就运用了KNN的思想。

KNN方法既可以做分类，也可以做回归，这点和决策树算法相同。

KNN做回归和分类的主要区别在于最后做预测时候的决策方式不同。

KNN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。

而KNN 做回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。

由于两者区别不大，虽然本文主要是讲解KNN的分类方法，但思想对KNN的回归方法也适用。

由于scikit-learn里只使用了蛮力实现(brute-force)，KD树实现(KDTree)和球树(BallTree)实现，本文只讨论这几种算法的实现原理。

1. KNN算法三要素KNN算法我们主要要考虑三个重要的要素，对于固定的训练集，只要这三点确定了，算法的预测方式也就决定了。

这三个最终的要素是k值的选取，距离度量的方式和分类决策规则。

对于分类决策规则，一般都是使用前面提到的多数表决法。

所以我们重点是关注与k值的选择和距离的度量方式。

对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。

选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。

这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

离群值检测算法和kmeans离群值检测算法（Outlier Detection）和K均值聚类算法（K-means Clustering）是机器学习和数据分析领域中两个不同的概念。

1. 离群值检测算法（Outlier Detection）：离群值指的是在数据集中与其他样本明显不同的异常数据点。

离群值检测算法的目标是识别这些异常点，这些异常点可能是由于数据损坏、错误采样、异常行为等原因导致的。

离群值检测是一种无监督学习任务，它不需要事先有标记的异常样本。

常见的离群值检测算法包括：-基于统计方法的离群值检测算法：例如基于均值和标准差的Z-Score方法、基于箱线图的IQR方法等。

-基于距离的离群值检测算法：例如基于密度的LOF（局部异常因子）算法、基于距离阈值的DBSCAN算法等。

-基于概率模型的离群值检测算法：例如高斯混合模型（GMM）方法等。

-基于深度学习的离群值检测算法：例如自编码器（Autoencoder）方法等。

2. K均值聚类算法（K-means Clustering）：K均值聚类是一种常见的无监督学习算法，用于将数据集中的样本分为K个类别或簇。

它的目标是将样本划分到K个簇中，使得每个样本与所属簇的中心（质心）的距离最小化。

K均值聚类算法的步骤如下：-随机选择K个初始质心。

-将每个样本分配到距离其最近的质心所在的簇。

-更新每个簇的质心，使其成为该簇中所有样本的平均值。

-重复上述两个步骤，直到质心不再发生显著变化或达到预定的迭代次数。

K均值聚类是一种迭代算法，结果可能受到初始质心的选择和迭代次数的影响。

它适用于数据集中簇结构明显的情况。

尽管离群值检测和K均值聚类都是无监督学习任务，但它们的目标和方法是不同的。

离群值检测是识别异常点，而K均值聚类是将数据样本划分为簇。

在实际应用中，可以将它们结合使用，对数据进行聚类后再检测离群值，以更好地理解数据的结构和异常情况。