分布式识别(精选五篇)
分布式识别 篇1
遥感信息提取的主要对象是陆地表层系统中各类自然和人文要素,水体是其中主要的自然要素之一,具体表现为湖泊、河流、湿地等形态[1]。快速、准确地从卫星遥感影像上获取水体信息,已成为水资源调查及监测湿地保护、洪水灾害评估等领域的重要技术手段[2]。随着遥感技术的不断发展,水体大数据呈几何级数倍增,而传统的遥感图像处理软件数据处理能力有限,使得遥感图像的处理速度成为遥感技术在不同领域应用和发展的瓶颈。
为了解决信息提取中的数据密集与计算密集问题,满足对实时性要求较高的应用对速率的要求,并行计算受到国内外学者的普遍关注[3,4,5]。2004年,Google提出MapReduce[7,8]分布式计算模型。MapReduce模型隐藏了并行计算、数据分配、任务调度及负载均衡等复杂细节,可以实现自动伸缩的大规模并行计算。由于MapReduce编程模式简单,具有高性能和高容错而得到广泛的应用。
本文探讨将分布式并行计算思想应用于遥感图像的水体信息提取中,构建基于MapReduce的遥感图像水体识别模型。选取渭干河-库车河三角洲区域Landsat 8影像,利用水体指数模型、单波段阈值法、波谱间关系模型等进行水体信息自动提取的实验,水体识别效率得到了一定的提高。
1 MapReduce
1.1 MapReduce编程模型
MapReduce是一个处理超大数据集的分布式并行编程模型,它把整个任务拆分成多个子任务,并将这些任务分发给一个主节点(Name Node)。主节点将子任务进行分组并分发给自己管理的各个从节点(Data Node)共同完成。然后,通过整合各个节点的中间结果而得到最终结果。
在分布式计算中,MapReduce框架负责处理并行编程中分布式存储、工作调度以及网络通信等复杂问题,它把处理过程高度抽象为两个函数:Map和Reduce。Map负责把任务分解成多个子任务,Reduce负责把多个子任务处理的结果汇总起来。
1.2 MapReduce处理过程
MapReduce处理数据分为两个阶段:Map阶段和Reduce阶段。Map阶段开始前,要对输入数据进行“分片”(即将超大输入数据划分成大小相等的“数据块”)。每个Map任务接收一个数据“分片”,然后产生一个<key,value>键值对形式的中间结果。MapReduce模型将所有中间结果按照key值进行排序和合并,作为Reduce任务的输入。Reduce()函数接收一个如<key,(list of values)>形式的输入,合并key相同的value值,产生<key,value>对形式的最终输出。MapReduce的执行流程如图1所示。
2 基于分布式计算的水体识别
2.1 数据划分及组织形式
在海量遥感数据并行计算中,数据块的划分方式和数据分块的大小直接影响着并行计算的效率[9]。本研究采用矩形块方式切分每幅影像,以默认数据分块大小(64 MB)为单位,对研究区影像进行切分。选取开源的Hadoop为实验平台,基于HDFS(Hadoop Distributed File System)和HBase(Hadoop Database)的特点,将遥感影像文件存放到HDFS中。而其他元数据信息存入HBase中,并采取为同一数据块建立多个副本以提高数据块的可靠性与可用性(如图2所示为B0、B1等数据块存储在HDFS中的示例)。
2.2 基于MapReduce模型的的水体识别
常用的遥感影像水体信息提取方法主要是依据水体和其他地物在各个波段上光谱特征的差异(如图3所示)。利用单个波段或多个波段构造一定的水体提取模型,将水体和其他地物区分开来。本文主要选取单波段阈值法、谱间关系法和水体指数法对水体信息进行提取。
(1)单波段阈值法
利用某种地物与背景地物在某一波段上的反射率(或像元灰度值)的差异,确定某一数值为区分该地物和背景地物的方法,称为单波段阈值法[10]。本文选取TM5短波红外波段数据,通过选择一定的阈值T,小于该阈值的为水体,水体提取模型如下所示:
(2)谱间关系法
谱间关系法是多波段方法的一种,通过分析地物与水体的光谱特征属性,在Landsat TM影像上,水体对不同波长的光谱反射率随着波长的增加而减小,同时光谱反射率变化范围有限。早期研究表明,通过比较TM2与TM3的光谱值和以及TM4与TM5的光谱值和,可以有效增加水体与地物的光谱差异。而这一谱间关系特点是水体特有的,可以有效的区分水体信息[11]。
(3)水体指数法
水体指数法是水体识别应用最广泛的方法,它通过选取与水体提取紧密相关的多个波段,构建水体指数数学模型,增强水体与背景地物之间的反差,实现水体信息的提取。本研究选取较为经典的归一化植被指数(NDVI)、归一化差分水体指数(NDWI)[12]和改进归一化差异水体指数(MNDWI)[13]进行水体信息提取,其公式分别为:
其中,NIR代表近红外波段,即b4波段;Red代表红光波段,即b3波段;Green代表绿光波段,即b2波段;MIR代表短波红外波段,即b5或b7波段。
针对Landsat ETM+遥感数据,利用上述方法对研究区水体进行识别。Map函数处理划分后的遥感数据块并对水体信息进行提取,输出<影像名,地址>键值对。Reduce函数把所有key值(影像名)相同的键值对的value(影像地址)相加,输出<影像名,影像水体识别结果地址>键值对。
3 实验结果与分析
3.1 研究区及数据源
渭干河流域位于新疆阿克苏以东225公里的沙雅县境内,经纬度40°55'~41°20'N,82°30'~83°30'E。渭干河是塔里木河的支流之一,发源于天山北坡,由木扎尔特河、克孜尔河等六条支流汇合而成。研究选取2013年6月的渭干河Landsat 8卫星遥感影像作为实验数据,并对影像进行包括辐射定标以及大气校正的预处理。
3.2 实验环境
实验采用Hadoop的完全分布式模式进行,集群包括4台主机,其中1台作为主节点(Name Node),其余3台作为数据节点(Data Node)。在每台主机上安装Linux Ubuntu 12.04、Java环境、JDK 1.6和Hadoop 0.20,搭建基于Hadoop的并行水体识别集群系统。计算机的硬件配置详细信息如表1所示。
3.3 实验结果与分析
3.3.1 实验一正确性测试与分析
使用基于MapReduce的水体识别模型对渭干河-库车河三角洲地区进行水体信息提取,部分水体提取结果如图4所示。实验的验证样本为试验区域的高分辨率遥感影像,利用ENVI5.1软件对其进行监督分类得到真实参考源。
为了确定水体信息提取的精度和可靠性,使用错提率、kappa系数和总体精度等评价指标对5种分类结果进行评价(如表2所示)。
表2中,不同水体提取方法的精度由大到小顺序依次为:MNDWI>NDWI>NDVI>谱间关系法>单波段阈值法。归一化差异水体指数(MNDWI)能消除地形差异的影响,增强水体与建筑物的反差,因此识别率最高。而单波段阈值法只利用了水体在某一个波段上的特征,而忽略了水体在其他波段上的特征。此外,利用单波段阈值法不能很好地区分山区阴影与水体,影响了整体的识别精度。基于MapReduce的水体识别模型,5种水体指数提取精度都在90%以上,这表明了本文提出的模型具有较高的识别精度。
3.3.2 实验二可扩展性和伸缩性测试与分析
为了验证模型的可扩展性和伸缩性,通过控制计算节点个数和数据量进行以下实验。选取渭干河流域2013年的6幅Landsat 8影像,分别选取1幅、2幅、4幅、6幅影像进行水体提取实验。实验数据集D1={1,2,4,6}(单位:幅),影像详细信息如表3所示。
由实验一可知,使用归一化差异水体指数(MNDWI)对遥感图像进行水体提取的精度最高。因此,选用归一化水体指数进行水体识别并对比识别耗费时间。图5为计算节点不同的情况下,分别对1幅、2幅、3幅、4幅遥感图像进行水体识别所耗费的时间。
此处引入加速比作为一个评价指标。加速比是同一个任务在单节点上运行时间与在多个相同节点构成的并行系统上运行时间的比率,用来衡量并行系统或程序并行化的性能和效果。加速比的计算公式如下:
式中,Sp是加速比,T1是单节点下的运行时间,Tp是在有p个节点构成的并行系统中下运行时间。图6为不同数据量下并行加速比与计算节点的关系。
从图5、图6我们可以看出:(1)当数据量一定时,随着计算节点的线性增加,水体识别的时间线性降低。随着计算节点的增加,水体提取的加速比呈一定比例增加。当计算节点个数为2时,平均加速比为1.918;计算节点个数为3时,平均加速比为2.654;计算节点个数为4时,平均加速比为3.936。由此验证了基于分布式计算的水体识别模型具有稳定的可扩展性,可以满足不同规模的大型计算问题。(2)随着数据量的线性增长,水体识别时间基本呈线性增长。这就验证了提出模型的可伸缩性,可以适应大规模数据量的遥感影像水体识别。
4 结语
通过引入分布式并行计算的思想,结合水体识别理论与技术方法,提出基于分布式计算的水体识别模型,以渭干河-库车河三角洲地区为例进行实验分析。实验结果表明,基于分布式计算的水体识别模型具有较高的识别精度,能够快速识别水体信息,并具有稳定的可扩展性和伸缩性。下一步的研究工作主要是进一步完善基于分布式计算的水体识别模型,考虑水利设施(包括大坝、水库、水电站)等信息的提取策略。
摘要:为了提高遥感数据的处理速度,解决遥感信息提取中的数据密集与计算密集问题,将并行计算的思想引入到遥感图像的处理与信息提取中,构建基于Landsat ETM+影像的分布式遥感图像水体提取模型。以渭干河流域为研究区,利用单波段阈值法、多波段谱间关系法、水体指数法等方法进行水体信息自动提取的实验。实验结果表明,该模型具有较高的识别精度,能够快速识别水体,并具有稳定的可扩展性和伸缩性。
分布式识别 篇2
分布在LAN或者WAN上的多台Web服务器主机通过自组织方式或者由专门的设备负责组织调度的方式进行协同工作, 而组成一个Web站点, 共同分担用户对该站点的Web请求负荷, 这样的系统, 我们称之为分布式Web服务器系统 (Distributed Web Server System, 以下简称DWSS) 。DWSS是目前最前沿的Web服务器性能提升技术之一。当系统的性能不能满足需求时, DWSS通过增加系统中服务器数目的办法改善系统性能, 因而具有灵活的扩展性, 而且保护了原有投资。负载平衡是DWSS的关键技术, 其目的在于将用户请求均衡地分发给系统中的多个服务器来处理而提高系统吞吐率, 缩短用户响应时间。实现负载平衡的方案很多, “识别内容的请求分发 (以下简称CARD, 基于CARD的DWSS简称CARD-DWSS) ”方法是其中的一种。
除了CARD方法之外, 目前提出的其它DWSS负载平衡方案都只是考虑多个服务器的CPU负载均衡, 而没有服务器端的其它资源利用问题, 比如没有考虑Cache的命中率。从Cache命中率来看, 在长时间范围内, 每一个服务器都倾向于提供该站点的全部内容, 而这些内容往往超出单个服务器的缓存能力;另一方面, 相同的内容可能在多个服务器中重复缓存, 资源利用率低, 系统的整体缓存命中率不高。实际上, CPU速度的提高远远比磁盘存取速度的提高要快得多, 因此, 在磁盘存取速度远远不能满足CPU的需求时, 提高Cache的命中率对于改善DWSS的性能将十分有益, 为此, 一种新的负载平衡方案———CARD方法被提了出来。
基于CARD方法的DWSS的组织结构可以视为基于分配器的DWSS的一种, 它以一台运行某种CARD方法的分配器为前端机, 不但能够控制所有的用户请求流量, 而且还可以为站点提供单一的IP映像。一般情况下, 分配器的IP就是站点对外公布的IP。所有的用户请求都首先发往分配器, 由它将请求转发给系统中的某一个主机来处理。因此, 通常也把分配器称为DWSS的前端机, 而将系统中实际处理用户请求的Web服务器称为后端机。
2 基于标记的缓存协作CARD方法
CARD方法的特点是, 前端机首先了解用户请求的文档内容, 然后再选择适当的服务器来处理它。由于HTTP协议是建立在面向连接的TCP/IP协议之上的, 因此, 用户必须经过3次握手建立与服务器端的TCP连接之后, 才能提交URL请求。负责用户请求调度的分配器根据用户请求的URL选择相应的服务器, 为了保持调度方法对用户透明, 也为了不增加网络开销而加大服务的延迟, 必须有某种方法, 使后端机无需再次建立与用户的TCP连接, 而是接受已有的连接, 直接处理用户的请求并给出回应, 目前提出的解决办法有3种:代理方式, TCP接合 (TCP Splicing) 方式, TCP连接转交 (TCP Handoff) 方式。
其中, TCP连接转交 (TCP Hand off) 是目前的较好的方案, 称基于TCP连接转交的CARD方法为LARD (Local Aware Requests Distribution) 。
基于LARD的DWSS中, 前端机维护站点内容 (URL) 与后端机的对应关系, 并负责建立与用户的TCP连接, 在了解用户请求的URL之后, 前端机根据当前各个后端机的负载情况和URL在后端机缓存中的分布情况选择一个后端机, 将相应的TCP连接转交给它, 由它来处理浏览器的请求, 并直接向用户回应相应数据。LARD减少了相同内容在多个服务器中不必要的重复缓存, 提高了DWSS的总体缓存命中率, 加快响应速度, 因此, 基于LARD的系统能够获得比基于WRR的系统更高的吞吐率。但是由于前端机所负责的TCP连接的建立和转交等功能十分耗费资源, 致使前端机成为系统的潜在性能瓶颈, 系统扩展性不好。
Mohit Aron等人提出了一种改进的方法———SCARD。SCARD通过使用多个设备分担前端机的工作来改善系统的可扩展性。但是该系统中前端机性能的改善是以增加系统内部各设备之间的通信量为代价的。分发器需要与分配器进行通信以便了解URL的分布情况, 完成TCP转交或者连接中断时, 分发器需要与前端机通信以便其更改连接信息。这些内部通信不但增加参与通信的各个部件的负担, 也占用了系统内部宝贵的网络带宽资源, 使系统的扩展性受到限制。作者建议分发器使用批量查询的方法, 既收到多个用户的URL请求之后再向分配器查询其分布情况, 而不是为每一个用户的URL请求单独发送一个查询包。显然, 这种方法将增加用户的响应延迟。
(1) 基于TB-CCRD的DWSS的系统框架结构及工作原理
为了保持LARD和SCARD的优点, 克服其不足, 我们设计了一种新的TB-CCRD (Tag Based Cache Cooperative web Requests Distribution) 请求调度方法, 该方法通过集中管理URL在各个服务器存储系统中的分布来提高Cache的命中率, 并可实现分布式存储;利用标记传递URL分布信息, 避免额外的网络通信量;用分布式处理TCP连接转交消除系统的瓶颈, 从而使基于TB-CCRD的DWSS获得更好的性能和扩展性。
基于TB-CCRD的新系统采用和Linux直接路由式虚拟服务器相同的框架结构。如图1所示, DWSS的各个后端服务器通过高速以太网相互连接, 它们屏蔽ARP协议, 并拥有与前端机相同的IP (记为vIP) 和Web服务端口号 (记为vPort) , 在用户看来, 这个系统就相当于一个IP地址为vIP, 服务端口号为vPort的Web服务器。新系统中, 前端机负责接收来自用户的数据包, 发放用于指示处理该数据包最适当的服务器ID (可以是后端机在系统内部的标识符, 也可以是它的MAC地址) 的标记, 并转发数据包;后端机则负责处理由前端机转发而来的用户数据包并直接回应用户, 具体包括建立/拆除与用户的TCP连接、TCP连接转交以及提供URL内容等工作。
(2) 系统工作流程
TB-CCRD方法需要前端机和后端机的配合来实现。基于TB-CCRD的DWSS的工作流程如图2所示。
3 性能的数值比较
LARD通过提高URL请求命中率而获得了较好的Web服务性能, 但是LARD以集中处理的方式完成TCP连接的建立和转交, 导致前端机容易成为系统瓶颈, 扩展性较差;SCARD致力于改进前端机的处理能力, 从而改进系统性能和扩展性, 但是它的URL分发方案带来了随系统规模增长的不可忽视的系统开销, 使系统的扩展性受到限制;WRR系统虽然有更好的扩展性, 但是Web服务性能较差。以上方法在系统的可扩展性和Web服务性能上不可兼得。DWSS系统的扩展性主要体现在前端机的处理能力以及系统内部信道的开销上, 而Web服务的性能主要体现在URL的cache命中率及吞吐率上。我们的TB-CCRD方法, 同时考虑了以上两个方面的问题, 在维护系统良好的扩展性的同时获得高的性能。下面, 我们通过模拟试验和性能比较来分析TB-CCRD系统的扩展性和Web服务性能。
3.1 前端机扩展性比较
根据81, 82, 基于LARD的DWSS中, 前端机处理一个请求所需的CPU时间为:T1=连接建立时间 (T conn) +TCP转交时间 (T hand off) +任务分派时间 (TDispatch) +Pack转发时间 (Ttranfer) , 其中, Thandoff、Tconn都在Ttransfer的15倍以上, 而Tdispatch为Thand off的10%~20%。
对基于TB-CCRD的系统, 同等条件下, 前端机处理一个请求所需的CPU时间为:T2=Psyn/Pfin/rst/Purl/Pack的转发时间 (4*Ttransfer) +任务分派时间 (Tdispatch) 可见TB-CCRD系统前端机的处理能力是LARD系统的5倍以上。
3.2 系统内部信道开销比较
SCARD系统中, 分配器与每一个后端机之间建立一个持久的TCP连接, 当后端机收到客户的URL请求之后, 它将利用这个连接向分配器询问该URL该由哪一个后端机来处理。因此, 了解一个URL的缓存位置所带来的系统内部信道开销包括从后端机发往分配器的查询数据包和相应的分配器的回应数据包。根据82作者的原型系统93, 后端机发往分配器的查询数据包的最小长度为:
以太网帧报头/尾 (26B) +IP报文报头 (20B) +应用层报文报头 (22B) +URL_hash (16Bytes) =84 Bytes。
分配器的回应数据包最的小长度为:
以太网帧报头/尾开销 (26B) +IP报文报头开销 (20B) +应用层报文报头 (26B) =72 Bytes
而TB-CCRD系统采取类似于MPLS夹缝头 (Shim Header) 的标记封装方式, 在客户的URL请求包中加贴一个标记来传播URL的缓存分布信息。大多数的HTTP连接包含5-6个来自用户的数据包82。因此, 后端机了解一个URL的缓存位置所带来的系统内部通信开销为:
6Bytes*6=36 Bytes
小于SCARD系统通信开销的1/4。
4 结束语
研究表明, CARD在提高系统性能方面有独特的优势, 我们提出的新方法可以进一步确保基于CARD的DWSS的可扩展性。它的另一个用途是方便QoS方案的实施, 比如, 某个电子商务网站需要为下订单的用户提供比普通的信息浏览用户更好的服务, 以确保在线交易的顺利进行, CARD的使用, 使得Web服务器系统在为用户提供服务之前, 可以通过用户的URL请求区分这两类用户。CARD还有一个重要的优点, 就是有助于分布式存储方案的实施。
参考文献
[1]林闯, 单志广, 任丰原.计算机网络的服务质量[M].北京:清华大学出版社, 2004.
[2]徐恪, 吴建平, 徐明伟.高等计算机网络-体系结构、协议机制、算法设计与路由器技术[M].北京:清华大学出版社, 2003.
[3]徐荣, 龚倩.高速宽带互联网技术[M].北京:人民邮电出版社, 2002.
[4]白建军, 钟读杭, 朱培栋, 等.Internet路由结构分析[M].北京:人民邮电出版社, 2002.
[5]白建军, 卢泽新.路由原理与设计[M].北京:人民邮电出版社, 2002.
[6]王乐春, 龚正虎, 白建军, 夏建东, 等.高端路由器测试技术[M].北京:人民邮电出版社, 2002.
[7]崔勇, 吴建平, 徐恪, 等.互联网络服务质量路由算法研究综述[J].软件学报, 2002 (11) .
分布式识别 篇3
数据是关于自然、社会现象和科学试验的定量或定性的记录,是科学研究以及科学决策的重要基础。数据作为研究依赖的基础资源,其质量好坏直接关系到以此为据的正确性和科学性。而日常生活工作中,产生的数据可能会出现异常情况。这些异常数据的产生,可能是网络入侵或传感器故障引起的;可能是数据产生的机制内在特性引起的;也可能是抽样调查技术问题;数据采集设备不完善;数据录入及传输错误;测量单位混乱;测量仪器不正常,样本达不到要求,或测量环境偏离正常值较大;虚报、瞒报使统计数据失真;输入错误或系统运行错误所致;看错、读错、抄错、算错、转移错误等人为因素所致。
异常数据的出现会极大程度地降低数据的质量,导致统计分析发生显著变异,使得样本对总体的推断、控制与预测等工作产生不准确或者出现错误,甚至造成宏观决策上的失误,带来不可挽回的损失。因此,及时有效的检测、追踪和防治异常具有重要的意义。
1 关于异常数据的基本概念
1.1 异常的定义
Hawkins的定义:异常是在数据集中偏离大部分数据的数据,使人怀疑这些数据的偏离并非由随机因素产生,而是产生于完全不同的机制。
1.2 异常数据的定义
异常数据就是数据集中与其它数据明显不一致的数据或远离数据集中其余部分的数据。异常数据具体表现在数据提取过程中,可能存在一些数据,它们与其它数据的一般行为或模型不一致。
1.3 数据存在的结构形式
异常是数据其中的一个外在表现形式,下面给出数据的结构形式。
大量的数据集合在一起形成样本矩阵。样本矩阵中每一行就是一个数据对象,这个不同的数据对象表示了不同的物质实体、方案、观测等,注意每个对象的样本数据是在同一次观测或同种方案下进行的。每一列代表某种属性特征,其属性值是指描述对象特征的数据值。设对象个数为m,属性的个数为n,这时样本数据构成了一个m×n的样本矩阵。第i个对象的第j个属性数据值为aij,则样本矩阵A为:
若n=1,样本数据是单属性,n>1时是多属性。本文只研究单属性的情况。
2 异常数据发现与识别的算法
2.1 基本思想
概率分布的方法是用于处理单属性数据的。目前,该方法一般处理过程是先设定属性数据服从正态分布,再给定一个置信概率,并确定一个置信门限,凡超过此限的误差,就认为它不属于随机误差范围,将其视为异常数据剔除。但这种方法存在两个问题:
(1) 假设属性数据服从正态分布,然而现实生活中也大量存在不服从正态分布的数据,因此需要确定数据的分布特性;
(2) 置信门限作为一个恒定值是不合理的,因为小概率事件在大量抽样时,发生的概率也比较大,因此需要设定自适应门限阈值。
针对以上问题,本文先确定数据的分布形式,再使用可接受频率值p作为门限。另外,在构建算法模型前提出假设,假定样本矩阵中被认为正常的对象远远超过被认为异常的对象。
2.2 异常数据发现算法
这种方法一般处理的数据对象是单属性的,则n=1。样本矩阵变为简单的样本向量形式。其数据结构为:
A=(a11,a21,…,am1)T
基于统计的方法是最早并且最为成熟的异常数据检测方法。改进的算法思想是:首先假设被检测数据服从某种分布,给出分布模型(如:正态分布),然后根据已有观察数据来对未知参数(均值,方差)进行估计,最后使用假设检验的方法来计算出精确的或者近似的概率分布模型。然后根据该概率分布模型来计算某个特定值取值的概率,并根据一个自适应门限阈值来判断一个数据异常情况。
2.2.1 确定单属性数据的分布形式
现实生活中,某个属性值,在噪声的影响下或是由于人为工作上的疏忽存在着数据与理论上的误差。这个属性值可以看作是随机变量X,它服从某种分布f(x)。记为:
应用统计学,由该属性的样本数据可以统计求出属性的频率分布fp(x),并对均值和方差进行参数估计。
在统计学中,可以使用χ2拟合优度检验,科尔莫戈罗夫检验或斯米尔诺夫检验的方法,求出该属性的拟合分布函数或概率密度函数。这里采用概率分布结构相似的方法,确定属性值的概率分布f(x)。使用这种方法是因为在日常生活中的数据基本上服从以下的分布类型;另外,计算上简单易行。
日常生活实践中,大多数随机变量服从以下几种分布之一,设第k个概率密度函数或分布律分别为gk(x)和gk(n)。
(1) 连续型
正态分布:
γ分布:
其中,
把求得的样本估计参数带入到概率密度函数簇中,以确定具体的概率密度函数。
运用同样的方法可以确定均匀分布、指数分布、χ2分布、t分布、F分布、瑞利分布等的概率密度函数。
(2) 离散型
泊松分布:
而且,λ=μ或λ=σ2,这时分布参数同样由样本数据估计求得。
可见参数λ可以用多种方法求出,可以先验证参数是否满足该分布,即
各种分布的相似度计算:
连续型:
离散型:
其中sup、sub分别为上、下确界。由Cauchy Schwartz不等式,容易得出:
0≤Sk≤1 k∈(1,2,…,N)
N为概率密度函数或分布律的个数。当fp(x)=h·gk(x)或fp(n)=h·gk(n)时,Sk=1。其中,h为比例系数。
若最大的一个相似度
fp(x)∝gk0(x)⇒f(x)=gk0(x)
或f(n)=gk0(n)
2.2.2 发现对象异常的算法
由于属性值的分布函数f(x)已经确定,而且是单属性样本,异常值通常出现在极值处。因此从极值处判断是否异常。
最大值和最小值的异常判别公式为:
m·∫
m·∫
其中,p为可接受的频率值,这里取p=0.1。当上述不等式满足时,该属性值判断为异常,可以理解为,理论上该值出现不到0.1个,实际上出现了1个,相差一个数量级,认为是异常。删除该值,循环判断余下点是否异常,直到不等式的方向改变。为了更清晰地描述异常属性发现的算法,下面给出流程如图1所示。
2.3 异常数据的识别
由于是单属性情况,异常数据的识别比较简单,就是异常对象对应的数据值。如果是多属性的情况,异常数据的识别比较复杂,这里不再讨论。
3 结 语
通过算法计算提高了数据的合理性与有效性,也为进一步的数据挖掘处理做好了准备,这样获得的信息或知识更加可靠,为决策提供了有力的依据。
算法的优点:异常点检测的概率分布方法具有完善的数学理论基础,建立在标准的统计学技术(如分布参数的估计)之上,现实中有很多待检测数据确实服从某种分布。当数据样本充分以及所用的检验类型确定时,这些检验可能非常有效。
算法的缺点:大部分统计方法都是针对单个属性的,处理多元数据技术方法较少,对于高维数据很难估计真实的分布;在许多情况下,数据分布是未知的,而且现实数据也往往不符合任何一种理想状态的数学分布,只能做到近似分布的初步估计计算。因此,当没有特定的检验时,该方法不能确保发现所有的异常数据。另外,由于研究的是单属性数据,没有利用数据之间的关联信息,特别是对周期性数据不能够很好地工作。
参考文献
[1]师义民,徐伟,秦超英,等.数理统计[M].北京:科学出版社,2009.
[2]陈希孺.概率论与数理统计[M].合肥:中国科学技术大学出版社,2002.
[3]董尤心,张杰,唐宏,等.效能评估方法研究[M].北京:国防工业出版社,2009.
[4]周俊临.基于数据挖掘的分布式异常检测[D].成都:电子科技大学,2010.
[5]张葛祥.雷达辐射源信号智能识别方法研究[D].成都:西南交通大学,2005.
[6]应磊.农业搜索引擎中的异常数据检测[D].合肥:中国科学技术大学,2010.
分布式识别 篇4
通信信号的调制识别在电子侦察和无线电监控等领域占据着十分重要的作用, 它主要的任务就是在调制信息未知的情况下确定调制信号的调制方式以及估计出信号的一些参数如载波频率、波特率等, 从而为进一步分析和信号处理提供依据。现有的调制信号识别的研究多数是以高斯噪声作为背景噪声, 识别算法多数也是适用于高斯噪声环境下。但近年来的研究发现, 无线通信中往往存在一些尖峰脉冲状的非高斯噪声, 比如多用户干扰、低频大气噪声以及其他自然或人为的电磁脉冲噪声。以美国加州大学的Nikas教授为代表的研究学者在充分研究各种随机过程模型后, 发现Alpha稳定分布是描述这类随机信号的有效的噪声模型[1,2]。因此, 在以Alpha噪声为背景噪声情况下进行数字调制信号识别就具有重要的意义。
近些年, 基于高斯噪声下调制识别的研究已有很多, 陈卫东[3]利用四阶累量实现了2PSK、4PSK、8PSK信号的调制识别, 并证明了高阶累量具有尺度、相位旋转不变的特性, 并可以抑制高斯噪声的影响。文献[4]通过提取信号的瞬时特征对信号进行识别, 但是这种方法对噪声比较敏感, 在低信噪比的环境下识别率比较低。文献[5]利用小波系数作为特征对信号进行识别, 但是这种方法需要精确的相位信息。文献[6]对数字调制信号谱相关特性进行分析, 通过计算不同信号谱相关函数f截面的归一化面积来检测信号, 实现了对四种信号的识别, 但是这种方法需要选取精确的阈值。
现已有学者对非高斯噪声下信号处理进行了一些研究, 但是对Alpha分布噪声下的数字调制信号识别的研究还不是很多。文献[7]采用表征信号的分形盒维数作为特征参量对信号进行识别, 但是用这种方法必须在较高的混合信噪比的情况下才能取得理想的识别率。文献[8]利用KolmogorovSmirnov检验法对MQAM、MPSK信号进行识别, 在低混合信噪比情况下识别性能较差。文献[9]提出了分数低阶循环谱系数的方法对数字调制信号进行识别, 但该方法的识别复杂度较高。
针对上述研究存在的问题, 本文提出了一种方法:根据本文提出来的预处理函数对被Alpha噪声污染的信号进行预处理, 使其存在有效的循环谱, 然后根据不同调制方式信号的循环谱特征不同提取出4个特征参数对所选信号进行调制识别。仿真结果表明, 在混合信噪比较低的情况下, 该方法可以取得较高的识别率。
2 Alpha稳定分布的概念
Alpha稳定分布是唯一的一类满足广义中心极限定理的分布, 它是一种更加广义化的高斯分布, 高斯分布只是Alpha稳定分布的一个特例。Alpha稳定分布没有统一的闭式概率密度函数, 一般采用特征函数描述[10]:
式中sgn (·) 为符号函数, , α为特征指数, 取值范围为0<α<2, 它表征着分布函数脉冲特性的程度, α越小, 表明其脉冲特性越强;μ是位置参数;γ为分散系数, 其含义与高斯分布的方差类似;β为对称参数, β=0时, 稳定分布关于μ对称, 此时的分布称为对称Alpha稳定分布, 简称SαS。当α=2时, 稳定分布与均值为μ, 方差为2γ的高斯分布等效。当对称Alpha稳定分布满足μ=0, γ=1时被称为标准Alpha稳定分布, 不失一般性, 本文采用标准SαS作为噪声模型。对于Alpha稳定分布噪声来说, 由于其不存在二阶及二阶以上的统计量, 所谓的噪声方差也就没有意义, 因此采用混合信噪比QMSNR=10lg (σS2/γ) 来表示噪声的强弱, 其中σS2为信号的方差, γ为Alpha噪声的分散系数[11]。
3 信号预处理
由于Alpha噪声不存在二阶及二阶以上的统计量, 所以被Alpha噪声污染的信号也就不会存在有效的循环谱, 分析原因主要是因为Alpha噪声中存在着很大的冲激脉冲, 致使受污染后的信号存在着较大的幅度。基于此原因, 本文提出一种预处理函数:
其中x为要处理的信号, H (·) 表示希尔伯特变换。任何一点的信号都可以写成x=rcosθ, 则可以得到的取值范围为[-1, 1]。所以上述函数可以将所处理信号的幅值映射在一个[-1, 1]的范围内, 并且不改变信号的相位信息, 从而也不会改变信号的周期平稳特性。因为此函数消除了Alpha噪声的大幅脉冲, 所以受噪声污染的信号具有有效的循环谱。
4 通信信号的循环谱
4.1 循环谱相关概念
实际应用中, 通信信号更接近于一个周期平稳过程, 其统计特性 (均值、相关函数等) 常呈现出时间的周期性。信号x (t) 的自相关函数定义为:
信号x (t) 的循环自相关函数定义为[12]:
式中ε为信号的循环频率, T0为信号x (t) 的Rx (t, τ) 的周期。
对信号x (t) 的循环自相关函数Rxε (τ) 求傅里叶变换得:
上式中Sεx (f) 即为信号x (t) 的循环谱密度函数。
4.2通信信号的循环谱以及特征
2PSK信号可以表示为[13]:
其中fc为载频, θ为初始相位, q (t) 表示矩形脉冲波形, an等概率的取±1, T为码元周期。经过式 (2) 的处理, 结合式 (4) (5) 得出预处理后2PSK信号的循环谱为:
MSK信号可以表示为[13]:
其中, 令式 (9) 中f=0, 结合Qg (f) 、Q0 (f) , 可以得到f=0时的ε截面表达式:
由式 (10) 可以得到当ε=±2fc+1/2T时, Sεx (0) 取得较大非零值[14], 在ε取其他值时, 幅值较小。由此可以得出, 当f=0时, 在循环频率轴上, ε=±2fc+1/2T时, 会存在明显谱线。
2FSK信号可以表示为[13]:
其中, fc为载频, fm为频偏, θ为初始相位, T为码元周期。经过式 (2) 的处理, 结合式 (4) (5) 得出预处理后2FSK信号的循环谱为:
同理可以推导得出, 预处理后的QPSK信号的循环谱当f=0时, 在循环频率轴上, 不存在明显的谱线, 预处理后的4FSK信号的循环谱在f=0时, 在整个循环频率轴上, ε=±2 (fc+fm) 处存在8条明显谱线。
5 基于循环谱特征参数的识别方法
对于受Alpha噪声污染的通信信号, 前文提出一种预处理函数, 使得受污染的信号的循环谱还保持了原有的特征。前文推导了各种调制信号的循环谱特性, 不同的调制信号在f=0的循环频率轴上具有不同的特征, 由于Alpha噪声不具有循环统计量下的循环频率, 从循环频率轴上提取特征参数, 可以减小Alpha噪声的影响。信号的循环谱在循环频率域上的特征关于零循环频率对称, 因此本文只取正循环频率域特征作为分类特征。通过对各信号循环谱的正循环频率域部分对比分析可知, MSK信号在f=0, ε=2fc± (fd/2) (fc为信号载频, fd为码元速率, fd=1/T) 位置处存在着明显的谱线, 而其他信号在此位置处均不存在明显谱线。2PSK信号在f=0, ε=2fc和ε=2fc±fd处存在明显谱线, QPSK信号在f=0时整个循环频率轴不存在明显的谱线。2FSK信号在f=0时, 在ε=2 (fc+fm) 处存在两条明显谱线, 4FSK信号在f=0时, 在ε=2 (fc+fm) 位置处存在四条谱线。
通过对以上信号的循环谱特征的分析, 以归一化的循环谱各个轴上的幅度为研究对象, 本文提取出了四个分类特征参数。通过分析离散谱一阶差分序列的符号变化并结合适当的阈值检测谱线[13]。本文提取出了四个分类特征参数。
特征参数R1表示被测信号循环谱在f=0, ε=2fc- (fd/2) 处是否存在谱线, 若存在, 则令R1=1, 否则令R1=0, 通过R1可以将MSK信号与其他信号区分出来。
特征参数R2表示被测信号循环谱在f=0, ε>0时是否存在谱线, 若存在, 则令R2=1, 否则令R2=0, 通过R2可以将QPSK信号从信号集中识别出来。
特征参数R3表示被测信号循环谱在f=0, ε>0截面的谱线个数, 由于在此范围内4FSK信号相比其他信号存在较多谱线, 一共存在四条谱线。则若信号存在四条谱线, 令R3=4, 否则令R3=0, 通过R3可以将4FSK信号从信号集中识别出来。
特征参数R4表示被测信号在f=0, ε=2fc位置处是否存在谱线, 若存在, 则令R4=1, 否则令R4=0, 通过R4可以将信号2PSK与2FSK信号区别开。下面给出本文建议方法的识别流程图 (图1) 。
6 仿真结果及性能分析
为了验证本文所提方法的有效性, 利用MAT-LAB仿真软件进行仿真实验。实验中所识别信号的载频f=150k Hz, 系统采样频率fs=1200k Hz, 码元速率fd=50KB, MFSK信号的频偏为0.25倍的载波频率, 信号的采样点数为4098点, 噪声为加性标准SαS分布噪声。
实验1验证本文所提方法在Alpha稳定分布噪声背景下的识别性能。按照图1所给的信号识别流程图对信号进行调制识别。其中Alpha稳定分布噪声的特征指数α值取1.5。每种信号在每个混合信噪比下进行100次识别, 取识别正确的次数和识别总次数的比值为该信号的识别正确率。识别结果如图2所示。
由图2可以看出, 在所选的混合信噪比区间内, 当混合信噪比等于0d B时MSK、2PSK、2FSK信号都取得了85%以上的识别率, QPSK、4FSK的识别率相对较低;混合信噪比等于1d B的时候MSK、2PSK、2FSK信号的识别率都达到了100%, QPSK、4FSK的识别率为95%和88%;当混合信噪比为3d B时, 5种信号的识别率都达到了100%。由此说明本文所提的方法在Alpha稳定分布噪声下具有良好的识别性能。
实验2仿真Alpha噪声的特征指数α的取值对识别率的影响。在混合信噪比为5d B的前提下, α在[1 2]区间取值, 步长为0.1, 每种信号在每个α值下进行100次识别, 取识别正确的次数与识别总次数的比值为正确识别率。识别结果如图3所示。
由图3可以看出, 在所选取的α的区间内, α值较小时, 识别率相对下降, 这是因为α值越小, Alpha噪声的的脉冲特性越明显, 对信号的影响越大, 随着α值的增大, 信号的识别率越来越好, 并趋于稳定, 当α=1.2时, 五种信号的识别率保持在90%以上, α≥1.4时, 五种信号的识别率都达到了100%, 尤其是当α=2噪声为高斯分布噪声时同样具有良好的识别率。说明本文所建议的方法在一定的α值范围内是适用的。
7 结语
分布式识别 篇5
关键词:支持向量机,概率分布,识别模型
在装备可靠性工程领域, 准确、有效地识别使用数据或试验数据的概率分布模式是一项十分重要的工作。对于分布模式的识别, 目前普遍采用的基于数理统计的检验方法, 其理论基础是样本数目趋于无穷大的渐近理论, 对样本容量要求较高, 采用其对小样本数据进行分析, 分析结果的准确性得不到有效保证。如:判定一组产品寿命试验数据是否服从正态分布, 一般应使样本容量n≥50[1]。研究适用的小样本数据概率分布模式识别方法, 以有效利用小样本数据的潜在信息, 做好信息挖掘工作, 是当前亟需解决的一个难题。
近年来迅速发展起来的统计学习理论是建立在结构风险最小化原则的基础上, 专门研究小样本情况下机器学习规律的理论。支持向量机 (Support Vector Machine, 简称SVM) 是在20世纪90年代中期由Vapnik V等人提出的基于统计学习理论的机器学习算法, 它根据有限的样本信息, 在最小化样本点误差的同时, 缩小模型预测误差的上界, 从而提高了模型的泛化能力和抗噪声扰动能力。
本文运用现代统计学原理及支持向量机分类算法构建了小样本数据概率分布模式自动识别模型, 对装备可靠性工程中常见的概率分布模式进行识别。
1 支持向量机分类算法
1.1 支持向量机二分类算法
支持向量机是通过构造最优分类超平面实现数据样本分类的, 其二分类算法如下[2]:
设训练样本集
yi[Wφ (xi) +b]-1≥0;i=1, …, n (1)
的约束下求解
当训练样本集在Ω中线性不可分时, 为了保证分类的正确性, 引入松弛变量ξi≥0;i=1, …, n, 即在
yi[ (Wφ (xi) +b]-1+ξi≥0 (3)
的约束下求解
(4) 式中, C (C>0) 为惩罚因子, 实现经验风险与置信范围的折衷。
由于特征空间的维数可能很高, 甚至是无穷的, 且变换φ并未直接给出, 不易直接求解。该问题可转化为其对偶问题, 即在
的约束下求解
(6) 式其中, αi为约束条件式 (3) 对应的拉格朗日因子。
求解出上述各系数αi, b对应的最优解α*i, b*后, 得到最优分类函数为
(7) 式中, sgn[]为符号函数, 由分类函数f (x) 的正负即可判定x所属的分类。
选择不同的核函数, 可以形成不同的算法, 目前在分类方面研究较多也较常用的核函数有四种:线性核函数、多项式核函数、径向基核函数及Sigmoid核函数。
1.2 支持向量机多分类算法
将支持向量机应用于概率分布模式识别这样的统计数据分类问题, 必须由支持向量机二分类器构造多分类器。基于二分类的支持向量机多分类算法主要有一对一和一对多两种, 本文采用一对一的多分类算法构造多分类器, 其算法如下[3]:
在N类训练样本中构造所有可能的二分类器, 每个二分类器只用N类中的两类训练样本进行训练, 这样可以共构造出N (N-1) /2个二分类器。在对测试样本的分类中, 采用“投票法”。将测试样本x*输入给由N类训练样本中第k类样本和第l类样本构造的二分类器, 如果分类函数的输出结果判定x属于第k类, 则给第k类加一票, 如果属于第l类, 则给第l类加一票。所有N (N-1) /2个两类分类器对测试样本x分类后, N类中哪一类得票最多 (Max Wins) , 就判定测试样本属于哪一类。采用这种方法构造的多分类器, 单个支持向量机训练规模较小, 易于扩展。
2 小样本数据概率分布模式识别
实践表明, 在装备可靠性工程领域, 试验获使用数据主要符合指数分布、正态分布、对数正态分布、威布尔分布及伽玛分布等[4]。
2.1 数据分布特征参数的选取
根据统计学原理, 数据分布主要有三大特征:统计数据的集中程度、离散程度及数据分布的形态特征[5]。
2.1.1 统计数据的集中程度
统计数据的集中程度是指数据向其中心值靠拢或集中的程度。测定集中趋势的参数指标主要有两大类:位置代表值 (众数、中位数、四分位数等) 及数值平均数 (算术平均数、调和平均数、几何平均数等) 。其中, 四分位数有3个, 分别为下四分位数、中位数和上四分位数。
2.1.2 统计数据的离散程度
统计数据的离散程度是对数据变异的统计描述, 用于衡量均值的代表性及测定数据变动的均匀性或稳定性程度。测定统计数据离散程度的指标主要有:极差、四分位差、平均差、方差、标准差、离散系数及异众比率等。其中, 离散系数又称为变异系数, 是数量数据的各离散程度指标与其算术平均数的比值, 是一个无量纲的量, 适用于比较不同现象或具有不同水平数据的变异程度情况。离散系数有极差系数、平均差系数、标准差系数等, 最常用的是标准差系数V (标准差与其算术平均数之比)
2.1.3 数据分布的形态特征
数据分布的形态特征有矩、偏度及峰度等。矩也称动差, 是总体中所有变量值与任意常数离差k次方的算术平均数。
统计中, 常应用三阶矩或四阶矩来刻画分布的形态特征。其中, 三阶中心矩v3及四阶中心矩v4为
偏度指分布不对称的方向和程度。偏度有皮尔逊偏度、四分位数偏度、矩法偏度等, 其中:矩法偏度精确程度较高。常用的偏度指标α为三阶中心矩除以标准差的三次方
峰度又称峭度, 是指分布图形的尖峭程度或峰凸程度。分位数峰度是峰度的一个简单测量, 峰度的精确测量, 需要用到矩的概念, 即矩法峰度, 计算公式为
数据分布特征参数的选取对于数据概率分布模式识别结果有着非常大的影响, 基于上述论述, 通过大量试验, 选取数据样本的四分位数 (下四分位数、中位数、上四分位数) 、离散系数 (选用标准差系数) 、偏度 (α) 及峰度 (β) 共6个参数作为数据样本分布特征参数。
2.2 数据概率分布模式的细分
深入分析上述5种概率分布模式在不同分布参数下的概率密度函数形状, 对每种概率分布模式分别取不同的分布参数进行细分, 共细分为498种概率分布模式。细分后的数据概率分布模式如表1所示。
2.3 训练样本集的生成
每种概率分布模式对应的一组分布特征参数值构成一个训练样本, 498种概率分布模式对应的分布特征参数值构成由498个训练样本构成的训练样本集。
对每种概率分布模式分别采用10 000、1 000、500、100、50个计算机仿真随机数据序列来生成训练样本参数。为便于推广应用及更好地表明训练样本的单参数特征, 四分位数采用随机数据序列中的四分位数表示, 并对其进行了归一化处理。采用10 000个计算机仿真随机数据序列生成的部分训练样本如表2所示。
2.4 识别过程
概率分布模式识别过程如下:
(1) 采用多元分类支持向量机对训练样本集学习分类, 核函数采用径向基核函数, 获得概率分布模式自动识别的记忆权值, 即求取最优分类超平面;
(2) 由计算机仿真生成5种分布类型、498种概率分布模式中任一分布的随机数据序列, 计算其6个输入特征参数值, 构成测试样本集;
(3) 采用获得的多元分类支持向量机最优分类超平面对测试样本集进行概率分布模式识别。
本文分别由50、30、20个计算机仿真随机数据序列来生成测试样本, 构建3个测试样本集, 进行概率分布模式识别, 各概率分布模式的识别率如表3所示。
注:表中仿真识别率对应的“/”前后数值, 前为生成训练样本的仿真随机数据数量, 后为生成测试样本的仿真随机数据数量。
3 讨论与结论
(1) 对于小样本数据, 由于样本容量小, 不能很好地反映出数据的分布特征, 其分布特征参数的扰动性较大, 如采用过多的计算机仿真随机数据序列生成训练样本, 训练样本中各分布特征参数准确度较高, 不能很好地适应测试样本的扰动特征, 即生成训练样本的计算机仿真随机数据数量越多, 概率分布模式识别率越低;
(2) 对于固定的训练样本集, 生成测试样本的计算机仿真随机数据越多, 其分布特征参数的准确性提高, 概率分布模式的识别率也将提高, 即生成测试样本的计算机仿真随机数据数量越多, 识别率越高。
(3) 采用50个仿真随机数据构建的小样本数据概率分布模式识别模型 (对5种概率分布模式, 分别取不同的分布参数细分为498种数据概率分布模式;对细分后的每种概率分布模式, 分别采用50个计算机仿真随机数据序列生成由数据样本的四分位数、离散系数、偏度及峰度6个特征参数构成的训练样本;在此基础上, 对训练样本集采用一对一支持向量机多分类算法构建多分类器) 对50、30、20个计算机仿真随机数据序列生成的测试样本具有较强的识别能力, 识别率分别达到了90%、84%、81%。
在此基础上, 通过大量试验, 进一步改进其分布特征参数的选取, 可有效解决当前装备可靠性工程中面临的小样本数据概率分布模式识别这一难题。
参考文献
[1]张恒喜.小样本多元数据分析及应用.西安:西北工业大学出版社, 2002:21
[2]Vapnik V.统计学习理论的本质.张学工, 译.北京:清华大学出版社, 2000:91—108
[3]Chapelle O, Vapnik V, Bousquet O.Choosing multiple parameters for support vector machines.Machine Learning, 2002; (46) :131—159
[4]贺国芳, 许国宝, 翟荣贞.可靠性数据收集与分析.北京:国防工业出版社, 1995:57