用于提高分类精度的交互式可视数据挖掘

摘要

本公开涉及用于提高分类精度的交互式可视数据挖掘。例如，一种方法包括以下步骤。从一个高维数据集合生成至少两个决策树数据结构。生成包括该至少两个决策树数据结构的复合数据结构。基于该至少两个决策树数据结构之间计算的相关性来生成该复合数据结构。将该复合数据结构可视化在显示器上。经由与该显示器上的该复合数据结构的该可视化的交互，允许该复合数据结构的修改。

说明书

技术领域

本发明涉及数据分类，并且更具体而言，涉及用于提高数据分类精度的可视数据挖掘技术。

背景技术

在从数据集合特别是本质上高维并且稀疏的数据集合中提取信息和知识(即，数据挖掘)的过程中，数据分类是重要的。这种高维数据集合目前被称为“大数据”。如已知的，被描述为大数据的数据集合的尺寸太大，以至于完全超出常用软件工具管理/处理该数据的能力，至少无法在适当的时间内完成。例如，与大数据相关联的高维度通常导致用于分类新数据记录的现有数据分类器的不良性能。

通常，数据分类器通过如下步骤被学习：数据预处理；模型训练；以及模型评估。为了更好的精度，在模型评估步骤之后，可以回顾数据预处理和模型训练步骤，调谐参数，并且随后可以重新运行整个分类器学习过程。但是，该过程不能很好地适用于大数据分析。该过程本身的一次重复可能是成本不允许的，更不用说多次重复。这样，需要一种改善用于分类高维数据集合(包括但不限于被描述为大数据的数据集合)的数据分类器的性能的技术。

发明内容

本发明的实施方式提供了用于提高数据分类精度的可视数据挖掘技术。

在一个实施方式中，一种方法包括以下步骤。从一个高维数据集合生成至少两个决策树数据结构。生成包括至少两个决策树数据结构的复合数据结构。基于至少两个决策树数据结构之间计算的相关性来生成复合数据结构。将复合数据结构可视化在显示器上。经由与显示器上的复合数据结构的可视化交互，允许对复合数据结构的修改。方法还可以包括对于复合数据结构中的每个决策树数据结构计算分类精度(例如强度)。

在一个示例中，复合数据结构是随机森林数据结构。经由与显示器上的复合数据结构的可视化的交互来允许复合数据结构的修改可以进一步包括允许以下至少一个：至少一个决策树数据结构从复合数据结构的移除；以及至少一个决策树数据结构到复合数据结构的添加。方法可以进一步包括使用复合数据结构分类新数据记录。

在另一个实施方式中，提供了一种包括处理器可读存储介质的计算机程序产品，其中将一个或多个软件程序的可执行代码编码在处理器可读存储介质中。当一个或多个软件程序被处理设备的处理器执行时实现上述方法的步骤。

在另一个实施方式中，一种装置包括存储器以及可操作地耦合到存储器并且被配置为执行上述方法的步骤的处理器。

本文所述的示例性实施方式有利地提供复合数据结构如用于高维数据集合(如可以被描述为大数据的数据集合)的随机森林集成的可视化，从而用户可以与随机森林可视化交互以便有效地改善分类精度。

通过附图和以下详细描述，本发明的这些以及其他特征和优点将变得更加显而易见。

附图说明

图1示出了根据本发明的一个实施方式基于云的数据存储系统环境。

图2A示出了根据本发明的一个实施方式云架构和交互式可视数据挖掘模块。

图2B示出了图2A的云架构的更详细的视图。

图3示出了根据本发明的一个实施方式的处理平台，其中在该处理平台上实现图2A的云架构和交互式可视数据挖掘模块。

图4示出了根据本发明的一个实施方式用于从训练数据集合生成决策树模型的过程。

图5示出了根据本发明的一个实施方式的决策树和随机森林的可视化。

图6示出了根据本发明的一个实施方式用于生成并且与随机森林可视化交互的方法。

具体实施方式

将参考示例性计算系统和数据存储系统以及相关的服务器、计算机、存储单元和设备以及其他处理设备来描述本发明的实施方式。但是要认识到，本发明的实施方式不限于与所示具体示范性系统和设备配置一起使用。此外，如这里所使用的短语“计算系统”和“数据存储系统”适用于被广义地解释为包括例如专用或公共云计算或存储系统以及包括分布式虚拟架构的其他类型的系统。但是，给定的实施方式可以更普遍地包括一个或多个处理设备的任意配置。

