从形成模型的共同可能性进行预测

摘要

本发明涉及一个系统，方法和计算机程序产品，用来确定是否一个测试例子是在第一或第二数据类中(例如：癌变的和正常的)，该方法包括：从一个训练数据组中提取多个形成模型，创建第一和第二列表，其中分别包含每一个在第一和第二数据类中有非零发生的形成模型的发生频率；使用固定数量的形成模型，计算分别衍生于在第一列表中的形成模型的频率也在测试数据中发生的第一和第二得分，在第二列表中的形成模型的频率也在测试数据中发生的第一和第二得分；通过选择在第一和第二得分中较高的得分，推断测试例子是归类于第一还是第二数据类中。

说明书

技术领域

本发明广泛地涉及数据挖掘方法，更特别地涉及基于规则的方法，该方法是基于那些类的数据知识，将一个测试范例正确地分到2个或多个可能的类之一中。特别是本发明使用了形成模型的技术。

背景技术：

数字时代的到来就象洪水猛兽扑面而来：信息的洪流被释放出来，我们在经受着不断扩大地数据浪潮的冲击。信息、结果、测试、计算—数据，通常—是非常丰富，而且以一种随时可取可用的方式存储于磁介质或光介质上。随着计算能力不断地提高，能够有效分析巨大数据量的希望经常被实现，而且对能够分析更大量数据的期望仍然在为发展更为尖端的分析方案提供着推动力。因此，要把经常存在的变成有意义的数据，从而把他转换成有用的知识。这是需要通过使用统计分析、模型识别和数据挖掘的方法来驱动实质性的研究成果。现有的挑战不但包括当面对大量的数据时有正确衡量方法的能力，而且要提供处理噪声数据的方法。这些挑战还未完成，或是存在于复杂的参数空间中。

数据不仅仅是数字、值或包含的属性。数据存在于多维空间象丰富的海港和多样的地形，他们不仅仅是奇异的和费解的，而且是不容易被大脑所理解的。最复杂的数据是来自测量和计算中，依赖于许多明显独立的变量。成百变量的数据组来自于当今生活中的许多专业，包括：用于揭示染色体与不同蛋白质之间编码联系的基因表现数据；通过人口统计学和消费者概况数据来获得潜在的社会和经济趋势；通过环境测量数据来理解现象，诸如污染、气象变化和资源冲突的问题。

在处理数据的原理性操作中，象回归、分组、概括、依靠模型、变换和偏移检测，这些分类是最重要的。当在特定的变量之间没有明显的相关性时，必须要推出潜在的模型和规则。数据挖掘的分类重点在建立精确和有效的分类器，象模型和规则。在过去，这种方法可能还适用，但将这种方法用于大量的数据组就成为艰苦的劳动。因此，导致了多年以后机器学习领域的产生。

因此通过简单的洞察来提取模型、关系和隐含规则已经被自动分析工具的使用所替代。然而，理想的推导模型代表的不仅是对复杂问题的征服，还包括推导规则，即指示那些确定性的参数和指向使用新的、实用的方法。这是用数据挖掘的实质：模型不但利用加在数据上的结构，而且提供一个预测作用，这个作用是有价值的，能确定新数据在哪里能连续地获得。从这种意义上说，一个广泛合适的范例是通过使用一些初始的数据组和通常称做一个训练组，从“学习”的过程中得出模型。然而今天使用许多技术不是在没有建立规则和模型就预测新数据的属性，就是建立了具有预测性但不可理解的分类方案。此外，许多这类方法对于大量数据组不是非常有效的。

近期，四种优良的模型属性已经被清楚的表达出来(参见，Dong andLi，″Efficient Mining of Emerging Patterns：Discovering Trends andDifferences，″ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining，San Diego，43-52(August，1999)，通过目录的方式都集合于此)：(a)他们是合法的，即新数据也肯定遵守这条规则；(b)他们是新颖的，从这个意义讲由机器衍生的模型对专家是不明显的，并提供新的观点；(c)他们是有用的，即他们能可靠的预测；(d)他们是可理解的，即他们代表的态势对他们的理解没障碍。

在机器学习的领域，最广泛使用的预测方法包括：K-最近邻居(参见，例如：Cover & Hart，″Nearest neighbor pattern classification，″IEEETransactions on Inforrleation Theory，13：21-27，(1967))；neuralnetworks(see，e.g.，Bishop，Neural Networks for Pattern Recognition，Oxford University Press(1995))；Support Vector Machines(seeBurges，″A tutorial on support vector machines for patternrecognition，″Data Mining and Knowledge Discovery，2：121-167，(1998))；Naive Bayes(see，e.g.，Langley et al.，″An analysis ofBayesian classifier，″Proceedings of the Tenth National Conference onArtificial Intelligence，223-228，(AAAI Press，1992)；originally in：Duda &Hart，Pattern Classification and Scene Analysis，(John Wiley & Sons，NY，1973))；and C4.5(see Quinlan，C4.5：Programs for machinelearning，(Morgan Kaufmann，San Mateo，CA，1993))。尽管他们流行，但是每种方法都受到某些缺点的困扰，就是说他们都不能产生具有前面讨论过的四种优良属性的模型。

K—最近邻居方法(“k-NN”)是一个基于实例的例子，或着称“懒惰—学习”(lazy-learning)方法。在懒惰学习法中，新数据实例是通过直接与在学习组中的项目对比来进行分类，而不是得自外在的模型。k-NN方法把测试例子分配给在训练例子中它的K最近邻居的类，在那里近的程度被按照类似距离的度量方法被测量。虽然k-NN方法简单且具有良好的性能，但是不能经常帮助更深层次对复杂情况的完全理解，也从来没有建立过预测的基本规则。

神经网络系统(参见，例如，Minsky & Papert，″Perceptrons：Anintroduction to computationalgeometry，″MIT Press，Cambridge，MA，(1969))也是预测新数据分类工具的例子，但是没有产生人可以理解的规则。神经网络系统在喜欢使用“黑匣子”方法的人中仍保持流行。

单纯贝叶斯(“NB”)使用贝叶斯规则计算数据组中每个数据类随机性的和。当给定一个测试例子，NB根据他们随机性的和使用评估功能来进行分类，把例子分配给最高得分的类。然而，NB引起给定测试数据实例的随机性，并没有导出一般可识别的规则和模型。此外，一个重要的假设使用在NB中，他的特征是独立统计的，然而对于多个种类的数据并不是这种情况。例如，许多基因包含于一个基因表现图谱中，明显不是独立的，但他们中的一些关系很接近的(参见，例如，Schena etal.，″Quantitative monitoring of gene expression patterns with acomplementary DNA microarray″，Science，270，467-470，(1995)；Lockhart et al.，″Expression monitoring by hybridization to high-densityoligonucleotide arrays″，Nature Biotech.，14：1675-1680，(1996)；Velculescu et al.，″Serial analysis of gene expression″，Science，270：484-487，(1995)；Chu et al.，″The transcriptional program ofsporulation in budding yeast″，Science，282：699-705，(1998)；DeRisietal.，″Exploring the metabolic and genetic control of gene expressionon a genomic scale″，Science 278：680-686，(1997)；Roberts etal.，″Signaling and circuitry of multiple MAPK pathways revealed by amatrix of global gene expression profiles″，Science，287：873-880，(2000)；Alon et al.，″Broad patterns of gene expression revealed byclustering analysis of tumor and normal colon tissues probed byoligonucleotide arrays″，Proc.Natl.Acad.Sci.U.S.A.，96：6745-6750，(1999)；Golub et al.，″Molecular classification of cancer：Class discoveryand class prediction by gene expression monitoring″，Science，286：531-537，(1999)；Perou et al.，″Distinctive gene expression patterns inhuman mammary epithelial cells and breast cancers″，Proc.Natl.Acad.Sci.U.S.A.，96：9212-9217，(1999)；Wang et al.，″Monitoring geneexpression profile changes in ovarian carcinomas using cdnamicoroarray″，Gene，229：101-108，(1999)).

支持向量机(“SVM’s”)处理不能有效使用线性方法模拟地数据。SVM’s使用非线性内核功能在例子和他们的类属性之间建立复杂的映像。结果模型是那些有信息的，因为他们突出那些通过定义理想的超平面来分离在多维空间中的数据类。SVM’s能处理复杂的数据，但是行为象“黑匣子”(参考，Furey et al.，″Support vector machine classificationand validation of cancer tissue samples using microarray expressiondata，″Bioinformatics，16：906-914，(2000))和趋向计算的高昂。此外，令人满意的是具有一些数据的可变评价，用来选择合适的非线性内核功能—正确的评价不是每次都出现的。

因此，从数据挖掘的角度来这种将把看似全异的信息块压缩成清楚的组合规则的技术是令人满意的。基于规则在数据中展现结构模型的两种基本方法是确定树和规则归纳法。确定树提供有用和直观的分割数据组的框架，但是重点在选择起始点。这样，假设在训练组中几个规则块是明显的，通过确定树的构造使得规则立刻变的明显，规则主要取决于使用哪个分路器来种树。所以非常重要的规则和对数据的重要分析框架经常可见的确定树中看到。此外，虽然从树到一组规则的转换通常是一直向前的，但是那些规则通常不是最清楚或最简单。相比，规则归纳法是最优先的，因为他们搜索说明象许多规则一样的可能性，还有依据一个或多个规则对数据组中的每个实例分类。然而，许多的混合规则归纳法、确定树法已经设计尝试去分别利用树使用的易用性和规则归纳法的详尽。

C4.5法是如今使用的最成功的确定树法中的一种。他采用确定树逼近包含持续变化数据的数据组。尽管，一种采用确定树中叶节点一直向前的规则是将所有情形简单的连接在一起。这些情形是从根节点到叶之间来回穿梭的路径中遇到的，C4.5法试图通过修剪树在中间的点和引入地对可能修剪操作的出错估计来简化这些规则。虽然C4.5产生易于理解的规则，但是如果确定边界不是线性的，他就不具高的性能，这个现象造成有必要对在树中不同的点特定的变化用不同的分割。

近期，具有前面提到的4种优良属性的类预测法已经被提议。他是基于形成模型的理念(Dong and Li，ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining，San Diego，43-52(August，1999))。一个形成模型(“EP”)在比较数据类中是有用的：它指示大的存在在第一数据类中的属性，还有大的不存在第二互补数据类的属性，即数据与第一类没有重复。算法已经完善，是由大型数据组演变来的EP’s和已经应用于基因表现数据的分类法中(参见，例如，Li and Wong，″Emerging Patterns and GeneExpressionData，″Genomelnformatics，12：3-13，(2001)；LiandWong，″Identifying Good Diagnostic Gene Groups from GeneExpression Profiles Using the Concept ofEmergingPatterns，″Bioiformatics，18：725-734，(2002)；and Yeoh，etal.，″Classification，subtype discovery，and prediction of outcome inpediatric acute lymphoblastic leukemia by geneexpressionprofiling，″Cancer Cell，1：133-143，(2002))。

通常可能会从给定的数据组中产生成千的EP’s，在这种情况下用EP’s来划分新的数据实例是难于处理的。先前尝试处理这个问题包括以下方法：通过聚合形成模型的分类法(参考Dong，et al.，″CAEP：Classification  by Aggregating  Emerging Patterns，″in，DS-99：Proceedings of Second International Conference on Discovery Science，Tokyo，Japan，(December 6-8，1999)；also in：Lecture Notes in ArtificialIntelligence，Setsuo Arikawa，Koichi Furukawa(Eds.)，1721：30-42，(Springer，1999))；and the useof″jumping EP′s″(Li，etal.，″Making useof the most expressive jumping emerging patternsforclassification.″Knowledge and Information Systems，3：131-145，(2001)；and，Li，et al.，″The Space of Jumping Emerging Patterns and ItsIncremental Maintenance Algorithms，″Proceedingsof 17thInternational Cofaferece on Machine Learning，552-558(2000))，在整体中通过参考把所有的模型都组合在一起。在CAEP中，识别一个给定的EP也许只能在给定的数据组中分类出少量的实例，一个测试数据的例子通过构造它形成模型的合成分数来分类。跳跃式EP’S(”J-EP’S)是特殊的EP’S，它的支持为一个得分是零的数据类，但是它的支持在数据互补类中不为零。这样J-EP’S在分类法中是有用的，因为他们代表的模型的变化很强，但是这样仍然还有大量的模型，意味着分析还是很复杂的。

同时使用CAEP和J-EP’S的工作还很困难，因为当分类新数据时，要考虑EP’S的所有或很大数量的数字。在如今的应用中当处理非常大的数据量时，有效性是极其重要的。然而理想的方法应该是通向合法的、新颖的、有用的、可理解的规则，但是在低成本下，通过使用有效的逼近来确定少量的规则的方法在分类法中是真正有用的。

发明内容

本发明提供了一种方法，用计算机程序产品和系统来确定是否一个测试例子，具有测试数据T，归类于许多类的其中之一。

优选地，类的数字是3或更多方法的组成；从训练数据组D中提取多数的形成模型，N个数据类的每个都至少有一个实例；创建n个列表，其中：n个列表的第i列表包含在第i数据类中非零发生的多数形成模型的每一个形成模型EPi(m)的一个发生的频率，Fi(m)；使用形成模型的一个固定数量，k，在这里k充分小于在多数形成模型中的形成模型的总数，计算n个得分其中：n个得分的第i个得分是来自在测试数据中也发生中的第i列表中的k个形成模型的频率；通过选择n个得分中最高的，推测测试数据在n个数据类中被归类于那个类。

另外，发明也提供一个方法，确定是否测试范例，有测试数据T，在第一类或第二类中分类，包括：从训练数据组D中提取至少有一个第一数据类的实例和至少有一个第二数据类的实例的多数的形成模型；在其中创建第一列表和第二列表：第一列表包括在第一数据类中有非零发生的多数形成模型的每个形成模型EP1(m)的一个发生频率F1(m)；第二列表包括在第二数据类中有非零发生的多数形成模型的每个形成模型EP2(m)的一个发生频率F2(m)；使用形成模型的一个固定数量，k，其中数字k充分小于在多数形成模型中形成模型的总数，计算：第一个得分是来自也在测试数据中发生的在第一个列表中的k个形成模型的频率，第二个得分是来自也在测试数据中发生的第二个列表中k个形成模型的频率，同时；通过选择第一得分和第二得分中较高的，推测测试数据是归类于第一数据类或第二数据类。

本发明进一步提供了计算机程序产品来确定是否一个测试例子，存在测试数据是按第一数据类或第二数据类分类，其中计算机程序产品使用连接的计算机系统，计算机程序产品由计算机可读的存储介质计算机程序设备组成，计算机程序设备包括：至少一个统计分析工具；至少一个排序工具；控制指令包括：获取一个数据组至少包括一个第一数据类的实例和至少包括一个第二数据类实例；从数据组中提取一个多数的形成模型；为每一个多数的形成模型创建第一列表和第二列表：第一列表包括在第一数据类中有非零发生的多个形成模型的每一个形成模型i的一个发生频率，Fi(1)，第二列表包括在第二数据类中有非零发生的多个形成模型的每个形成模型i的一个发生频率，Fi(2)；使用形成模型的一个固定数量，k，其中k是充分小于在复杂形成模型中形成模型的总数，计算：第一得分来自也在测试数据中发生的第一列表k个形成模型的频率，第二得分来自也在测试数据中发生第二列表k个形成模型的频率；通过选择第一得分和第二得分较高的，推测测试例子是归类于第一数据类或第二数据类。

本发明还提供了一个系统用于确定是否测试例子存在可用第一类或第二类分类的测试数据，系统包括：至少一个存储单元，至少一个处理器，至少一个用户界面，所有设备都相互连在至少一个总线上；其中至少一个处理器设置成：可以获取数据组中至少含有一个第一数据类的实例和至少含有一个第二数据类的实例；从数据组中提取多数形成模型；在其中建立第一列表和第二列表，对每一个多数形成模型：第一个列表包含在第一数据类中有非零发生的多数形成模型的每个形成模型i的一个发生频率Fi(1)，在第二列表中包含在第二数据类中有非零发上的多数形成模型的每个形成模型i的一个发生频率Fi(2)；使用形成模型的一个固定数量，k，其中k充分小于在多个形成模型中形成模型的总数，计算：第一得分来自于在测试数据中也发生的在第一列表中的k个形成模型的频率，第二得分来自于在测试数据中也发生的在第二列表中的k个形成模型的频率。通过选择在第一得分和第二得分中较高的，推测测试数据是归类于第一数据类或第二数据类。

更详细的方法体现在，本发明的系统和计算机程序产品，k从5左右-50左右最好是20。此外，发明的其它优秀体现，就剩下使用了边界的形成模型。在其它好的体现中，数据组包括选自以下分组的数据：基因表现数据、病人的医疗记录、金融交易、人口普查数据、制造产品特性、粮食产品特性，原材料特性、大气数据、环境数据，种群总数特性

附图说明

图1为本发明的计算系统；

图2显示在坐标系统中如何表示支持；

图3根据本发明预测是第一或第二数据类的T例子的共同可能性的方法描述；

图4描述获取形成模型的典型方法，按频率在两个数据类中排序；

图5说明使用形成模型计算一个T在数据类中预测可能性的方法；

图6说明预测多于6个ALL例子的次类型的数结构系统。

具体实施方式

本发明的方法最好是使用计算机系统100来进行处理，见图1。计算机系统100可以是一个高性能的机器，象一个超级计算机，或桌面工作站或个人电脑，或者是便携式电脑象LAPTOP或NOTEBOOK，或一个分布式计算阵列或一组网络计算机。

