加权算法(通用7篇)
加权算法 篇1
摘要:蓝牙定位问题中, 由于采样网格划分不够致密等原因, 如果测试点的位置并没有标记, 则会影响该点的定位结果精度。针对这种情况, 本文提出了一种利用对数衰减模型的加权质心定位算法。该方法首先使用对数衰减模型, 计算出强度值对应的距离;在此基础上, 应用强度值比值与距离的乘积作为加权因子的加权质心算法, 对未知坐标的Beacons进行定位。在固定环境下, 对算法进行测试, 实验结果表明, 与原始质心算法相比, 定位精度提高了约22%。
关键词:蓝牙定位,对数衰减模型,加权质心
定位算法是室内定位系统的关键, 定位结果的精确度很大程度上取决于定位算法。目前, 基于位置指纹的定位算法主要分为概率性算法和确定性算法[1,2,3,6]。由于环境多变, RSSI值并不稳定, 为了提高准确度, 将统计学中的概率引到定位中, 从而形成了基于概率的定位方法。确定性算法原理简单, 计算复杂度低, 但是应用到实际中定位精度不高。
本文实现了原始加权质心定位算法[3,4,5], 定位精度不尽如人意。所以提出了一种在信号衰减模型的基础上, 将信号强度比值与距离的乘积作为权重因子的改进加权质心定位算法, 定位精度有了明显的提高。
1 系统模型
1.1 对数衰减模型
通过大量的实验数据, 并通过计算机的拟合以及理论的辅助, 得到无论在室内还是室外, 接收端接收到的信号强度值与收发双方的距离是成一定对数变化的[7]。对于任意的接收端与发射端之间的距离, 路径损耗为:
根据路径损耗推导出信号强度与距信号源距离的关系:
根据公式 (2) 得出:
其中, PL (d0) 为参考距离d0处的路径损耗, r为路径传播损耗指数, d为接收端与发射端的实际距离, d0为参考距离, Pr (d) 为接收端距发射端d处的信号强度, Pr (d0) 为接收端距发射端d0处的信号强度。
1.2 加权质心算法
质心算法[3,4,5]的主要思想是:未知坐标点以某一范围内已知坐标的点构成多边形的质心作为自己的估计位置。加权质心算法主要是利用已知坐标点和未知坐标点之间接收的RSSI值计算权重, 通过权重决定已知坐标点对质心的影响程度。
已知m个采集点的坐标分别为, 根据对数衰减模型, 计算出每个采集点对应的距离值di, 我们设每个采集点对应的权值为, 应用距离加权的质心算法即可得到待测Beacon的位置坐标
2 定位算法的实现
2.1 改进的加权质心定位算法
对于Beacon来说, 环境对强度值的影响非常大。在固定环境中, 虽然信号强度值相同, 但是不同点对Beacon的距离有可能是不同的, 相应的权重也不相同[8]。所以, 在计算Beacon位置时, 不应该仅仅考虑收集到的强度值的影响, 而应该加入其他的修正方法。否则, 可能导致定位误差变大。
针对已有的加权质心定位算法的缺陷, 本文做的改进策略是把各采集点接收到的Beacon信号强度的比值与距离的乘积, 作为每个采集点的权值, 这样做既可以体现不同Beacon对采集点的影响, 也可以使环境改变时权值基本保持不变。
对于m个采集点, m个采集点测得的信号强度为。定位算法如图1所示。
则权值为
最终得到改进的加权质心计算公式为
2.2 实验测试及结果分析
利用Matlab对本文提出的加权质心算法进行仿真分析。实验环境为7m×18m区域, 采集点均匀分布在3×8网格内, Beacons均匀分布在3×10网格内, 网格间隔均为2m。采集点数为24个, Beacons数为30个。在实验中, 所有数据点强度值为100次实验的平均值。
在距离的倒数作为权值的质心算法中, 设d0=1, 根据测得的数据, 分别计算出对数衰减模型中, 30个未知点对应的未知参数r和Pr (d0) , 从而求得方程。接着, 根据1.2中所述, 计算出了30个未知点的坐标。在改进的加权质心算法中, 未知点坐标的误差和原始坐标误差如图2和表1所示。
从图2可以看出, 改进后的定位算法比原始定位算法精度有明显的提高, 提高了约22%。
3 结语
本文提出了基于信号强度比值和距离乘积作为权重因子的加权质心算法, 该方法考虑了不同距离对定位结果的影响, 减小了距离相同, 方向不同的点信号强度对定位结果的影响, 降低了环境对定位结果的影响。通过与距离倒数作为权重因子的质心算法比较, 实验结果表明, 定位精度均值有明显的提高。
参考文献
[1]曹喆.基于低功耗蓝牙和位置指纹的室内定位系统的研究与实现[D].云南大学, 2014.
[2]Wenzhe Zhang, Lei Wang.INBS:An Improved Naive Bayes Simple Learning Approach for Accurate Indoor Localization[C].Conference on Communications (ICC) .IEEE, 2014, 148-153.
[3]纪程程.基于接收信号强度测量的室内定位技术研究[D].山东师范大学, 2013.
[4]陈维克, 李文锋, 首珩, 等.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报, 2006, 30 (2) :265-268.
[5]杨新宇, 孔庆茹, 戴湘军.一种改进的加权质心定位算法[J].西安交通大学学报, 2010, 44 (8) :1-4.
[6]Gholoobi A, Stavrou S.RSS Based Localization Using a New WKNN Approach[C].Computational Intelligence, Communication Systems and Networks (CICSy N) , 2015 7th International Conference on.IEEE, 2015, 27-30.
[7]Rida, M.E, Liu F, Jadi, Y, et al.Indoor Location Position Based on Bluetooth Signal Strength[C].Information Science and Control Engineering (ICISCE) , 2015 2nd International Conference on.IEEE, 2015:769-773.
[8]Park S, Savvides A, Srivastava M B.Sensor Sim:a simulation framework for sensor networks.[C].In Proceedings of MSWi M.2000:104-111.
基于时间加权的协同过滤算法研究 篇2
推荐系统是为解决Internet上的信息过载问题而提出的一种智能代理系统,能从Internet的大量信息中向用户推荐出符合其兴趣偏好或需求的资源[1]。个性化推荐系统中,应用最成功的算法之一是最近邻居的协同过滤算法。协同过滤算法主要有基于用户的和基于项目的两种算法[2]。基本思想是通过计算目标用户与各个基本用户对项目评分之间的相似性,搜索目标用户的最近邻居,然后由最近邻居的评分数据向目标用户产生推荐,即目标用户对未评分项目的评分可以通过最近邻居对该项目评分的加权平均值进行逼近,从而产生推荐[3]。
用户的兴趣偏好是随着时间动态漂移,要求推荐系统能实时地向用户推荐新颖的资源。但传统的协同过滤推荐算法并没有考虑用户的兴趣随时间的推移而发生变化,导致推荐的信息可能是过时的或不是用户当前最感兴趣的信息,影响了算法的准确性。 因此,本文在传统协同过滤算法的基础上,提出了基于时间加权的协同过滤算法。并利用实验数据集对传统算法和本文提出的改进算法的精确度进行了比较。
1 时间加权的协同过滤技术
1.1 问题分析
具体用户对各个项目的评分不是同时发生的,用户对项目的评分随着时间的推移会发生变化,这种变化反映了用户兴趣的漂移。为了使推荐系统能够及时跟踪用户兴趣漂移,本文认为用户的最近评分值相对比过去的评分值的重要性大。如果将用户在不同时间段的兴趣同等对待,则算法很难预测用户当前的兴趣。例如用户上个时间段对幽默剧评分较高,而下个时间段用户对战争剧产生兴趣,对战争剧也赋予较高的评分。按照传统的协同过滤算法计算,如果最近邻居用户对当前用户未评分项目的评分值相同或相近,系统可能会把幽默剧和战争剧都推荐给用户,但显然幽默剧不是用户当前的最新兴趣。针对这个问题,在预测推荐项目集的过程中对算法进行改进,把时间权重赋予具体的评分值,每个评分值都有一个唯一的权重值,并且用户最近的评分值被逻辑斯谛函数赋予较大的权重,过去评分值赋予较小的权重,强调用户最新的评分值反映用户当前的兴趣度。
1.2 时间加权的协同过滤算法过程
(1) 输入数据表达
输入通常表示为m×n的用户-项评估矩阵Rmn, m表示用户数,n表示项数, rij表示第i个用户对第j个项目的评估数值。
(2) 时间加权的最近邻居形成
协同过滤最重要的步骤是目标用户邻居的形成。邻居是指与目标用户具有相同兴趣的用户。两个用户间的相似性用相似度sim(i,j)度量。邻居关系的计算是为了对每一个用户u找到一个邻居用户集合Neighboru={n1,n2,…,nm},u∉Neighbor,使得sim(u,n1)>sim(u,n2)>…>sim(u,nm)。
用户相似性的度量主要包括三种方法:余弦相似性,Pearson相关相似性,修正的余弦相似性[5]。本文采用Pearson相关相似性计算用户的最近邻居。Pearson相关相似性为:
其中,Iui表示用户u和用户i共同评分的项目集合, ri,c表示用户i对项目c的评分,
(3) 加权预测推荐项目集合
得到目标用户最近邻居集合后,设目标用户u已评价项目集合为Iu,则目标用户u对任意项j(j∉Iu)的预测评分可以通过邻居用户i对项目j的评分得到,计算方法为[6]:
其中;sim(u,i)表示表示目标用户u与最近邻居用户i的相似性度量,ri,j表示用户i对项目j的评分。
为了准确计算用户的当前兴趣,改进的算法用logistic(tu,j)赋予每个评分一个唯一权重,用ri,j×logistc(ti,j)代替ri,j,缩放了原始评分的大小,也就是说,用户最近数据贡献度更大,过去数据反映用户以往的偏好,因此占较小的权重。逻辑斯谛函数为:
logistic(tu,j)是单调递增函数,输出值随时间t一直增加并且权重值始终保持在(0,1)的范围内。tu,j表示任意用户u在t时刻对项目j的评分值。笔者在实验前,预先应用标准化变量转换将时间变量t的范围转化为-1到1。在这个范围中,它们的行为几近线性[4],并且时间变量t的微小变化会导致权重值的微小变化,从而推荐算法能更精确地跟踪用户的兴趣转移。
通过上述方法预测用户对未评分项目的评分,然后取其中N个排在前面且不属于Iu的项作为推荐集。
1.3 改进算法描述
整个算法的运算步骤包括算法的输入、输出和运算过程。
1) 输入
(1)用户-项矩阵,m个用户对n个项目的评分;
(2)相似性度量sim,共同评分的项目集合Iui,推荐项目数N。
2) 输出
任意用户u和top-N推荐集。
3) 算法过程
(1)根据式(1)计算任意用户u和任意用户i(i∈Neighboru)的相似性sim(u,i)。
本文选择前20-30的相似用户作为目标用户的邻居用户,因为在这个范围的邻居数目对于预测当前目标用户的兴趣是个比较好的选择[7]。
(2)根据邻居用户在项目j的评价分,根据式(2)预测目标用户u对项目j的评价值Pu,j 。
(3)根据Pu,j的大小从高到低排序,选取前N项推荐给目标用户u。
2 实验结果
2.1 数据集
实验数据采用美国Minnesota大学GroupLens项目组提供的Movielens数据集(http://www.cs.umn.edu/research/GroupLens/
index.html)。该数据集包括943个用户对1682部电影的100,000条评分记录,每个用户至少对20部电影进行了评分,数据集中包含本文必要的时间属性,选用u1.base 数据集中的记录为基本用户,对u1.test数据集中的目标用户进行推荐测试。
2.2 度量标准
平均误差MAE(Mean Absolute Error)评价标准,是由Shardanand&Mases和Sarwar提出的,用于评价系统预测的性能。本文采用MAE进行评价。MAE用于度量预测值与实际值之间的偏差,偏差越小,预测的精度越高,推荐质量越高。MAE的定义:
pi是预测值,qi是实际评分,预测项目个数为N。
2.3 实验结果
在验证算法的有效性时,将目标用户最近邻居个数从20增加到30(间隔为2),查看不同的邻居数量大小对算法精确度的影响。为了验证本文提出的基于时间加权的协同过滤算法的有效性,与传统的协同过滤算法进行了实验比较。结果如图1所示。
从图1得,对于不同的邻居数量大小,基于时间加权的改进算法的MAE值均小于传统的协同过滤算法。由此可知,本文提出的算法比传统的协同过滤算法的推荐质量更高。
2.4 结论和进一步研究工作
本文提出的算法与传统协同过滤算法的最大不同是:考虑了用户兴趣随时间变化的问题,并且逻辑斯谛函数对时间变量的变化更为敏感,使推荐算法能更精确地跟踪用户的兴趣漂移。实验结果表明,基于时间加权的协同过滤算法显著地提高了推荐质量。后期研究工作是研究时间权重对具体用户兴趣的影响,因为每个用户兴趣变化的时间趋势是不同的,为每个用户制定具体的变化趋势应该会取得更好的推荐效果。
摘要:协同过滤算法是目前个性化推荐系统中应用最成功的推荐算法之一,但传统的算法没有考虑用户兴趣漂移的问题,导致推荐系统的推荐质量下降。针对这个问题,提出了基于时间加权的协同过滤算法。实验表明,改进的算法提高了推荐系统的推荐质量。
关键词:协同过滤,兴趣漂移,时间权重,推荐系统,平均误差
参考文献
[1]吴丽花,刘鲁.个性化推荐系统用户建模综述[J].情报学报,2006,25(1):55-56.
[2]Deshpande M,Karypis G.Item-based Top-N Recommendation Algo-rithms[J].ACM Transactions on Information Systems,2004,22(1):143-168.
[3]李涛,王建东,叶飞跃.一种基于用户聚类的协同过滤推荐算法[J].系统工程与电子技术,2007,29(7):1177-1178.
[4]Michael J A,Berry Gordon S Linoff.数据挖掘技术[M].机械工业出版社,2006:151-152.
[5]Sarwar B,Karypis G,Konstan J,et al.Item-Based collaborative filteringrecommendation algorithms[C]//Proceedings of the 10th InternationalWorld Wide Web Conference,2001:285-295.
[6]Breese J,Heckerman D,Kadie C.Empirical analysis of predictive algo-rithms for collaborative filtering[C]//Proceedings of the 14th Confer-ence on Uncertainty in artificial Intelligent,1998:43-52.
一种基于属性加权的决策树算法 篇3
ID3算法和C4.5算法应用于探井生产决策支持系统发现在解决复杂决策的问题准确性差的问题,由于基于信息墒的算法都没有考虑在实际应用中不同属性对决策结果影响的程度,并且由于在计算信息墒的过程中计算量大,算法复杂度高,导致对于探井生产管理决策支持系统中大数据量的计算存在计算准确率低。本文提出一种基于属性约简的加权决策树算法,根据不同属性对决策影响程度的不同进行加权,以提高决策结论准确性,实验结果表明,相比ID3和C4.5算法,基于属性约简的加权决策树算法应用于探井生产决策支持系统中有效地提高了决策的准确率,决策树算法的核心是分裂节点的选取,本文首先介绍决策树算法ID3和C4.5,然后介绍属性加权算法,以及权值选取标准,最后通过对实际探井数据测试,说明算法改进后的效果。
2 决策树算法简介
2.1 ID3算法
ID3算法[1]是一种基于信息熵的决策树学习算法,是决策树算法的代表。ID3算法把Shannon信息论引入到了决策树算法中,采用分治策略。在决策树各级结点上选择属性时,检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止,最后得到一棵决策树,对新的样本进行分类。
2.2 C4.5算法
C4.5算法是在ID3算法的基础上增加了对连续型属性和属性值空缺情况的处理,对树剪枝和生成规则也有了较成熟的方法。与ID3不同,C4.5采用基于信息增益比的方法选择测试属性。
C4.5算法基本思想是把连续值属性离散化。若A是在连续区间取值的连续型属性,首先将训练集X的样本根据属性A的值按升序排列为a1,a2,…,am(m为训练集的样本数)。如果A有n种取值,则对每个取值vj(j=1,2,…,n)将所有的记录进行划分。这些记录被分成两个部分:一部分落在vj的范围内,而另一部分则大于vj。针对每个划分,分别计算增益比率,选择增益最大的划分来对相应的属性进行离散化。
3 基于属性加权的决策树算法
本文采用对属性加权的方法标记属性的重要性,根据不同属性对决策结果的影响程度不同,计算属性的权值,使对决策结果影响程度越大,也就是越重要的属性权值越大。在建立决策树的过程中每次选择权值最大的属性作为分裂节点。
3.1 属性约简
属性约简[3]是粗集理论[6]的核心内容之一,在数据库系统中,经常存在大量冗余的信息,为了减少冗余信息,提高数据库蕴含知识的可理解性,人们在属性约简上已做了很多工作,提出了一些比较有效的方法,例如基于条件熵的决策表约简[7]、基于可辨识矩阵的属性约简等等。本文利用属性约简方法对属性进行约减,去掉不重要的属性,再利用约简之后获取的可辨识矩阵进行权值计算。
属性简约算法是在保持分类能力不变的前提下,逐个约去冗余的属性,直到不再有冗余的属性,此时得到的属性集是最小属性集。
定义1:令R为等价关系族,设P⊆R,且P≠Φ,则P中所有等价关系的交集称为 P上的不可分辨关系,记作IND(P),IND (P)也是一种等价关系。
定义2:设K=(U, A)为一个信息系统,其中U为论域,A为属性的非空有限集合。若P∈A 是满足IND (P)= IND (A)的极小属性子集,则称 P为A 的一个约简。
定义3:(可辨识矩阵).令决策表系统S=< U,R,V,f >,R=C∪D是属性集合,子集C={ai|i=1,2, …,m}是条件属性集合,D={d}是决策属性集合,U={x1,x2,…,xn}是论域,ai(xj)是样本xj在属性ai上的取值。CD(i,j)表示可辨识矩阵中第i行j列的元素,则可辨识矩阵CD定义为
undefined
其中i,j=1,2,…,n
为了便于计算,本文把可辨识矩阵进行了量化,如下式:
undefined
其中i,j=1,2,…,n
属性约简的实现:
第1步:建立可辨识矩阵CD。在给定的数据矩阵M×N的基础上,把属性值两两比较,相同为0,不同为1,则可得到(M-1)!×N的可辨识矩阵。其中,前N-1列为条件属性,最后1列为决策属性。
第2步:逐个判定CD中的任一列,若删除第i列,对应的属性为ai(ai∈C),若IND(C)=IND(C-{ai}),则ai可以约去,删除CD中的第i列,属性子集C’=C-{ai};若IND(C)≠IND(C-{ai}),则ai不可以约去;
第3步:继续检查CD中每个属性是否能被约去,直到出现某个属性子集C’’中的每个属性都不能被约去为止,此时该属性子集C’’即为所有的属性简约。
3.2 属性加权
探井生产管理决策支持系统中处理的属性数据多数是连续型数据,而建立决策树必须使用离散化的属性值,因此在选择条件属性后必须对连续的属性值进行离散化[8]。本文对连续属性值离散化的方法采取二值分裂法,方法如下:
对于连续属性ai,首先对属性值由小到大排序:b0,b1,…,bn,其候选断点可取为
undefined
针对每个断点ci分别计算信息熵ei,选取ei最小的断点ci作为分裂点。一般信息熵越小,说明集合中个别决策属性值占主导地位,因此混乱程度越小。选取信息墒最小的断点cmin作为连续属性ai离散化的分裂点。
对离散化后的数据集建立可辨识矩阵CD,对CD进行属性约简。得到约简后的可辨识矩阵C’’。属性ai权值twi计算过程如下:
(1)计算属性ai在数值矩阵C’’中出现次数Mi:
undefined
其中,i=1,2,…,k,C’’(j,i)表示C’’中j行i列的数据。
(2)计算属性ai的频度:
undefined,其中,i=1,2,…,k
(3)计算属性ai的权值:
undefined, 0
其中,i=1,2,…,k,所有属性的权值之和满足:undefined。
表1是探井进尺调整决策过程利用加权算法计算的属性权值结果,对决策结果影响程度大的属性权值较大。
3.3 基于属性加权的决策树算法
把每个属性的权值作为属性对决策结果的影响程度,每次选择权值最大的属性为分裂属性,即对决策结果影响程度最大的属性作为分裂节点。
基于属性加权的决策树算法的具体建立步骤如下:
输入:训练样本samples;属性列表attribute_list;
输出:一棵判定树Generate_Decision_Tree(samples, attribute_list)。
(1)创建节点N;
(2)如果 samples都在同一类C,返回N作为叶节点,以类C标记;
(3)如果 attribute_list为空, 返回N作为叶节点,用samples中最普通的类标记;
(4)计算attribute_list中每个属性的权值;
(5)选择attribute_list中具有最大权值的属性test_attribute;
(6)标记节点N为test_attribute;
(7)对于每一个test_attribute中的已知值ai;
(8)由节点N长出一个条件为test_attribute= ai 的分支;
(9)设si为samples样本中test_attribute= ai的集合;
(10)如果si为空,加上一个树叶,用samples中最普通的类标记。否则,加上一个由Generate_Decision_Tree (si, (attribute_list-test_attribute))返回的节点。
上述建树过程是一个递归过程,其终止条件为:①给定节点的所有样本属于同一类(步骤2);②没有剩余属性可以用来进一步划分样本(步骤3);③没有样本满足test_attribute = ai (步骤10)。
算法流程如图1所示。
4 实验结果比较
实验采用探井生产管理决策支持系统中的下套管决策过程构建决策树。下套管决策过程所需数据包括测井数据和录井数据,其中测井数据记录每口井每个小层的测井属性数据及其测井解释结果;录井数据记录、录取钻井过程中的各种相关信息,主要包含气测综合录井解释成果数据、定量荧光分析数据、罐顶气评价成果数据等不同类别数据。
下套管决策过程的目的是根据录井数据推理出每口井每个小层含油、气、水产状解释结果。实验选择了气测综合录井解释成果数据、罐顶气评价成果数据及地化岩石热解分析储层含油气评价数据三种录井数据分别构建决策树。实验主要分为五个阶段:
第一步,确定一口测试井,选取聚类属性,聚类求参考井。
第二步,根据参考井,选取参考井在录井表中的小层属性数据,将参考井各小层的测井解释结果作为最后一列加入选出的录井小层数据,构成训练样本。
第三步,根据训练样本,将测井解释结果作为决策属性,使用决策树算法,建立决策树。
第四步,根据已建好的决策树推理出If-Then决策规则。
第五步,选取测试井小层在录井表中的属性数据,根据决策规则推理出测试井小层的决策结果。
实验按以上步骤选取已完钻井的相关数据,把利用属性加权算法、ID3算法、C4.5算法获得的决策结果与数据库中已完钻井的实际解释结果数据相比较,以测试三种不同算法的平均准确率,验证利用属性加权算法的改善决策准确度的有效性。
实验结果如表2所示。表2中各字段的含义:井号即为测试井名,层位是测试井对应的段层,底界深度和顶界深度为段层中一个小层的底界和顶界,测井结果是测试井小层对应的正确解释结果,ID3算法、C4.5算法和属性加权算法分别是三种决策树算法推理出的分类结果。将三种算法推理出的结果与测井结果进行比较,与测井结果一致,说明推理正确。统计计算平均准确率。
由实验结果表3看出,属性加权决策树算法比ID3算法的平均准确率高出近12个百分点,比C4.5算法高出4个百分点,实验效果显著。
5 结束语
本文主要根据实际应用系统研究决策树算法,针对ID3算法和C4.5算法在复杂决策问题准确性差的问题,将粗集理论与决策树有机结合,提出基于属性加权的决策树算法。实验表明属性加权算法准确率较高。
参考文献
[1]QUINLAN J R.Induction of Decision Tree[J].Machine Learning.1986.81-106
[2]BANFIELD R E,HALL L O,BOWYER K W.A Comparison of Decision Tree Ensemble Creation Techniques[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007.173?180
[3]ZDZISLAW P.Rough set theory[J].Kunstliche Intelligenz.2001,15(3):38-39
[4]LIU L L,ANDREW K.C.W,WANG Y.A Global Optimal Algorithm for Class-Dependent Discretization of Continuous Data[J].Intelligent Data Analysis.2004.151-170
[5]HU Keyun,LU Yunchang,SHI Chunyi.Feature Ranking in Rough Sets[J].AI Communications,2003,16:41-50
[6]王国胤.Rough集理论与知识获取[M].西安:交通大学出版社,2001.
[7]王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,7(25):759-766
[8]谢宏,程浩忠,牛东晓.基于信息熵的粗糙集连续属性离散化算法[J].计算机学报,2005,1570-1573
[9]吴成东,许可,韩中华,裴涛.基于粗糙集和决策树的数据挖掘方法[J].东北大学学报,2006,27(5):481-484
[10]乔梅,韩文秀.基于Rough集的决策树算法[J].天津大学学报,2005,138(9):842-846
加权算法 篇4
图像信号在形成和传输过程中, 由于噪声的引入而使图像质量下降。而椒盐噪声是导致图像信号质量下降的主要噪声之一, 这种噪声表现为某一像素相对于其邻域内的其它像素的灰度值突变而与图像中的边缘细节一样具有较大的梯度值, 于是给图像分析工作造成极大的困难[1]。如何将图像中的噪声去除并且能够保持图像特征是一个重要挑战, 图像去噪已成为图像处理和计算机视觉的重要研究内容。对于椒盐噪声的去除, 比较传统的方法是非线性中值 ( SM) 滤波[2]。SM 滤波虽然在低噪声率时能较好地去除图像中的椒盐噪声, 但依然存在一些问题:由于算法对图像的所有像素都进行处理, 使得未被噪声污染像素的灰度值也改变了;在噪声强度增加时, 滤波效果很差。为了改善这种问题, 出现了多种基于中值滤波的改进算法[3]。
一些学者提出如自适应中值滤波 (Adaptive median filter, AMF) [4], 开关中值滤波 (Switch median filter, SWF) [5], 极值中值滤波 (Extremum median filter, EMF) [6,7], 加权中值滤波 (Weighted median filter, WMF) [8], 这些算法都在中值滤波的性能方面做了很多改进, 但在实际应用当中都有各自的优缺点。AMF具有较为优越的滤波性能, 可自适应调整窗口尺寸, 但随着噪声密度的增加, 保护细节的能力快速下降;SWF在噪声密度低时效果较好, 其性能随着输入图像信噪比的降低接近于标准中值滤波;EMF虽然是很优秀的滤波算法, 在一定程度上可以减少误差的累计传播, 但在噪声检测上存在不足, 尤其在高噪声情况下, 漏检情况尤为明显;WMF通过加权, 虽然降低了细节的损失, 但同时去噪声性能也下降了。
本文基于以上问题提出了一种有效的检测和滤波算法, 并且在高噪声密度的情况下, 效果明显。该算法通过阈值检测出孤立噪声点, 再跟据中心像素点与邻域像素点之间的关系做进一步判断, 确定噪声点。然后根据该噪声点与其邻域点之间的距离关系和模糊关系, 找出适合的权重系数, 重新计算待处理像素点的灰度值, 从而实现噪声滤除。用该判断方法可以将图像细节更好地保留下来, 避免中值滤波盲目将图像中所有像素都进行滤波变换, 造成图像中细节信息大量丢失的后果, 同时使噪声点还原更接近真实值。
1 噪声检测
自然图像邻域之间存在很大相关性。某一点的灰度值和其周围点的灰度值非常接近, 除了孤立点 (一般认为是噪声) 外, 即使在边缘部分也是这样。在一幅图像中, 如果一个像素点的值远大于或小于其邻域的值, 也就是说, 该像素点与其邻域的相关性很小, 那么, 该点很可能已被噪声污染了。否则, 如果该值与其邻点值接近, 就应该是一个有效的信号点。
设Sm, n是一个中心在 (i, j) 、尺寸为ω×ω的窗口函数 (ω为奇数) , 通常取ω=3;δi, j (i, j) 为ω×ω窗口的中心像素, σm, n (m, n) 为ω×ω窗口中非中心像素, 其中 (m, n) ϵ{i-1, j-1}, (i-1, j) , (i-1, j+1) , (i, j-1) , (i, j+1) , (i+1, j-1) , (i+1, j) , (i+1, j+1) 。当ω=3取时, 算法实现步骤如下:
Step1:取ω=3, 即3×3窗口, 设定噪声阈值λ、ρ、β。
Step2:设定图像白椒盐噪声的灰度范围为[255-λ, 255], 黑椒盐噪声的灰度范围为[0, ρ]。
Step3:若窗口中心点δi, j (i, j) , ∈[255-λ, 255]∪[0, ρ]则计算窗口内非窗口中心元素σm, n (m, n) 与窗口中心像素δi, j (i, j) 的算子值, 其中:
设窗口中心点为δi, j (i, j) , 除中心点外的其邻域点为σm, n (m, n) , 中心点与其邻域点灰度值之间的差值的绝对值与阈值β进行比较。
其中, N为噪声点, S为信号点。
设n为中心点与其领域点之间差值的绝对值大于β的个数, 当n=0时, δi, j (i, j) 为信号点, 原值输出。当时n=8, δi, j (i, j) 为噪声点, 输出yi, j。当0<n<8时, 将窗口扩大至5×5, 判断δi, j (i, j) 是噪声点, 还是边缘信号点。可以保护边缘细节。
Step4:在文献[9]中给出了
阈值T应随着图像灰度分布的不同而自适应地调整, 依据人眼视觉的对数特性, 文中采用如下方法自适应确定阈值:
2 噪声滤除
经上述检测完毕确定某点是噪声点, 输出值为
yij=aδi, j (i, j) +bc (xm+dxn) , (m=1, 3, 5, 7, n=2, 4, 6, 8)
通过中心像素点与邻域点的距离位置关系建立模型如图1所示。以中心像素点为中心, 将中心像素点与其邻域像素点连接起来, 可构成8个等腰直角三角形。中心像素点到其邻域的距离分别是三角形的4条直角边和4条斜边, 取任意一个三角形得构建等式4c+4d=1, 计算c与d的值, 经计算可知d=0.7, c=0.15。
又由模糊集合论知, 它是以逻辑真值[0, 1]的模糊逻辑为基础的。模糊控制就是在模糊数学的基础上产生的。模糊集合的概念为:给定论域X, A={X}是论域X中的模糊集合的定义是
μA (x) →[0, 1]
隶属度函数是表示其特征的集合, μA (x) 可以解读成变量x隶属于集合A的程度, 若μA (x) 接近于1, 则x表示属于A的程度高, 若μA (x) 接近于0, 则表示属于A的程度低。假定被噪声污染的点, 其真实值为1, 分别考查δi, j (i, j) 和c (xm+dxn) 与真实值的模糊关系, 它们的取值分别在[0, 1]之间, 中心点δi, j (i, j) 与真实值更为接近, 取值相对较大, 得出a=0.8, b=0.2, 图像效果最佳。
3 仿真结果及性能分析
为了验证文中算法的有效性, 在这里给出了用文中算法和其他几种滤波算法对大小为256×256的标准lena图像进行滤波的结果 (如图2所示) 。从图中可以看出, 文中算法的主观视觉效果明显优于其它算法, 可在高密度噪声的情况下, 可基本将噪声滤除。
除进行视觉上的比较之外, 还可以进行客观的比较。一般采用峰值信噪比 (PSNR) 来衡量, 设图像大小为M×N, 原始图像的像素值为f (x, y) , 去噪后输出图像的像素值为g (x, y) , PSNR值定义为,
4 结束语
从以上的仿真实验可以看出, 本文提出的算法对椒盐噪声的滤波能力优于其他三种滤波算法。很多算法都是在噪声的检测上做的改进, 最终采用中值滤波算法来取代噪声点。本文着重在滤波过程中做了改进, 用本文算法去取代噪声点, 效果较中值更优。很多算法在低噪声的情况下可以获得较好的滤波效果。而本文算法在噪声密度高达的情况下, 效果仍然非常明显。通过客观的对比和主观视觉效果的对比, 本文提出的算法在性能上明显优于同类算法。
参考文献
[1]宋宇, 李满天, 孙立宁.基于相似度函数的图像椒盐噪声自适应滤除算法[J].自动化学报, 2007, 5 (5) :475-479.
[2]DONG Ji2yang, ZHANG Jun2yin.A nonlinear algorithm for the re-moval of salt and pepper noise from highly corrupted images[J].Journal of Optoelectronics.Laser, 2003, 14 (12) .
[3]王红梅, 李言俊, 张科.一种改进型椒盐噪声滤波算法[J].光电子.激光, 2007, 1 (1) :113-116.
[4]HwangH, Haddad R A.A Adaptive median filters:New algorithmsand results[J].IEEE Transaction on Image Processing, 1995, 4 (4) :499-502.
[5]Wang Z, Zhang D.Progressive switching median filter for the re-moval of mi pulse noise from highly corrupted mi ages[J].IEEETrans.OnCircuits and Systems-II:Analog and DigitalSignalProcessing, 1999, CAS-II, 46 (1) :78-80.
[6]Xing Zangju, Wang Shoujue, Deng Haojiang, et al.A new filteringalgorithm based on extremumand median value[J].Journal of Imageand Graphics, 2001, 6 (6) :533-536.
[7]Dong Jiyang, Zhang Junyin.Anonlinear algorithmfor the removal ofsalt and pepper noise from highly corrupted images[J].Journal ofOptoelectronics.Laser.2003, 14 (12) :1336-1339.
[8]Brownrigg D R K.The weighted median filter[J].Commun.Ass.Comput.Mach., 1984, 27 (8) :807-81.
加权算法 篇5
1离群点检测算法
1.1基于统计学的方法[3,4]
统计学方法又分为参数方法和非参数方法。参数方法假定正常数据的分布符合一个统计模型, 而离群点就是不遵循分布模型的点;非参数方法对数据作较少的假设, 常见的有使用直方图的方法和基于核密度估计[5]的方法。统计学方法的检测结果在统计上是无可非议的, 但检测的结果往往难以理解, 而且即使是非参数方法也需要用户提供参数, 例如用直方图进行离群点检测时, 箱的宽度的选择对检测的结果将产生很大的影响。
1.2基于邻近性的方法[6,7]
基于邻近性的方法比较直观易懂, 离群点就是远离其他点的点。基于距离的方法就是给定一个邻域半径, 如果某点邻域范围之内的点的数量如果小于某个阈值, 那么该点就被视为离群点, 邻域半径和相应的阈值将直接影响检测的结果。针对基于距离的检测只适用于全局离群点的检测的不足, 提出了基于密度的方法, 基于密度的检测方法将离群点定义为密度明显小于其邻域密度的点, 最经典的基于密度的方法就是LOF算法[6], 后续又提出了许多对LOF算法的改进和变种[8—10]。
1.3基于分类的方法[11]
分类离群点检测算法主要是针对有标号训练集的, 通过对标记训练集的学习, 可以得到分类模型, 基于分类模型就可以区分出正常数据点和离群点, 检测效果依赖于分类模型的质量。
1.4基于聚类的方法[12]
基于聚类的方法就是在聚类的基础上, 将不属于任何簇的以及小簇归为离群点的检测算法, 优点是可以实现无监督学习, 缺点是高度依赖于所选择的聚类算法。
本文主要关注基于邻近性的方法。基于邻近性的离群点检测, 都要进行数据点之间距离的计算, 常见的距离计算方法有欧氏距离、马氏距离、闵可夫斯基距离等, 这些距离都是综合考虑数据在各个维度上的差异, 但并没有考虑各个维度具体的影响有多大。针对不同属性对数据的局部离群因子的贡献的不同, 提出了一种计算距离时的加权策略。加权策略对数值属性和标称属性分别考虑, 数值属性在规范化的基础上根据标准差的不同, 赋予不同的权值, 而标称属性则通过信息熵来进行加权, 当数据既包含数值属性又包含标称属性时, 为此提供了了一种综合加权策略。在加权距离的基础上, 运用LOF算法的思想, 提高了离群点的检测精度, 通过实验进行了证明。
2 LOF算法
局部离群点因子 (local outlier factor, LOF) 算法[6]由Breunig等人于2000年提出, 主要思想是为每个数据点定义一个直观的局部离群点因子, 通过比较LOF值的大小, 就可以知道数据点的离群程度。LOF由数据点周围的密度与其邻域周围的密度的比值来体现, 考虑了数据分布的局部特性, 在实际的离群点检测中体现了良好的性能。
定义1k-距离邻域设D为数据集, 数据点的k-距离邻域包含到o的距离不大于distk (o) 的数据点的集合, 记作Nk (o) ,
dist (o, o') 为o和o'之间的距离, distk (o) 是数据点o的k-距离, 即o与其第k个最近邻之间的距离, distk (o) 满足以下性质:
为了克服某些离o特别近的点对o的局部密度的影响, 定义了可达距离的概念, 在计算o的局部密度时用可达距离代替实际距离可以起到光滑的效果。
定义2可达距离数据点o与o'之间的可达距离reachdistk (o←o') 为
reachdistk (o←o') =max{distk (o) , dist (o, o') }可达距离通常不对称, 即
reachdistk (o←o') ≠reachdistk (o'←o) 。
定义3局部可达密度数据点o的局部可达密度ldrk (o) 为
定义4局部离群因子数据点o的局部可达密度LOFk (o) 为
LOF算法就是根据给定的k值, 计算所有数据点的LOFk (o) , LOFk (o) 较大的点就是离群点。
3距离加权策略
从上述描述可以看出, 数据点的离群因子主要由两个因素决定, 一是k值的选取, 二是距离的度量, k值的选取通常取决于具体的应用环境, 本文主要探究距离的度量, 研究具体每个维度对两个对象的差异起到了多大的影响, 为每个维度赋予相应的权值。
3.1标称属性加权策略
x= (x1, x2, …, xm) , y= (y1, y2, …, ym) 为m维数据集D中的两个数据点, attr为属性集, attr中所有的属性都是标称属性, 那么可以定义x和y之间的距离d (x, y) 为:, wi为权重, qi为x和y在第i维的差异, 。wi的确定需要注意, 现在常见的做法是将每个属性同等看待, 这样显然是不科学的, 因为每个维度对于两点之间实际距离的贡献是不同的。
根据属性在所有数据点上的取值情况, 计算属性的信息熵, 熵的计算方法如下:
设属性A有n个取值, dom (A) ={A1, A2, …, An}, p (Ai) 表示取第i个值的概率, 属性A的信息熵信息熵反映了数据分布的混乱程度, 熵越大, 数据的分布越不规律。文献[8]指出从信息熵角度考虑, 离群点的存在使得数据集的不确定性增强, 而离群点所表现出的不确定性正是通过其在某些属性上的取值分布造成的。熵值较大的属性有可能正是由于离群点在该属性上引起的混乱造成的, 应该特别关注, 因此, 在计算距离时应该突出熵值较大的属性上的差异, 也就是赋予其较大的权值, 由此可以对wi进行量化, 。后续的实验证明了为每个属性赋予wi的权重提高了LOF算法离群点检测的准确率。
3.2数值属性加权策略
对于数值属性, 为了排除量纲的影响, 必须先进行数据的规范化。数据规范化的方法主要包括最小-最大规范化、z分数规范化以及小数定标规范化, 最小-最大规范化易受离群点的影响而使数据失真, 因此选用z分数规范化方法。属性A的取值vi经标准化处理以后变为vi', , μA为属性A取值的均值, 为了增强鲁棒性, sA取A的均值绝对偏差, 即
x= (x1, x2, …, xm) , y= (y1, y2, …, ym) 为m维数据集D中的两个数据点, attr为属性集, attr中所有的属性都是数值属性, 那么可以定义x和y之间的距离d (x, y) 为:, wi为权重, 继续使用标称属性加权的思路, 对于分布比较混乱的属性应重点关注, 但连续属性需要离散化才能求熵, 为此, 引入另外一种数据分布离散程度的度量指标—标准差。属性A的标准差, 在σA的基础上得到
3.3混合属性加权策略
在现实世界中, 许多数据集都是既包含标称属性, 又包含数值属性, 因此混合属性条件下的离群点检测研究也是非常重要的。对混合属性数据集的距离度量是在分别处理标称属性和数值属性的基础上综合加权。
设D为m+n维混合属性数据集, c Attr为标称属性的集合, ‖c Attr‖=m, n Attr为数值属性的集合, ‖n Attr‖=n, Entropies={e1, e2, …, em}为c Attr中属性的信息熵的集合, Deviations={d1, d2, …, dn}为n Attr中属性标准差的集合。根据上述假设, 给出数据集D上各属性的权重
使用此权重计算两数据点x和y的距离, , qi的计算方法同3.1节。
4算法复杂度分析
提出的加权策略比LOF需要额外的计算开销, 计算权值需要对数据集进行一次扫描, 增加的时间复杂度为o (N) , N为数据集的规模, 而LOF本来的复杂度为o (N2) , 所以用提出加权策略的时间复杂度为o (N) +o (N2) ≈o (N2) , 因此因加权引起的时间开销增加是可以接受的, 不会影响算法整体的复杂度。
5实验分析
为验证所提加权策略的有效性, 仿真实验分三步进行, 第一步在标称属性数据集上验证基于信息熵加权的有效性, 第二步在数值属性数据集上检验基于标准差加权的有效性, 第三步在混合属性数据集上研究综合加权的有效性。
5.1实验1
本实验在UCI Mushroom数据集上验证基于信息熵加权的有效性。Mushroom数据集共包含8 124条记录, 22个标称属性, 1个类别属性用来标记Mushroom是否有毒。本实验随机选取1 000条有毒Mushroom记录作为正常数据, 10条可食用Mushroom作为离群点, 分别用经典LOF算法以及本文提出的基于加权距离的LOF (以下简称WLOF) 算法进行离群点检测, 实验结果如图2所示。
5.2实验2
本实验在UCI Ecoli数据集上验证基于标准差加权的有效性。Ecoli数据集共包含336条记录, 7个数值属性, 1个类别属性。本文选取标号为“cp”的143条记录作为正常数据, 标号为“om L”、“im L”和“im S”的共9条记录作为离群点, 分别用LOF和WLOF进行检测, 为了说明数据规范化的必要性, 还是用未规范化的数据进行了检测, 用ULOF标记, 实验结果如图3所示。
5.3实验3
本实验选取UCI Statlog (Heart) 数据集来验证综合加权算法的有效性。Statlog数据集共包含270条记录, 6个数值属性, 7个标称属性, 1个类别属性。本实验选取标号为“1”的150条数据作为正常数据, 标号为“2”的10条数据作为离群点, 分别用LOF和WLOF进行检测, 实验结果如图4所示。
5.4实验分析
上述三个实验分别用标称属性数据集、数值属性数据集和混合属性数据集验证了所提的加权策略, 从结果的对比可以看出本文加权策略的有效性。实验1中k取任何值时WLOF的检测准确率都要大于或等于LOF, 因为对不同属性的加权可以使离群点的离群特性更加明显;实验2中虽然三种方法随着k的增长, 效果趋于相同, 但在k比较小时WLOF的效果还是要明显好于LOF和ULOF, ULOF的效果较差的原因是由于数据没有进行规范化, 这样在计算距离时可能会发生取值较大的属性覆盖了取值较小的属性之间的偏差;实验3在k=15和k=17时LOF的准确率高于WLOF;但随着k的增长, WLOF的检测准确率明显高于LOF。
6结束语
离群点检测过程需要用到数据点之间的距离度量, 本文提出了一种距离度量时的属性加权策略, 通过加权突出不同属性对数据点之间距离的贡献的不同, 使离群点与正常数据之间的区别更加显著, 仿真实验验证了加权策略的有效性。
参考文献
[1] Hawkins D.Identification of outliers.London:Chapman&Hall, 1980
[2] Han Jiawei, Kamber M, Pei Jian.Data Mining:Concepts and Techniques (third edition) .范明, 孟小峰, 译.北京:机械工业出版社, 2012:351—375Han Jiawei, Kamber M, Pei Juan Data Mininy:Concepts and Techniques (third edition) .Fan Ming, Meny Xiaofeng, transtated.Beijing:China Machine Press, 2012:351—375
[3] Rousseeuw P J, Hubert M.Robust statistics for outlier detection.Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery, 2011;1 (1) :73—79
[4] Eskin E.Anomaly detection over noisy data using learned probability distributions.Proceedings of the Int.Conf on Machine Learning, Stanford University, 2000:255—262
[5] Latecki L J, Lazarevic A, Pokrajac D.Outlier detection with kernel density functions.MLDM, 2007;4571:61—75
[6] Breunig M M, Kriegel H P, Ng R, et al.LOF:identifying densitybased local outliers.ACM SIGMOD Int Conf Management of Data, 2000:93—104
[7] Jin W, Tung A K H, Han J, et al.Ranking outliers using symmetric neighborhood relationship.Knowledge Discovery and Data Mining (PAKDD'06) , Singapore, 2006:577—593
[8] 胡彩平, 秦小麟.一种基于密度的局部离群点检测算法DLOF.计算机研究与发展, 2010;47 (12) :2110—2116Hu C P, Qin X L.A Density-based local outlier detecting algorithm.Journal of Computer Research and Development, 2010;47 (12) :2110—2116
[9] 王敬华, 赵新想, 张国燕, 等.NLOF:一种新的基于密度的局部离群点检测算法.计算机科学, 2013;40 (8) :181—185Wang J H, Zhao X X, Zhang G Y, et al.NLOF:a new density-based local outlier detecting algorithm.Computer Science, 2013;40 (8) :181 —185
[10] Ke Zhang, Hutter M, Jin Huidong.A new local distance-based outlier detection approach for scattered real-world data.Advances in Knowledge Discovery and Data Mining, 2009; (5476) :813—822
[11] Babu S, Widom J.Continuous queries over data streams.SIGMOD Record, 2001; (30) :109—120
加权算法 篇6
1 局部加权回归
局部加权回归算法(LOWESS)由C1eveland提出,并由C1eveland和Develin推广到多个自变量的情形,主要利用局部观测数据对欲拟合点进行多项式加权拟合,并用最小二乘法进行估计。它允许线性回归模型中的参数随着自变量的不同取值而变化,即不同的观测值对应于一组不同的参数,在自变量空间的任一点处给出回归函数的一个估计值。
1.1 变参数回归模型
对于单参变量来说,设{xi,yi},i=1,2,⋯,n.为n组观测值。建立如下模型
其中α0(xi),α1(xi),⋯αp(xi)为相对于xi的未知参数,εi,i=1,2,⋯n为独立同分布的随机误差项。p为事先给定的值。
1.2 相关概念
1.2.1 r次最近邻点
对每一个xi计算周围每一个点xm(m=1,2,⋯,n)到它的距离,记为dim=|xi-xm|。记hi为dim(m=1,2,⋯,n)中第r个小的值。令0
1.2.2 局部加权回归
对每一个点xi,在窗口内所有的xk上,k=1,2,⋯n,由权值函数可得到权值ωk(xi),使用带有权值ωk(xi)的加权最小二乘法对xi进行d阶多项式拟合,得到拟合值yi^。利用ωk(xi)得到yi^就称为局部加权回归。
1.3 权函数的确定
对于一系列观测点{xi,yi},i=1,2,3,⋅⋅⋅,n,给出一个权值函数W(x),满足:
1)|x|<1,W(x)>0;
2)W(-x)=W(x);
3)对于x≥0,W(x)是一个非增函数;
4)当|x|≥1时,W(x)=0。
满足上述条件的函数有很多,目前最常用的是三次权函数
还有形如下式的(n,m)型权函数
除上述两种权函数外还有其他的权函数,如高斯加权函数和正态型权函数。
1.4 参数估计
局部加权拟合方法应用于变参数模型(1.1),即对于任意给定的自变量空间的点xi,i=1,2,⋯,n,求α0(xi),α1(xi),⋯αp(xi)使得
达到最小
令
而
为对角矩阵,则由加权最小二乘理论可知x点处的参数向量α(x)的估计值为:
这里假设对任意的x,[X′W(x)X]-1均存在。因变量在x处的拟合值为
1.5 强局部加权回归
2 强局部加权回归算法实施流程
2.1 算法实施流程
1)选取适当的f,对每一个观测点xi,(i=1,2,⋯n)尽量以xi为中心选取窗口宽度。
2)定义区间内所有点的权数。权数由权值函数来确定。
3)利用最小二乘法对每个带有权值ωk(xi)的观测点(xi,yi),计算回归系数α(xi)的估计值,此时得到的yi^为在xi处的拟合值。
4)令B由式定义的4次方权值函数
5)对每一个i在{xi,yi}点处用δiωk(xi)代替原来的权值ωk(xi),利用最小二乘法进行d阶多项式拟合,计算新的yi^。
6)重复执行4)、5)R次,最后得到的就是强局部加权拟合值。
一般来说,利用强局部加权回归算法对观测点进行拟合时,多项式的阶数、权值函数、迭代次数以及窗口宽度是很重要的,但是前三个参数是可以预先给出来的。正常情况下,多项式阶数取1,迭代次数取2,权值函数取3次方权值函数已经足够。f是参加局部回归的观测值的个数占观测值个数的比例,n是观测值的个数,一般来说f的取值在1 3到2 3之间。本文我们选取f=0.5。r与f的取值一般没有确定的准则,其大小会影响平滑值的外观。增大r或f值,将会导致平滑程度的增加,而对于数据中潜在的细微变化模式则分辨率低,但噪音小。而对数据中大的变化模式的表现则比较好;而小的r或f值,则会使曲线非常粗糙。对于数据中潜在的细微的变化模式的分辨率则较高,但噪音大。对数据中大的变化模式的表现就比较差。
2.2 算法的程序实现
由于强加权局部最小二乘法中,大量运用了矩阵运算,比如矩阵的加减乘除、矩阵的迹,矩阵的转置和秩,以及求取矩阵的特征值特征向量,所以从网站上下载了一个关于矩阵运算的包JAMPACK,然后在次基础上编程实现算法,其中算法中的类图和条用关系:
图中各类的功能如下:
算法MAIN类的工程主类,用于调用其他的各类来完成最小二乘算法
JAMPACK包中包含了常用的矩阵类型和常用的矩阵算法的类,矩阵运算类包含了矩阵的乘除加减、求转置、求逆、求特征值和特征向量等运算类,对整个算法实现起了关键的支撑作用。
Weight类用于生成权重值K(i)的类,使得K满足高斯分布
Distance类用于计算样本点到拟合曲线的暂时距离。
3 结束语
文中对单自变量的强局部加权回归做了比较详细的介绍,并利用局部加权技术拟合变参数回归模型,通过实例,可以看出强局部加权回归很好的反映了变量之间的相互依赖关系。但是还是有些不足,当数据量巨大的时候,算法的运算量太大。单机耗费的时间会达到几天甚至更长时间。本文以后的工作就是将局部加权回归算法MapReduce化后部署到Hadoop云计算平台上运行,并用以解决实际问题。
参考文献
[1]McLeod A I.Robust Loess:S lowess[EB/OL].http://www.stats.uwo.ca/faculty/aim/2004/04-259/notes/RL.pdf.
[2]梅长林,张文修.利用局部加权拟合方法检验线性回归关系[J].系统科学与数学,2002(10):467-480.
[3]蒋乐天等基于强局部加权回归算法的软件老化趋势提取[J].上海交通大学学报,2006,11(4):1006-2467.
[4]董芳英,张帼奋.基因芯片数据标准化局部加权回归法权函数探究[J].浙江大学学报,2010(1).
[5]王国权.基于强局部甲醛回归算法的电力设备老化评估[J].华北电力大学,2009(1).
[6]李军华.云计算及若干数据挖掘算法的MapReduce化研究[J].电子科技大学,2010(3).
加权算法 篇7
被动传感器的测量一般包括方位角和俯仰角。由于被动传感器在搜索目标时不发射信号, 不容易被敌方目标发现, 因此被动传感器在军事防空领域获得了广泛的应用。被动传感器所涉及的一个重要研究内容是如何利用多个被动传感器对目标进行精确交叉定位。在过去的研究过程中, 人们提出了最大似然估计算法 (Maximum Likelihood Estimate, MLE) 、Stansfield算法、伪线性估计 (Pseudolinear Estimate, PLE) 和修正辅助变量估计 (Modified-Instrumental Variable estimate, MIV) 等算法[1,2,3]。文献[4]在目标的被动定位过程中, 采用了加权最小二乘估计方法, 也取得了较好的效果。针对被动传感器在机动目标跟踪的情况, 文献[5]应用自适应最小二乘方法, 取得了较好的跟踪结果。文献[6]利用被动定位所得的目标位置, 对运动目标采用不同滤波算法进行滤波, 并对比了不同滤波算法的跟踪性能。最近, 文献[7-9]又提出了一种几何约束最小二乘 (Geometric Constraint Least Square, GCLS) 测向交叉定位算法, 并给出了详细的数学推导和仿真实验。该算法巧妙地将传感器几何位置信息融入到提高测量数据的准确程度过程中, 在默认各个测向传感器误差相同的条件下, 取得了良好的实验效果。文献[7-9]也提到可以采用几何约束加权最小二乘法 (Geometric Constraint Weighted Least Square, GCWLS) 构造目标函数, 使之适用于多个传感器量测误差不同甚至相关的情况。但是, 在实验过程中发现, 直接采用GCWLS算法效果并不理想。究其原因, 是该算法没有考虑各个传感器的测角误差和径向距离对定位精度的影响, 本文从该问题出发, 提出了一种计算交叉点权值的方法, 在交叉定位过程中对不同交叉点进行加权处理, 能够较大幅度提高定位性能。本文算法是在GCWLS算法基础上的改进算法, 称之为改进的基于几何约束的加权被动定位算法 (Geometric Constraint Weighted Least Square Plus, GCWLS+) 。新算法在相同的优化函数以及相同的参数设置条件下, 具有更好的定位性能, 而且时间复杂度增加量较小。
1 基于几何约束的被动定位算法
在利用测向传感器进行目标定位的过程中, 如果只有两个传感器, 并且和目标不在一条直线上, 那么方位角测量值所指示直线的交叉点就是目标的估计位置。如果多个测向传感器进行交叉定位, 则会出现多个交叉点的情况, 如图1所示, 这就是交叉定位不一致现象。从多传感器融合的角度来看, 多个传感器融合之后的数据应该能够获得更精确的定位结果。几何约束最小二乘算法就是利用多个传感器自身的位置信息通过优化算法计算每个传感器观测值可能出现的偏差, 并以此修正各个传感器的观测值, 从而提高测量值的准确程度。
假定有三个测向传感器, 并以x轴为零点和顺时针旋转为正方向进行测量。测量值分别为和由于每个传感器存在量测误差, 因此测量值存在误差设测量值和精确值之间的关系为
假定各个传感器的位置事先知道, 传感器i到传感器j的角度θij通过计算可以得到。为了计算方便, 我们取θiT, θij∈[, 02π) 。下面定义角度
并将其限制在 (-π, π]。φijT其实就是传感器i和传感器j之间线段和传感器i和目标T之间线段的夹角。由式 (1) 、式 (2) 易知:
定理1:假设有三个传感器对同一目标进行观测, 如图2, 其中任意两个传感器和目标不在同一条直线上, 即θiT≠θij, i, j∈1{, , 2}3andi≠j, 若θˆijT已知, 则下式成立:
定理2:假设有三个传感器对目标进行观测, 其中任意两个传感器和目标不在同一条直线上, 即θiT≠θij, i, j∈1{, , 2}3andi≠j, 若传感器i和j之间的距离dij及相应的夹角θˆijT已知, 则下式成立:
定理1和定理2的详细证明参见文献[7]。
将式 (4) 或者式 (5) 作为约束条件, 并记为
则对于具有k>3个传感器的测向定位系统, 可以得到 (k-2) 个约束条件, 即:
下面讨论三维空间中的被动定位情况。在三维空间中, 被动传感器通常通过测量目标的俯仰角θ和偏转角φ对目标进行定位, 如图3所示。
定理3:假定有两个传感器分别处于不同位置, 并且两个传感器和目标三者不共线。两个传感器和点A在同一个平面上, AT是该平面的法线方向。则:
其中:i, j∈1{, 2}, i≠j;θij T和φij T是真实角度;θˆij T和φˆij T是包含量测值的角度;eθij T和eφij T是角度误差。
假定传感器都位于坐标系中的x-y平面上, 则:
其中:φij是第i个传感器和第j个传感器之间的角度。则下式成立:
定理3的证明过程参见文献[7]。与二维情况类似, 如果传感器多于两个, 此时可以获得多个与式 (11) 类似的约束条件。
在上面的讨论中, 利用三角函数获得了二维和三维空间中测向角度、传感器间角度以及传感器间距离三者的约束关系。下面我们利用加权最小二乘方法获得最小的测角误差, 如果令传感器之间的测角协方差矩阵为∑, 而e=[e1e2e3...]T则有
将式 (12) 作为目标函数, 式 (4) 和 (5) 作为非线性约束函数, 利用最优化方法求解各个测量值的测角误差ei并对测量值进行修正, 修正公式为
2 改进的基于几何约束的加权定位算法
在求交叉定位点的过程中, 两个测向传感器确定一个目标位置, 所以k个传感器可以确定Ck2个交叉点。由于优化算法的精度问题, 这些交叉点并不重合, 目标位置要进一步计算。文献[7]采用的计算办法是直接求多个交叉点的重心, 但是在实验中发现这种计算方式误差较大。原因是每一个交叉点的精度不相同, 对最终估计位置的贡献不一样。为了能够进一步的提高定位性能, 对交叉点误差的影响因素进行分析, 计算第i和第j个传感器交叉点的权值wij。此时目标的位置计算如下:
考虑到影响交叉点误差的因素有两个, 即:传感器的测角误差标准差σi和传感器到目标的距离ir。在计算权值的时候应该把这两个因素对定位精度的影响都考虑进去。由于目标的误差范围可以近似的计算为εi≈sin (σi) ri, 在标准差非常小的情况下再进一步近似, 从而获得第i个传感器的误差度量:
其中:ir表示第i个传感器到目标的径向距离, σi表示传感器i的误差标准差。由于目标位置此时尚未确定, 因此并不能得到ir的精确值, 只能通过估算得到其近似值, 例如通过计算各个交叉点的重心获得目标位置近似值。
由式 (15) 可知, 定位误差与测角标准差和径向距离成正比。为了计算每个交叉点的权值, 首先对每个传感器的误差度量值εi进行归一化, 即:
然后再计算每个交叉点的权值:
其中M (εˆi, εˆj) 是一个求均值的函数, 例如几何均值或者算术均值函数。
最后对所有交叉点权值wij进行归一化, 即:
由wij的定义可知, 当确定交叉点Pij的两个传感器测角误差较大时, 权值wij较小, 反之权值则较大;当确定交叉点的传感器与目标之间的距离ri和rj较大时, 权值wij较小, 反之权值则较大。交叉点权值计算方法步骤总结如下:
Step 1:利用式 (15) 计算每个传感器的误差度量;
Step 2:利用式 (16) 对每个传感器的误差度量进行归一化;
Step 3:利用式 (17) 计算各个交叉点的权值;
Step 4:利用式 (18) 对各个交叉点权值归一化。
对于二维空间三个传感器的被动定位问题, 改进后的基于几何约束的二维被动定位算法步骤如下:
Step 1:把定理1或定理2作为约束条件, 把式 (12) 作为目标函数, 利用最优化方法计算每个传感器的测量误差ie;
Step 2:利用式 (13) 计算修正过的量测值;
Step 3:传感器量测值两两结合, 再加上传感器的坐标, 计算出所有交叉点Pij;
Step 4:利用交叉点权值计算方法获得各个交叉点的权值wij;
Step 5:利用式 (14) 计算出目标位置。
对于三维空间的改进算法与上述算法类似, 不再赘述。
3 仿真实验及结果分析
为了验证改进算法的有效性, 从定位误差和时间复杂度两个方面入手, 分别对二维和三维情况进行仿真实验, 并对实验结果进行分析。其中, GCLS、GCWLS算法来自文献[7], GCWLS+是本文提出的改进算法。
3.1 实验1:二维空间中三个测向传感器交叉定位
传感器的位置分别是 (0, 0) 、 (100, 30) 和 (250, 0) , 目标的位置是 (100, 100) 。考虑到不同性能传感器组合可能会对算法结果产生影响, 因此实验中设置了6种不同情况的测量误差标准差组合。三个传感器的测角误差标准差 (Standard deviation) 如表1前3行所示, 单位为度。每一种情况都重复观测10 000次, 分别采用GCLS、GCWLS、GCWLS+三种方法进行目标定位, 并求取不同方法的定位误差。
表1表明, 本文算法与GCWLS算法和GCLS算法相比, 误差性能有较大提高。不论是采用定理1还是采用定理2都能取得几乎相同的误差结果。此外, 在各个传感器测量标准差相互差别较大的情况下, GCWLS的误差性能甚至比GCLS的误差性能差, 而本文算法由于考虑了径向距离对误差性能的影响, 因而误差在各种情况下都低于GCLS和GCWLS, 如表1第4、5列数据所示。这种情况在各个传感器测量误差完全相同但是都非常小的情况下也会出现, 如表1中第6列数据所示。
3.2 实验2:三维空间中三个测向传感器交叉定位
传感器的位置分别为 (0, 0, 0) 、 (200, 200, 0) 和 (100, 0, 0) , 目标的位置为 (250, 500, 100) 。由于不同性能传感器组合对算法误差性能有所影响, 因此设定了6种组合, 然后计算在不同组合条件下的误差性能。其中, 传感器的测角误差标准差设定如表2前6行所示, 单位为度。分别对目标重复观测10 000次。采用GCLS、GCWLS、GCWLS+三种方法对目标定位, 并求取不同方法的定位误差。
表2表明实验结果同二维空间中情况类似, 本文算法能够较大幅度提高目标定位性能。同样, GCWLS并不能很好处理在误差不相同情况下的定位问题, 如表2中第3、5列数据所示。甚至在传感器误差性能相同情况下, 定位效果也不理想, 如表2中第1列数据所示。但是采用本文算法能够有效改善这种状况, 在各种情况下误差都能大幅度降低, 能够提高定位的准确性。
3.3 实验3:时间复杂度分析
实验一和实验二运行1 000次所需要的时间如表3所示。表3表明, 改进算法与GCWLS算法时间复杂度基本相当, 而GCLS算法时间复杂度表现不稳定, 有时比GCWLS+大, 有时比GCWLS+小, 这是由于加权矩阵会影响优化过程所需要的时间。在实验一中, GCLS、GCWLS和GCWLS+三种算法时间复杂度依次增大的, 但是使用定理1或者定理2需要的时间复杂度则各有伯仲。
s
结束语
本文在GCWLS算法的基础上, 给出了一种交叉点权值的计算方法, 在传感器量测标准误差不相同的情况下, 取得了较好的定位性能。值得注意的是, 该算法与优化算法的精确程度息息相关。理想情况下, 利用优化算法得到的测量偏差值对各个测量值进行修正之后, 所有这些量测值计算出来的交叉点是重合的, 并不需要对各个交叉点进行加权。但是, 由于优化算法并不能保证每次都能得到精确解, 往往得到近似解或者是局部最优解。此时, 就需要采用本文提出的计算交叉点权值的办法进行加权, 从而获得更为精确的定位结果。
参考文献
[1]Gavish M, Weiss A J.Performance of analysis of bearing-only target location algorithms[J].IEEE Trans.on Aerospace and Electronic Systems (S0018-9251) , 1992, 28 (3) :817-827.
[2]Nardone S C, Lindgren A G, Gong K F.Fundamental properties and performance of conventional bearings-only target motion analysis[J].IEEE Trans.on Automatic Control (S0018-9286) , 1984, 29 (9) :775-787.
[3]Dogangay K, Ibal G.Instrumental variable estimator for3D bearings-only emitter localization[C]//Proceedings of the2nd International Conference on Intelligent Sensors, Sensor Networks and Information Processing, Melbourne, Australia, Dec5-8, 2005:63-68.
[4]刘宗香, 谢维信, 杨煊.网状被动传感器系统视线交叉目标定位方法[J].电子与信息学报, 2005, 27 (1) :17-20.LIU Zong-xiang, XIE Wei-xin, YANG Xuan.Target location method based on intersection of lines of sight in the netted passive sensor system[J].Journal of Electronics&Information Technology, 2005, 27 (1) :17-20.
[5]宋骊平, 姬红兵, 高新波.多站测角的机动目标最小二乘自适应跟踪算法[J].电子与信息学报, 2005, 27 (5) :793-796.SONG Li-ping, JI Hong-bing, GAO Xin-bo.Least-squares adaptive algorithm for bearings-only multi-sensor maneuvering target passive tracking[J].Journal of Electronics&Information Technology, 2005, 27 (5) :793-796.
[6]后小明.三站目标被动定位数据处理算法研究[J].电子与信息学报, 2007, 29 (3) :565-569.HOU Xiao-ming.Algorithm research for passive locating processing of three station target data[J].Journal of Electronics&Information Technology, 2007, 29 (3) :565-569.
[7]Bishop A N, Anderson B D O, Fidan B, et al.Bearing-only localization using geometrically constrained optimization[J].IEEE Trans.on Aerospace and Electronic Systems (S0018-9251) , 2009, 45 (1) :308-320.
[8]Bishop A N, Fidan B, Anderson B D O, et al.Optimality analysis of sensor-target geometries in passive localization:Part1–Bearing-only localization[C]//Proceedings of the3rd International Conference on Intelligent Sensors, Sensor Networks, and Information Processing, Melbourne, Australia, Dec3-6, 2007:7-12.