短语“数据结构”涉及用于在计算设备存储、组织并且/或者处理数据的机制和/或方法，因而可以更有效地访问并且/或者分析数据。例如，在这里所述的示范性实施方式中，使用诸如“决策树”和“随机森林”的数据结构。决策树是一种决策支持型数据结构，其使用树型图或决策的模型和它们的可能的结果。随机森林是一种集成分类器型的数据结构，其包括多个决策树并且通常输出例如该随机森林的单独的决策树所输出的类别构成的类别。Leo Breiman在“Random Forests”Machine Learning 45(1)：5-32，2001中公开了用于引起随机森林的算法。虽然本发明的示范性实施方式使用决策树和随机森林，但是要明白本文所述的原理可以适用于与所述的那些数据结构、机制、方法和数据处理环境不同的数据结构、机制、方法和数据处理环境。

在描述用于生成图4-图6的环境中的随机森林数据结构和决策树数据结构的交互式可视化的示范性实施方式之前，将在图1-3的环境中详细描述可以在其中实现该技术的计算环境的示范性实施方式。

图1示出了根据本发明的一个实施方式的基于云的数据存储系统环境100。如图所示，客户端设备102-1、102-2、......、102-M被耦合到通信网络(例如因特网、内联网、无线网络、有线网络或它们的组合)104，其中客户端设备可以经由该通信网络访问来自一个或多个服务提供商的云服务。在该云服务的一个示例中，由数据存储系统106经由通信网络104向客户端设备102-1、102-2、......、102-M之后的一个或多个客户端设备提供大数据存储服务。

如上所述，“大数据”通常是指高维数据集合，其尺寸太大以至于完全超出常用软件工具管理/处理该数据的能力，至少无法在适当的时间内完成。仅通过示例的方式，用于处理该“大数据”的系统架构可以包括被称为EMC Greenplum^TMHD数据计算器(马塞诸塞州霍普金顿EMC公司)，其始于Apache Hadoop^TM(Apache软件公司)开放式源代码软件来提供“大数据”分析和服务。图1中的系统106表示该大数据系统架构。因此，客户端设备102-1、102-2、......、102-M被配置为使用一个或多个大数据存储服务来访问数据存储系统106。数据存储环境100是基于云的，在以下图2A和2B的环境中将给出对它的解释。

因此，根据本发明的实施方式，客户端设备102-1、102-2、......、102-M能够在存储在数据存储系统106的高维数据上执行数据挖掘和数据分类操作。为此目的，环境100支持跟将本文所述的实施方式的随机森林可视化技术的实现。即该客户端设备中的一个客户端设备的用户能够在该客户端设备的显示器上交互式地可视化从存储在数据存储系统106上的数据生成的随机森林数据结构(其包括多个决策树数据结构)。下文将更详细地描述该随机森林的生成以及与随机森林的交互。

图2A示出了根据本发明的一个示范性实施方式配置的系统200。如图所示，系统200包括云架构210和交互式可视数据挖掘模块220。如下文更详细地解释的，交互式可视数据挖掘模块220允许用户可视化用于表示高维数据集合的随机森林数据结构，因而用户可以与该随机森林数据结构交互(例如，从/向随机森林数据结构移除/添加决策树以改善分类精度)。在该图中将云架构210示范性地描述为包括执行环境，该执行环境具有执行组件，包括一个或多个中央处理器(CPU)212、一个或多个虚拟机(VM)214以及存储设备216(基于该存储设备实现逻辑单元(LU))，它们执行一个或多个过程218，该过程218在一个或多个过程输入数据集合上进行操作，该一个或多个过程输入数据集合生成一个或多个过程输出数据集合。要明白，在云架构210实现该交互式可视数据挖掘模块220将要处理的高维数据集合(大数据)(因此，云架构210也可以被称为云服务架构210)。

