计算机辅助医学 医学数据挖掘（上） 刘雷 上海生物信息技术研究中心 2013.3.15

提纲 基本概念 1 关键技术 2 应用实例 3 相关工具 4 创新点 单列

提纲 基本概念 1 关键技术 2 应用实例 3 相关工具 4 创新点 单列

背景 什么激发了数据挖掘？ 需求是发明之母 数据挖掘引起了信息产业的极大关注，主要原因是存在大量的数据，并且迫切需要将这些数据转换成有用的信息和知识。

背景 数据挖掘是信息技术自然演化的结果 数据收集和数据库创建 数据库管理系统 高级数据库系统 基于Web的数据库系统 数据仓库和数据挖掘 （20世纪60年代和更早） --原始文件处理 数据库管理系统 （70年代） 层次和网状数据库系统 关系数据库系统 数据建模工具：实体-联系模型 索引和数据组织技术：b+树 查询语言：SQL等 联机事务处理（OLTP） 高级数据库系统 （80年代中期-现在） 基于Web的数据库系统 （90年代中期-现在） --高级数据模型 --面向应用 --基于XML的数据库系统 --Web挖掘 数据仓库和数据挖掘 （80年代后期-现在） --数据仓库和OLAP --数据挖掘和知识发现 数据库技术的演化 Jiawei Han， Data Mining 新一代综合信息系统 （2000-。。。）

背景 数据的丰富带来了对强有力的数据分析工具的需求 Databases are too big

数据挖掘—概念 数据挖掘是从大量数据中提取或“挖掘”知识。 大规模和快速的统计学。 数据挖掘正处在变动和发展过程中，有很多数据挖掘的定义，也有很多关于数据挖掘是什么和不是什么的讨论。 数据挖掘是从大量数据中提取或“挖掘”知识。 --Jiawei Han，Micheline Kamber， Data Mining： Concepts and Techniques 大规模和快速的统计学。 --Darryl Pregibon 数据挖掘是用模式识别、统计学、数学等方法过滤存储在数据库中大量的数据来发现新的、有意义的关系、模式和趋势的过程。 --Gartner小组

数据挖掘—概念 相关概念 a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases. 机器学习（machine learning） 人工智能（machine learning） the intelligence of machines and the branch of computer science that aims to create it. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes In machine learning, pattern recognition is the assignment of some sort of output value (or label) to a given input value (or instance), according to some specific algorithm. 模式识别 （ pattern recognition ）

数据挖掘– 概念 数据挖掘是一个交叉学科 数据库技术 机器学习 数据挖掘 信息科学 统计学 可视化 其他科学

（description and visualization） 数据挖掘– 任务分类 分类（classification） 聚类（clustering） 预测（prediction） 估值（estimation） 数据挖掘 描述和可视化 （description and visualization） 关联分析（association）

背景 什么激发了医学数据挖掘？ 需求是发明之母 计算机信息管理系统的应用 电子病历和病案的大量应用 医疗设备和仪器的数字化 分子生物学方法在医学上的应用 数据 数据 数据 数据

背景 如何利用海量数据的信息资源 为疾病的诊断和治疗提供科学的决策 为医学基础、临床研究提供知识 更好的为远程医疗及社区医疗提供保证

背景 常用医学数据分析方法 统计方法 常用统计软件 SPSS SAS S-Plus

背景 常用方法的局限性 量 – 大数据量 维 -- 高维度 Data Mining 医学数据 模型 知识 数据挖掘的方法 1 现有的方法要求你给他的变量要求低维度； 2 只有数据挖掘领域是在研究变量的抽提，传统领域的特征都是靠研究人员自己选取的，经验很重要，

医学数据挖掘 医学数据 记录内容多 病人基本信息 手术记录 出院小结 免疫组化结果 影像学检测结果

医学数据挖掘 医学数据 记录的形式多样 纸质vs电子 Excel vs 自然语言 图像 …… 电子病历 EXCEL表格