系统100包括：一个或多个处理单元(CPU)102；存储体108要有代表性的包括高速的随机存储体和良好的稳定性的存储体(象一个或多个磁盘驱动器)；用户界面104，包括显示器、键盘、鼠标或触摸屏；网络或其它通讯界面134，用来和其它设备或其它电脑进行通讯；一个或多个通讯总线106，用来连接CPU102、至少一个存储体108、用户界面104、网络界面134。

系统100还能直接连接到实验设备140，从实验设备直接将数据下载到存储体108。实验设备140包括数据采样设备，一个或多个分光记，用于收集微阵列数据象使用于基因表现分析、扫描设备、或在这些领域使用的便携设备。

系统100也能通过网络接口134获取在远端数据库136中的数据。远端数据库134可以分布在一个或多个其它的电脑上、盘上、文件系统或网络上。远端数据库134可以是关系型数据库或其它形式存储的数据，他们的格式要有处理大数据阵列的能力，例如象由Microsoft Excel产生的扩展表单，纯文本文件和XML数据文件。

系统100可以随意连接一个外部设备150象打印机、向其它介质写的设备，包括：CD-R、CD-RW、闪存卡、记忆棒、软盘、ZIP盘，磁带机，光学设备。

计算机系统的存储体108保存指令和数据，有代表性的包括：一个能提供基本系统服务的操作系统110；用于分类和组织文件和数据的文件系统112；一个或多个应用程序114，象用于统计分析118和排序120的用户等级的工具。操作系统可以是以下任何一种：UNIX操作系统象UltrixIrix Solaris Aix；Linux操作系统；Windows系统象Windows 3.1 WindowsNT Windows95 Windows 98 Windows ME WindowsXP或其它类型；或Macintosh操作系统象MacOS 8，x，MacOS 9，x，MacOS X；或VSM系统；或其它热和兼容的操作系统。统计分析软件包括：不仅限于这些，用来运算相关基本特性选择的工具、X验证法分析、信息量基本离散化、熵函数、留一校验法。应用程序114也适于包括：数据挖掘和从数据组中提取形成模型的程序。

另外，存储体108保存一组来自数据组126的形成模型122和他们分别发生的频率。数据组126被合适的分成至少有第一数据类128表示为D1，一个第二数据类130表示为D2，也许有附加类Di这里i＞2。数据组126可以存成任何方便的格式，包括关系型数据库、扩展表单、或纯文本。测试数据132也可存与存储体108或直接由实验设备140提供，或通过用户界面104，或从远端数据库中提取象136，或从外部介质读取，但不仅限于软盘、CD-ROM，CD-RW或闪存卡。

数据组126可以包含无限数字和各种来源的数据。发明的优良表现在，数据组126包含基因表现数据，这种情况下第一数据类可以对应与第一种细胞类型的数据，象一个正常细胞，同时第二数据类可以对应第二种细胞类型的数据，象一个瘤细胞。当数据组126包含基因表现数据时，也可能是第一数据类对应第一人口总数和第二数据类对应第二人口总数。

从来自数据组126的其它数据类型可能包括以下：病人的医疗记录；金融交易；人口普查数据；人口统计学数据；粮食特性象农业产品；工业商品特性象汽车、计算机或服装产品；气象数据表示，例如，随时间的过去收集一个或多个地方的信息；或表示在指定时间不同地方的信息；生物体的族群特性；市场数据，包括例如，销售和广告图；环境数据，象对在不同时间或不同地点不同化学品的有毒废物的编辑，全球变暖倾向，树木采伐的水平和物种消失的速度。

数据组126更适宜以关系型数据库的形式存放。本发明的方法不仅限于关系型数据库，还应用于存为XML、Excel扩展表单、或其它格式的数据，只要数据组能通过合适的步骤转换成关系型表格。例如，在扩展表单中的数据有自然的行和列的格式，这样行X列Y可以分别理解为记录X和属性Y。同时，在行X和列Y格中的数据可以理解为记录X的属性Y的值V。根据对特定数据合适的解释，可以用其它方法把数据组转换成关系型表格。对格式合理的解释以及相应的步骤是一个具有熟练技能的人的能力之内。

在数据库和数据挖掘中的知识发掘。

传统地，在数据库中知识发掘已经定义成在数据中识别具有合法性、新颖性、潜在有用性和最终可理解性的模型。依据本发明的方法，一种特定的模型种类，被称作有特殊重要性的“形成模型”。

确定模型的过程通常称为“数据挖掘”，包括在某些可接受的计算效率极限下使用算法来产生特殊必须模型的列举。数据挖掘的一个主要方面是在发现数据中的从属关系，通过使用结合规则完成目标，而且也开始应用与其它类型的分类器。

关系型数据库可以看成含有收集信息的表称做关系；每个表包含一组记录；每个记录是一对属性--值的清单(Codd，″A relational model forlarge shared databank″，Communications of the ACM，13(6)：377-387，(1970))。最基本的项是“属性”(也叫“特征”)，只是一个特定性质和种类的名称。一个值是一个有特殊性质和种类的实例。例如，在交易数据库中，可能使用的商品内容，属性可以是分类的商品名称，象牛奶、面包、奶酪、计算机、汽车、书等。

属性有值域，值域可以是离散的(例如，无条件的)或连续的。颜色是一个离散属性的例子。它可以取的值为红、黄、蓝、绿等。姓名是一个连续属性的例子，它可以在一个允许范围内取任意值，例如[0，120]。在交易数据库中，例如，属性可以是2进制取0或1值，其中值1的属性代表特定的商品已出售。一对属性—值被称做“项目，”或“条件”。这样，“颜色--绿色”和“牛奶—1”是项目(或条件)的例子。

一组项目可以称做项目组，无论包含多少个项目。数据库，D，包括许多记录。每条记录包括许多项目，每条项目有一个与在数据中的属性数相同的基数。记录被称做“事务”或“实例”依赖于问题的自然属性。特别，“事务”项专门使用依赖具有二进制属性值的数据库，然而“实例”项通常依赖包含多值属性的数据库。这样，数据库或数据组就是一组事务或实例。每个在数据库中的实例没有必要都有相同的属性。实例或事务的定义，在单一的数据组中可自动提供固定实例的一组属性—值对。

数据库的“卷”D，是在D中实例的数字，把D看作一个正常的组，表示为|D|。D的维数是在D中使用的属性数，有时被称做基数。项目组的“计数”，X，表示为countD(X)定义为事务的数量，T，在D中包含X。事务包含X写成XT。在D中X的“支持”表示为suppD(x)是在D中包含X的事务的百分比。即

$$ >>>supp>D>>>(>X>)>>=>>>>count>D>>>(>X>)>>>>|>D>|>>>,>>$$

“大的”或“频繁的”项目组是一个支持是大于一些实数，δ，这里0＜＝δ＜＝1。推荐的有代表性的δ值依赖对数据类型的分析。例如对基因表现数据，推荐的δ值在0.5-0.9之间，其中后面是特别满意的。实际上，δ甚至可以取象0.001这样小的值也可以是合适的，只要在相似或相反的类或数据组中的支持是更小。

在D中的结合规则是隐含式X→Y，这里X和Y是在D中的两个项目组，同时X∩Y＝0。项目组X是“事务”的规则，项目组Y是随之发生的规则。在D中“支持”的结合规则X→Y是在D中事务的百分比，包含X∪Y。这样支持规则表示为suppd(X∪Y)。结合规则的“信心”是在D中事务的百分比，包含X也包含Y。这样信心规则X→Y是公式

$$ >>>>>count>D>>>(>X>\cup >Y>)>>>>>count>D>>>(>X>)>>>>,>>$$

挖掘结合规则的问题变成一个如何产生具有支持和信心分别都大于或等于用户指定的最小支持和最小信心的所有结合规则。通常，解决这个问题是通过把它分解成两个次问题：产生所有大量数据组对应的最小支持；为给定的大量数据组产生所有的结合规则，只输出那些信心超过最小支持的规则。结果这些次问题的第二个是直接向前的，因此有效的挖掘结合规则是在发现所有大量项目组中，发掘出那些支持超过给定门限的项目组。