将会理解，系统200的一部分或全部可以实现在图1的基于云的数据存储系统环境100中。例如，可以将交互式可视数据挖掘模块220部分或整体实现在图1的客户端设备102-1、102-2、......、102-M中的至少一个客户端设备中。类似地，可以将交互式可视数据挖掘模块220部分或整体实现在图1的数据存储系统106中。此外，可以将交互式可视数据挖掘模块220部分或整体实现在图1的云服务网络104中的一个或多个其他计算设备或系统(未示出)中。

虽然在图2A中将系统元件210和220显示为独立的元件，但是可以将这些元件以及它们的部件至少部分地实现在公共处理平台上。在其他实施方式中，可以将系统元件210和220中的一个或多个中的每一个实现在独立的处理平台上如下文结合图3所述的处理平台。例如，可以将云架构210实现在第一处理平台的第一处理设备上并且可以将交互式可视数据挖掘模块220实现在第二处理平台的第二处理设备上。还要理解，系统200的给定实施方式可以包括系统元件210和220的多个示例，但是为了说明的清楚和简单起见，在系统图中仅显示了该元件的单个示例。

如图2B中所示，(与图2A中的210相对应的)云架构230包括使用管理器234实现的虚拟机(VM)232-1、232-2、......、232-N。管理器234是这里更通常地被称为“可视化架构”的东西的示例。管理器234运行在物理架构236(例如可以包括图2A中的CPU212和/或存储设备216)。云架构230还包括在管理器234的控制之下(利用相关LU)运行在各自的虚拟机(VM)232-1、232-2、......、232-N上的应用238-1、238-2、......、238-N的集合。

虽然在图2B的示例中仅显示了单个管理器234但是根据本发明的实施方式所配置的云架构的给定实施方式可以包括多个管理器，其中每个管理器运行在它自己的物理架构上。可以对该物理架构的部件进行可视化。

如已知的，虚拟机是可以被安装在一个或多个物理处理元件(例如服务器、计算机、处理设备)上的逻辑处理元件。即“虚拟机”通常涉及以与物理机类似的方式执行程序的软件机器(即计算机)实现。因此不同的虚拟机可以在同一物理计算机上运行不同的操作系统和多个应用。由管理器234实现可视化，其中如图2B中所示的管理器234被直接插入到计算机硬件的顶部以便动态地并且透明地分配物理计算机(物理架构236)的硬件资源。管理器234承担多个操作系统在单个物理计算机上同时允许并且彼此共享硬件资源的能力。

可用于实现本发明的一个或多个实施方式中的云架构230(210)的部件的可购得的管理器平台的一个示例是vSphere^TM，其可以具有相关的虚拟架构管理系统如vCenter^TM。基本物理架构236可以包括一个或多个分布式处理平台，其包括存储产品，例如从马塞诸塞州霍普金顿的EMC公司可购得的VNX和对称VMAX。可以利用各种其他存储产品来实现云架构230(210)的至少一部分。

图3所示的处理平台300是可用于实现图2A的云架构210和/或交互式可视数据挖掘模块220(以及图1的环境100的组件)的处理平台的一个示例。该实施方式中的处理平台300包括系统200(和/或环境100)的至少一部分并且包括在网络304上彼此通信的多个计算设备，被标记为302-1、302-2、302-3、......、302-P。系统200(100)的一个或多个元件中的每一个因此可以运行在可以被视为在这里可以更普遍地被称为“计算设备”(或处理设备)的示例的服务器、计算机或其他处理平台元件上。如图3中所示，该设备通常包括至少一个处理器和相关存储设备，并且实现用于控制系统200(100)的特定特征的一个或多个功能模块。同样地，在给定实施方式中可以由单个处理设备实现多个元件或模块。

处理平台300中的计算设备302-1包括处理器312、存储器314、输入/输出设备316和网络接口318。处理器312可以包括微处理器、微控制器、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其他类型的处理电路以及该电路元件的一部分或组合。存储器314可以被视为在这里被更普遍地称为“计算机程序产品”的东西的示例。计算机程序产品包括处理器可读的存储介质，其具有编码在其中的一个或多个软件程序的可执行代码。该存储器可以包括电子存储器例如随机访问存储器(RAM)、只读存储器(ROM)或其他类型存储器的任意组合。当计算机程序代码被诸如计算设备302-1的处理设备执行时导致该设备执行与系统200(100)的一个或多个元件相关联的功能。给定本文提供的教导，本领域的熟练技术人员将能够容易实现该软件。用于实现本发明的实施方式的计算机程序产品的其他示例可以包括例如光盘或磁盘。