医学数据挖掘 医学数据 不完整性 时间性。 冗余性。 病例和病案的有限性使医学数据库不可能对任何一种疾病信息都能全面地反映, 表现为医学信息的不完全性。 时间性。 医学检测的波形、 图像都是时间的函数。 冗余性。 医学数据库是一个庞大的数据资源, 每天都会有大量相同的或部分相同的信息存储在其中。

医学数据挖掘 高通量生物医学数据特点 纬度高 数据量大

医学数据挖掘 数据挖掘技术在生物医学方面面临的挑战 医学数据存储 大规模、高通量、高维度数据的处理 高效、准确、稳定的分析方法

医学数据挖掘的关键技术 数据预处理 医学数据库中含有海量的、 不同来源的原始信息, 其中包括大量模糊的、 不完整的、 带有噪声和冗余的信息。 在数据挖掘之前, 必须对这些信息进行清理

医学数据挖掘的关键技术 信息融合技术 医学信息是由文字、 数据、 波形信号、 图像、 以及少量的语音和视频信号组成。 对这些不同物理属性的医学数据, 应采用不同的技术和措施进行处理

医学数据挖掘的关键技术 快速的、 鲁棒的挖掘算法 医学数据数据量大，必须考虑医学数据挖掘的效率问题 研究快速挖掘算法对于远程医疗和社区医疗具有更深远的意义, 将直接影响其响应速度和医疗成本。

医学数据挖掘的关键技术 提供知识的准确性和可靠性 医学数据挖掘的主要目的是为医疗活动和管理提供科学的决策 如何降低医学数据挖掘过程中的风险, 提高挖掘结果的准确性和科学性, 是医学数据挖掘能否得到实际应用的关键所在。

数据挖掘的一般过程 挖掘出的知识 结果解释和评估 数据挖掘 算法执行 数据收集 数据预处理 问题定义 数据挖掘的过程

数据挖掘的关键步骤 Learning the application domain 学习领域知识 relevant prior knowledge and goals of application 相关知识和目标 Creating a target data set: data selection 选择数据 Data cleaning and preprocessing: (may take 60% of effort!) 数据清理 Data reduction and transformation 数据转换 Find useful features, dimensionality/variable reduction, invariant representation 提取特征 早 期 预 处 理 数 据 预 处 理

数据挖掘的关键步骤 Choosing functions of data mining 选挖掘功能，如： summarization, classification, regression, association, clustering Choosing the mining algorithm(s) 选算法 Data mining: search for patterns of interest 挖掘模式 Pattern evaluation and knowledge presentation 评价结果，知识表达 visualization, transformation, removing redundant patterns, etc. 可视化，转换 Use of discovered knowledge 挖 掘 后 期 处 理

数据挖掘金字塔 Decision Making 决策 Data Presentation表达 不同层次的用户 End User Increasing potential to support business decisions 向上—更宏观 决策 Decision Making 决策 Data Presentation表达 Business Analyst Visualization Techniques Data Mining 挖掘 Data Analyst Information Discovery Data Exploration 统计等等 Statistical Summary, Querying, and Reporting 预处理/集成, 数据仓库 DBA Data Sources 数据源 Paper, Files, Web documents, Scientific experiments, Database Systems

数据预处理 数据整合 数据仓库 不同试验点 不同时间段 不同记录格式 不同的数据集合度 不同的错误形式 数据关联 整合程度 挑战 将不同数据源进行整合式一项具有挑战性的工作 数据仓库 整合程度

数据预处理 残缺值 不正确的值 通常指超出正常范围，或者在一个正常情况下不可能出现0值的位置出现0. 填补残缺值 残缺值出现的原因 舍去残缺值 寻找残缺值出现的原因，并根据原因觉得是否填补残缺值。 找到数据中的不良属性及属性值，同时要注意数据的有效性和时效性 不良属性及属性值 数据的有效期