纯逼近去发掘这些大量的数据组是在D中产生所有可能的项目组，检查每个项目组的支持。对于N维的数据库，这将需要检查2N-1个数据组的支持(即，没有包括空组)，随着N的增大，方法迅速变的难以处理。已经有两种发展了的算法用来部分解决用纯算法带来的困难。APRIORI和Max-Miner两个通过他们完整的参考文献(Agrawal andSrikant，″Fast algorithms for mining associationrules，″Proceedings ofthe Twentieth International Conference on Very Large Data Bases，487-499，(Santiago，Chile，1994))andMAx-MINER(Bayardo，″Efficiently mining long patternsfromdatabases，″Proceedings of the 1998 ACM-SIGMOD InternationalConference on Management of Data，85-93，(ACM Press，1998)在这里合在一起。

尽管使用结合规则，附加的分类器在数据挖掘应用中找到使用。非正式地，分类法是一个确定制作过程基于一套实例，通过将新实例分配到一个许多的可能组中。分别按照分类法是“管理的”或“无人管理的”，组群被叫做类或群。群的方法是无人管理分类法，在这里群的实例被指定和确定。相比下，在管理分类法中，每个给定实例的类被认为是在开始和主要的目标是获取知识，象来自一个给定实例的规则或模型。发明的方法适宜的应用于管理的分类法的问题上。

在管理分类发中，发掘知识引导一个新实例进入一个预先定义的类中。有代表性的分类法问题包括2个短语：“学习”短语和“测试”短语。在管理分类中，学习短语包括从给定收集的实例中产生一组模型或规则中学习知识。测试短语依照，利用它分类新实例来产生模型和规则。“模型”是一组简单的条件。在学习短语中，数据挖掘分组法利用模型和他们结合的属性，象频率和从属性。两个被指定的主要问题是模型的定义，和对发掘他们有效算法的设计。然而，那里的模型数量是非常大的—经常是有着庞大数据组的情况—第三个重要的问题是如何为确定制作选择更有效的模型。在选择第三个中，得到的满意分类器对人们来说应该是不会太复杂和容易理解的。

在管理的分类法问题中，“学习实例”是一个类标签已知的实例。例如，在一个包含建立在健康和感冒者的总数上的数据，训练实例是一个人健康的数据。相比，测试实例是类标签未知的实例。分类器的功能是将测试实例映射到类标签中。很好广泛使用分类器的例子是：CBA分类器(″Classification Based on Associations″)、大型贝叶斯分类器(Meretakis and Wuthrich，″Extending naive Bayes Classifiers using longitemsets″，Proceedings of the Fifth ACM SIGKDD InternationalConference on Knowledge Discoveryand Data Mining，165-174，SanDiego，CA，ACM Press，(1999))、C4.5(基于确定树)分类器(Quinlan，C4.5：Programs for machine learning，Morgan Kaufmann，San Mateo，CA，(1993))、k—NN(K—最近邻居)分类器、感知器、神经网络系统、NB(纯贝叶斯)分类器。

分类器的准确性可以通过典型的一个或多个方法来确定。例如：一种方法，固定百分比的训练数据被抑制，分类器使用剩余数据训练，接着把分类器应用于抑制的数据上。正确分类的抑制数据的百分比用来当作分类器的准确性。另外一种方法，N折交叉对比，在这个逼近中，训练数据被分成N组。第一组数据抑制。分类器通过其它(n-1)组训练在应用到抑制组。这个过程接着在第二组重复，知道第N组。通过获得这些N组的平均准确性来作为分类器的准确性。第三种方法，留一策略这样使用的，第一训练实例抑制，其余的实例用来训练分类器，接着在用于抑制实例。接着处理过程在第二实例、第三实例上重复、直到到达最后一个实例。在这种方法中正确分类实例的百分比被用来表示分类器的准确性。

本发明涉及衍生一个分类器，该分类器具有满意地执行以上描述的所有三种测量准确性的方法，和在数据挖掘、机器学习、诊断学、其它被认知的巧妙的诊断学领域常用的其它测量方法。

形成模型

本发明的方法使用一种模型，叫做形成模型(“EP”)，用于来自数据库的知识发掘。通常地说，形成模型是与2个或更多的数据组或数据类有联系，并且通常描述重要变化(例如，差别和倾向)在一个数据组和另一个之间或其它的。EP’S描述在：Li，J.，Mining Emerging Patterns toConstruct Accurate and Efficient Classifiers，Ph.D.Thesis，Department ofComputer Science and Software Engineering，The University of Melbourne，Australia，(2001)，通过他完整的参考在这里体现。形成模型是简单条件的基本联接。合适的形成模型具有四个性质：合法性、新颖性、潜在的有用性、和可理解性。

模型的合法性涉及模型对新数据的适用性。理想情况下已发现的EP是合法的，是在当把它应用于新数据时，具有一些程度的确定性。一种研究这种性质的方法是，在原始数据库通过加入小比例的新数据更新后在测试一个EP的合法性。一个EP可以是特别强，如果甚至当一个大比例的新数据合并到先前处理过的数据中，他还保持合法性。

新颖性涉及模型是否已经被发掘，无论是通过传统统计方法或是通过人类的专家。通常，这样一个模型包含许多条件或低支持等级，因为一个人类的专家可能知道一些，但不是全部包含的条件，或因为人类的专家倾向注意那些发生频繁的模型，而很少注意几乎不发生的。一些EP’s，例如，由令人惊奇的长模型组成的包括超过5—包括象15一样多的—条件当在数据组中属性的数量大的象1000，因此要在先前的好理解的问题里提供新的不是预期的见识。

如果它能用于预测，模型潜在的有用性将提升。形成模型可以描述在任何两个或多个无重复的临时数据组中的趋势和在任何两个或多个空间数据组中的重要的区别。在这个内容中，区别是指类中的许多数据都符合一组条件。因此，EP’s可以在应用中发现承认的使用，例如预测商业市场的趋势，确定隐藏在不同种族一些特殊疾病的起因，对于手写字符的识别，区分在基因之间的核糖体蛋白的编码和其它蛋白的编码，区分正实例和负实例，例如“健康”或“有病”，在离散数据中。

模型是可理解的，如果它的含义从对它的检查中是直观清楚的。实际上，EP是简单条件的联接，意味着理解起来很容易。当实际关于它能区别两个已知数据类的能力是已知的时，对EP的理解特别有帮助。

假设一对数据组，D1和D2，EP定义成一个项目组，它的支持的增长主要来自一个数据组D1到另一个D2。表示在数据库Di中项目组X的支持为suppi(X)，来自D1到D2的数据组X的增长率定义为：

$$ >>>growth>->>>rate>>>D>1>>\to >>D>2>>>>>(>X>)>>=>\begin{array}{}>>0>,>>if\; sup>>p>1>>>(>X>)>>=>0>and\; sup>>p>2>>>(>X>)>>=>0>;>\; >>\infty >,>>if\; sup>>p>1>>>(>X>)>>=>0>and\; sup>>p>2>>>(>X>)>>\ne >0>;>\; >>>>>supp>2>>>(>X>)>>>>>supp>1>>>(>X>)>>>>,>>otherwise>.>\; >\; >>\end{array}$$

这样增长率就是在D2中数据组X的支持除以它在D1中的支持的比率。一个EP的增长比率是测量在它的支持变化的程度和在本发明的方法中一个主要的量。对增长速率的其它定义可以表示成数据组数量的形式，定义是在两个数据组有极不平衡的总数的情况下找到特殊的适用性。

可以理解的是，在这里的公式不仅限于两个数据类的情况除了特别地指示向相反的，可以通过一种通常在数据组有3个或多个数据类的情况中产生。因此，进一步的理解对在这里对变化方法的讨论，通过应用与有两个数据类的组合来做为例子，通过一个用于3个或多个数据类可以产生能够被承认的。这里一个数据类被认为是在一个较大数据组中的子集数据，是在次数据组中的一些共有属性的方法进行典型选择。例如用特定方法从所有人测试中取得数据，一类可能是这样的数据关于这些人或特殊的性别、或是接受特殊治疗协议的人。

特别喜欢的是EP’s是那些增长率大于给定门限ρ的数据组。特别是，把给定ρ＞1作为增长速率的门限，数据X被称做一个从D1到D2的ρ-形成模型。如果growth_rateD1→D2(X)≥ρ一个ρ形成模型通常被说成ρ-EP，或一个ρ值可理解的EP。

从D1到D2ρ＝无穷大的ρ-EP也被叫做从D1到D2的“跳跃EP”。因此一个从D1到D2的跳跃EP是代表在D2中存在和在D1中无。如果D1和D2是可理解的，那么称跳跃EP或J—EP是合适的。本发明的形成模型就是好的J—EP的模型。

给定两个模型X和Y，这样对于每个可能的实例d，当Y在D中发生时X也在D中发生，这就是说X比Y更一般。也可以说Y比X特殊，如果X比Y一般。

从D1到D2给定一个EP的收集C，如果没有一个EP在C中比它更一般，我们说这个EP是C中最一般的。同样的，如果没有一个EP在C中比它更特殊，我们说这个EP是C中最特殊的。在给定的D1、D2和C中，也许会有多于一个的EP被提交成最特殊的，和多于一个的EP被提交成最一般的。在C中最一般的和最特殊的EP和起来被称做C的边界。最一般的EP被称做在C中“EP的左边界”，最特殊的EP被称做在C中EP的右边界。这里内容是清楚的，提到EP的边界是表示没有提及C的EP的左边界。EP的左边界是非常重要的，因为他们最一般。

给从D1到D2的EP一个收集C，C的子集C’被称做“坪”如果它包含C的EP左边界和X，同时所有在C’中的EP具有在D2中和X的相同支持，所有其它在C中但不在C’中的EP支持具有在D2中不同于X的支持。在C’中的EP叫C的“EP的坪”。如果C可理解，那么说EP的坪是充分的。

对于成对的数据组D1和D2，提及的协定包括：用在D2中的支持表示一个EP的支持；用D1表示“背景”数据组，D2表示“目标”数据组，在例子中数据是按时间排序的；用D1表示“负”类，D2表示“正”类，在离子中数据是有关系的类。

此外，形成模型在数据组间捕获重要的变化和区别。当应用于时间标记的数据库时，模型能在总量的行为中捕获形成趋势。这是因为在例子数据库中在连续时间点的数据组之间的不同可以用来确定趋势，例子数据库中包含在时间的不同点处比较的商业或大气的数据块。另外，当离散类应用与数据组时，EP能捕获类之间的有用的差异。这样离散类的离子包括，不仅限于这些：在种群人口的数据中，男人和女人；在霉菌的总量数据中，有毒的和可食用的；在病人的采取治疗的总量中，治愈的和没治愈的。EP已经证明有能力建立有效的分类器，它对于许多数据类的分类都比C4.5和CBA更精确。降到中等支持(象1％-20％)的EP能给专家新的见识和方向，甚至在“很好理解”的情况下。

可以找到EP指定特殊的类型。当在其它地方讨论时，EP的增长率是∞，既在背景数据组中他的支持为零，被称做“跳跃形成模型”或“J—EP”(Li，etal.，″The Space of Jumping Emerging Patterns and ItsIncremental Maintenance Algorithms，″Proceedingsof 1＜InternationalConference on Machine Learning，552-558(2000))。涉及本发明的体现使用“跳跃形成模型。”另外的体现使用具有最高增长速率的最一般的EP，但是他们被很少提及，因为他们的抽取比J—EP的更复杂并且因为他们可以不必给出比J—EP更好的结果。然而，在没有可用的J—EP的情况下，使用其它有高增长率的EP是有必要的。

通常将类指定成作为EP的基类或自己时EP有非零频率的类。其它的类，具有EP是零或较低的频率，称作EP的相似类。在多于两个类的情况下，基类被当作一个类，在这个类中EP拥有最高频率。

另外，另一个特殊类型的EP，表示为“强EP”，是一种满足子集封闭的属性，即它的非空子集也是EP’s。通常，一组收集C展示子集封闭性，如果仅当任何组X(X∈C，即X是C的一个元素)的所有子集也属于C。一个EP被称作“强k—EP”，如果每个子集的元素数量至少是K，那它也是一个EP。虽然强EP的数量可能很小，但强EP是很重要的，因为他们比其它EP倾向于更强，(即，他们保持合法性)，当一个或多个新实例被加入到训练数据中。

EP’s的图表表示见图2。对于增长速率的门限ρ和两个数据组D1和D2，两个支持，supp1(X)和supp2(X)，可以在一个坐标系组用y和x轴分别表示。轴的平面叫“支持面”。这样横坐标测量每个数据组在目标数据组中的支持，D2。图上显示的是一条直的通过原点A的斜线(1/ρ)和线supp2(X)＝1在C处相交。在横坐标上代表supp2(X)＝1的点指定成B。任何从D1到D2的形成模型X都可以通过点(supp1(X)，supp2(X))来表示。如果它的增长率超过或等于ρ，他必须在三角形ABC的内部或边上。一个跳跃形成模型处在图2的水平轴上。

形成模型的边界和坪

探寻边界属性的规则，使用这个规则分离两个数据类引出形成模型的更多方面。许多EP可能有非常低的频率(象，1或2)在他们的基类中。边界EP已经提议被用做捕获两个类之间不同的目的。一个“边界”EP是一个所有的他的适合的子集不是EP’s。清楚地，模型包含越少的项目，在给定的类中他的发生频率越大。这样从边界EP中去掉任何项目都会提高它的基类的频率。然而，从边界EP的定义看，当这些做完后，他的在相似类中的频率变成非零，或以这么一种方式增长，EP不在满足比率ρ的门限值。通过定义，这总是真的。

为了看到这些在跳跃边界EP的情况，例如(在基类中有非零频率和在相似类中有零频率)，他的次模型没有一个是跳跃EP。因为次模型不是跳跃—EP，所以在相似类中需要非零频率，这样，它才也是跳跃EP。在ρ—EP的情况中，它在基类中频率的比率在相似类中必须大于ρ。但是从ρ—EP中去除一项使得在两个类满意的数据中有更多的实例，这样比率ρ可能不在满意，虽然在一些情况中会出现。因此，边界EP’s是他们基类中最大的频率，因为没有边界EP的特级组能有更大的频率。此外，想在上面讨论的，一些时候，如果再一个项目被加入到存在的边界EP中，结果模型会变的比原始EP的频率更小。因此，边界EP’s具有区分EP’s和非EP’s的属性。他们还可以区分高发生的EP’s和低发生的EP’s，因此可以使用他们来捕获数据类之间的大量不同。边界EP’s的有效发掘已经在其它地方有描述(Li et al.，″The Space of Jumping EmergingPatterns and Its Incremental MaintenanceAlgorithms，″Proceedingsof17th International Conference on Machine Learning，552-558(2000))。

相反在前面的例子中，如果在一个条件(项目)被加入到边界EP中，因此会产生一个EP的特级组，特级组EP仍然具有和在基类中的边界EP一样的频率。具有这个特性的EP’s被称做“坪EP’S”，并用以下方式定义：给定一个边界EP，所有他的超级组都具有和他自身相同的频率是他的“坪EP’s”。当然，边界EP’s他们自己一般的坪EP’s。如果EP的频率不是零，超级组的这个属性也是必须的EP。

作为整体的坪EP’s可以用来定义一个空间。所有相互间具有相同频率的边界EP’s的所有坪EP’s称做“坪空间”(或简单的，“P-空间”)。这样，所有在P-空间的EP’s都处在同样重要的等级上按照他们在他们基类和相似类的发生。假设基频率是N，那么P-空间用Pn-空间表示。

所有的P-空间都有一个有用的属性，叫“凸性”，它意味着P-空间可以通过它的最一般和最特殊的元素来压缩地表现。P-空间最特殊的元素贡献于基于EP’s的一个高精确性的分类系统。凸性是大量收集特定种类数据的重要属性，可以开发简明的表示如此的收集。如果收集是凸空间，那么“凸性”被保持。通过定义，一个模型是“凸空间”的收集C，如果对于任何模型X、Y、Z，条件XYZ和X、Z∈C意味着Y∈C。关于凸性的更多讨论可以在(Gunter等人，“The common order-theoreticstructure of version spaces and ATMS’s，”Artificial Intelligence，95：357-407，(1997))中找到。

P-空间的定理保持如下：给定一组正实例Dp和一组负实例Dn，每个Pn空间(n＞＝1)是凸空间。定理的证明如下：定义一个Pn空间，在相同基类中有相同频率的n的一组所有边界EP’s的所有坪EP’s。不失一般性，两个模型X和Z满足(i)XZ(ii)X和Z是具有在Dp中n发生的坪EP’s。那么对于任何模型Y在满足XYZ，就是在Dp中具有相同N发生的坪EP。这是因为：

1.X在DN中不发生。所以，Y，X的超组，也在DN中不发生。

2.模型Z在DN中有n发生。所以，Y，Z的子集，在DN中有非零频率。

3.在DN中Y的频率应该小于或等于X的频率，但要大于或等于Z的频率。当X和Z的频率都是n时，在DN中Y的频率也是n。

4.X是边界EP的一个超组，由于XY，是边界EP的一个超组。

从第一，二点能推出Y是Dp的EP.从第三点，Y的发生在Dp中是n。因此，结合第四点，Y是一个坪EP。因此，每个Pn-空间被证明是一个凸空间。

例如，模型{a}，{a，b}，{a，c}，{a，d}{a，b，c}{a，b，d}建立一个凸空间。组L由这个空间的最一般元素组成是{{a}}。组R由这个空间的最特殊元素组成是{{a，b，c}，{a，b，d}}。其它所有的元素被认为是在L和R之间。凸空间可以通过两个和组L和R相似的组来划分边界。组L是由边界EP’s组成。这些EP’s是P--空间的最一般元素。通常特征包括在R中的模型，是多于在L中的模型。这表示一些特征组能在保持他们重要性的同时进行扩展。

在凸空间中心位置的模型通常更重要，因为他们的邻居模型(那些模型在空间里比中心模型少一项或多一项)是所有的EP’s，因为他们合适的子集不是EP’s。当凸空间的边界EP’s是最频繁的EP’s时，所有这些思路都是特别有意义的。

更适合的是，所有的EP’s都有相同的无限频率的增大速率，从他们的基类到他们的相似类。然而，所有合适的边界EP子集都有一个无限增大速率，因为他们同时发生在两个类里。在这些子集在两个类间改变他们频率的行为可以通过研究他们的增长率来确认。

阴影模型是直接的边界EP子集，即比边界EP少一项，，象这样的特殊属性。边界EP存在的可能性可以通过检验边界EP的阴影模型来粗略估计。基于这个思路，阴影模型是EP的直接子集、边界EP’s可以被分成两种类型“合理的”和“反方向的重要性”。

阴影模型可以用来测量边界EP’s的重要性。最重要的边界EP’s是那些具有高发生频率的，但不能包括那些“合理的”和那些非“预期的”在下面讨论。给定边界EP，X，如果它的阴影模型的增长率接近∞，或在ρ—EP’s情况中的ρ，那么边界EP的存在就是合理的了。这是因为阴影模型比EP本身更容易识别。这样可以使许多的阴影模型被识别，在这种情况下，推断X自己也有高的发生频率就是合理的。否则，如果阴影模型的增长率是平均小数字象1或2，那么X模型是“反方向的重要性”。这是因为当作为边界EP的X的可能性小时，它的存在是“非期望的”。换句话说，那会是惊奇的如果许多阴影模型有低频率但是他们的相似边界EP有高的频率。

假设对于两个类，正的和负的，边界EP，Z在正类里有非零发生。把Z表示成{x}∪A，这里x是一项，A是非空模型，观察A是Z的一个直观子集。通过定义，在两个正类和负类中模型A有非零发生。如果在负类中A的发生是小的(1或2)，那么Z的存在是合理的。否则，边界EPZ是不合理的。这是因为

              P(x，A)＝P(A)*P(x|A)，

这里P(模型)是模型的概率，同时假设可以通过模型的发生来近似。如果在负类里P(A)是大的，那么P(x，A)在负类里也是大的。那么模型{x}∪A＝Z成为边界EP的机会就小了。因此，如果Z需要边界EP，结果是不重要的。

形成模型与判别规则具有一些表面的相似性，在这个意义上两个都倾向于捕获不同数据组直接的区别。然而，形成模型在类之间能够发掘低支持，高增长率，然而判别规则主要指示在类间高支持的比较。

本发明的方法可应用到具有大增长率的J—EP’s和其它EP’s上。例如：方法能利用于当输入EP’s是最一般的EP’同时增长速率超过2，3，4，5，或其它任何树。然而在这种情况下，从数据组中提取EP’s的算法将区别于使用在J—EP’s的。对J—EP’s合适的提取算法给在：(Li，etal.，″The space of Jumping Emerging patterns and its incrementalmaintenance algorithms″，Proc.17th International Conference onMachine Leaming，552-558，(2000))中。对于非—J—EPs，一个复杂的算法被满意的使用，象描述在：(Dong and Li，″Efficient mining ofemerging patterns：Discovering trends and differences″，Proc.Sth ACMSIGKDD International Conference on Knowledge Discovery &DataMining，15-18，(1999))中。

通过共同相似性预测的概述

本发明方法的概述，称作“通过共同相似性预测”(PLC)分类算法，图3-5提供了联结方式。在全部的逼近中，如图3所示，从数据组126开始，表示为D，通常称作“训练数据”或“训练组”或“原始数据”，数据组126被分成第一类D1128和第二类D2130。从第一类和第二类里，形成模型和他们分别在D1和D2里的发生频率被确定，在步骤202。分开，形成模型和他们分别在测试数据132中的发生频率表示成T，称作测试范例，被确定，在步骤204。使用类D1和类D2的定义来在测试数据中确定形成模型和他们的频率。通过在D1、D2和T中形成模型的发生频率，用于预测在D1或D2中T状态的共同相似性的计算在步骤206处展开。这个结果在T类的预测中，即，无论T是否在D1或D2中分类。

在图4中，可以看到从数据D得到形成模型过程的大概框架。开始于300来自D的类D1和D2，象熵分析的技术应用在步骤302为数据组D的属性产生切断点。切断点允许模型的确定，他的标准用于满足形成模型的属性，被用来在步骤308，为类1提取形成模型，为类2，在步骤310。类1的形成模型依照在D1中的频率排成升序来存入的，在步骤312，类2的形成模型依照在D2中的频率排成升序来存入的，在步骤314。

在图5中，描述了一种从固定数量形成模型的频率来计算得分的方法。数字K，在步骤400中选择，最顶部的K个模型，依据在T中的频率被选择在步骤402。在步骤408，计算得分，S1，在T中的顶部的K个形成模型上也可以在D1中找到，使用在D1404中的发生频率。同样的在步骤410得分S2，是通过计算在顶部T中k个形成模型也可在D2中找到，上面使用在D2406中的发生频率。S1和S2的值在步骤412比较。如果S1和S2的值相互不同，则T的类在步骤414被推断出来根据S1和S2中大的值。如果得分是相等的，则T的类在步骤416推断出来根据D1和D2中大的值。

虽然图3—5没有显示，但是本发明的方法是可理解的，同时把它缩减成切实的形式制作成计算机程序产品并在系统上运用该方法，这个方法可以应用于包含3个或多个数据类的数据组就象上面描述过的。

数据准备

在分析卷数据中的主要挑战是属性和特征的无法抵制数量。例如，在基因表现数据中，主要的挑战是包含大量的基因数据。如何提取信息特征和如何避免噪声数据的影响是在处理卷数据中重要的问题。发明良好的体现使用了基于熵的方法(参考文献Fayyad，U.andlrani，K..″Multi-interval discretization of continuous-valued attributes forclassificationlearning，″Proceedings of the13th International JointConference on Artificial Intelligence，1022-1029，(1993)；and also，Kohavi，R.，John，G.，Long，R.，Manley，D.，and Pfleger，K.，″MLC++：Amachine learning library in C++，″Tools with Artificial Intelligence，740-743，(1994))，and the Correlation based Feature Selection(″CFS″)algorithm(Witten，H.，& Frank，E.，Data mining：Practical machinelearning tools and techniques with java implementation，MorganKaufmann，San Mateo，CA，(2000))来分别进行离散化和特征选择。

许多数据挖掘任务需要将连续的特征离散化。基于熵的离散化方法忽略了那些有着不同的类标签包含随机分布的值。它能发现那些特征，有大的间隔包含几乎所有点的同类。CFS方法是离散化的推迟处理。胜于给单个特征打分(和排列)，该方法给有价值的子集的离散化特征打分(和排列)。

此外，该发明良好的体现，基于熵的离散方法用于离散一定范围的真实值。该方法的基本观点是将一定范围的真实值分成一定数量的间隔区间，这样区间的熵是最小的。在这个离散化过程中切断点的选入是至关紧要的。使用最小熵的思路，区间是“最大的”和在一个数据类的值和另一个数据类的值之间有可靠的鉴别。这个方法可以自动忽略那些范围，包括来自两个数据类的相关统一混合的值。因此，许多噪声数据和噪声模型被有效的去除，允许保持离散特征的探察。为了举例说明这点，考虑以下三个可能的分配范围的点和两个类标签，C1和C2，显示在表A：

                                                  表A

       范围1      范围2    (1)    所有C1的点    所有c1的点    (2)    所有C1的点    所有c2的点    (3)      超过范围的混合点

对于实际值的范围，其中的每一个点和一个类标签联系在一起，分配类标签有三种主要形态：(1)大的无重叠范围，每一个都包含相同类的点。(2)大的无重叠范围，其中至少有一个包含相同类的点；(3)类点随机混合在这个范围。使用两类之间的中间点，基于熵的离散方法(Fayyad & Trani，1993)在第一种情况中将数据分入两个区间。这样的划割熵是零。把范围划割成最少两个区间叫做“离散化”。对于第二中情况在表A中，这个方法使用右区间包含足够多的C2点和包含尽可能少的C1点的方法分割范围。这样的目的是最小化熵。对于第三种情况在表A中，来自两个类的点被分配到整个区域，方法忽略了特征，因为把混合点分配到区域，没有提供可靠的分类规则。

基于熵的离散化是一种离散化方法，他使用离散最小化的启发式。当然，任何区域的点能被分割到特定数量的区间中这样他们每个都包含相同类的点。虽然这种分割熵是零，但当他们的覆盖非常小时，区间(或规则)是无用的。基于熵的方法通过使用递归的分割步骤和有效的停止分割标准来保证区间可靠和确信他们有足够的覆盖来解决这个问题。

采用的符号表示在(参考文献Dougherty，J.，Kohavi，R.，& Sahami，M.，″Supervised and unsupervised discretization of continuousfeatures，″Proceedings of the Twelfth International Conference onMachine learning，94-202，(1995))，让T把例子组S分割成子集S1和S2。让那里有k个类C1...Ck，让P(Ci，Sj)为在Sj中例子的部分并含有类Ci。子集Sj的“类熵”，j＝1，2定义为：

$$ >>Ent>>(>>S>j>>)>>=>->>\Sigma >>i>=>1>>k>>P>>(>>C>i>>,>>S>j>>)>>log>>(>P>>(>>C>i>>,>>S>j>>)>>)>>.>>$$

假设子集S1和S2是通过分割在点T处的特征A。那么，分割的“类信息熵”表示为E(A，T；S)，通过给定：

$$ >>E>>(>A>,>T>;>S>)>>=>>>|>>S>1>>|>>>|>S>|>>>Ent>>(>>S>1>>)>>+>>>|>>S>2>>|>>>|>S>|>>>Ent>>(>>S>2>>)>>.>>$$

对A的二进制离散化是通过选择切断点TA，E(A，T；S)是在所有坐标系中最小的。相同的过程可以递归地应用到S1和S2直到遇到停止的规范。

“最小描述长度的规则”是合适的使用停止分割。根据这个技术，递归的分割在一组值S个停止里，当且仅当：

N是在组S中值的数量；Gain(A，T，S)＝ENT(S)—E(A，T；S)和δ(A，T；S)＝log₂(3^k-2)-[k Ent(S)-k₁ Ent(S₁)-k₂ Ent(S₂)]，这里kj是代表在组Si中类标签的数量。

这种二进制离散化法已经通过MLC++技术应用，在http：//www.sgi.com/tech/mlc/有可用的执行代码。已经发现基于熵的选择方法是非常有效的，当应用于基因表现图谱时。例如有代表性的基因在数据组中只占10％，他们通过这个技术来选择，因此这种选择比率提供一个更容易的平台从其中衍生重要的分类规则。

尽管离散化方法，象基于熵的方法在从大数据组里自动去除90％多的特征中的表现显著。这可仍然意味着和1000多的数据一样，或特征还是存在。手动检查这么多的特征还是很冗长的。因此，在本发明令人满意的体现中，基于相关性的特征选择(CFS)方法(文献Hall，Correlation-based feature selectionmachine lea1rling，Ph.D.Thesis，Department of Computer Science，Universityof Waikato，Hamilton，NewZealand，(1998)；Witten，H.，& Frank，E.，Data mining：Practicalmachineleaing tools and techniques with java inaplementation，MorganKaufmann，San Mateo，CA，(2000))and the″Chi-Squared″(；？)method(Liu，H.，& Setiono，R.，″Chi2：Feature selection and discretization ofnumeric attributes.″Proceedings of the IEEE 7ry′International Con.ference on Tools with Artificial Intelligence，338-391，(1995))；Witten &Frank，2000)被用来进一步缩小对重要特征的查找。只要在离散化之后保持的特征数量不广泛，这些方法就能很好的应用。