计算设备302-1还包括输入/输出(I/O)设备316，例如用于向处理器312和/或存储器314输入数据的一个或多个设备或机制(例如键盘或鼠标)以及用于提供与处理器312和/或存储器314相关联的结果的一个或多个设备或机制(例如显示器或打印机)。

在计算设备302-1中还包括网络接口电路318，其用于将该计算设备与网络304或其他系统组件接口。该电路可以包括本领域公知的类型的常规的收发器。

假设处理平台300的其他计算设备302被以与对于图中的计算设备302-1类似的方式进行配置。

图3中所示的处理平台300可以包括附加的已知部件，例如但不限于，批处理系统、并行处理系统、物理机器、虚拟机、虚拟开关、存储容量、逻辑单元等等。同样地，仅通过示例的方式给出该图中所示的具体处理平台，并且系统300可以包括附加的或可替换的处理平台以及大量不同的处理平台的任意组合。

在系统300中还可能存在服务器、计算机、存储设备、计算设备或其他组件的多种其他配置。该组件可以在任意类型的网络，例如广域网(WAN)、局域网(LAN)、卫星网络、电话或电缆网络或这些以及其他类型的网络的各种不服或组合上与系统300的其他元件通信。

现在将参考图4到图6来描述交互式可视数据挖掘模块220的示范性的细节。

本文所述的示范性的实施方式是基于随机森林分类模块的。在下文的详细描述中，我们首先引入随机森林的概念，然后我们描述如何可视化随机森林。最后，我们提出关于随机森林可视化的各种各样交互式操作。

使用随机森林作为分类模型

如前所述，决策树是用于分类问题的树形结构模型。作为示例，图4示出了包括10个记录的训练数据交换(表402)，其中每个记录具有3个属性，即“退款”、“婚姻状况”和“可征税收入”。表402中的最后一列是用于指示在每行中的纳税人情况(由纳税人ID或“Tid”所识别)是否是欺诈情况的类别标记。假设由过程404生成决策树406。在诸如406的决策树中，每个内部节点测试被称为分裂属性的属性并且每个分支对应于一个属性值。每个树叶节点向记录分配一个分类。从树根到树叶的路径是属性测试的连结。决策树406概述以下4个规则：

a)(退款＝是)＝＞(欺诈＝否)

b)(退款＝否)AND(婚姻状况＝单身)AND(可征税收入＜80k)＝＞(欺诈＝否)

c)(退款＝否)AND(婚姻状况＝单身)AND(可征税收入＞80k)＝＞(欺诈＝是)

d)(退款＝否)AND(婚姻状况＝已婚)＝＞(欺诈＝否)

决策树是一种分类模型，其在某种程度上预测用于测试记录的类别标记：决策树(记录)→类别标记。

如果预测结果与实际分类相同，则预测结果为真。给定一个测试数据集合，决策树的精度是总体中的为真结果的比例。但是，决策树是性能不佳的分类器。因此，我们将其称为弱分类器或基本分类器。根据集成学习理论，提供开发决策树的集成并且使决策树票选最受欢迎的类别，可以显著改善性能。决策树的该集成(集合)被称为随机森林。假设包括100的决策树{DT1，DT2，...DT100}的随机森林RF即RF＝{DT1，DT2，...DT100}。然后对于给定记录r，随机森林分类器使得DT票选大部分结果，即：RF(r)＝主要{DT1(r)，DT2(r)，...DT100(r)}。

随机森林可视化

现在参考图5和图6，其中根据一个示范性的实施方式，在图5中示出了决策树和随机森林的示例并且在图6中示出了用于生成并且与随机森林可视化交换的方法。

如(图6的)方法600的步骤602中所示，第一步骤是对随机森林集成(集合或数据结构)进行可视化，以生成决策树并且随后使之可视化。为此，确定决策树的什么特性对用户而言是重要的并且如何表示该特性。在图5的实施方式中，使用三维树(即实际树的计算机生成的视图)来表示决策树数据结构，并且：

(i)使用树枝来表示分裂的属性；

(ii)使用不同树叶形状(例如圆形、矩形等等)来指示不同的类别标记；