变量选择 The more , the better? Yes and No 维度增高，对数据的描述全面， 信息量增大 有些数据维度可能带有噪声 维度过大增加了计算量 数据量 数据维度

变量选择 特征选择 特征抽提 降低特征空间的维数 降低计算复杂度 提高分类的准确率 从一组特征中选出一部分最有代表性的特征。 从原来的特征空间里面选出一个真子集 特征抽提 采用变换的方式将原来的高维空间映射到一个低维空间 可以看作从测量空间到特征空间的一种映射(Mapping) 或变换( Transform) 特征选择和特征抽取可以降低特征空间的维数 ,从而达到降低计算复杂度和提高分类的准确率的目的 ,并为后面的分类器的设计提供参数。

特征选择 涉及的领域越来越广 电子、工业、医学 数据类型越来越多 高通量数据 文本 图像 ……

特征选择 特征选择的数学定义： 所谓特征选择，就是从 L 个度量值集合{x1,x2,…,xL}中，按某一准则 J 选择出供分类用的子集，作为降维(m 维,m<L)的分类特征 特征选择的任务是求出一组对分类最有效的特征，因此，我们需要一个定量的准则（或称判据）来衡量特征对分类的有效性

特征选择 特征选择是模式识别的重要组成部分，它主要有两方面应用： 从特征空间中选择一个维数更小的特征子空间以最好的表达某个类自身； 从特征空间中选择一个维数更小的特征子空间用于最好的区分不同类别。

特征选择 特征选择可以有效的降低维数 不相关的变量（irrelevant features） 冗余的变量（redundant features） 计算此圆的面积 在知道半径r的情况下，直径d为冗余变量 颜色（） 为不相关的变量 S=π*r*r

特征选择 两种途径 排序（rank） 子集（subset） —————— ————— ———— ——— —— S1 S2 S3

特征选择 相关概念 Models Search strategies Feature quality measures Evaluation

特征选择 models Filter Methods Wrapper Methods Select the best features according to a reasonable criterion The criterion is independent of the real problem Wrapper Methods Select the best features according to the final criterion For each subset of features, try to solve the problem Filter: Basic idea: select the best features according to some prior knowledge, eg :features should have strong correlation with the target Wapper: Basic (naive) algorithm: 1 For each subset of features, solve the problem. 2 Select the best subset. Impossible because the problem is exponentially long! Alternatives: greedy heuristics such as forward selection or backward elimination Both methods are ultimately heuristics because of the combinatorial barrier. Wrappers try to solve the real problem, hence you really optimize your criterion. Filters solve a different problem... it might not be appropriate. Wrappers are potentially very time consuming: you have to solve the ultimate problem numerous times. Filters are much faster because the problem they solve is in general simpler.

特征选择 Search strategies 完全搜索策略 非完全搜索策略 前向 后向 随机 穷举法 分支定界法 启发式搜索策略 P Q F 穷举法：对所有可能的组合进行搜索 分支界定法： Branch and bound (BB or B&B) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized. 求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出某种意义下的最优解。分支界定法以广度优先或者以最小消耗优先的方式搜索解空间树。 在分支界定法中，每一个活节点只有一次机会成为扩展结点。活结点一旦成为扩展结点，导致不可行解或者导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点列表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这一过程一直持续到找到所需的解或者活结点表为空时为止。 常见的两种分支界定法：1、队列式（FIFO：first in first out）按照队列先进先出原则选取下一个结点为扩展结点 2、 优先队列式---按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展结点。 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 一般需要领域知识，针对特定问题 F F F 前向：最优P F F F F F 后向：最优Q

