（计算机系统结构专业论文）基于数据挖掘技术的肺癌预后系统的研究.pdf

摘要 肺癌在世界范围内是最常见的恶性肿瘤之一，在发达国家已占男性恶性肿瘤 的首位，女性恶性肿瘤的第二、三位，但目前的治疗效果不尽理想。因此，针对 肺癌发病机理及治疗方法的研究已发表了许多论文。然而，利用计算机科学技术 的成果，从大量的临床数据中挖掘有价值的信息，协助医学工作者进行临床治疗 的研究不多，事实上这将会成为一个极为重要的方向。本文围绕这问题展开研 究，采用数据挖掘技术对肺癌生存期进行预测，并尝试探索最佳治疗方案，实现 了一种肺癌预后系统。论文主要内容如下： 1 采用数据挖掘中的离散化方法，对原始数据进行预处理，目的是消除噪声和 不一致数据，以便进一步的分析。 2 使用数据挖掘中的多种分类算法，从原始数据中提取有效的规则，对肺癌病 人的生存期进行预测。在这里，本文采用了决策树、贝叶斯、神经网络等算 法对数据进行分析。针对医学领域的生存期分析问题，我们对这些算法都进 行了改进，希望通过多种方法的比较，找到最合适的解决方法。最后从理论 上和实验结果对这些算法进行比较，总结出各自的优缺点，使系统可以根据 原始数据的变化而自动选择合适的算法。该功能可以推广到其他慢性疾病的 生存期分析，因此，具有相当的经济效益和社会效益。 3 使用基于范例推理的方法解决最佳治疗方案决策问题。这种方法符合医学工 作者的日常思维。同时，我们将决策理论与范例推理相结合，用于解决医学 数据中的不完整和缺失问题。通过输入病人的情况，系统自动搜索范例库， 给出建设性的治疗方案。 4 介绍肺癌预后系统的总体框架与部分功能演示，友好的界面和简单的操作将 给用户一个直观的体验。区别于其他软件，该软件更适合医生和病人在临床 中使用，为肺癌病人个性化治疗提供指导。 关键词数据挖掘；决策；贝叶斯；基于范例的推理；生存分析；神经网络 ， 丝堡翌三奎耋三兰堡圭耋堡垒塞 a b s t r a c t l u n g c r n c e ri so n eo f m o s tf a m i l i a r m a l i g n a n c y w o r l d w i d e n d e v e l o p e dc o u n t r i e s ，i t h a sb e e nt h ef i r s to f m a l e m a l i g n a n c ya n d t h es e c o n d ，t h et h i r do f f e m a l em a l i g n a n c y h o w e v e r , t h et r e a t m e n tr e s u l ti sn o tg o o d t h e r e f o r , t h e r ea r em a n y p a p e r sa b o u t p a t h o g e n e s i sa n dt h e r a p yo f l u n gc a n c e ri s s u e d h o w e v e r , i t h a sb e e na v e r yi m p o r t a n t d i r e c t i o nt h a tm i n i n gv a l u a b l ei n f o r m a t i o nf r o man u m b e ro f d a t at oh e l pd o c t o r sc l i n i c t h e r a p yb y r e s u l t so f c o m p u t e r t e c h n o l o g y i nt h i st h e s i sw e f o c u so n a l g o r i t h mi m p r o v e m e n t o f d a t a m i n i n g t op r o g n o s t i c a t es u r v i v a lt i m ea n d t r yt oc h o o s et h eb e s tt h e r a p yp r o j e c t a t l a s t w ed e s i g na l u n gc a n c e rp r o g n o s t i cs y s t e m n e m a i nw o r ki n c l u d e s ： 1 i no r d e rt oe l i m i n a t en o i s ea n d c o n f l i c t i n gd a t a , w e u s ed i s p e r s ea l g o r i t h mt op r e - t r e a t w i m o r i g i n a ld a t a 2 i no r d e rt op r o g n o s t i c a t e p a t i e n t s s u r v i v a lt i m e ，w eu s e d i f f e r e n t a l g o r i t h m t og a i n e f f e c t i v er u l e s i nt h i sp a p e r , w ec h o o s ea l g o r i t h m o f b a y e s ，n e u r a ln e t w o r k ，d e c i s i o n t r e et oa n a l y s ep a t i e n t s s u r v i v a lt i m e w ei m p r o v et h e s ea l g o r i t h mt oa d a p tt om e d i c a l p r o b l e m w eh o p e t oc o m p a r et h e s ea l g o r i t h mt of i n do u tt h eb e s ta l g o r i t h m w e c o m p a r et h e m i nt h e o r ya n dw i t h e x p e r i m e n t sa n d s u m m a r i z et h e i rm e r i ta n df l a w t h e n ，t h es y s t e mp r o d u c t sm o s ta p p r o p r i a t em e t h o da u t o m a t i c l y b a s e do n v a r i e t yo f o r i g i n a ld a t a t h i sf u n c t i o n c a nb eg e n e r a l i z e dt os u r v i v a la n a l y s i so f o t h e rc h r o n i c s o ， i th a sv a l u a b l ee c o n o m i cb e n e f i ta n ds o c i a lb e n e f i t 3 w eu s eb a s e dc a s er e a s o n i n gt or e s o l v et h ec h o i c ef o rt h eb e s tt h e r a p yp r o j e c t n l i s m e t h o di sa c c o r dw i t ht h ed o c t o r s d a i l yt h o u g h t a tt h es a m et i m e ，w ei n t e g r a t eb a s e d c a s er e a s o n i n gw i t hd e c i s i o nt h e o r yt or e s o l v el o s ta n dn o i n t a c tm e d i c a ld a t a t 1 l i s s y s t e mc a n s e a r c hc a s eb a s ea n d g i v ec o n s t r u c t i v e t h e a t m e n ta u t o m a t i c l yb a s e do n p a t i e n t s i n s t a n c e 4 i tw i l li n t r o d u c et h es y s t e m sf r a m ea n ds o m ef u n c t i o n s d e m o u s e r sc a l lg e ta w h o l e e x p e r i e n c eb y f r i e n di n t e r f a c ea n d s i m p l eo p e r a t i o n d i f f e r e n t f r o mo t h e r s ，t h i ss o r w a r e i sm o r es u i tt ob eu s e di nm e d i c a lf i e l da n dp r o v i d e sg u i d a n c ef o rp a t i e n t s i n d i v i d u a t i o n c i i r e k e y w o r d s d a t am i n i n g ；d e c i s i o n ；b a y e s ；n e u r a ln e t w o r k ；b a s e dc a s e r e a s o n i n g ； s u r v i v a la n a l y s i s ； 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写的成果作品。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：朱华虹埭砷虹日期：2 0 0 3 年5 月1 5 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密d 。 ( 请在以上相应方框内打“4 ”) 作者签名：朱华虹康绰舛 导师签名：郑启伦撕讼孵 日期：2 0 0 3 年5 月1 5 日 日期：2 0 0 3 年5 月1 5 日 第一章绪论 第一章绪论弟一早三百化 1 1 肺癌治疗中存在的问题 肺癌在世界范围内是最常见的恶性肿瘤之一，在发达国家已占男性恶性肿瘤 的首位，女性恶性肿瘤的第二、三位 1 1 。我国1 9 7 3 - 1 9 7 5 年和1 9 9 0 2 0 0 2 年两次 全国肿瘤死亡回顾调查结果显示，男性肺癌由7 0 年代的9 9 4 1 0 万提高至j j 9 0 年代 的2 1 9 6 1 0 万，增加了1 2 0 9 3 ，女性由4 9 5 1 0 万提高到8 7 4 1 0 万，增加了 9 0 4 。目前在城市居民中癌症死亡率肺癌已占第一位，且发病率持续升高。 肺癌可分为小细胞肺癌和非小细胞肺癌，小细胞肺癌的治疗手段主要是化学 治疗1 2 ，非小细胞肺癌的主要治疗手段有手术、放射治疗和化学治疗，但目前的 治疗效果不尽理想。由于肺癌的治疗效果不尽人意，探讨研究各种治疗手段的合 理综合应用，尽可能地提高肺癌的治愈率，便成为了一个极为重要的问题。 目前肺癌治疗疗效不佳的原因是多方面的。首先，肺癌单一手段治疗效果不 佳，多学科综合治疗成为必然，但最佳的综合治疗模式仍未建立。如对术前、术 后放疗和化疗等是否需应用、何时应用等仍有争议p j 。其次，肺癌的复发转移问 题一直未能解决，但对于如何确定复发转移的高危人群、如何处理这些病人却知 之不多。由于未能在早期鉴别出转移复发的高危人群，也无对肿瘤治疗敏感性进 行预测的有效手段州，目前主要依靠病人的临床表现、影像学诊断、手术中情 况、常规的细胞学或组织学诊断等资料进行临床或病理分期，并据此给予化疗或 放疗。但临床分期或病理分期并不代表对治疗有效，由于肺癌放疗和化疗的有效 率仅约5 0 左右，不加区别地旌治导致约半数的病人出现“陪治”的状况。既损 害了病人的健康，加重了病人经济负担，也极大地浪费了社会医疗资源。要克服 目前肺癌治疗中存在的以上问题，必须对肺癌病人的各个疗效、疾病转归不同的 人群进行鉴别，提高对治疗前、治疗中、治疗后肺癌病人治疗的疗效、转移复发 的规律和疾病的发展趋势的预测能力，研究更有效、更合理的治疗方案，从而指 导临床医师对肺癌病人进行个性化的最佳治疗方案设计。 今天，医学的发展已经由经验医学、实验医学转向目前以证据为基础的循证 医学。肺癌治疗学的未来发展将是基于高可信度证据的个性化治疗。而目前肺癌 治疗方面仍缺少这样的证据来指导个性化治疗。 篓至矍三盔兰三耋堡圭兰堡篁塞 1 2 肺癌预后分析的任务 肺癌的发生与年龄、性别、吸烟、环境危险因素等有关1 5 1 。肺癌预后分析就 是要研究这些因素对病人的影响情况，根据肺癌病人的各项指标预测病人的生存 期，并给出建设性的最佳治疗方案，以指导医生进行临床治疗。 这里，肺癌的生存期是指：狭义地讲是从某个标准时点起至死亡止，即患者 的存活时间。例如，患有某病的病人从发病到死亡或从确诊到死亡所经历的时 间。广义的说，“死亡”可定义为某研究目的“结果”的发生，如宫内节育器的 失落，疾病的痊愈，女孩月经初潮的到来等( 生存分析中往往统指“死亡”为失 效) 。此类资料的生存时间变量多不符从正态分布，且常含有删失值，故不适于 用传统的数据分析方法如t 检验或线性回归进行分析。 而生存分析，是用于以处理生存时间( s u r v i v a lt i m e ) 为反应变量、含有 删失数据一类资料的统计方法。对于急性病的疗效考核，一般可以用治愈率、病 死率等指标来评价，但对于肿瘤、结核及其他慢性疾病，其预后不是短期内所能 明确判断的，这时可以对病人进行长期随访，统计一定期限后的生存和死亡情况 以判断疗效。 肺癌预后的任务就是要根据长期随访得到的数据，分析各种因素对肺癌生存 期的影响，预测病人的存活时间，并给出建设性的治疗方案。事实上，采用 d n a 编码的预测方法，使用某些基因( 如m g m t 基因中甲基化状况) 的制定预 测存活率是很有前途的。我们的挖掘算法能从历史数据库中找出一定的规律，为 这些方法提供高可信度的证据来指导个性化治疗，实现以证据为基础的循证医 学。 1 3 肺癌预后分析的现状 2 1 世纪人类全面进入了信息社会，信息成为最关键的战略物资，它被转化为 现代的智力工具。“智能革命”在许多领域内得到广泛的应用。尤其是近年来， 电子病历，远程医疗系统，医院信息系统已经得到了广泛地应用，为医学发展提 供了大量的数据资源 6 1 。医学工作者面对大量积累的医学信息和患者资料，要从 中挖掘出有价值的信息，必须获得计算机智能技术的帮助。然而，根据患者资料 进行智能诊断依然是医学发展的瓶颈。有调查表明，在科学研究形成的数据中， 9 0 从未被使用过，造成这一局面的一个根本原因在于缺乏利用数据的手段。虽 然采用数据库技术将数据组织起来大大提高了检索速度并能提供简单的分析功 能，但是它无法发现数据中隐藏的具有相当价值的规律，而人本身对数据的分析 2 第一章绪论 能力受到多种主观、客观因素的限制。另外，由于医学方面的原因，我们收集到 的数据有时不完整，而现有的研究方法所建立起的统计学模型容错性差，对这些 不完整的数据难以处理。 传统地，我们依然使用一些医学统计软件对癌症患者进行预后分析。如 s p s s ，s a s 等统计软件的统计方法来迸行单因素或多因素分析，在医学杂志上也 查到了类似的文章，如肖永红的“1 0 9 1 例肺癌患者的预后分析”【4 9 】。但是，他 们并不能实时地用于病人的诊断，因此需要采用一种新的技术，为临床医学提供 专家的经验知识，更好地帮助医生进行诊断与选择治疗方案。数据挖掘能自动从 数据集中抽取函数的关系，应用决策理论分析各种规则，为用户提供专家知识。 这一类的研究，国内外人员也有了一定的探索，如基于范例推理的结核病专家系 统，采用机器学习进行生存期预测1 5 0 等。但是，这些都是针对癌症预后中的一 个问题提出某种解决的算法，在癌症治疗方面，目前仍然缺少一个综合的预后分 析系统，它能集成多个算法，可以友好的与病人进行交互。 癌症治疗学的未来发展将是基于高可信度证据的个性化治疗。而目前该方面 仍缺少这样的证据来指导个性化治疗。本文提出采用多种数据挖掘算法进行预后 分析，并形成一个集成、统一、综合的系统，为个性化治疗提供一个新的支持。 1 4 肺癌预后分析采用数据挖掘的必要性 近年来，数据挖掘技术 7 1 引起了信息产业界的极大关注，其主要原因是先进 的科学手段为我们产生了大量的数据，并且迫切需要将这些数据转换成有用的信 息和知识。获取的信息和知识可以广泛用于各种应用，包括商务生产、生产控 制、市场分析、工程设计和科学探索等。 数据挖掘是信息技术自然演化的结果。自2 0 世纪6 0 年代以来，数据库和信息 技术已经系统地从原始的文件处理演化到复杂的、功能强大的数据库系统。自7 0 年代以来，数据库系统的研究和开发已经从层次和网状数据库系统发展到开发关 系数据库系统、数据建模工具、索引和数据组织技术。自8 0 年代中期以来，数据 库技术的特点是广泛接受关系技术，研究和开发新的、功能强大的数据库系统。 现在，数据可以存放在不同类型的数据库中。 数据的丰富带来了对强有力的数据分析工具的需求，大量的数据被描述为 “数据丰富，但信息贫乏”。快速增长的海量数据收集、存放在大型和大量数据 库中，需要强大的工具进行分析【s l 。 数据挖掘技术，是从大量数据中提取或“挖掘”知识。数据挖掘技术进行数 据分析，可以发现重要的数据模式，对商务决策、知识库、科学和医学研究作出 了巨大贡献嘲。数据挖掘技术可分成四中常见的任务：关联发现，聚类分析，分 ： 竺皇堡三查耋三兰堡圭耋鲁笙兰 类与回归，偏差检验。作为一门具有广泛应用的新兴学科，数据挖掘得到了广泛 的应用。 近年来大量出现的基因组数据，各种有关生物数据数量正以指数式增长，如 何对大量的数据进行存储、管理、对比、检索，寻找其相关性，挖掘数据中所隐 藏的规律，以及对海量的数据进行自动获取，需要新的技术。有调查表明在科学 研究形成的数据中9 0 从未被使用过，造成这一局面的一个根本原因在于缺乏利 用数据的手段。虽然采用数据库技术将数据组织起来大大提高了检索速度并能提 供简单的分析功能，但是它无法发现数据中隐藏的具有相当价值的规律，而人本 身对数据的分析能力受到多种主观、客观因素的限制。另外，由于医学方面的原 因，我们收集到的数据有时不完整，而现有的研究方法所建立起的统计学模型容 错性差，对这些不完整的数据难以处理。数据挖掘能自动从数据集中抽取函数的 关系。由于数据挖掘有较强的容错性，输入数据在某些部分上的错误对数据挖掘 最终结果的正确性影响不大。如果我们所使用的数据越多越全面，则其中所蕴含 的事物本身的规律性就越强，利用数据挖掘从中所抽取的函数关系就越具有普遍 性，因而就更准确。以非线性大规模并行分布处理为特点的数据挖掘理论突破了 传统的线性处理模式，以其高度的并行性，良好的容错性和自适应能力成为人们 探索和研究某些复杂大系统的有力工具。肺癌病因复杂，因此，必须在大量收集 临床资料所产生的海量信息的基础上引入数据挖掘技术。 我们利用数据挖掘方法和人工智能算法，开发了肺癌预后分析系统。本软件 意义重大，具有极大的可行性，目前国内外有关的开发还非常有限，利用数据挖 掘技术在肺癌中的系统性研究几近空白，因此开展这领域的软件开发和研究工 作将可望填补国内外空白，并可形成产业化，产生巨大的社会效益和经济效益。 1 5 本文主要内容和意义 1 5 1 主要研究内容 ( 1 ) 根据中山三院提供的历史数据，建立数据库。由于原始数据存在许多 不一致性等问题，所以必须对数据进行数据清理，数据集成，数据变 换，形成一个规范、统一的数据库。 ( 2 ) 对肺癌生存期进行预测。采用多种数据挖掘算法，如贝叶斯算法，决 策树算法，神经网络算法等，对训练样本进行分类，获得规则，从而 对新病人的生存期进行预测。 ( 3 ) 提供建设性的治疗方案。采用多种数据挖掘算法，如基于范例推理， 决策分析，专家系统方法等，从训练样本中获得知识，向病人提供最 4 佳治疗方案，指导医生的治疗。 ( 4 ) 对软件进行测试，验证系统的各项性能。将数据结果与统计软件、商 业软件的结果进行比较，证实本软件的准确性、实时性、易用性、直 观性。 1 5 2 课题意义 本课题是广州市科技攻关项目，得到广东省自然科学基金和广州市科委基金 资助。该项目是采用微阵列技术对肺癌和正常人肺组织进行检测，并完整收集肺 癌病人的临床资料，从而获得大量肺癌生物学信息。在此基础上，综合运用数据 挖掘的多种学习算法和数据分析，实现知识的自动获取。同时以设计严密、执行 严格的临床随机对照研究，对分析的结果可靠性进行验证，最终，建立肺癌预警 预测预后系统。而目前，我们将医院的历史电子病历作为原始数据库，目的在于 进行前瞻性研究，建立一个肺癌预后模型，验证数据挖掘算法的有效性，为整个 项目的研究打下稳固的基础。在研究过程中，我们得到了中山三院医生博士、硕 士的热情帮助，在此表示衷心感谢。研究中建立的一个基于数据挖掘技术的肺癌 预后系统，可以提供优化的肺癌治疗个性化服务。本软件意义重大，建立的系统 可以直接应用于医院临床，并可形成产业化，产生巨大的社会效益和经济效益。 本软件的创新点在于： ( 1 )数据挖掘技术、人工智能算法用于肺癌预后分析，并形成了一个系统 软件。本软件可以实时地用于病人的预后分析，帮助医生更好地进行 临床治疗，提供建设性的治疗方案。 ( 2 )肺癌生存期预测中，对决策树算法i d 3 进行改进，使用信息熵的增益 率来选择扩展属性，并采用聚类技术进行分支合并，使得得到的决策 树在大小和精度上都优于i d 3 算法建立的决策树。 ( 3 )肺癌生存期预测中，对贝叶斯算法迸行改进，提出基于熵和基于分类 误差与不确定性抽样相结合的两种主动学习方法，提高了分类精度。 ( 4 )肺癌生存期预测中，对神经网络算法迸行改进，激活函数采用双曲正 切函数使得激活值范围较s i g t a o i d 型激活函数的值域大，并对隐藏层 节点激活值进行聚类，使信息更加浓重。 ( 5 )最佳治疗方案选择中，将决策理论与基于范例推理相结合，其中范例 复用提高了问题求解效率，而决策理论帮助选择最佳的范例，提高了 算法的准确性。 。 耋里塞三奎兰三兰堡圭兰堡鎏窒 第二章数据预处理算法 2 1 为什么要预处理数据 当今现实世界中的数据库易受噪声数据、空缺数据和不一致数据的侵扰，为 了提高数据质量，从而提高挖掘结果的质量，必须进行数据预处理。 存在不完整的、含噪声的和不一致的数据是大型的、现实世界数据库或数据 仓库的共同特点。不完整数据的出现可能有多种原因。有些感兴趣的属性，并非 总是可用的。其他数据没有包含在内，可能只是因为输入时认为是不重要的。相 关数据没有记录是由于理解错误，或是因为设备故障。同其他记录的数据不一致 可能由于被删除。此外，记录历史或修改的数据可能被忽略。空缺的数据，特别 是某些属性上缺少值的元组可能需要推导。 数据含噪声可能有多种原因。收集数据的设备可能出现故障；人的或计算机 的错误可能在数据输入时出现；数据传输中的错误也可能出现。这些可能是由于 技术的限制，如用于数据传输同步的缓冲区大小的限制。不正确的数据也可能是 由命名或所用的数据代码不一致而导致的。重复元组也需要数据清理。 数据预处理的方法有： 数据清理：用于填充空缺的值，平滑数据，找出孤立点并纠正数据的不一致 性。 数据集成：将来自不同数据源的数据整合成一致的数据存储。元数据、相关 分析、数据冲突检测和语义异种性的解析都有助于数据集成。 数据变换：将数据变换成适于挖掘的形式。例如，属性数据可以规范化，使 得他们可以落入小区间，如0 0 到1 o 。 数据归约：可以用来得到数据集的归约表示，他小得多，但仍接近于保持元 数据的完整性。这样，在归约后的数据集上挖掘将更有效，并产生相同的分析结 果。如数据立方体聚集、维归约、数据压缩、数值归约和离散化都可用来得到数 据的归约表示，而使得信息内容的损失最小。 概念分层：可以根据定义分层的属性的不同值个数自动产生。 2 2 肺癌预后数据的预处理 中山三院提供的原始数据包含有1 7 0 0 多条记录，每条记录具有1 9 个属性。这 6 第二苹数据预处理算法 些属性中，对预后起作用的只有1 4 个属性，他们是年龄，性别，疾病名称，肿瘤 大小，病理类型，手术名称，死亡原因，辅助治疗方案，手术级别，手术性质， 临床分期，淋巴结转移，远处转移，生存期。除去无用属性后，原始数据库的部 分数据见表2 1 ： 表2 - 1 原始数据库部分数据 t a b l e 2 - 1s 咖ed a t ai no r i g i n a ld a t a b a s e 辅 i 助淋 疾肿病手死治手手临巴远 病瘤理术亡疗术术床结处 病案性 在 名大类名原方性级分转转 号别龄称小型称因案质别期移移生存期 腺 下鳞肺 3 9 9 1 0m5 0 叶 t 2癌叶1r l2n lm o5 1 7 7 腺 下鳞全 4 0 2 2 4m5 2 叶 t 3癌肺lr 23n o d o5 8 0 7 下鳞肺 4 1 0 2 4m6 0 肿 t 2癌 叶 o clr 1ln of r o5 6 3 4 下腺肺 4 2 0 2 2m5 6叶t 2癌 叶 1r lln om o5 4 4 7 下腺肺 4 2 6 l lm5 4 叶 t 2癌 叶lr 2l n om o 4 6 9 8 下鳞契 4 3 3 4 8m4 8 叶 t 2癌形 lr 1ln om o 4 9 5 5 下鳞契 4 3 9 8 2m6 5 卧 t 3癌形 2r 33n lm o 4 1 3 6 下鳞肺 4 4 0 5 6f5 4 叶 t 2癌 叶 1r 2ln om o 5 0 6 0 下鳞肺 4 4 3 4 5 m5 5叶t l癌 叶lr 21n om o3 2 2 1 原始数据中，存在一些矛盾或不一致的数据，由于这样的数据并不多，所以 我们使用人工方法删除这样的记录。 7 。 竺童堡三奎兰三兰璧圭兰堡篁塞 由上表我们可以看到，属性年龄是以年为单位的，生存期是以天为单位的， 它们都是连续属性。为了便于使用分类算法，提高挖掘效率，必须减少属性值的 个数。 采用离散化技术可以将属性域划分为区间，减少属性值的个数。区间的标号 可以代替实际的数据值。尤其是基于决策树的分类挖掘方法，减少属性值的数量 特别有好处。通常这种方法是递归的，大量的时间花在每一步的数据排序上。因 此，待排序的不同值越少，这种方法就应当越快。许多离散化技术都可以递归使 用，以便提供属性值的分层或多分解划分。我们将通过分析选择合适的方法将年 龄和生存期离散化。 对于年龄的区间划分，是根据医生的经验，将肺癌发病人群迸行分类得到。 在这里，年龄的划分区间为：0 3 9 ，4 0 - 4 9 ，5 0 5 4 ，5 5 - 5 9 ，6 0 6 9 ，7 0 以 上。类标号为0 ，1 ，2 ，3 ，4 ，5 。将类标号作为属性值，方便计算。 对于生存期的区问划分，是采用等频率的算法进行离散化。等频算法的思想 是：对于一连续型属性在实例集s 中观察到的最大值和最小值分别为u ，b ，将 b ，u 分成n 个小区间，使得每个小区间内包含的实例数大致相等。划分距离 d i s t a n c e 设为1 6 0 ，得到的区间为：0 1 2 2 ，1 2 3 2 0 8 ，2 0 9 - 3 1 4 ，3 1 5 4 2 0 ， 4 2 1 - 5 6 3 ，5 6 4 7 5 9 ，7 6 0 - 1 3 0 7 ，1 3 0 8 3 9 8 7 。类标号为0 ，l ，2 ，3 ，4 ， 5 ，6 ，7 。将类标号作为属性值，方便计算。 表2 - 2 为经过预处理后的数据库。 灏生成的数据库拥有1 3 0 0 多条记录，将作为后续算法的样本数据库。以上数 据表中，属性性别用1 表示男性，0 表示女性。而年龄和生存期已经进行了离散 化。疾病名称有“上叶”等四个属性值，肿瘤大小有“t 2 ”等五个属性值，死 亡原因有“m ”等八个属性值，病理类型有“腺癌”等八个属性值，远处转移 “m o ”等有两个属性值，淋巴结转移有“n o ”等五个属性值，临床分期有 “1 ”等四个属性值，手术性质有“0 ”等四个属性值，辅助治疗方案有 “o ”等二十一个属性值，手术级别有“r l ”等五个属性值，手术名称有“开 胸”等六个属性值。由此可见，数据库中记录条数并不多，但潜在的分类可能是 比较多的，这对挖掘工作提出了更高的要求，必须采用合适的算法进行挖掘a 预处理过程需要两次遍历数据库，由于数据库只有1 0 0 0 多条记录，大概几百 k ，所需的时间并不长。 8 第二章数据预处理算法 表2 2 新的数据库部分数据 1 a b l e 2 2s o m ed a t ai nn c w d a t a b a s e 辅 助淋 疾肿病手死治手手临巴远 病瘤理术亡疗 术术 床结处 病案性年名大类名原方性级分转转 号别龄称小型称因案质别期移移生存期 其腺开 6 1 5 0 2l3它t 3癌胸 3r o3n 2m o3 上腺契 7 2 2 6 0o3 叶 t 3癌形2r o4n 2m 13 上鳞肺 7 1 6 5 015 叶 t 3癌 叶 1r 43n 2m o3 腺 下 鳞契 7 0 6 1 814 卧 t 2癌形o2r o4n om 13 中腺肺 5 2 8 3 61 1 叶 t 2癌 叶 1r 21n o m 03 腺 上鳞肺 3 6 0 3 7 12 叶 t 2癌 叶 r1r t2n l哟 3 2 3 本章小结 概言之，现实世界的数据一般是脏的，不完整的和不一致的。数据预处理技 术可以改进数据的质量，从而有助于提高其后的挖掘过程的精度和性能。由于高 质量的决策必然依赖于高质量的数据，因此数据预处理是知识发现过程的重要步 骤。 原始数据库经过预处理，减少了许多不必要的数据或者噪声数据，得到的新 的数据库将作为进一步分析的样本数据库。 9 兰童堡三奎耋三兰堡圭兰堡丝苎 第三章肺癌生存期预测算法 生存期分析是肺癌预后的一个重要部分，通过分析样本病历，挖掘其中的规 律，给出新的病人生存时间的预测值。目前，生存期分析有不同的方法，医学领 域通常使用统计方法如寿命表，k a p l a n - m e i e r ，c o x 回归模型进行分析。而其他 慢性疾病也有采用专家系统进行分析的。但是，采用多种数据挖掘方法对肺癌生 存期进行预测的系统并未出现。 数据挖掘功能用于从指定数据挖掘任务中找到潜在的模式类型。挖掘任务一 般可分为描述和预测。预测性任务在当前数据上进行推断，以进行预测。医学数 据库内容丰富，蕴含信息量大，通过描述可以建立一个分类模型，如生存期分类 模型；同时建立预测模型，给定病人的各个属性，预测他的生存期。数据分类的 技术有很多，如判定树归纳、贝叶斯分类、神经网络等。本章将详细介绍用于肺 癌生存期预测的几个主要算法。讲述他们的基本原理以及算法实现和改进，然后 详细讨论他们与统计方法的比较结果。 3 1 决策树算法 决策树是一种结构简单、搜索效率高的分类器。这类方法以信息论为基 础，对大量的实例选择重要的特征建立决策树。决策树是一种经常要用到的技 术，可以用于分析数据，同样也可以用来作预测( 就像银行官员用它来预测贷款 风险) 。常用的算法有c h a i d 、c a r t 、q u e s t 和c 5 0 等。 决策树方法利用信息增益来寻找数据库中具有最大信息量的字段，建立决策 树的一个节点，再根据字段的不同取值建立决策树分支【“。最后，针对每个分支 子集，重复建立决策树的下层节点和分支过程。棵典型的决策树如图3 1 所 示。它表示概念b u y s c o m p u t e r ，即是，他预测a l l e c t r o n i c s 的顾客是否可能购 买计算机。每个节点用矩形表示，而树叶节点用椭圆表示。 1 0 ；。，一： 叁三垂壁查圭童塑鍪型叁鎏 图3 - i 一棵典型的决策树 f i g u r e 3 1 o n et i p i c a ld e c i s i o nt r e e 3 1 1 决策树归纳学习算法 决策树的基本算法是i d 3 算法 1 2 , 1 3 ( 贪心算法) ，它以自顶向下递归的各个 击破方式构造决策树。 算法概述如下： g e n e r a t e _ d e c i s i o n t r e e 由给定的训练数据产生一棵决策树 输入：训练样本s a m p l e s ，由离散属性表示，侯选属性的集合a t t r i b u t e 1 i s t 输出：一棵决策树 方法： 1 创建节点n ； 2 i fs a m p l e s 都在一个类ct h e n 3 返回n 作为叶节点，以类c 标记； 4 i fa t t r i h u t l i s t 为空t h e n 5 返回n 作为叶节点，标记为s a m p l e s 中最普通的类； 6 选择a t t r i b u t e l i s t 中具有最高信息增益的属性 t e s ta t t r i b u t e ； 7 标记节点n 为t e s ta t t r i b u t e ； 8 f o re a c ht e s ta t t r i b u t e 中的已知值a i ： 9 由节点n 长出一个条件为t e s t a t t r i b u t e = a i 的分枝； 1 0 设s i 是s a m p l e s 中t e s t a t t r i b u t e = a i 的样本的集合； 1 1 i fs i 为空t h e n 1 2 加上一个树叶，标记为s a m p l e s 中最普通的类； 1 3 e 1 s e 加上一个由 l i 一，丝查堡三奎兰三耋堡圭兰堡笙塞 g e n e r a t e d e c i s i o n t r e e ( s i ，a t t r i b u t el i s t ， t e s t a t t r i b u t e ) 返回的节点； 以上算法中的信息增益是这样计算的： 设s 是s 个数据样本的集合。假定类标号属性具有m 个不同值，定义m 个不 同类c j ( i = 1 ，m ) 。设s 。是类c l的样本数。对一个给定的样本分类所需的期望 信息为： i ( _ ，s 2 ，s 。) 2 一a l 0 9 2 ( p ；) ( 3 1 ) i = i 其中麒是任意样本属于e的概率。设属性a 具有v 个不同值 口，口： ， 口， 。可以用属性a 将s 划分为v 个子集 ( s，s 2 ， s ， ；其中，s ，包含s 中这样一些样本，它们在a 上具 有口。如果a 选为测试属性，则这些子集对应于由包含集合s 的节点生长出来 的分枝。设j 。是子集s ，中类c 。 的样本数。根据由a 划分成子集的熵为： e ( a ) = 窆翌粤鱼耶，) ( 3 - 2 ) 项兰二盟充当第j 个子集的权， s 并且等于子集中的样本个数除以s 中的样本 总数。熵值越小，子集划分的纯度越高。在a 上分枝将获得的编码信息是： g a i n ( a ) = i ( 函，s 2，j 。) 一e ( a ) ( 3 3 ) i d 3 选择使g a i n ( a ) 最大的属性a 作为分枝属性，这种方法使生成的决策树平均 深度较小，从而有较快的分类速度。但实践证明这个标准偏向于取值较多的属 性，于是q u i n l a n 对此进行了修正，提出了信息增益率的选择方法，增益率 定义为： g a i nr a t i o ( a ) = g a i n ( a ) e ( a )( 3 - 4 ) 3 1 2 决策树算法的改进和实现 i d 3 的算法核心是在决策树中各级节点上选择属性。目标是使得得到的分类 树精度高，速度快。j o h nm i n g e r s 等曾经用各种实验来比较各种属性选择标准， 最后的结论是属性的选择对精度影响不大 1 4 , 1 5 】。那么，在决策树的构成中影响这 些指标的因素是什么1 2 1 ? 我们可以从示例学习最优化的角度进行一下分析。 早在7 0 年代，m i c h a l s k i 就提出了示例学习的优化问题 ，而对其精度的 描述和计算复杂性的证明是由洪家荣于1 9 8 5 年给出的【2 2 】，在寻找最优化规则的 归纳偏向下，优化问题有口6 】： ( 1 ) 最优覆盖问题( m c v ) 一生成最少数目的公式( 合取式) 第三苹肺癌生存期预测算法 ( 2 ) 最简公式问题( 斛c o m p ) 一生成具有最少数目选择子及属性值的公式 ( 3 ) 最优示例学习问题( o p l ) 一生成只有最简公式的最优覆盖 考虑决策树归纳学习的最优化唧，可以先将决策树转化为规则形式，从而 由规则优化的三个目标就可以得到决策树归纳学习相应的三个优化原则。 假设t 是由m 个不同类c ，( b 1 ，m ) 所构成的决策树，对于t 中任何个非 叶节点h ，假设h 上的测试属性为爿，及树枝上的值v ，用一个选择子 a ；：v ， 来表示，那么，从根到任一叶节点的一条路径上的所有这样的选 择子合取就构成了一条公式，而根到所有标识为c ，的叶子的路径对应的公式的 析取即为c ，上的规则。 因此，要寻找最优决策树，也要解决如下三个最优问题： ( 1 ) 生成最少数目的叶子( 对应于m c v ) ( 2 ) 生成的每个叶子的深度最小( 对应于m c o m p ) ( 3 ) 生成的决策树叶子最少且每个叶子的深度最小( 对应于o p l ) i d 3 算法只是试图减少树的深度，而忽略了对决策树叶子数目的研究，而后 者对决策树的精度起了主要作用。 从最优决策树的角度出发，对原有算法进行改进。其基本思想是：在扩展决 策树的每一个非叶节点时，首先用信息熵的增益率作为属性选择标准，选择一个 增益率最大的属性作为扩展属性，然后利用值聚类来进行分枝合并。 使用信息熵的增益率来选择扩展属性，目的是保证该非叶节点到达各后代叶 节点的平均路径最短，即满足决策树优化的第二个条件，这样使得在每一非叶节 点进行测试时，能获得关于被测试例子最大的类别信息。 合并分枝是为了保证在每一非叶节点上进行扩展时，使它发出的分枝尽量 少，即叶子尽量少，从而满足决策树的第三个条件。 假定在决策树的某个非叶节点上，选择某一个属性a 作为扩展属性，a 的取 值范围是 v ，v ： ， v 。 ，计算出a 的各个值v ，的条件概率 对应a 的每一取值v ，选择类标号记为n ，使得 如果p r o b ( v ，c 。) p r o b ( v l c j ) 如果p r o b ( v ，c j) a r t v a l u e = v a l u e ： t e m p 一 s u n 2 s u n ： t e m p 一 n e x t = n u l l ； if ( s u d c o u n t = = o ) l a s t = s u n l is t = t e m p ： s u n _ c o u n t + + ： ) e l s e l a s t 一 n e x t = t e m p ： l a s t = t e m p ： t n o d e ( ) l a s t = n u l l ： s u n l i s t = n u l l ： s u nc o u n t = o ： ) t s u n _ n o d e * l a s t ： i n ts u nc o u n t ：代表该节点的子节点数 3 1 3 应用结果及分析 我们用c + + 实现了1 0 3 算法和改进后的算法，分别在下列实际闯题上进行了 比较。 首先，我们使用下表3 - 1 中的例子集进行测试。 华南理工大学工学硕士学位论文 表3 - 1 例子集 t a b l e 3 1 s a m p l ed a t a b a s e n oo u t l o o k t e m p e r a t u r eh u m i d i t yw i n d yc l a s s l o v e r c a s th o t h i g h f a l s e p 2r a i nm i l d h i g h f a l s e p 3r a i nc o o ln o r m a lf a l s e p 4o v e r c a s tc o o ln o r m a lt r u e p 5 s u n n y c o o ln o r m a lf a l s e p 6r a i nm i l dn o r m a lf a l s e p 7s u n n ym i i dn o r m a lt r u ep 8o v e r c a s tm i l dh i g h t r u e p 9o v e r c a s th o t n o r m a lf a l s e p 1 0 s u n n y i o t h i g h f a l s e p 1 1 s u n n y