(iii)使用树干半径来指示与该决策树相关的记录的数量(并且分支厚度表示与该决策树的给定分支相关联的记录的数量)；并且

(iv)使用树干的高度来指示分类精度即决策树的强度。从袋外(out-of-bag)数据或测试数据集合计算精度。如随机森林理论中已知的，当通过重置采样来描绘当前决策树时，大约三分之一的情况未被采样所考虑。随着决策树被添加到随机森林，袋外数据来获得分类误差的运行无偏估计。在图6的步骤604中表示该分类精度/强度计算。

在一个示范性实施方式中，在图5的视图502中显示了如此生成并且可视化的决策树。

为了可视化随机森林作为平面中的随机森林，根据图6执行以下步骤。

对于随机森林中的任意决策树配对DTi和DTj，步骤606计算它们的相关性Corr(DTi，DTj)。该相关性是两个树的相似性度量，可以从袋外采样的分类结果计算出。

然后，步骤608将每个决策树配对DTi和DTj之间的距离计算为其相关性的倒数，即Dist(DTi，DTj)＝1/Corr(DTi，DTj)。

给定树的配对距离，步骤610继而计算用每个树的二维(坐标)轴(x，y)。这基本上是一个低维空间投影的问题，并且在一个实施方式中对该问题采用度量多维缩放(MDS)方法。

基于这些计算，在步骤612中在用户的计算机屏幕上绘制(即显示)随机森林作为一个或多个可视化。

在图5中，示出了全景视图504中以及近景视图506中随机森林的示例。

该随机森林用于对未来记录进行分类。在一个实施方式中，我们演示随机森林如何完成分类。假设给予系统(例如图2中的模块220)记录r。决策树输出用于该记录的分类结果DT(r)。将该新记录可能的每个类别标记与不同的阴影或暗影模式相关联。因此，作为新记录的分类结果，树在森林中被绘制具有对应的阴影/暗影形式的树。在图5的视图506中显示了结果的随机森林。备选地，除了视图506中的阴影/暗影形式之外，可以对于每个类别标记使用唯一的颜色。

与随机森林的交互

假设已将系统可视化为随机森林。本发明的示范性实施方式为提供操作以便用户如图6中的步骤614所示与随机森林(RF)交互。

(i)分类：允许用户输入记录。RF中的每个树通过显示对应的阴影/暗影形式，输出分类结果。还报告主要形式(类别标记)。

(ii)砍伐：用户可以选择RF中的一些树，并且随后砍伐该树。砍伐表示从RF移除所选择的树。

(iii)生长：用户可以决定要生长的新树的数量。生长表示可以向RF添加一个或多个新树。

在由于砍伐或生长操作而修改随机森林之后，系统(图2中的模块220)迅速地评估新森林，因而用户知道该操作的效果。在砍伐之后，剩余的树的位置保持不变，而在生长之后，需要计算新添加的树的位置。在更严格的设置中，在任意砍伐和生长操作只要重新布局全部树。

将会理解，随机森林的分类精度取决于个体树的强度以及树之间的相关性。为了实现高精度，树的强度应该高(不低)并且树应该不紧密相关。因此，我们提出用于用户交互的示范性方针：

(i)可以砍伐森林中的拥挤区域中的一些树，以降低总体相关性。

(ii)一些小树可因为其低强度而被砍伐。

(iii)假设存在一些测试记录。然后，可以使用分类功能来找弱的树。因此，我提出使得系统因而输入测试记录并且检查分类结果。如果一些弱小的树非常频繁地错误分类记录，或者如果一些弱小的树做出一些非常幼稚的错误分类，则用户可能决定砍伐一些弱小的树。

(iv)当随机森林中的树的数量由于砍伐操作而小于预定义数量比如说100时，用户可决定执行生长操作以向随机森林添加一些树。

应该再次强调，仅仅为了说明的目的提供本发明的上述实施方式。在所示的具体配置中可以做出许多变形。例如，虽然在具体系统和设备配置的环境中描述该技术，但是该技术可以应用于各种各样其他类型的信息处理系统、处理设备和分布式虚拟架构配置。另外，以上在描述示范性实施方式的过程中做出的任意简化假设模式应该被视为示例性的而是本发明的要求或限制。本领域的熟练技术人员将容易理解落入所附权利要求的范围中的大量其他可替换的实施方式。