特征选择 Feature quality measures 欧几里德距离（Euclidean distance） 特征熵 信息增益 @欧几里得距离定义： 欧几里得距离（ Euclidean distance）也称欧式距离，它是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。 　　在二维和三维空间中的欧式距离的就是两点之间的距离，二维的公式是 　　d = sqrt((x1-x2)^+(y1-y2)^) @熵（entropy）指的是体系的混乱的程度，它在控制论、概率论、数论、天体物理、生命科学等领域都有重要应用，在不同的学科中也有引申出的更为具体的 定义，是各领域十分重要的参量。熵由鲁道夫·克劳修斯（Rudolf Clausius）提出，并应用在热力学中。后来在，克劳德·艾尔伍德·香农（Claude Elwood Shannon）第一次将熵的概念引入到信息论中来。 @信息增益是常用的特征变量选取的方法之一，也是最有效的特征选择方法之一。随机事件的信息量通常使用熵的形式来度量，信息增益是信息熵的差值，表示某一属性存在于否对正确分类带来的信息量。某一属性的信息增益表 示为： InfoGain(Class,Attribute) = H(Class) - H(Class | Attribute) 其中H(Class)表示观测某属性（Attribute）前系统的熵，即类别Class 所提供的信息量；H(Class | Attribute)表示观测某属性（Attribute）后分类的不确定性；信息增益InfoGain(Class,Attribute)表示属性Attribute 对分类的作用，即Attribute 所能提供的分类信息量。

特征选择 Evaluation 特征选择前后的比较 不同特征选取方法的比较 特征选择前后 对 数据挖掘任务完成能力的比较

特征选择 有指导 无指导 半指导 数据集有分类标签 例如：信息熵增益 数据集无分类标签 例如：聚类--k-means 小部分数据有分类标签 大部分数据没有分类标签

数据挖掘—方法 数据挖掘方法 统计方法 机器学习 神经计算 可视化

医学数据挖掘—方法 数据挖掘方法 常用的数据挖掘方法一般都可用于医学数据 分类方法 聚类方法 SVM Logistic回归 决策树 K-近邻 SOM

数据挖掘 – 方法 Apriori Algorithm 关联规则 强关联规则满足最小支持度和最小置信度 找频繁项集 候选项集合 Support 置信度表示了这条规则有多大程度上值得可信 The first step of Apriori is to count up the frequencies, called the supports, of each member item separately We can define a minimum support level to qualify as "frequent," which depends on the context. 频繁项集 产生关联规则 Confidence(A==>B)=P(B|A)=support(A∪B)/spuuort(A) 有效规则

数据挖掘– 方法 Logistic回归 分类 因变量可以是二分类、多分类 自变量可以为类别变量、连续属性 寻找危险因素 预测 判别 流行病学和医学最常用的分析方法 由此可以见，富士康的跳楼人数最终会稳定在在22人左右。。。由此仍然不会超过全国平均跳楼率。 　　对此曲线的分析，我们借鉴微生物生长曲线的方法，将其分为： 　　缓慢期，对数期，稳定期，衰亡期 　　     　　缓慢期，富士康员工虽然受到很大的工作压力，可是其自身的心理并没有崩溃，因此跳楼这种事件发生频率很少，而且呈线性关系，说明没有跳楼者受到别的跳楼者的影响。 　　对数期，富士康员工由于受到工厂巨大的工作压力，以及来自社会各方的压力，甚至加上上级的欺压，心理防线渐渐崩溃，无处发泄。而一旦有想不开者跳楼，则为其提供了一个发泄的模板，这种情况下，很容易有相同经历的员工收到跳楼者的影响，从而一个接一个的跳楼自杀。目前的富士康正处于此时期 　　稳定期，由于社会、媒体各方面的关注，以及社会，广大人民对工厂的压力，工厂不得不做出改变，员工的心理压力渐渐得到释放，从而员工跳楼亲生频率会很快下降。 　　衰亡期，这个。。。由于资料长期保存，不小心遗失；或者某机关的辟谣；或者所有人的健忘，导致跳楼人数被修正，被减少。 p是特定事件发生的概率。Logistic回归中的常数项（b）表示在不接触任何潜在危险/保护因素条件下，效应指标发生与不发生的概率之比的对数值；回归系数（）表示某一因素改变一个单位时，效应指标发生与不发生事件的概率之比的对数变化值。一般可以使用迭代的方法求解公式中的系数和b。 logistic回归又称logistic回归分析，主要在流行病学中应用较多，比较常用的情形是探索某疾病的危险因素，根据危险因素预测某疾病发生的概率，等等。例如，想探讨胃癌发生的危险因素，可以选择两组人群，一组是胃癌组，一组是非胃癌组，两组人群肯定有不同的体征和生活方式等。这里的因变量就是是否胃癌，即“是”或“否”，为两分类变量，自变量就可以包括很多了，例如年龄、性别、饮食习惯、幽门螺杆菌感染等。自变量既可以是连续的，也可以是分类的。通过logistic回归分析，就可以大致了解到底哪些因素是胃癌的危险因素。 一是寻找危险因素 　　正如上面所说的寻找某一疾病的危险因素等。 二是预测 　　如果已经建立了logistic回归模型，则可以根据模型，预测在不同的自变量情况下，发生某病或某种情况的概率有多大。 三是判别 　　实际上跟预测有些类似，也是根据logistic模型，判断某人属于某病或属于某种情况的概率有多大，也就是看一下这个人有多大的可能性是属于某病。 寻找危险因素 预测 判别 富士康跳楼事件