在CFS方法中，用这个方法对特征子集的价值的打分(排列)胜于对单独特性的打分(排列)。因为特征子集空间通常是巨大的。CFS使用最好第一查找渐进。这个渐进算法在预测类时考虑到单个特征的有效性，随同在他们信任中的相关性等级，好的特征子集和类保持高的相关，这样相互间没有相关。CFS先计算来自训练数据中特征库和特征一特征相关的矩阵。下来通过渐进给子集特征打分定义如下：

$$ >>>Merit>S>>=>>>kver>>>r>cf>>‾>>>>k>+>k>>(>k>->1>)>ver>>>r>ff>>‾>\; >>,>>$$

矩阵是特征子集S的渐进优点，包括k特征，--rcf是平均特征类相关性，--rff是平均特征—特征相互相关性。“对称的不确定性”在CFS中使用，用来估计在离散特性之间或特征和属性(Hall，1998；Witten & Frank，2000)之间的联系程度。对称的不确定性用于两个属性或属性和类X和Y，他的范围是[0，1]，给定方程是：

$$ >>>r>xy>>=>2.0>>(>>>H>>(>X>)>>+>H>>(>Y>)>>->H>>(>X>,>Y>)>>>>H>>(>X>)>>+>H>>(>Y>)>>>>)>>>$$

在这H(X)是属性X的熵，给定如下：

$$ >>H>>(>X>)>>=>->>\Sigma >>x>\in >X>\; >p>>(>x>)>>>log>2>>>(>p>>(>x>)>>)>>.>>$$

CFS开始于空的特征组，使用最好—第一—查找逼近用停止规则5连续的完全的扩展非改良的子集。在查找期间找到最高优点的子集被选中。

χ2(“χ检验法”)法是另一种逼近的特征选择。它通常通过考虑类的χ检验法统计测量评价属性(包括特征)。对于数量属性，该方法首先需要把他的范围离散成多个区间，例如使用上面描述的基于熵的方法。属性的χ2值定义成：

$$ >>>\chi >2>>=>>\Sigma >>i>=>1>>m>>>\Sigma >>j>=>1>>k>>>>>(>>A>ij>>->>E>ij>>)>>2>>>E>ij>>>,>>$$

这里m是区间的数量，k是类的数量，Aij是在第i区间第j类例子的数量，同时Eij是Aij的期望频率(即，Eij＝Ri*Cj/N，这里Ri是在第i区间中例子的数量，Cj是在第j类中例子的数量，N是例子的总数)。在计算所有确定的特征χ2值之后，值可以排列成最大值在第一个位置，因为χ2的值越大，他的特征越重要。

应该说明的是尽管离散化和选择的讨论是相互分开的，离散化方法也在选择中扮演角色，因为每个离散到单个区间的特征可以被忽略，当在做选择处理时。依靠学习领域，形成模型可以衍生，通过χ2法来划分顶部选择特征。在优良的体现中，顶部选择特征20个。在其它体现中，顶部10，25，30，50或100选择特征，或任何其它在0和100左右之间的方便数量被使用。多余100个的特征可以使用也是可理解的，在行为中描述，和适合这里的。

产生形成模型

