【月入过万】√在家能赚钱的工作|能够在家赚钱的工作|

【doc】用于动态心电图波形分类改进的K近邻算法研究 用于动态心电图波形分类改进的K近邻算 法研究 第28卷第3期 2008年7月 天津师范大学(自然科学版) JournalofTianjinNormalUniversity(NaturalScienceEdition) VO}.28NO.3 Ju1.2008 文章编号:1671一ll14(2008)03—0060—04 用于动态心电图波形分类改进的K近邻算法研究 苑静中 (天津理工大学计算机科学与技术学院,天津300191) 摘要:针对动态心电图波形数据量大且具有明显个体差异性的特点,提出了一种改进的K近邻分类算法,用于 动态心电图波形分类.该算法首先将实例间的度量改为曼哈顿距离(CityBlockDistance),然后引入高斯核, 将K近邻算法改进为非线性分类算法,以达到分类动态心电图波形的目的.实验结果表明,该算法在对动态心电 图波形进行分类时,分类精度在9O以上. 关键词:分类;曼哈顿距离;K近邻算法;动态心电图 中图分类号:TP301.6;TP311.1文献标识码:A OnimprovedK-nearestneighboralgorithmusedfor classificationofwaveformsofdynamicelectrocardiogram YUANJingzhong (SchoolofComputerScienceandTechnology,TianjinUniversityofTechnology,Tianjin300 191,China) Abstract:AnimprovedK— nearestneighboralgorithmusedforclassificationofwaveformsofdynamicelectrocardio— gramisproposedbasedonitsfeaturesofabundantdatabaseandobviousindividualdifference .Knearestneighbor algorithmisimprovedtOnonlinearsortingalgorithmbytransformingthedistancebetweens amplesintoCityBlock DistanceandbringinginGaussiankernelfunction.Theexperimentresultsshowthattheclassi ficationprecisionof thealgorithmismorethan90. Keywords:classification;CityBlockDistance;Knearestneighboralgorithm;dynamicelect rocardiogram(Hoher) 心电图(Electrocardiogram,ECG)是心脏病诊 断的重要手段之一[1].心电图反应了心脏各部位的 工作状况,记录了随时间推进心电电压变化的情况. 心电图的理论基础来自多年创立的各种心电学说, 如Einthoven原理,单极概念,心向量学说等. 由于心电图通常是在人静息状态下获取的,因此 Hoher于1957年发明了另外一种记录人们日常活 动时心脏状况的心电图仪器,称为动态心电图(Dy— namicElectrocardiogram),依据发明人的名字,又 称为Hoher_l.它与普通心电图的区别在于,它可 以长时间(通常为24h)地记录心脏的状况,一般情 况下会记录10万次左右的心跳所产生的心电图(平 均心跳70次/min).动态心电图记录人们不同活动 时心脏的状态,包括静息,活动,立位,卧位,坐位 等[3.随着计算机技术的发展,心电图数字化趋势 已经形成.美国在20世纪80年代初研制出数字心 电图机,使得心电图的数字化成为现实,这为计算 机软件用于检测心电图波形奠定了基础.对于动态 心电图来说,如何快速,准确地和识别心电图成 为当今计算机和医学领域共同关注的热点问[4]. 本研究拟根据由聚类获得心电波形样本, 对24h心电图进行分类研究,提出适用于心电波形 数据的改进K近邻分类算法.图1是典型的心电波 形示意图,其中S,T,Q,R,P是对心电波形中各段 波形的命名,S—T表示S波到T波的组合波段, P—R表示P波到R波的组合波段,Q—T表示Q波 到T波的组合波段,QRS表示Q波,R波和S波的 组合波段,具体如图1中所示的位置. 收稿日期:2007—12—27. 基金项目:天津市高等学校科技发展基金(20061009) 作者:苑静中(196O),男,讲师,硕士,主要从事颜色检测技术方面的研究.E, mail:sunnyhd@126.corn 第28卷第3期苑静中:用于动态心电图波形分类改进的K近邻算法研究'61' t}ms 图1典型的心电图波形 1动态心电图向量化预处理 一 个独立的心电波形的起点为P波,终点为下 一 个P波之前.但是,P波的能量相对于R波较小, P波和其他波形不容易分清,检测P波较为困难,而 检测R波就比较容易.因此,两个R波之间的波形 可以看作一个完整的心电波形,医学角度上称为 R-R问期],本研究以R-R间期内的波形为独立心 电波形,见图1.为了获得独立的完整心电波形需要 对R波进行定位,本研究采用了小波变换分析,由于 动态心电图数据量巨大,并具有较高的实时性,而小 波变换的计算复杂度较高,不能用小波变换对全部 的心电图进行滤波,基线漂移等预处理.本研究采 用下面的策略进行预处理: 1)对所有的动态心电图数据进行简单的消除 基线漂移,滤波等操作. 2)对每个被检测人,选择10S的心电图波形. 3)根据小波变换进行R波定位,得到R—R间隔 的宽度和R波峰高度. ,如果R波形高度超 4)根据R波峰高度定位R波 过R波峰高度,则将其定为R波,否则记为普通波形. 5)根据R—R间隔宽度获得每个波形的维度,对 动态心电图进行维度统一. 经上述预处理,可以获得维度统一的动态心电 图数据,从而为进一步应用机器对其进行数据处理 奠定良好的基础. 2改进的最近邻分类方法 对于动态心电图来说最重要的是从24h的波 形中筛选出具有典型诊断意义的波形,本研究拟采 用聚类的方法进行筛选.其原因如下:同时对10万 个心电波形进行聚类,从时间上是不可行的,为此本 研究首先从一小部分波形数据入手,进行聚类分析, 从中获得标定的样本波形;然后,利用这些标定的波 形数据训练分类器完成后继数据的分类工作.聚类 方面的研究在另外文章中阐述,这里只利用其结果 进行分类器的训练.本研究分别对多类分类算法进 行了研究,包括决策树,神经网络和基于实例的分类 器,根据心电图波形数据的特点,提出了一种改进的 最近邻分类算法.对于心电波形向量分类来说,向量问的比较最好采用距离度量,CityBlock距离最 适宜度量两个心电波形向量问的关系. 在分类器模型中基于实例的分类模型是以距离 作为分类的依据,KNN是其中的一种,它以欧几里 德距离度量两个向量间的关系,这对本研究分析的 心电波形向量非常有效.KNN算法是基于实例的 分类方法,它假定所有的数据(向量)都可以对应于 维空问R"中的点.向量间的度量使用了欧几里德 距离,目标函数厂:R"一V可以将向量分到恰当的类 {,,…,}中,V为有限集合._厂()的 别v一 估计值为: k f(xq)一argmax(,f(x)),(1) t?=i 对于给定的k值,算法可以根据计算相邻向量间的 距离得到分类结果. 但是,由于KNN属于线性分类,分类的准确率 不高.心电波形向量通过目标函数简单地映射到一 个一维空间,这样不能达到完全分类,不能满足心电 波形筛选的要求.因此,引入另一个概念即核函数, 它可以将向量映射到一个高维空问,具备找到一系 列最优分类超平面用于分类的条件,期望可以提高 心电波形分类的准确率. ?62?天津师范大学(自然科学版)2008年7月 用KNN方法进行分类时,本研究采用了距离 加权的方法来描述当前点与周围相邻向量的距离关 系,距离当前点越近的点其权重系数越大.因此, (-z)的估计值由公式(1)变为: k (')一arg… max ?面(,厂()),(2)…i=i 面为权重,定义为: 一 K(((-z)).(3) 本研究选择高斯核函数作为KNN分类的权重 获得方法: x) K((-z,-z))一e(x-- ,(4) 3实验结果 其中志为核函数的数量,高斯函数的中心点位-z,方 差为. 通过上面的,可以获得一个较为简单的基 于核函数的G—KNN分类模型,与原始的KNN模 型相比,进行了两项改进: 1)利用CityBlock距离代替Euclid距离度量 两个向量间的关系,符合心电波形向量的特殊性. 2)利用高斯核函数对KNN算法中当前向量与 相邻向量间的距离加入权重,使得KNN的线性分 类转化为非线性分类. 图2为此算法的流程图. 图2基于核函数的G—KNN算法流程图 在获得了心电波形样本向量后,以这些样本为 训练数据构造了集中分类器,并对心电波形进行了 分类,获得了如下的结果. 本研究在训练中采用已获得的单体3000个已 标注样本进行训练,以2000个样本为训练样本, 自分类器的训练.利用构造分类器对被检测人的聚 类分析以外的心电向量进行分类,表1是3位被检 测人的筛选结果,表1给出了筛选类别数量最多的 3类在全部心电波形中所占的比例.从表2可以看 出,实际分类的正确率中,KNN和基于核函数的 KNN的结果要好于其他分类器,这从实验的角度 证明了心电向量数据的特点,即适合于基于实例相 l000样本为测试样本,共进行了9个被检测人的各似性度量的分类器. 表1筛选3个被检测人心电波形数据 第28卷第3期苑静中:用于动态心电图波形分类改进的K近邻算法研究?63? 4结论 表2筛选9个被检测人分类准确率 本研究讨论了用于动态心电图波形分类的算 法,研究从心电波形的向量化,样本波形的类别标定 出发,根据心电图波形的固有特点,提出了一种改进 的K近邻算法,并与其他分类算法进行了比较,从 实验结果看改进的K近邻算法的分类准确率在 9O以上,并适于心电图波形的分类.今后还将继 续围绕分类算法的计算复杂性和进一步提高分类准 确率方面进行深入地研究. 参考文献: [1]杨庭树,卢喜烈.心电图基础理论[M].天津:天津科学技术出 版社,2005:2—3. [2]刘广芝.心电图学概论[?.贵阳:贵州科技出版社,2003:8—9. r3]李天德,高洁.临床动态心电图图谱[M].北京:金盾出版社, (上接第59页) [8]SasaoT.Representat|0noflogicfunctionsusingEXORopera— tors[C]77ProcWorkshopApplicationsoftheReed—MullerEx— pansioninCircuitDesign.Japan:Makuhari,1995:441—452. [9]GreenDH,DualFormofReed—Mullerexpansions[J].IEE ProcComputDigitTech,1994,141(3):184—192. [1O]WangI,AlmainiAEA.OptimizationofReed—MullerPLA implementations[J].IEEProceedingsCircuits,Devicesand Systems,2002,149(2):119—128. [4] [5] [6] [7] l993:2—3. SzilagyiL,SzilagyiSM,FordosG,eta1.QuickECGanalysis foron—lineholtermonitoringsystems[C]//Proceedingsofthe 28thIEEEEMBSAnnualInternationalConference.New York:AssociationforComputerMachinary,2006:1678— 1681. NovakD,Cuesta—FrauD,TormosPM,eta1.Numberofar— rhythmiabeatsdeterminationinholterelectrocardiogram: Howmanycluster?[c]//Proceedingsofthe25thIEEEEM— BSAnnualInternationalConference,2003,3:2845—2848. DickhausH,GittingerJ,MaierC,ClassificationofQRSmot phologyinholtermonitoring[C]//Proceedingsofthe1stJoint BMES/EMBSconference.Atlanta:ServingHumanity,Ad— vancingTechnology,1999:270—270. ZhengGang,HuangYalou.StudyofIndividualcardiogramwave formautomaticselectioninholter[C]//2007IEEE/ICMEInter— nationalConferenceonComplexMedicalEngineering,2007: 8O8—81】 [11]AlmainiAEA,MckenzieI. ringKroneckerexpansions[J] 1996,143(4):205—212. (责任编校李宏伟) Tabulartechniquesforgenera IEEProcComputDigitTech, [12]WangL,XiaY,YangM,eta1.Anapproachtoobtaincompact multi-levelmixedpolarityRMfunctionswithon—settable[J]. WSEASTransactionsonCircuitsandSystems,2006,5(5): 625—634. (责任编校李宏伟)