数据挖掘 – 方法 AdaBoost 分类 将分类性能较差的弱分类器串联起来，通过加权投票机制有效提升弱分类器的分类性能

数据挖掘– 方法 分类 决策树 通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值 CEA 阳性 阴性 AFP 预后差 预后好 实例是由属性-值对表示的 目标函数具有离散的输出值 可能需要析取的描述 训练数据可以包含错误 训练数据可以包含缺少属性值的实例

数据挖掘– 方法 分类 AD Tree Alternative Decision Tree（ADTree）是一种结合决策树（Decision Tree）和Boosting的分类方法 一棵ADTree由若干决策节点（decision node）和预测节点（prediction node）组成，其中决策节点表示一个预测状态，预测节点包含一个数字。ADTree以预测节点为根节点，同时以预测节点为叶子节点。 ADTree方法优于AdaBoost之处在于，ADTree方法假定当前的弱分类器是建立在之前迭代结果的基础上的，并能以树（Tree）的形式将各弱分类器展示出来，

数据挖掘 – 方法 聚类 K近邻 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。 K近邻中的k一般为奇数，避免因两种票数相等而无法决定。 基因芯片分析 癌细胞聚类分析

数据挖掘– 方法 聚类 自组织映射 自组织神经网络SOM（self-organization mapping net）通过自动寻找样本中的内在规律和属性，自组织、自适应的改变网络的参数与结构。 竞争学习 基于无监督学习方法的神经网络的一种重要类型。 向量归一化 胃癌尿液蛋白组数据分析 寻求获胜神经元 网络输出与权值调整

数据挖掘 – 评价 算法评价效果的评价 常用评价方法 True Positive False Positive Accuracy Specific Sensitive

数据挖掘– 评价 算法评价效果的评价

数据挖掘– 评价 算法评价效果的评价 ROC曲线 receiver operating characteristic curve 横坐标为FPR值 纵坐标为TPR值 是算法的综合评价 ROC曲线下面积评价算法的优劣

数据挖掘 ROC曲线计算方法

数据挖掘的评价 交叉验证 K折交叉验证（k-fold cross validation） 留一法（leave-one-out）

参考资料 Books Journal articles Internet Jiawei Han, Micheline Kamber. Data Mining-Concepts and Techniques.(Second Edition) Ian H. Witten, Eibe Frank. Data Mining- Practical Machine Learning Tools and Techniques. (Second Edition) … Journal articles Riccardo Bellazzi, Blaz Zupan. Predictive data mining in clinical medicine: Current issues and guidelines. Isabelle Guyon, Andr´e Elisseeff. An Introduction to Variable and Feature Selection. Internet

谢谢！ 刘雷 上海生物信息技术研究中心 2013.3.15