从数据库中有效的挖掘强形成模型的问题是有些象挖掘频繁项目组的问题，当使用象算法APRIORI(先验)(Agrawal and Srikant，″Fastalgorithms for mining association rules，″Proceedings of the TwentiethInternational Cofzference on Very Large Data Bases，487-499，(Santiago，Chile，1994)和MAX-MINER(最大挖掘)时，(Bayardo，″Efficiently mining long patterns from databases，″Proceedings of the1998 ACM-SIGMOD International Conference on Managenaent ofData，85-93，(ACM Press，1998))，两个通过完整的参考文献结合。然而，一般有效的EP’s挖掘是一个具有挑战性的问题，有两个主要原因。第一先验属性，为了是长模型发生频繁，所有它的次模型也发生频繁，不再为EP’s保持，第二，通常有大量的候选EP’s用于高维数据库或小的支持门限象0.5％。确定EP’s有效的方法很好的使用，和本发明的方法连接在一起。描述在：Dong and Li，“Efficient Mining of Emerging Patterns：Discovering Trends and Differences，”ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining，SanDiege，43-52(August，1999)，通过完整的参考文献在这里结合。

为了展示包含的挑战，用纯贝叶斯法从数据组D1到D2逼近发掘EP’s：初始化计算同在D1和D2中所有可能项目组的支持，接着进行检查是否每个项目组的增长率都大于或等于一个给定的门限。对于关系的描述，3类属性，例如，颜色、形状和尺寸，其中每个属性有两个可能的值，数据组全部可能量是26，即$$ >\left(\begin{array}{}>>3>\; >>1>\; >\end{array}\right)>*>>2>1>>+\left(\begin{array}{}>>3>\; >>2>\; >\end{array}\right)>*>>2>2>>+\left(\begin{array}{}>>3>\; >>3>\; >\end{array}\right)>*>>2>3>>,>>$$总和包括，分别地，单个项目组的数量和用两个或三个片的项目组的数量。当然所有项目组数量和属性数量按指数增长，因此在最大情况下，处理在所有项目组中彻底的查找来减少形成模型的花费很大。一个选择性的纯贝叶斯算法使用两个步骤，名字：首先通过考虑在目标数据组中一些支持门限来发掘大数据组；接着列举那些项目组的频率和计算在背景数据组中他们的支持，这样确定EP’s作为那些数据组，能满足增长速率门限。然而这种两步逼近的算法是有利的，因为他不枚举零支持和一些非零支持，在目标数据组中的项目组，通常是合理的，因为指数增长的组大小属于长频繁项目组。通常，那么算法通常是有效的但花费太大。

为了解决这个问题，(a)通过提升具有使用简练边界(在收集中最小的一对和最大的一对项目组)的项目组的大收集的描述，(b)指定EP挖掘算法，只利用收集边界(特别是使用多边界差异的算法)，使用边界表示发掘EPs。所有满足一个约束的EP’s可以有效的通过基于边界算法的发掘，使用边界，通过象程序衍生MAX-MINER(最大挖掘)(文献Bayardo，″Efficiently mining long patterns fromdatabases，″Proceedings of the 1998 ACM-SIGMOD IfzternationalConference on Management of Data，85-93，(ACM Press，1998))把大项目组的作为输入。

挖掘EP’s的方法对于具有熟练技能的人是可取的。挖掘EP’s的合适方法的特定描述，适合和本发明使用的可以在(文献Efficient Mining ofEmerging Patterns：Discovering Trends and Differences，″ACMSIGKDD International Conference on Knowledge Discovery and DataMining，San Diego，43-52(August，1999))和(文献The Space ofJumping Emerging Patterns and its Incremental MaintenanceAlgorithms″，Proceedingsof 17′h International Conference on MachineLeaming，552-558(2000)中找到。通过完整的参考文献在这里结合。在分类法中使用EP’s：通过共同相似性预测

边界EP’s的数量经常是大的。划分和可视化这样的模型是重要的问题。依照本发明的方法，边界EP’s被划分。另外，本发明的方法使用分类法中最顶划分模型的频率。最顶划分的模型可以帮助使用者更好更容易地理解应用。

EP’s，包括边界EP’s，可以按下面的方法划分。

1.给定两个EP’s Xi和Xj，如果Xi的频率大于Xj的，那么Xi在表中具有高于Xj的有先级。

2.当Xi的频率等于Xj的频率，如果Xi的基数大于Xj的，那么Xi在表中的有先级比高于Xj。

3.如果Xi和Xj的基数和频率都确定，那么Xi优先于Xj，当通过方法和计算机系统打印和显示EP’s先产生X时。

实际上，测试例子可能不仅包括来自自己类的EP’s，而且包含来自他相似类的EP’s。这使得预测更加复杂。测试例子应当适合地包含许多自他自己的类的顶部排列的来EP’s，也可以包含来自他的相似类的一些--适合的--不—低的—排列的EP’s。然而，从广泛的各种数据的经验来看，测试例子一些时候，尽管很少，包含从1左右到20左右来自他的相似类的顶部EP’s。为了产生可靠的预测，使用多种EP’s是合理的，在基类中有高频率的用来避免来自相似类的干扰信号。

合适的预测方法如下，为边界EP’s和测试例子举例，包含两个数据类。确认一个训练数据组D，有至少一个第一数据类的实例和至少一个第一数据类的实例，把D分成两个数据组，D1和D2。从D1和D2中抽取边界EP’s的多数。有序n1 D1的边界EP‘s表示为(EP1(i)，i＝1，...，n1)用他们频率的降序排列，并且每一个在D1中有非零发生。相似的，有序n2 D2的边界EP‘s表示为(EP2(i)，i＝1，...，n2)按他们频率的降序排列，并且每一个在D2中有非零发生。边界EP’S的这些组两个都可以方便的存入列表形式中。D1中第i个EP的频率表示为f1(i)，D2中第j个EP的频率表示为f2(j)。也是可以理解的，在两个列表中的EP’s可以存成按频率排列的降序，如果愿意。

假设T包含下列D1的EP’s，可以是边界EP’s：{EP1(i1)，EP1(i2)...，EP1(ix)}，这里i1＜i2＜...＜ix＜＝n1，且x＜＝n1。假设T也包含下列D2的EP’s，可以是边界EP’s：{EP2(j1)，EP2(j2)，...，EP2(jy)}，这里j1＜j2＜...＜jy＜＝n2，且y＜＝n2。实际上，很容易就可以建立第三个和第四个列表，其中第三个列表可以表示为f3(m)其中第m项中包含在D1中非零发生和也发生在测试数据中的多个形成模型的每个形成模型im的一个发生频率，f1(im)，同时其中第四个列表可以表示为f4(m)，其中第m项中包含在D2中非零发生和也发生在测试数据中的多个形成模型的每个形成模型的每个形成模型jm的一个发生频率，f2(jm)。形成模型在第三列表中按照他们分别的在D1中的发生频率降序排列，相似的，形成模型在第四列表中按照他们分别的在D2中的发生频率降序排列，这样也是合适的。

下一步是为预测T的类标签计算2个得分，其中每个得分对应于两个类中的一个。假设D1和D2的k顶部—排列EP’s被使用。接着在D1中T的得分定义如下：

$$ >>score>>(>T>)>>\_>>D>1>>=>>\Sigma >>m>=>1>>k>>>>>>f>1>>>(>>i>m>>)>>>>>f>1>>>(>m>)>>>>>|>>>EP>1>>>(>>i>m>>)>>\in >T>>>>=>>\Sigma >>m>=>1>>k>>>>>f>3>>>(>m>)>>>>>f>1>>>(>m>)>>>>.>>$$

相似的，在D2中的得分定义如下：

$$ >>score>>(>T>)>>\_>>D>2>>=>>\Sigma >>m>=>1>>k>>>>>>f>2>>>(>>j>m>>)>>>>>f>2>>>(>m>)>>>>>|>>>EP>2>>>(>>j>m>>)>>\in >T>>>>=>>\Sigma >>m>=>1>>k>>>>>f>4>>>(>m>)>>>>>f>2>>>(>m>)>>>>.>>$$

如果score(T)_D₁＞score(T)_D₂，那么例子T被预测是在D1类中。否则例子T被预测是在D2类中。如果score(T)_D₁＝score(T)_D₂，那么D1和D2的大小适合使用打断联系，即，T被分配到D1和D2中较大的那个。当然，在T中最频繁发生的EP’s将没必要和顶部排列一样的无论是在D1中还是D2中。

符号score(T)_D₁＞score(T)_D₂，是两个系数的和。第i个的系数值只能是1.0如果给定类的每个顶部iEP’s可以在T中找到。

一个特别合适的k值是20，虽然一般情况下，k是一个数字，选择是充分小于形成模型的总和，即，k典型的小小于n1或n2，k＜＜n1和k＜＜n2。其它适合的k值是5，10，15，25，30，50和100。一般，k合适的值在5左右和50左右之间。

在另一种体现里，分别有有n1和n2个D1和D2的形成模型，k选择是一个固定比率，在n1和n2里较小的那个。在另一个不同体现中，k选择是一个固定比率，是n1和n2的总和或n1和n2中任何一个。合适的固定比率，在这样的体现中，范围从1％左右到5％左右，k是一个接近整数值的周围，在这种情况下固定比率并不导致这个数量。

上面描述的计算分数的方法可以产生多类数据的并行分类法。例如，这样是特别有用的，对于发掘分割基因和多基因区别的列表用于从所有其它亚型中区分一个亚型。这样的区别是“全球的”，作为一个相反于所有的，与一个等级树分类法策略相对照，它的区分是本地的，因为规则表示根据一个亚型相反于它下面的其它保留亚型。

假设有c个数据类，(c＞＝2).表示成D1，D2，...，Dc。首先，本发明的产生方法发掘c组EP’s其中第n组(1＜＝n＜＝c)与Dn相对(∪i□nDi)。特征的选择和离散化可以用和处理典型两类数据的方法进行。例如，Dn的分割EP’s可以表示成：{EPn(i1)，EPn(i2)，...，EPn(ix)}且按照频率的降序在表中排列。

下一步，代替得分对，c得分通过预测T的类标签计算。这样，T在类Dn中的得分定义如下：

$$ >>score>>(>T>)>>\_>>D>n>>=>>\Sigma >>m>=>1>>k>>>>>>f>n>>>(>>i>m>>)>>>>>f>n>>>(>m>)>>>>>|>>>EP>n>>>(>>i>m>>)>>\in >T>>>>>$$

相应地，有最高分的类被预测成T的类，Dn的大小被用来停止关系。

本发明方法的根本原则是测量在中T包含的顶部k EP’s与给定类的顶部k EP’s之间有多远。通过使用多于一个顶部排列的EP’s，更多可靠预测的“共同”可能性被采用。因此，这个方法适合作为通过共同可能性预测(“PLC”)。

在k＝1的情况下，那么score(T)_D1指示是否包含在T中的第一分割EP与D1的最频繁发生EP距离很远。在这种情况下，如果score(T)_D1有最大值，1，那么“距离”是很近的，即，D1的最共同属性也同时存在与测试例子中。得分越小表示距离越大，这样，它就变的更不象属于D1类的T。一般地，score(T)_D1或score(T)_D2都是他们的最大值，如果每个k顶部排列的EP’s在T中。

可以理解的是，本发明的方法一般可以用来处理形成模型，包括但是不限于：边界形成模型；只有左边界的形成模型；坪形成模型；只有最特殊的坪形成模型；增长率大于门限ρ的形成模型，其中门限是任何比1大的数，适合的是2或∞(象在跳跃EP中)或数字从2到10。

在本发明另一个体现中，坪空间(P—空间，象在上面描述的)可以用于分类法。另外，最特殊的P—空间元素被使用。在PCL中，分割的边界EP’s被所有P—空间的最特殊元素所代替，在数据组和其它PCL的步骤中，象上面描述的，被实现。

这个体现的功效的理由是在多个情况下，P—空间的最特殊元素的邻居是所有EP’s，但是在边界EP’s的邻居中有许多模型不是EP’s。第二，包含在P—空间的最特殊元素中的条件通常比边界EP’s的多很多。所以条件的数量越多，为测试例子包含来自相反类的EP’s地机会越低。因此，成为正确分类的概率变的越大。

其它在分类法中使用EP’s的方法

PCL不是在分类法中唯一使用EP’s方法的。其它可靠的方法，能给出合理的结果是和本发明和上面描述的目标是一致的。

此外，给定一个测试实例，表示为T，他对应的训练数据D，为预测T类的第二个方法包括以下步骤，其中符号和术语的解释不限定：。

1.把D分成两个次数据组，表示为D1和D2，每一个分别由两个数据类里的一个组成，并建立空表，finalEPs。

2.在D1中发掘EP’s，同样在D2中发掘EP’s。

3.根据频率和长度(模型中项目的数量)，把EP’s(从D1和D2)排成降序。排列规则是：

(a)给定两个EP’s Xi和Xj，如果Xi的频率大于Xj，那么Xi在表里有先于Xj。

(b)当Xi和Xj的频率相同，如果Xi的长度长于Xj，那么在表中Xi优先于Xj。

(c)两个模型相同对待，当他们的频率和长度都相等时。排列EP表表示成orderedEPs。

4.把orderedEPs的第一个EP放入finalEPs。

5.如果第一个EP是来自D1(或D2)，建立新的D1(或新D2)，他由那些D1(或D2)的实例组成，并不包括第一个EP。

6.重复步骤2到步骤5直到新的D1或新的D2空为止。

7.在包含第一个EP的finalEPs中找到第一个EP，一个他们包含的直接合适的EP子集，T。如果EP是来自第一类，那么测试实例预测在第一类中。否则测试实例预测在第二类中。

根据第三个方法，使用强EP’s确认是否系统能做的更精确，效仿的步骤如下：

1.把D分成两个次数据组，表示成D1和D2，分别有第一类和第二类组成。

2.在D1中发掘强EP’s，同样在D1中发掘强EP’s。

3.根据频率，将两个表中的EP’s徘成降序。命名有序EP表为orderedEPs1和orderedEPs2分别为在D1和D2中的强EP’S。

4.从orderedEPs1里找到顶部k EP’s，必须包含在T中，表示为：EP1(1)，...，EP1(1)。同样，从orderedEPs2里找到顶部EP’s，必须包含在T中，表示为：EP2(1)，...，EP2(1)。

5.比较EP1(1)的频率和EP2(1)的频率，如果前面的大，测试实例就预测是在第一类数据中。相反，如果后面的大，测试实例就预测分类到第二类数据中。联系情况通过使用强2—EP’s分开，即EP’s的增长率大于2。

在分类法中评价EP’s的有用性

形成模型的有用性可以通过使用“留—交叉效验法”(LOOCV)分类法的研究来进行测试。在LOOCV中，数据组的第一个实例被认为是一个测试实例，其余的数据被当作训练数据。从第一个实例到最后一个实例重复这个步骤，就可能获取准确性，即，正确被预测的实例的百分比。其它获取准确性的方法是通常具有熟练技能的人所知道的，和本发明的方法是一致的。

本发明的实用性是通过几个例子来说明的。对于一个具有熟练技能的人是可以理解的。这些例子并不限制本发明的范围，和只不过是说明典型的表现。

实施例

例1.形成模型

例1.1：生物数据

许多EP’s可以从UCI知识库的迅速增加的数据组中找到。(Blake，C.& Murphy，P.，“The UCI machine learning repository，”略)对于增长率门限是2.5。下列是两个典型EP’s，每一个包含3项。

X＝{(ODOR＝none)，(GILL_SIZE＝broad)，(RING_NUMBER＝one)}

Y＝{(BRUISEs＝no)，(GILL_SPACING＝close)，(VEIL_COLOR＝white)}

它们在蘑菇，有害的，可食用的两个类中的支持，如下：

EP有害的支持可食用的支持增长率X0％63.9％∞Y81.4％3.8％21.4

那些具有大增长率的EP’s在可食用和有害蘑菇类间显示显著的区别特性，他们对于建立强有力的分类器是有用的。(文献J.Li，G.Dong，andK.Ramamohanarao，Making use of the most expressive jumpingemerging patterns for classification.″Knowledge and InformationSystems，3：131-145，(2001)，有趣的，没有一个项目组{ODOR＝none}，{GILL_SIZE＝broad}，和{RING_NUMBER＝one}是一个EP，尽管有些包含超过的8项。

例1.2：地理数据

大约120个包含13项EP’s的收集在美国人口普查数据组中发现，“PUMS”(可用的来自www.census.gov)。这些EP’S通过比较德克萨斯州的人口数量和密歇根州的比较来得到，使用增长率门限1.2。一个这种EP是：

{Disabl 1：2.Langl：2，Means：1，Mobili：2，Perscar：2，Rlabor：1，Travtim：[1..59]，Work89：1}.项目分别描述为：残疾(disability)、language at home交通(means oftransport)、个人医疗(personal care)就业情况(employment status)traveltime to work and是否工作(working or not)在1989年里，每一个属性值在列举的值域表中对应一项。在不同的社会和地区之间，这样的EP’s能描述不同的人口特性。

例1.3：销售数据中的趋势。

假设在1985年在2亿的有记录的交易中取出1000个模型{计算机、调制解调器、教育软件}的销售，在1986年在2.1亿的交易中取出2100个这种销售。从1985到1986年，这个销售模型是一个增长率为2的EP，这样，在任何分析中被确认的而且它的增长率门限设成小于2的数。在这种情况下，项目组的支持是非常小的甚至在1986年。这样在赏识具有低支持的模型的重要性中很有价值。

例1.4：医学记录数据

确定研究癌病患者，一个数据组包含被治疗病人的记录和另一组包含没有治疗的病人记录，数据包含的信息有症状，S和治疗T。假设有用EP{S1，S2，T1，T2，T3}，增长率为9来自未治疗的比已治疗的，可以说，在所有癌病患者中具有病症S1和S2，接受所有T1、T2、T3治疗的人，治愈病人的数量是没有治愈的9倍。这样可以建议治疗的组合可以应用于无论哪些症状组合的发生(如果没有更好的方案)。EP可以有低支持，象1％，但是除了当医疗领域有了新的知识因为缺少有效的方法来找到有如此低支持和包含许多项的EP’s。这个EP甚至可能和主要流行的对例子特征Si的每个治疗有效性的有关知识相反。选择这样一组的EP’s因此能是对医生在确定在一个给定的医学情况下使用哪种治疗时一个有用的指导，通过一组症状简短的说明，例如：

例1.5：作为例证的基因表现数据

把一个基因的DNA序列转录成RNA的过程称作基因表现。转换后，RNA编码由氨基酸序列组成的蛋白。基因表现等级是在细胞中产生基因的RNA的副本数量。基因表现数据，通常包含通过类似实验高度使用技术象微阵列(文献Schena，M.，Shalon，D.，Davis，R.，and Brown，P.，″Quantitative monitoring of gene expression patterns with acomplementary dnamicroarray，″Science，270：467-470，(1995))低聚核苷酸“基片”(文献Lockhart，D.J.，Dong，H.，Byrne，M.C.，Follettie，M.T.，Gallo，M.V.，Chee，M.S.，Mittmann，M.，Wang，C.，Kobayashi，M.，Horton，H.，and Brown，E.L，″Expression monitoring by hybridization tohigh-density oligonucleotide arrays，″Nature  Biotechnology，14：1675-1680，(1996))基因表示的连续分析(“SAGE”)Velculescu，V.，Zhang，L，Vogelstein，B.，and Kinzler，K.，Serial analysis of geneexpression.Science，270：484-487，(1995)，在特殊实验条件下记录的基因表现等级。

在两个数据类见的重要区别知识是在生物医学有用的。例如，在一些基因表现实验中，医学博士或生物学家希望知道在正常细胞和病态细胞之间的确定基因或基因组急剧改变的表现等级。那么这些基因或他们的蛋白产品就可以用语诊断指示或特定病的药物目标。

基因表现数据典型的组织成矩阵。这样的矩阵有n行和m列。N通常表示考虑过的基因数量，m表示实验的次数。有两种主要类型的实验。第一种实验类型针对同时监测在连续变化条件下n个基因m次(文献DeRisi，J.L.，Iyer，V.R.，and Brown，P.O.，″Exploring the Metabolicand Genetic Control of Gene Expression on a Genomic Scale，″Science.278：680-686，(1997))。这种类型的实验趋向与提供在连续变化条件下每个基因的可能趋势或规则。结果数据一般是零时的。第二个类型实验用于在一种情况下但从m个不同细胞中检查n个基因(文献Alon，U.，Barkai，N.，Notterman，D.A.，Gish，K.，Ybarra，S.，Mack，D.，andLevine，A.J.，″Broad Patterns of Gene Expression Revealed byClustering Analysis of Tumor and Normal Colon Tissues Probed byOligonucleotide Arrays，″Proc.Natl.Aead.Sci.U.S.A.，96：6745-6750，(1999))这种类型的实验期望有助于在分类新细胞和表现是好的诊断指示[1，8]的有用基因的证明。结果数据一般是空间。

基因表现值是连续的。给定一个基因，表示为genej，在连续变化条件下或在单个条件不同类型细胞中的表现值形成一个实际值的范围。假设范围是[a，b]，间隔[c，d]是包含在[a，b]中。称genej@[c，d]为一“项”，意味着genej的值限制在c和d之间。一个单个项的组，或来自不同基因的几个项目的一个组称作一个模型。这样一个模型的形式是：{geneil@[ail，bil]，...，genej@[a ak，bik]}这里it≠is，1≤k。模型总是数据组中的一个频率。这个例子显示了如何计算一个模型的频率，和，这样，形成模型。

表B：简单仿效的基因表现数据组

                                                        细胞类型  基因  正常  正常  正常  正常  正常  正常Gene_1  0.1  0.2   0.3  0.4  0.5  0.6Gene_2  1.2  1.1   1.3  1.4  1.0  1.1Gene_3  -0.70  -0.83   -0.75  -1.21  -0.78  -0.32Gene_4  3.25  4.37   5.21  0.41  0.75  0.82

表B有在6个细胞中的4个基因表示值组成，其中3个是正常的，3个是癌变的。表B的每个6列是一个“实例”。模型{genel@[0.1，0.3]}在整个数据组中有一个50％的频率因为第一个三个实例的genel的表现值在区间[0.1，0.3]中。另一个模型，{genel@[0.1，0.3]，gene3@[0.30，1.21]}，在整个数据组中有0％的频率因为没有一个实例满足这两个条件：(i)genel的值必须在范围[0.1，0.3]中；(ii)genel的值必须在范围[0.3，1.21]中；然而可以看到模型{genel@[0.4，0.6]，gene3@[0.41，0.82]}有50％的频率。

为了显示形成模型，表B的数据组被分到两个次数据组中；一个由3个正常细胞的值组成，另一个由3个癌变细胞的值组成。给定模型的频率可以从一个次数据组变到另一个次数据组。形成模型是那些在两个次数据组间频率变化巨大的模型。模型{genel@[0.1，0.3]}是形成模型，因为它在由正常细胞组成次数据组中有一个100％的频率，但在癌变细胞次数据组中的频率为0％。

模型{genel@[0.4，0.6]，gene3@[0.41，0.82]}也是一个形成模型，因为他在有正常细胞的次数据组中有0％的频率。

两个公开地基因表现数据组使用在下面的例子中。一个白血病数据组(文献Golub et al.，″Molecular classification of cancer：Classdiscovery and class prediction by gene expression monitoring″，Science，286：531-537，(1999))和一个结肠瘤数据组(文献Alon，U.，Barkai，N.，Notterman，D.A.，Gish，K.，Ybarra，S.，Mack，D.，andLevine，A.J.，″Broad Patterns of Gene Expression Revealed byClustering Analysis of Tumor and Normal Colon Tissues Probed byOligonucleotide Arrays，″Proc.Natl.Acad.Sci.U.S.A.，96：6745-6750，(1999)列在表C中。基因表现数据的共同特性是例子的数量与商业市场的数据比较是小的。

    数据组    基因数  训练的大小    类    白血病    7129    27    ALL    11    AML    结肠瘤    2000    22    Normal    40    Cancer

其它的符号表示法，基因的表示等级，X，可以给成gene(X).。形成模型的一个例子，模型在正常组织中0％的频率变成在从这个结肠瘤数据中取出的癌组织中75％的频率，包含以下3项：{gene(K03001)≥89.2，gene(R76254≥127.16，gene(D31767)63.03}这里K03001、R76254和D31767是特殊的基因。根据这个形成模型，在新的细胞实验中，如果geneK03002的表现值不小于89.20和gene R763254的表现值不小于127.16和geneD31767的表现值不小于63.03，那么这个细胞就比正常细胞更象是一个癌变细胞。

例2：来自瘤数据组的形成模型。

这个数据组包含的基因表现等级有正常细胞和癌变细胞的和通过前面在例1.4中讨论的第二种实验中包含的。数据由基因从22个正常组织例子中约6500个基因和从一个Affymetrix Hum6000组(文献Alon etal.，″Broad patterns of gene expression revealed by clustering analysisof tumor and normal colon tissues probed by oligonucleotidearrays，″Proceedings of National Academy of Sciences of the UnitedStates of American，96：6745-6750，(1999)中获得40个瘤组织例子的表现值组成。这些例子的2000个基因的表现等级是根据其在例子边的最小密度来选择，忽略那些具有较抵最小密度的基因。http：//microarray.princeton.edu/oncology/affydata/index.html为简化数据组所在的网站，这些数据是公开可用的。

这个例子主要关心下面的问题：

1.哪些基因的表示值的区间或哪些多个基因的区间组合只发生在癌变组织中但没有在正常组织中，或只发生在正常组织中但没有在癌变组织中？

2.把一个基因的表示值的范围离散化到多个区间中已至于上面提到的反向区间或区间组合，在所有EP’s中，是有情报的可靠的，如何把这变成可能。

3.发现的模型可以执行分类任务吗？，即，在进行了相同类型的表现实验后，预测是否一个新细胞是正常的或癌变的。

这些问题通过几个技术来解决。对于有2000个基因的结肠癌数据组，只有35个相关基因被离散成2个区间当通过使用该方法将剩余的1965省略掉。因为多个基因被看作是“不重要的”，这个结果是非常重要的。在有许多好的诊断指示的简单的平台上出的结果。

对有离散化，数据被重新组织成使用MLC的工具需要的格式(参考文献Kohavi，R.，John，G.，Long，R.，Manley，D.，and Pfleger，K.，″MLC++：A machine learning library in C++，″Tools with Artifzcial17atelligence，740-743，(1994))。简而言之，重新组织的数据组斜对称于原始数据组。在这个例子中，我们提出离散化的结果来哪些是被选择的基因和那些是被忽视的基因。一个基于熵的离散化方法产生具有“最大的”和在来自正常细胞的表现值和来自癌变细胞的表现值之间的可靠区分的区间。这样基于熵的离散化方法可以自动忽略大部分的基因和选择一些最有区别的基因。

离散化方法将2000个基因中的35个分到两个不连接的区间中，当在剩余的1965个基因中没有切断点时。这显示只有1.75％(＝35/2000)的基因被认为是特殊区别基因，其它的可以认为是对于分类来讲关系不重要的。为衍生一些小数量好的诊断基因，这样离散化方法放掉一个有效发现可靠形成模型的基础，因此排除了产生大量的噪声模型。

离散化结果总结在表D，其中：第一列包含35个基因条目；第二列显示基因数量；区间显示在列3；基因的序列和名字分别显示在列4和5。表D中的区间表示在一个众所周知的数学转换中，这里方括号表示包含范围边界的数字，圆括号不包括边界数字。

表D：35个基因通过基于熵的方法被离散化分到多于一个的区间内。

序号基因数区间序列名称1T51560(-∞，101.3719)，[101.3719，+∞)3’UTR40S RIBOSOMAL PROTEIN S16(HUMAN)2T49941(-∞，272.5444)，[272.5444，+∞)3’UTR PUTATTVE INSULIN-LIKE GROWTHFACTOR IIASSOCIATED(HUMAN)3M62994(-∞，94.39874)，[94.39874，+∞)基因 Homo sapiens thyroid autoantigcn(truncatedactin-binding protein)mRNA，complete cds4R34701(-∞，446.0319)，[446.0319，+∞)3’UTR TRANS-ACTING TRANSCRIPTIONALPROTEIN ICP4(Varicella-zoster virus)5 X62153(-∞，395.2505)，[395.2505，+∞]基因 H.sapicns mRNA for P1 protein(P1，h)6T72403(-∞，296.5696)，[296.5696，+∞)3’UTR HLA CLASS II HISTOCOMPATIBILITYANTIGEN，DQ(3)ALPHA CIIAINPRECURSOR(Homo sapiens)7L02426(-∞，390.6063)，[390.6063，+∞)基因Human 26S protease(S4)regulatory subunitmRNA，complete cds  8 K03001(-∞，289.19624)，[289.19624，+∞)基因Human aldehyde dehydrogcnase 2 mRNA9U20428(-∞，207.8004)，[207.8004，+∞)基因Human unknown protein(SNC19)mRNA，partial cds10R53936(-∞，206.2879)，[206.2879，+∞)3’UTRPROTEIN PHOSPHATASE 2C HOMOLOG2(Schizosaccharomyces pombe)11H11650(-∞，211.6081)，[211.6081，+∞)3’UTRADP-RIBOSYLATION FACTOR 4(Homosapicns)12R59097(-∞，402.66)，[402.66，+∞)3’UTRTYROSINE-PROTEIN KINASE RHCEPTORTIE-1 PRECURSOR(Mus musculus)13T49732(-∞，119.7312)，[119.7312，+∞)3’UTRHuman SnRNP core protein Sm D2 mRNA，complete cds14J04182(-∞，159.04)，[159.04，+∞)基因LYSOSOME-ASSOCLATED MEMBRANEGLYCOPROTEIN 1 PRECURSOR (HUMAN)15M33680(-∞，352.3133)，[352.3133，+∞)基因Human 26-kDa cell surface protein TAPA-1mRNA，complcte cds16R09400(-∞，219.7038)，[219.7038，+∞)3’UTRS39423 PROTEIN I-5III，INTERFERON-GAMMA-INDUCED17R10707(-∞，378.7988)，[378.7988，+∞)3’UTRTRANSLATIONAL INITIATION FACTOR2ALPHA SUBUNIT(Homo sapicns)18D23672(-∞，466.8373)，[466.8373，+∞)基因Human mRNA for biotin-[propionyl-CoA-carboxylase(ATP-hydrolysing)]ligase，compleie cds19R54818(-∞，153.1559)，[153.1559，+∞)3’UTRHuman eukaryotic initiation factor 2B-epsilonmRNA，partial cds20J03075(-∞，218.1981)，[218.1981，+∞)基因PROTEIN KINASE C SUBSTRATE，80KDPROTEIN，HEAVY CHAIN(HUMAN)；contains TAR1 rcpetitive element21T51250(-∞，212.137)，[212.137，+∞)3’UTRCYTOCHROME C OXIDASEPOLYPEPTIDE VIII-LIVER/HEART(HUMAN)22X12671(-∞，149.4719)，[149.4719，+∞)基因Human gene for heterogeneous nuclearribonucleoprotein(hnRNP)core protein A123T49703(-∞，342.1025)，[342.1025，+∞)3’UTRGOS ACIDIC RIBOSOMALPROTEIN P1(Pollyorchis penicillatus)24U03865(-∞，76.86501)，[76.86501，+∞)基因Human adrenergic alpha-lb receptor proteinmRNA，complete cds 25  X16316(-∞，65.27499)，[65.27499，+∞)基因VAV ONCOGENE(HUMAN)26U29171(-∞，181.9562)，[181.9562，+∞)基因Human casein kinase Idelta mRNA，completecds 27  H89983(-∞，200.727)，[200.727，+∞)3’UTRMETALLOPAN-STIMOLIN 1(Homo sapiens)28T52003(-∞，180.0342)，[180.0342，+∞)3’UTRCCAAT/ENHANCER BINDING PROTEINALPHA(Rattus norvegicus)29R76254(-∞，127.1584)，[127.1584，+∞)3’UTRELONGATION FACTOR 1-GAMMA(Homosapiens)30M95627(-∞，65.27499)，[65.27499，+∞)基因Homo sapiens angio-associated migratory cellprotein(AAMP)mRNA，complete cds31D31767(-∞，63.03381)，[63.03381，+∞)基因Human mRNA(KIAA0058)for ORF(novelprotein)，complete cds 32  R43914(-∞，65.27499)，[65.2499，+∞)3’UTRCREB-BINDING PROTEIN(Mus musculus)33M37721(-∞，963.0405)，[963.0405，+∞)基因PEPTIDYL-GLYCINE ALPHA-AMIDATINGMONOOXYGENASE PRECURSOR(HUMAN)；contains Alu repcpctitivc element34L40992(-∞，64.85062)，[64.85062，+∞)基因Homo sapiens(clone PEBP2aA1)core-bindingfactor，runt domain，alpha subunit 1(CBFA1)mRNA，3’end of cds 35  H51662(-∞，894.9052)，[894.9052，+∞)3’UTRGLUTAMATE(Mus musculus)

这有总共70个区间。因此，包括70个项，每一项是一对含有一个联系区间的基因。这70项是已索引的，如下：第一个基因的两个区间是依照第1和第2项索引的，第i个基因的两个区间是依照第(i*2-1)和第(i*2)项索引的，第35个基因的两个区间是依照第69和第70项索引的。当读写形成模型时，这个索引是方便的。例如，模型{2}代表(genet51560@[101.3719，+∞)}。

基于离散化数据的形成模型通过使用2种有效的基于边界的算法来发掘，边界区别(BORDER-DIFF)和JEP-过程(JEP-PRODUCER)(参考文献)。这些算法可以衍生出“Jumping Emerging Patterns”(跳跃形成模型)—这些EP’s，他们在一个数据类里都具有最大频率(即，在这个情况中正常组织或癌变组织)，但是不是在所有其它类中都发生。19501EP’s的总数，在结肠瘤数据组的正常细胞中拥有的非零频率已被发掘，2165EP’s的总数，在癌变组织中具有非零频率，通过这些算法也被发掘。

表E和F，按照发生频率的降序排列，分别有22个正常组织和40个癌变组织，顶部20个EP’s和强EP’s。在每个情况中，列1显示EP’s。在模型中的数字，例如16，58，62在模型{16，58，62}，代表上面讨论过和已索引的项。

表E：顶部20个EP’s和顶部20个强EP’s，在22个正常组织中。

    形成模型  记数  正常组织瘤组织强EP’s记数正常模型{2，3，6，7，13，17，33}  20    90.91％  0％  {67}    7    31.82％{2，3，11，17，23，35}  20    90.91％  0％  {59}    6    27.27％{2，3，11，17，33，35}  20    90.91％  0％  {61}    6    27.27％{2，3，7，11，17，33}  20    90.91％  0％  {70}    6    27.27％{2，3，7，11，17，23}  20    90.91％  0％  {49}    6    27.27％{2，3，6，7，13，17，23}  20    90.91％  0％  {66}    6    27.27％{2，3，6，7，9，17，33}  20    90.91％  0％  {63}    6    27.27％{2，3，6，7，9，17，23}  20    90.91％  0％  {49，66}    4    18.18％{2，3，6，17，23，35}  20    90.91％  0％  {49，66}    4    18.18％{2，3，6，17，33，35}  20    90.91％  0％  {59，63}    4    18.18％{2，6，7，13，39，41}  19    86.36％  0％  {59，70}    4    18.18％{ 2，3，6，7，13，41}  19    86.36％  0％  {59，63}    4    18.18％{2，6，35，39，41，45}  19    86.36％  0％  {59，70}    4    18.18％{2，3，6，7，9，31，33}  19    86.36％  0％  {49，59，66}    3    13.64％{2，6，7，39，41，45}  19    86.36％  0％  {49，59，66}    3    13.64％{2，3，6，7，41，45}  19    86.36％  0％  {59，61，63}    3    13.64％{2，6，9，35，39，41}  19    86.36％  0％  {59，63，70}    3    13.64％{2，3，17，21，23，35}  19    86.36％  0％  {59，61，63}    3    13.64％{2，3，6，7，11，23，31}  19    86.36％  0％  {59，63，70}    3    13.64％{2，3，6，7，13，23，31}  19    86.36％  0％  {49，59，66}    3    13.64％

顶部20个EP’s和顶部20个强EP’s，在40个癌变组织中。

形成模型记数正常组织瘤组织  强EP’s  记数  正常模型  {16，58， 62}    30    0％    75.00％    {30}    18    45.00％  {26，58，62}    26    0％    65.00％    {14}    16    40.00％  {28，58}    25    0％    62.50％    {10}    15    37.50％  {26，52，62，64}    25    0％    62.50％    {24}    15    37.50％  {26，52，68}    25    0％    62.50％    {34}    14    35.00％  {16，38.58}    24    0％    60.00％    {36}    13    32.50％  {16，42，62}    24    0％    60.00％    {1}    13    32.50％  {16，26，52，62}    24    0％    60.00％    {5}    13    32.50％  {16，42，68}    24    0％    60.00％    {8}    13    32.50％  {26，28，52}    23    0％    57.00％    {24，30}    11    27.50％  {16，38，52，68}    23    0％    57.50％    {30，34}    11    27.50％  {16，38，52，62}    23    0％    57.50％    {24，30}    11    2750％  {26，52，54}    22    0％    55.00％    {30，34}    11    27.50％  {26，32}    22    0％    55.00％    {10，14}    10    25.00％  {16，54，58}    22    0％    55.00％    {10，14}    10    25.00％  {16，56，58}    22    0％    55.00％    {24，34}    9    22.50％  {26，38，58}    22    0％    55.00％    {14，24}    9    22.50％  {32，58}    22    0％    55.00％    {8，10}    9    22.50％  {16，52，58}    22    0％    55.00％    {10，24}    9    22.50％  {22，26，62}    22    0％    55.00％    {8，10}    9    22.50％

一些主要的观点可以从下面对形成模型的总结里推断出。首先，基于边界算法保证发现所有的形成模型。

部分形成模型惊奇的重要，特别对那些包含相关的大数量的基因。例如，尽管模型(2，3，6，7，13，17，33)包含7个基因一起，它仍能在正常组织中有非常的的频率(90.91)，即几乎每个正常细胞的表现值都满足所有的7项暗示的条件。然而，没有一个癌变细胞满足所有的条件。观察到所有合适的模型{2，3，6，7，13，17，33}的次模型，包括单个的和6项组合的，在正常和病变的组织中必须有一个非零频率。这意味着这里存在至少一个在正常和病变的组织中的细胞满足{2，3，6，7，13，17，33}的次模型暗示的条件。

单个形成模型的频率，象{5}没有必要大于一个包含多于一项的形成模型的频率，例如{16，58，62}。这样模型{5}是一个在癌变组织中有一个32.5％的频率的形成模型，它小于模型{16，58，62}的频率75％约2.3倍。这显示，对于基因表现数据的分析，基因组和他们的相互性比单个基因更好和更重要。

没有离散化方法和边界发掘算法，发现那些可靠的有大的频率的形成模型是很困难的。假设1965个其它基因每个都同样分到2个区间内，那么有C₂₀₀₀⁷*2⁷个可能的模型有7的长度。列举如此巨大数量的模型和计算他们的频率在这里是不实际的。甚至使用离散化方法，列举C₃₅⁷*2⁷个模型里发现模型{2，3，6，7，13，17，33}是很昂贵的。问题在现实中甚至更复杂可能会增值的，当已经知道的是一些发掘的包含超过7个基因的EP’s(没有列在这)时。

通过使用2个基于边界的算法，只有那些正确的子集是形成模型的EP’s被发掘。有趣的是，其它EP’s可以通过使用发掘的EP’s衍生。一般地，任何发掘模型的正确子集也是一个形成模型。例如，使用20计数的EP‘s(在表E中显示)，一个非常长的形成模型{2，3，6，7，9，11，13，17，23，29，33，35}，由12个基因组成，有同样20个能被衍生。

注意任何62个组织必须符合至少一个从它自己的类来的形成模型，但是不包括从其它类来的任何EP’s。因此，系统已经学习好了所有数据，因为数据的每一项通过系统通过发掘的模型掩盖。

总结，发掘形成模型总是包括一些数量的基因。结果不只允许使用者注意小数量的好诊断指示上，而且更重要的是他展现了基因的相互作用，那是起源在基因区间的结合和结合的频率。发掘形成模型可以用来预测新细胞的属性。

接着，形成模型用于执行分类任务来看模型在预测一个新细胞是正常还是癌变上的有用性。

象显示在表E和表F中，EP’s的频率是很大的，因此基因的组是对新组织分类好的指示。通过使用“留一交叉效验法”(LOOCV)分类任务，测试模型的可用性是有用的。通过使用LOOCV，62个组织的第一个实例被确定为测试实例，剩余的61个实例被当作训练数据。重复这个过程，从第一个实例到第62个，得到准确性是可能的，通过正确预测的实例的百分比给定。

在这个例子中，2个次数据组分别包括正常训练组织和癌变训练组织。确认正确地预测62个组织中的57个。只有3个正常组织(N1，N2，N39)被错误的分做癌变组织，同时两个癌变组织被错误的分做正常组织。这个结果可以和在著作中的结果比较。Furey等人(文献Furey，T.S.，Cristianini，N.，Duffy，N.，Bednarski，D.W.，Schummer，M.，andHaussler，D.，″Support vector machine classification and validation ofcancer tissue samples using microarrayexpressiondata，″Bioinformatics，16：906-914，(2000)错误分类的6个组织(T30，T33，T36，N8，N34，和N36)，通过使用1000个基因和SVM法逼近。

强调的是结肠瘤数据组非常复杂。通常地和理想地，测试正常(或癌变)组织应当包含来自正常(或癌变)训练组织的大量EP’s和来自其它组织类型的小数量的EP’s。然而，根据这里提及地方法，测试组织能包含许多EP’s，甚至顶部排列的高频率EP’s，来自组织的两个类。

使用上面提及的第三种方法，62个组织中的58个被正确的预测。4个正常组织(N1，N12，N27，和N39)被错误的分做癌变组织。这样，当强EP’s被使用，分类的结果提高。

根据在相同数据组上的分类结果，我们的方法执行比SVM方法和簇(clusering)方法好很多。

边界EP’s

另外，CFS方法从2000个最重要的原始基因中选择23个特征。所有23个特征被分入两个区间中。

总共371个边界EP’s被在正常细胞类中发掘，131个边界EP’s在癌变细胞类中，使用这23个特征。总共502个模型被依照上面的方法分类。一些顶部分类的边界EP’s表示在表G中。

表G。在正常类和癌变类中顶部10个分类的边界EP’s列入

边界EP’s发生正常发生癌变(2，6，7，11，21，23，31)18(81.8％)0(2，6，7，21，23，25，31)18(81.8％)0(2，6，7，9，15，21，31)18(81.8％)0(2，6，7，9，15，23，31)18(81.8％)0(2，6，7，9，21，23，31)18(81.8％)0(2，6，9，21，23，25，31)18(81.8％)0(2，6，7，11，15，31)18(81.8％)0(2，6，11，15，25，31)18(81.8％)0(2，6，15，23，25，31)18(81.8％)0(2，6，15，21，25，31)18(81.8％)0(14，34，38)030(75.0％)(18，34，38)026(65.0％)(18，32，38，40)025(62.5％)(18，32，44)025(62.5％)(20，34)025(62.5％)(14，18，32，38)024(60.0％)(18，20，32)023(57.5％)(14，32，34)0 22(55.0％)(14，28，34)0 21(52.5％)(18，32，34)0 20(50.0％)

不同的ALL/AML数据，下面在例3中讨论，在结肠瘤数据组中，没有一个基因，它的行为象仲裁人一样清楚的分离正常和癌变细胞。相反，基因组在两个类之间展现对比中的差异。注意到这个，和新颖性一样，这些边界EP’s，特别是那些具有很多条件的，对生物学家和医学博士并不明显。这样他们可以潜在的表现新生物学的功能和可能具有查找新路的潜力。

P—空间

可以看到，总共有10个边界EP’s在正常细胞组中拥有相同的最高发生18。基于这些边界EP’s，一个P18—空间可以被找到，在其中最特殊的元素是Z＝{2，6，7，9，11，15，21，23，25，31}。通过凸性，任何Z子集，也是10个边界EP’s的任何一个的超组，在正常类里有发生18。在这个P—空间里大约有100个EP’s。另外，通过凸性只使用11个EP’s就可以连续表示这个空间，象在表H中显示：

表H：在结肠数据的正常类中的一个P—空间

最一般和最特殊的EP’s在正常类中的发生  (2，6，7，11，21，23，31)  18  (2，6，7，21，23，25，31)  18  (2，6，7，9，15，21，31)  18  (2，6，7，9，15，23，31)  18  (2，6，7，9，21，23，31)  18  (2，6，9，21，23，25，31)  18  (2，6，7，11，15，31)  18  (2，6，11，15，25，31)  18  (2，6，15，23，25，31)  18  (2，6，15，21，25，31)  18  (2，6，7，9，11，15，21，23，25，31)  18

在表H中，前10个EP’s是最一般的元素，最后一个是在空间中最特殊的元素。所有EP’s在正常和癌变类中，类频率分别为18和0具有相同的发生。

从这个P—空间，可以看到重要的基因组(边界EP’s)可以通过增加一些没有丢失重要性的其它基因，即仍保持高的发生在一个类中，但不存在在其它类中。在确定生物学路径最大长度中可以是有用的。

同样地，在癌变类中可以找到一个P30—空间。在这个空间里最一般的EP只有{14，34，38}和最特殊的EP只有{14，30，34，36，38，40，41，44，45}。所以，一个边界EP可以增加6个多的基因而不改变它的发生。

阴影模型

也可以直接找到阴影模型。表J报告一个边界EP，显示在第一行，和它的阴影模型。这些阴影模型也可以用来说明这样的点，在两个类中在非零频率上边界EP正确的子集必须发生的点。

表J：边界EP和他的三个阴影模型

    模型                                         发生    正常    癌变    {14，34，38}    0    30    {14，34}    1    30    {14，38}    7    38    {34，38}    5    31

对于结肠数据组，使用PCL方法比其它分类方法象C4.5，纯贝叶斯，k--NN，和支持向量机能得到更好的LOOCV误差率。在表K中总结了结果，其中误差率用错误预测的绝对数量表示。

表K：PCL的误差率和其它方法的比较，在结肠数据组上使用LOOCV

    方法    误差率    C4.5    20    NB    13    k—NN    18                         SVM    24    PLC    K＝5    13    K＝6    12    K＝7    10    K＝8    10    K＝9    10    K＝10    10

另外，P—空间能使用于分类法。例如，对于结肠数据组，分割的边界EP’s被所有P—空间最特殊元素替代。换句话说，代替提取边界EP’s，最特殊坪EP’s被提取。应用PCL方法的剩余的步骤不变。通过LOOCV，得到一个只有6的错误分类误差率。相比那些表K中的，这种减少是巨大的。

例3：第一基因表示数据组(白血病病人)

一个白血病数据组(参考Golub，T.R.，Slonim，D.K.，Tamayo，P.，Huard，C.，Gaasenbeek，M.，Mesirov，J.P.，Coller，H.，Loh，M.L.，Downing，J.，Caligiuri，M.A.，Bloomfield，C.D.，& Lander，E.S.，″Molecular classification of cancer：Class discovery and classprediction by gene expressionmonitoring，″Science，286：531-537，(1999))，包含一个由27个急性的淋巴母细菌的白血病(ALL)的例子和11个急性的成髓细胞的白血病(AML)的例子组成的训练组，显示在上面的表C中。(ALL和AML是两个主要白血病的次类型)这个例子使用一个由20个ALL和14个AML的例子组成的隐蔽测试组。这个高密度的低聚核苷酸微阵使用6817个人类基因中的的7129个探头。数据在http：//www.genome.wi.mit.edu/MPR上是公开可用的。

例3.1：从白血病数据衍生的模型

CFS方法从总共7129个特征中只选择一个基因，Zyxin。离散化方法通过使用在994的切断点分割这个特征到两个区间里。这样，可以发现2个具有在它们的基类里100％发生的边界EP’s，gene_zyxin@(-∞，994)和gene_zyxin@[994，+∞)。

在生物学上，这两个EP’s指示，如果在例子细胞中Zyxin的表现小于994，那么这个细胞是在ALL类中。否则，这个细胞是在AML类中。这个规则没有任何例外的调整所有38个训练实例。如果规则应用于34个隐藏测试实例，只获得3个错误分类。这个结果比报告在Golub等人，Science，286-531-537，(1999).中的系统的准确性要好很多。

生物学的和技术上的噪声有时会发生在实验规程中的许多产生数据的步骤中，来自机器和人的原因。例子包括的是：DNA阵列的生产，准备的例子，表现等级的提取，还有从不纯的或错误分类的组织来的。为了解决这些可能的错误—甚至是很小的—建议使用多于一个基因来加强分类方法，在下面的讨论时。

可以找到4个基因，这四个基因是当通过基于熵的离散化方法分割时，熵值极小于那些所有其它7127个特性。这四个基因，他们的名字、切断点、和项目索引列在表L中，是选择用于模型发掘的。每个在表L中的特性，通过使用列2中的切断点被分割到两个区间里。项目索引指示EP。

表L：来自7129个特性的4个最有区别的基因

  特征  切断点  项目索引  Zyxin  994    1，2  Fah  1346    3，4  Cst3  1419.5    5，6  Tropomyosin  83.5    7，8

在ALL和AML类中每类都发现3个共6个边界EP’s。表M呈现出了整个类中的边界EP’s和它们发生及发生的百分比。包含在模型中的参考数据可查阅表2中的间隔索引。

表M：在ALL类中的三个边界EP’s和在AML类中的三个边界EP’s。

    边界EP’s在ALL中的发生频率(％  在AML中的发生率(％)    {5，7}    27(100％) 0    {1}    27(100％) 0    {3}    26(96.3％) 0    {2}    0 1(100％)    {8}    0 0(90.9％)    {6}    0 0(90.9％)

在生物学上，EP{5，7}作为一个例子表明，如果CST3的表现小于1419.5和Tropomyosin的表现小于83.5那么在ALL中这个样本具有100％的精确度。所以，所有那些基因包括通过本发明衍生的边界EP’s对分类ALL和AML来说都是非常好的诊断指示器。

基于两个边界EP’s{5，7}和{1}发现了一个P-空间。P27-空间由五个坪EP’s：{1}，{1，7}{1，5}{5，7}和{1，5，7}组成。最特殊的坪EP’s是{1，5，7}。注意在ALL类中这个EP仍然有一个完全发生27。

通过将PCL方法应用于白血病数据组(Golub等人，1999)34个隐蔽测试样本和对结肠数据组运用留一交叉效验法(LOOCV)，来检验PCL方法的准确性。当用于白血病训练数据时，CFS方法正确地选择一个基因，Zyxin，被离散化到两个区间内，从而形成了一个简单的规则，可表达成：“如果一个样本中的Zyxin等级小于994，那么这个样本是ALL；否则，样本是AML”。因此，因为只有一个规则，所以使用起来不会含糊不清。对于训练数据这个规则具有100％的正确率。然而，当用于这组隐蔽测试数据时，它会产生一些分类错误。为了提高它的准确性，使用一些其它的基因是合理的。通过基于熵的离散化方法，重新调用白血病的数据中那四个基因也被选择作为最重要的。这四个基因衍变来的边界EP’s使用PCL法，可以得到两个错误分类的测试误差率。这个结果比只使用Zyxin基因所得结果少一个错误。

例4：一个第二基因表现数据组(急性成淋巴细胞白血病的亚型)。

本例使用了大量的来自于“圣犹大书儿童研究医院”的基因表现图谱(文献Yeoh A.E.-J.et al.，″Expression profiling of pediatric acutelymphoblastic leukemia(ALL)blasts at diagnosis accurately predictsboth the risk of relapse and of developing therapy-induced acutemyeloid leukemia(AML)，″Plenary talk at The AmericanSociety ofHematology 43rd Annual Meeting，Orlando，Florida，(December2001)。这一数据包含急性成淋巴细胞白血病(ALL)样本的327个基因表现图谱。这些图谱是由包含12558个基因探针的Affymetrix U95A GenChip杂交而成。杂交数据被清除掉这样(a)所有小于3“P”的调用都被1替代；(b)所有强度值为“A”的调用都用1替代；(c)所有强度值小于100的调用都用1替代；(d)所有强度值超过45,000的调用都用45,000替代；(e)所有最大和最小强度值差别小于100的基因都用1替代。这327个基因表现图谱包括了所有已知的急性成淋巴细胞白血病的亚型，包括T-cell(T-ALL)，E2A-PBX1，TEL-AML1，MLL，BCR-ABL，和超二倍体的(Hyperdip＞50)。

一个树结构的确定系统已经被用于分类这些样本，如图6所示。对于一个给定的样本，无论它是一个T-ALL或者一个其它亚型的样本，都首先按照规则进行分类。如果它被分类为T-ALL，那么这个处理过程就结束了。否则，就移到这个树的第二层看这个样本能否被划分为E2A-PBX1或其它亚型的一种。同理可知一个基于这个树的决策过程在第6层就被结束了，在这里样本或者被划分为某亚型Hyperdip＞50或者被划分为“OTHERS”。

这些样本被划分成一个含有215个样本的“训练组”和一个隐蔽“测试组”。根据图6，将这两组中的每一组进一步划分成每个2组6对子集是必要的，每个子集都用于树的每一层。表N中给出了它们的名字和成分。

                           表N：六对训练数据组和隐蔽测试组

成对的数据组                 成分训练组大小测试组大小T-ALL vs.OTHERS1  OTHERS1＝{E2A-PBXI，TEL-AMLI，BCR-ABL，Hyperdip＞50，MLL，OTHERS} 28 vs 187    15 vs 97E2A-PBXS vsOTHERS2  OTHERS2＝{TEL-AML1，BCR，ABL，Hyperdip＞50，MLL，OTHERS} 18 vs 169    9 vs 88TEL-AML1 vs.OTHERS3  OTHERS3＝{HCR-ABL，Hyperdip＞50，MLL，OTHERS 52 vs 117    27 vs 61BCR-ABL vs.OTHERS4  OTHERS4 ＝{Hyperdip＞50，MLL，OTHERS} 9 vs 108    6 vs 55MLL vs.OTHERS5  OTHERS5＝{Hyperdip＞50，OTHERS} 14 vs 94    6 vs 49Hyperdip＞50 vs.OTHERS  OTHERS＝{Hyperdip47-50，Pseudodip，Hypodip，Normo} 42 vs 52    22 vs 27

正如表第二列所示，在表N中的“OTHERS1”，“OTHERS2”，“OTHERS3”，“OTHERS4”，“OTHERS5”，和“OTHERS”类组成了ALL样本的不止一个亚型。

例4.1：EP的产生

产生形成模型可分为两步。第一步，从训练数组的12,558个基因中选出少量差别最大的基因。第二步，根据所选择的基因产生形成模型。

将基于熵的基因选择方法应用于基因表现图谱。结果证明非常有效，因为12,558个基因中的多个被忽略了。仅仅大约1000个基因被认为在分类中是有用的。10％的选择率提供了一个更容易的平台来衍生重要规则。然而，对于人工检查1000个左右基因仍然令人感到厌烦。因此，χ统计法(χ²)方法(文献)和基于相关性的特征选择(CFS)的方法(文献Liu & Setiono，″Chi2：Feature selection and discretization of numericattributes.″Proceedings of the IEEE 7t International Conference onTools with Artificial Intelligence，338-391，(1995)；Witten，H.，& Frank，E.，Data mining：Practical machine learning tools and techniques withjava implementation，Morgan Kaufmann，San Mateo，CA，(2000))被用于进一步缩小搜寻重要基因的范围。在这个研究中，如果CFS方法返回的基因数量不大于20，那么CFS选择的基因就用来得到我们的形成模型。否则χ²方法就被用于顶部的20个排列的基因。

在本例中，发现了一个特殊类型的EP’s，称为是跳跃的“左边界”EP’s。给定两个数据组D1和D2，这些EP’s要求满足下面的条件：(i)D1(或D2)的频率是非零但另一数据组为零；(ii)没有一个他们正确的子集是子集。我们注意到跳跃的左边界EP’s是在所有EP’s中具有最大频率的EP’s。此外，绝多个跳跃的“左边界”EP’s的超集是EP’s，除了在D1和D2中有零频率。

在选择和离散化最大差别的基因后，BORDER-DIFF和JEP-PRODUCER算法(文献Dong & Li，ACM SIGKDD ItiternationalCovference on Knowledge Discovery and Data Mining，San Diego，43-52(1999)；Li，Mining Emerging Patterns to Construct Accurate andEfficient Classifiers，Ph.D.Thesis，The University of Melbourne，Australia，(2001)；Liet al.，″The Space of Jumping Emerging Patternsand Its Incremental Maintenance Algorithms，″Proceedings of 17′hInternational Conference on Machine Learning，552-558(2000))被用于从所处理的数据组中发现EP’s。当多个处理是边界，这些算法是很有效的。

例4.2：来自EP’s的规则

这部分报告从训练数据中发现的EP’s。这些模型可以被扩展形成规则用于区别ALL的各种子集的基因表现图谱。

T-ALL vs.OTHERS1的规则：

对于第一对数据组，T-ALL vs OTHERS1，CFS方法仅选一个基因38319_at，作为最重要的。离散化方法将这个基因的表示范围分割成两段：(-∞，15975.6)，[15975.6，+∞)。使用EP发现算法，得到两个EP’s：{gene_38319_at@(-∞，15975.6)}和{gene_38319_at@(15975.6，+∞)}。在T-ALL类中以前的有100％频率但是在OTHERS1类中是零频率；在T-ALL类中以后的有零频率但是在OTHERS1类中是100％的频率。因此，我们可以得到以下规则：

如果表达式38319_at小于15975.6，那么

ALL样本必然为T-ALL；

否则

它必然是在OTHERS1中的一个子集。

这个简单的规则在215个ALL样本(28个T-ALL加187个OTHERS1)中毫无例外的起着作用。

E2A-PBX1 vs OTHERS2的规则。

这儿还有一个用于E2A-PBX1 vs OTHERS2的简单规则。用这种方法挑出一个基因，33355_at，并将它离散到两个区间中：(-，10966)，[10966，+∞)。然后发现{gene_33355_at@(-∞，10966)}和{gene_33355_at@(10966，+∞)}在E2A-PBX1 vs OTHERS2中分别是具有100％频率的EP’s。所以，一个用于这些187个ALL样本(18 E2A-PBX1加169个OTHERS2)的规则是：

如果表达式33355_at小于10966，那么

ALL样本必然为E2A-PBX1；

否则

它必然是在OTHERS2中的一个子集。

这规则贯穿于3层到6层。

对于其余的四对数据组，CFS方法返回了超过20个基因。所以，χ²方法就被用于在这每一个四对数据组中选择顶部排列的20个基因。表0，表P，表Q，和表R列出了所选基因的名称，它们的划分，和分别四对数据组的区间的索引。索引将基因的名称和它们的区间匹配和联接起来，利用索引读和写EP’s是更方便的。

                        表O：

通过χ²方法从TEL-AML1 vs OTHERS3中选出顶部20个基因。第二列和第三列列出了通过熵方法和区间的索引产生的区间。

基因名区间区间索引38652_at(-∞，8997.35)，[8997.35，+∞)1，236239_at(-∞，14045.5)，[14040.5，16328.55)，[16328.55，+∞)3，4，541442_at(-∞，15114.1)，[15114.1，26083.95)，[26083.95，+∞)6，7，837780_at(-∞，2396.3)，[2396.3，5140.5)，[5140.5，+∞)9，10，1136985_at(-∞，19499.6)[19499.6，26571.05]，[26571.05，+∞)12，13，14  38578_at  (-∞，7788.95)，[7788.95，+∞)  15，16  38203_at  (-∞，3721.3)，[3721.3，+∞)  17，18  35614_at  (-∞，9930.15)，[9930.15，+∞)  19，20  32224_at  (-∞，5740.45)，[5740.45，+∞)  21，22  32730_at  (-∞，2864.85)，[2864.85，+∞)  23，24  35665_at  (-∞，5699.35)，[5699.35，+∞)  25，26  1077_at  (-∞，22027.55)，[22027.55，+∞)  27，28  36524_at  (-∞，1070.65)，[1070.65，+∞)  29，30  34194_at  (-∞，1375.85)，[1375.85，+∞)  31，32  36937_a_at  (-∞，13617.05)，[13617.05，+∞)  33，34  36008_at  (-∞，11675.35)，[11675.35，+∞)  35，36  1299_at  (-∞，3647.7)，[3647.7，9136.35]，[9136.35，+∞)  37，38，39  41814_at  (-∞，6873.85)，[6873.85，+∞)  40，41  41200_at  (-∞，11030.5)，[11030.5，+∞)  42，43  35238_at  (-∞，4774.85)，[4774.85，7720.4)，[7720.4，+∞)  44，45，46

                           表P

通过χ²方法从数据对BCR-ABL vs OTHERS4中选出的顶部20个基因

基因名间隔间隔索引1637_at(-∞，5242.15)，[5242.15，+∞)1，236650_at(-∞，13402)，[13402，+∞)3，440196_at(-∞，2424.4)，[2424.4，+∞)5，61635_at(-∞，5279.3)，[5279.3，+∞)7，833775_s_at(-∞，1130.75)，[1130.75，+∞)9，101636_g_at(-∞，11112.9)，[11112.9，+∞)11，12 41295_at(-∞，33488.7)，[33488.7，+∞)13，14 37600_at(-∞，24168.95)，[24168.95，+∞)15，16 37012_at(-∞，18127.7)，[18127.7，+∞)17，18 39225_at(-∞，14137.25)，[14137.25，+∞)19，20 1326_at(-∞，3273.55)，[3273.55，+∞)21，22 34362_at(-∞，13254.9)，[13254.9，+∞)23，24 33150_at(-∞，+∞)25 40051_at(-∞，+∞)26 39061_at(-∞，+∞)27 33172_at(-∞，+∞)28 37399_at(-∞，+∞)29 317_at(-∞，+∞)30 40953_at(-∞，2569.55)，[2569.55，+∞)31，32 330_s_at(-∞，6237.5)，[6237.5，+∞)33，34

表Q：通过χ²方法从数据从MLL vs OTHERS中选出20个顶部基因

基因名                             区间  区间索引 34306_at(-∞，12080.7)，[12080.7，+∞)1，2 40797_at(-∞，5331.15)，[5331.15，+∞)3，4 33412_at(-∞，29321.15)，[29321.15，+∞)5，6 39338_at(-∞，5813.1)，[5813.1，+∞)7，8 2062_at(-∞，10476.05)，[10476.05，+∞)9，10 32193_at(-∞，2605.6)，[2605.6，+∞)11，12 40518_at(-∞，23228.2)，[23228.2，+∞)13，14 36777_at(-∞，5873.9)，[5873.9，+∞)15，16 32207_at(-∞，7238.8)，[7238.8，+∞)17，18 33859_at(-∞，23053.2)，[23053.2，24674.9)，[224674.9，+∞)19，20，21 38391_at(-∞，16251.65)，[16251.65，+∞)22，23 40763_at(-∞，3301.3)，[3301.3，+∞)24，25 1126_s_at(-∞，6667.6)，[6667.6，+∞)26，27 34721_at(-∞，8743.05)，[8743.05，+∞)28，29 37809_at(-∞，2075.05)，[2075.05，+∞)30，31 34861_at(-∞，4780)，[4780，5075.05)，[5075.05，+∞)32，33，34 38194_s_at(-∞，859.2)，[859.2，6860.6)，[6860.6，+∞)35，36，37 657_at(-∞，8829.8)，[8829.8，+∞)38，39 36918_at(-∞，5321.15)，[5321.15，+∞)40，41 32215_i_at(-∞，2464.1)，[2464.1，+∞)42，43

  表R：通过χ²方法从数据对Hyoerdip＞50 vs OTHERS中选出顶部的20

                             个基因

基因名区间区间索引36620_at(-∞，16113.1)，[16113.1，+∞]1，237350_at(-∞，10351.95)，[10351.95，+∞]3，4171_at(-∞，6499.25)，[6499.25，+∞]5，637677_at(-∞，41926.9)，[41926.9，+∞]7，841724_at(-∞，20685.45)，[20685.45，+∞]9，1032207_at(-∞，15242.9)，[15242.9，+∞]11，1238738_at(-∞，15517.2)，[15517.2，+∞]13，1440480_s_at(-∞，4591.95)，[4591.95，+∞]15，1638518_at(-∞，13840)，[13840，+∞]17，1841132_r_at(-∞，10490.95)，[10490.95，+∞]19，2031492_at(-∞，17667.05)，[17667.05，+∞]21，2238317_at(-∞，4982.05)，[4982.05，+∞]23，2440998_at(-∞，11962.6)，[11962.6，+∞]25，2635688_g_at(-∞，3340.55)，[3340.55，+∞]27，2840903_at(-∞，3660.4)，[3660.4，+∞]29，3036489_at(-∞，6841.95)，[6841.95，+∞]31，321520_s_at(-∞，10334.05)，[10334.05，+∞]33，3435939_s_at(-∞，9821.95)，[9821.95，+∞]35，3638604_at(-∞，13569.7)，[13569.7，+∞]37，3831863_at(-∞，8057.7)，[8057.7，+∞]39，40

在对所选定基因进行离散化之后，每一个四对的数据组都可以发掘两组EP’s。表S列出了发现的形成模型的数量。表S的第四列显示了所发现的EP’s数量是相当大的。我们用另外四张表：表T，表U，表V和表W按照他们的频率列出了顶部的10个EP’s。这些顶部的10个EP’s的频率能够达到98.94％，多个的频率约为80％。即使一个顶部排列的EP不能覆盖整个样本类，它还是支配着整个类。在相似类中它们的不存在表明了顶部排列的形成模型能够俘获一个类的本性。

       表S：四对数据组中得到的左边界EP’s的总数

数据组对(D1 VS D2)D1中的EP’s数值D2中的EP’s数值合计TEL-AML1 vs OTHERS3 2178 943 3121BCR-ABL vs OTHERS4 101 230 313MLL vs OTHERS5 155 597 752Hyoerdip＞50 vs OTHERS 2213 2158 4371

                  表T：在TEL-AML和OTHERS3类中最大频率的EP’s

 EP’sTEL-AML1中频率％    OTHERS3中频率％EP’s  TEL-AML1中频率％  OTHERS3中频率％  {2，33}    92.31    0.00  {1，23，40}    0.00    88.89{16，22，33}90.380.00{17，29}0.0088.89  {20，22，33}    88.46    0.00  {1，17，40}    0.00    88.03  {5，33}    86.54    0.00  {1，9，40}    0.00    88.03  {22，28，33}    84.62    0.00  {15，17}    0.00    88.03  {16，33，43}    82.69    0.00  {1，23，29}    0.00    87.18  {22，30，33}    82.69    0.00  {17，25，40}    0.00    87.18  {2，36}    82.69    0.00  {7，23，40}    0.00    87.18  {20，43}    82.69    0.00  {9，17，40}    0.00    87.18  {22，36}    82.69    0.00  {1，9，29}    0.00    87.18

                 表U：在BCR-ABL和OTHERS4类中最大频率的EP’s

   EP’sBCR-ABL中频率％  OTHERS4中频率％EP’s  BCR-ABL中频率％  OTHERS4中频率％  {22，32，34}    77.78    0.00  {3，5，9}    0.00    95.37  {8，12}    77.78    0.00  {3，9，19}    0.00    95.37  {4，8，34}    66.67    0.00  {3，15}    0.00    95.37  {4，8，22}    66.67    0.00  {3，13}    0.00    95.37  {6，34}    66.67    0.00  {3，5，23}    0.00    93.52  {8，24}    66.67    0.00  {11，17，19}    0.00    93.52  {24，32}    66.67    0.00  {3，19，23}    0.00    93.52  {4，12}    66.67    0.00  {7，19}    0.00    93.52  {8，32}    66.67    0.00  {11，15}    0.00    93.52  {12，34}    66.67    0.00  {5，11}    0.00    93.52

                   表V：在MLL和OTHERS5类中最大频率的EP’s

 EP’s    MLL中频率％    OTHERS5中频率％   EP’sMLL中频率％OTHERS5中频率％{2，14}    85.71    0.00  {5，24}    0.00    98.94{12，14}    71.43    0.00  {5，22，38}    0.00    96.81{2，39}    64.29    0.00  {24，28，42}    0.00    96.81{14，26}    64.29    0.00  {5，28，30}    0.00    96.81{16，17}    64.29    0.00  {5，7，30}    0.00    96.81{4，36}    64.29    0.00  {24，26，42}    0.00    96.81{4，8}    64.29    0.00  {7，15，24}    0.00    96.81{14，36}    64.29    0.00  {15，24，26}    0.00    96.81  {8，36}    57.14    0.00  {15，24，28}  0.00    96.81  {2，32}    57.14    0.00  {7，24，42}  0.00    96.81

                表W：在Hyoerdip＞50和OTHERS类中最大频率的EP’s

 EP’sHyoerdip＞50中频率％  OTHERS中频率％EP’sHyoerdip＞50中频率％OTHERS中频率％{14，24}  78.57    0.00  {15，17，25}    0.00    78.85{2，12，14}  71.43    0.00  {7，15}    0.00    76.92{12，14，38}  71.43    0.00  {5，15}    0.00    76.92{4，14}  71.43    0.00  {1，15}    0.00    76.92{12，14，34}  69.05    0.00  {15，33}    0.00    76.92{12，14，16}  69.05    0.00  {3，15}    0.00    76.92{2，8，14}  69.05    0.00  {15，17，31}    0.00    75.00{14，32}  69.05    0.00  {15，17，19}    0.00    75.00{10，21，24}  69.05    0.00  {15，17，27}    0.00    75.00{12，21，24}  69.05    0.00  {15，39}    0.00    75.00

考虑TEL-AML1类的第一个EP，i.e.，{2，33}，作为如何将EP’s翻译成规则的说明。按照表O的索引，在这个EP中的数字2匹配基因38652_at中右边区间，并且代表了条件：38652_at表现大于或等于8,997.35。同样地，数字33匹配基因36937_s_at左边区间，代表了条件：36937_s_at表示小于13,617.05。因此模型{2，33}意味着TEL-AML1的92.31％(52个样本中的48个)满足以上两个条件，但是在OTHERS3中没有一个样本满足以上两个条件。因此，在这个情况下，整个类都可以被一些顶部-10个EP’s完全包括。这些EP’s就是我们要得到的规则。

一个用来测试规则可靠性的重要方法论是把他们应用于前面没有看到的样本中(即，隐蔽测试模型)。在这个例子中，先前保存了112个隐蔽测试样本。测试结果的总结如下：

在1层中，所有15个T-ALL样本被正确预测为T-ALL；所有97个OTHERS1样本被正确预测为OTHERS1。

在2层中，所有9个E2A-PBX1样本被正确预测为E2A-PBX1；所有88个OTHERS2样本被正确预测为OTHERS2。

根据使用EP’s的数量，在3到6层中仅有4-7个样本被错误分类。通过使用一个较大量的EP’s值，误差率可减小。

在1层和2层的每个中发现了一个规则，所以在运用这两个规则中没有模糊不清的。然而，在这个树剩余的层中发现了大量的EP’s。因此，因为一个测试样本可能不仅包含来自它自己类的EP’s，还有来自它相似类的EP’s，为了作出可靠的预测，使用多个“基”类的高频率EP’s来避免相似类的EP’s的干扰信号是合理的。这样，PCL方法就被用于3到6层。

表X显示了测试的精确度，当变化k时，使用规则的数量。从这些结果中，可以看出多个高频率EP’s(或多个强规则)能够提供一个简洁和有效的预测可能性。当k为20，25，30时，总共出现了4个错误分类。这四个测试样本的标识符(id)是：94-0359-U95A，89-0142-U95A，91-0697-U95A，和96-0379-U95A，使用符号来自Yeoh st al.，The AmericanSociety of Hematology 43rd Annual Meeting，2001.

表X：用于计算的EP’s数量对预测精度可能有些小的影响。误差率，x∶y，意味着在右边类中x个样本被错误分类，和在左边类中y个样本被错误分类。

测试数据                       当k变动时的错误率    5    10    15    20    25    30 TEL-AML1 vs OTHERS3    2∶0    2∶0    2∶0    1∶0    1∶0    1∶0 BCR-ABL vs OTHERS4    3∶0    2∶0    2∶0    2∶0    2∶0    2∶0 MLL vs OTHERS5    1∶0    0∶0    0∶0    0∶0    0∶0    0∶0 Hyoerdip＞50 vs OTHERS    0∶1    0∶1    0∶1    0∶1    0∶1    0∶1

多类预测的概括

一个BCR-ABL测试样本几乎包含了所有顶部的20个BCR-ABL鉴别器。接着，将一个得分19.6分配给它。几个顶端的20个“OTHERS”“鉴别器”，和其它一些超过20个顶端的条目也包含在这个测试样本中。接着，另外的得分6.97也被分配。这个测试样本不包含任何E2A-PBX1，Hyperdip＞50或者T-ALL的鉴别器。那么表Y中得分显示如下：

                                                              表Y

子类BCR-ABL E2A-PBX1 Hyperdip＞50 T-ALL MLL TEL-AML1 OTHERS得分19.63 0.00 0.00 0.00 0.71 2.96 6.97

因此，这个BCR-ABL样本以非常高的可信度被预测为BCR-ABL。通过这种方法，当k在15到35之间变动时总共112个测试样本中只有6到8个被错误分类。然而C4.5，SVM，NB，和3-NN分别有27，26，29，11个错误。

分类的改进：

在1层和2层中，只有一个基因用于分类和预测。为了克服可能发生的错误如在记录数据时产生的人为错误，或者DNA片段的机器错误——很少发生但仍可能存在，多于一个基因可被用于加强这个系统。

当使用离散化方法分割时，先前选定的一个1层中的基因38319_at有一个为0的熵。证明没有一个其它的基因有为0的熵。那么顶部的20个基因用x2方法排列的基因，被选择用于分类T-ALL和OTHERS1测试样本。这样，分别在T-ALL类和OTHERS1类中发现了96个EP’s和146个EP’s。使用这个预测方法，当使用单个基因时同样的完美精确度100％在隐蔽测试样本中取得。

当用离散化方法分割时，在2层共有五个基因具有零熵。这五个基因的名字是：430_at，1287_at，33355_at，41146_at，和32063_at。注意3355_at是我们先前选择的基因。所有五个基因被下面切割点分别分割成2区间：30，246.05，34，313.9，10，966，25，842.15和4068.7。当熵为零时，在E2A-PBX1类和OTHERS2类中100％频率会出现五个EP’s。用PCL预测方法，所有测试样本(在2层)都被无差错的正确分类，再一次获得了100％的准确性。

和其它方法的比较：

表格Z中将预测精度和用k-NN，C4.5，NB，和SVM方法使用相同选定的基因和相同的训练和测试样本所得到的精度进行比较。PCL方法将C4.5的14个错误分类的概率降低了71％，NB的8个错误分类的概率降低了50％，k-NN7个错误分类的概率降低了43％和SVM’s 6.1个错误分类的概率降低了33％。从医学治疗角度来看，误差率的降低将大大造福于病人。

                    Z表：

我们的方法k-NN，C4.5，NB，和SVM在测试数据中的误差率比较

测试数据    不同模型的误差率  k-NN C4.5 SVM NB本方法(k＝20，25，30)T-ALL vs OTHERS1  0∶0 0∶1 0∶0 0∶0    0∶0E2A-PBX1 vs OTHERS2  0∶0 0∶0 0∶0 0∶0    0∶0TEL-AML1 vs OTHERS3  0∶2 1∶1 0∶1 0∶1    1∶0BCL-ABL vs OTHERS4  4∶0 2∶0 3∶0 1∶4    2∶0MLL vs OTHERS5  0∶0 0∶1 0∶0 0∶0    0∶0Hyoerdip＞50 vs OTHERS  0∶1 2∶6 0∶2 0∶2    0∶1总错误率  7 13 6 8    4

正如早些讨论所得，PCL方法明显优于SVM，NB和k-NN，是一个可衍生有意义的和可靠的模型和规则。这些形成模型能够提供基因的相关型和相互作用的新颖见识，并能帮助对比仅分类更详细的理解。虽然C4.5也能产生相似的规则，但是有时它的性能较差(如在第六层中)，性能不是非常可靠。

评价顶部20个基因的使用。

大量的努力和计算用来确定最重要的以使用基因。这些实验结果表明选择的最顶部基因，或者顶部的20个基因在PCL预测方法中是非常有用的。不过，使用其它方法判断所选基因性质是可能的。在这种情况下，如果这20个基因或1个基因是随机从实验数据中抽取的，就能研究出精确的差异。

过程如下：(a)第一和第二层随机选择一个基因，并在其余四层的每层中随机选取20个基因；(b)运行SVN和k-NN，获取每层测试样本的精确度；(c)重复(a)和(b)步骤一百次，求它们的平均值和其它统计数据。

表AA列出了经过一百次SVN和k-NN实验得到的最小、最大和平均的精度。作为对比，这里也给出了一个“虚设的”分类器的精确度列表。使用虚设的分类器，如果给出的两个数据类不均衡，那么所有测试样本都被预测成一个较大的类。接下来的两个事实就变得明显了。首先，所有平均精度都低于或者只是稍高于它们的虚设精度。第二，所有的平均精度都大大低于(至少9％)基于选定基因的精度。差别能达到30％。因此，基因选择方法能使这个预测方法更为有效的工作。在可靠和准确的预测模型建立之前，参数选择方法是重要的第一步。

                               表AA：机于随机基因选择的性能

虚拟统计值    一层  二层  三层  四层  五层  六层86.6  90.7  69.3  90.2  89.1  55.1                                          SVM测试精度(％)    最小值82.1  90.7  40.9    72.6  76.4  49.0    最大值90.2  92.8  93.2    91.94  98.2  93.9    平均值86.6  90.8  73.35    84.32  89.0  67.8                                          k-NN测试精度(％)    最小值74.1  78.4  46.6    88.7  69.1  38.8    最大值93.8  92.8  89.8    90.3  96.36  81.6    平均值84.7  89.4  66.5    90.3  84.2  60.2

如果原始数据的12,558个基因的应用于这个预测方法，那么计算精确度是可能的。实验结果表明基因选择方法也会造成大的差别。对于原始数据，SVM，K-NN，NB，和C4.5会分别对隐蔽测试样本有23，33，63和26个错误分类。如果减少分别应用于SVM，K-NN，NB，和C4.5的数据，那么结果比6，7，8和13的误差率更差。由此，对基因选择法于建立可靠的预测模型是重要的。

最后，基于形成模型的方法有准确度高和容易解释两方面的优点，尤其是当应用于分类基因表现图谱时。当在对大量收集的ALL样本进行测试时，此方法对所有亚型进行了分类并且获得了远低于SVM，K-NN，NB，和C4.5方法的误差率。通过保留大约2/3的数据用于训练和1/3的数据用于隐蔽测试来进行测试。实际上，通过对训练数据进行10折交叉效验测试也可以在误差率中获得近似的的提升。显示在表BB中：

表BB：对训练组215 ALL样本进行10折交叉确认的结果

  训练数据                             10折交叉确认的错误率    k-NN    C4.5 SVM  NB本方法(k＝20，25，30)T-ALL vs OTHERS1    0∶0    0∶1 0∶0  0∶0  0∶0，0∶0，0∶0E2A-PBX1 vs OTHERS2    0∶0    0∶1 0∶0  0∶0  0∶0，0∶0，0∶0TEL-AML1 vs OTHERS3    1∶4    3∶5 0∶4  0∶7  1∶3，0∶3，0∶3BCL-ABL vs OTHERS4    6∶0    5∶4 2∶1  0∶4  1∶0，1∶0，1∶0MLL vs OTHERS5    2∶0    3∶10 0∶0  0∶3  4∶0，2∶0，2∶0Hyoerdip＞50 vs OTHERS    7∶5    13∶8 6∶4  6∶7  3∶4，3∶4，3∶4总错误率    25    53 17  27  16，13，13

在没有违反此发明的精神和范围的情况下，对于一个在有熟练技能的人来说可以通过替换和修改改变这里揭示的发明。例如，使用各种各样的参数，数据组，计算机可读介质和计算设备都包括在当前发明范围之内。从而，这些附加的体现就被包括在本发明和下面权利要求中。