第七章-数据挖掘及其安全问题剖析课件

第第七七章章数据挖掘及其安全问题数据挖掘及其安全问题1本本 章章 概概 要要 7 7.1.1 数据挖掘技术数据挖掘技术7 7.2.2 数据挖掘与国家安全数据挖掘与国家安全7 7.3.3 数据挖掘与数字安全数据挖掘与数字安全7 7.4.4 敏感数据的有限泄漏敏感数据的有限泄漏7 7.5.5 关联规则的隐藏关联规则的隐藏2 7.1数据挖掘技术数据挖掘技术7.1.1数据挖掘技术的产生数据挖掘技术的产生2020世纪世纪8080年代以来，数据库系统在各行各业得年代以来，数据库系统在各行各业得到广泛应用，全球的信息量每隔到广泛应用，全球的信息量每隔2020月就要增加月就要增加一倍，一个中等规模的企业每天要产生一倍，一个中等规模的企业每天要产生100MB100MB以上的业务数据。面对海量数据库和大量繁杂以上的业务数据。面对海量数据库和大量繁杂信息，如何才能从中提取有价值的知识，进一信息，如何才能从中提取有价值的知识，进一步提高信息的利用率，由此引发了一个新的研步提高信息的利用率，由此引发了一个新的研究方向：基于数据库的知识发现（究方向：基于数据库的知识发现（Knowledge Knowledge Discovery in DatabaseDiscovery in Database）及相应的数据挖掘）及相应的数据挖掘（Data MiningData Mining）理论和技术的研究。）理论和技术的研究。3“啤酒与尿布啤酒与尿布”的故事是最经典的营销案例之的故事是最经典的营销案例之一，主要讲述美国著名零售商沃尔玛利用网络一，主要讲述美国著名零售商沃尔玛利用网络信息技术，建立了顾客关系管理系统。信息技术，建立了顾客关系管理系统。数据挖掘的应用数据挖掘的应用v对于零售业中的数据挖掘，销售人员通过数对于零售业中的数据挖掘，销售人员通过数据挖掘建立预测模型，了解哪些人最有可能据挖掘建立预测模型，了解哪些人最有可能对销售业务中的直接信函做出响应，由此将对销售业务中的直接信函做出响应，由此将直接信函送给正确的客户，从而减少了开支，直接信函送给正确的客户，从而减少了开支，并增加了销售额。并增加了销售额。4v对于保险业中的数据挖掘，销售人员通过数对于保险业中的数据挖掘，销售人员通过数据挖掘可以识别哪些赔偿要求最有可能具有据挖掘可以识别哪些赔偿要求最有可能具有欺诈性，从而减少保险业中欺诈案件的发生欺诈性，从而减少保险业中欺诈案件的发生数量。数量。v对于金融市场中的数据挖掘，客户关系管理对于金融市场中的数据挖掘，客户关系管理中开办银行卡业务是掌握大量客户信息的重中开办银行卡业务是掌握大量客户信息的重要途径。数据挖掘与要途径。数据挖掘与CRM相结合，定位最相结合，定位最大贡献度的信用卡客户刺激持卡人用卡消费。大贡献度的信用卡客户刺激持卡人用卡消费。5 7.1.2 数据挖掘的定义数据挖掘的定义数据挖掘（数据挖掘（Data MiningData Mining，DMDM）:就是从大型就是从大型数据库中抽取有意义的（非平凡的，隐含的，数据库中抽取有意义的（非平凡的，隐含的，以前未知的并且是有潜在价值的）信息或模以前未知的并且是有潜在价值的）信息或模式的过程。式的过程。数据挖掘分为两大类：数据挖掘分为两大类：描述型挖掘和预测型描述型挖掘和预测型挖掘。挖掘。描述型挖掘描述型挖掘：是对现有数据的进一步精炼和是对现有数据的进一步精炼和归纳，从中抽取中更宏观的反映数据特征的归纳，从中抽取中更宏观的反映数据特征的概念描述。概念描述。预测型挖掘预测型挖掘：就是建立的挖掘模型具备预测就是建立的挖掘模型具备预测能力能力6数据挖掘系统的组成数据挖掘系统的组成数据挖掘系统结构数据挖掘系统结构数据仓库数据仓库数据清理数据清理 数据集成数据集成过滤过滤数据库数据库数据库或数据仓库数据库或数据仓库服务器服务器数据挖掘引擎数据挖掘引擎模式评估模式评估图形用户界面图形用户界面 知识库知识库7数据库，数据仓库或其他信息库：数据库，数据仓库或其他信息库：可以在数据可以在数据上进行数据清理和集成。上进行数据清理和集成。数据库或数据仓库服务器：数据库或数据仓库服务器：根据用户的挖掘请根据用户的挖掘请求，数据库或数据仓库服务器负责提取相关数求，数据库或数据仓库服务器负责提取相关数据。据。知识库：知识库：是领域知识，用于指导搜索或评估结是领域知识，用于指导搜索或评估结果模式的兴趣度。果模式的兴趣度。8数据挖掘引擎：数据挖掘引擎：数据挖掘系统的基本部分：由数据挖掘系统的基本部分：由一一些些功能模块组成，用于特征化、关联、分类、功能模块组成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。聚类分析以及演变和偏差分析。模式评估模块：模式评估模块：使用兴趣度量，并与数据挖掘使用兴趣度量，并与数据挖掘模块交互，以便将搜索聚焦在有趣的模式上，模块交互，以便将搜索聚焦在有趣的模式上，可能使用兴趣度阈值过滤发现的模式。可能使用兴趣度阈值过滤发现的模式。图形用户界面：图形用户界面：该模块在用户和数据挖掘系统该模块在用户和数据挖掘系统之间通信，允许用户与系统交互，指定数据挖之间通信，允许用户与系统交互，指定数据挖掘查询或任务，提供信息，帮助搜索聚焦，根掘查询或任务，提供信息，帮助搜索聚焦，根据挖掘的中间结果进行探索式数据挖掘。据挖掘的中间结果进行探索式数据挖掘。9数据挖掘任务：数据挖掘任务：包括分类或预测知识模型发现，包括分类或预测知识模型发现，数据总结，数据聚类，关联规则发现，时序模数据总结，数据聚类，关联规则发现，时序模式发现，依赖关系或依赖模型发现，异常和趋式发现，依赖关系或依赖模型发现，异常和趋势发现等。势发现等。数据挖掘对象：数据挖掘对象：包括关系数据库，面向对象数包括关系数据库，面向对象数据库，空间数据库，时态数据库，文本数据库，据库，空间数据库，时态数据库，文本数据库，多媒体数据库，异构数据库，数据仓库，和多媒体数据库，异构数据库，数据仓库，和WebWeb数据库等。数据库等。数据挖掘方法：数据挖掘方法：包括统计方法，机器学习方法，包括统计方法，机器学习方法，神经网络方法和数据库方法。神经网络方法和数据库方法。107.1.3 数据挖掘的过程数据挖掘的过程数据挖掘过程主要包括四个步骤，数据挖掘过程主要包括四个步骤，即数据选择、即数据选择、数据预处理、模式发现和解释评估。其中，模数据预处理、模式发现和解释评估。其中，模式发现是数据挖掘的关键步骤。式发现是数据挖掘的关键步骤。步骤步骤1 1：数据选择。：数据选择。提出挖掘目标，即根据限定的主题，来选提出挖掘目标，即根据限定的主题，来选择相关的数据。择相关的数据。步骤步骤2 2：数据预处理。：数据预处理。经过预处理来提高数据质量。数据预处理经过预处理来提高数据质量。数据预处理技术主要包括数据清洗、数据集成、数据变换技术主要包括数据清洗、数据集成、数据变换和数据归约。和数据归约。11步骤步骤3 3：模式发现：模式发现 蕴含在数据中的规律、规则或特片（即知蕴含在数据中的规律、规则或特片（即知识），表现在数据的某种模式上，发现数据模识），表现在数据的某种模式上，发现数据模式关键是人机交互地选择算法，这一步是数据式关键是人机交互地选择算法，这一步是数据挖掘中的核心内容。挖掘中的核心内容。步骤步骤4 4：解释评估：解释评估 从挖掘出的模式中得到有趣的模式，即对从挖掘出的模式中得到有趣的模式，即对用户有用的模式，即对挖掘出的模式进行解释用户有用的模式，即对挖掘出的模式进行解释评估。评估。12步骤步骤2 2：数据预处理：数据预处理数据预处理的主要任务数据预处理的主要任务数据清理数据清理v填入缺失数据填入缺失数据v平滑噪音数据平滑噪音数据v确认和去除孤立点确认和去除孤立点v解决不一致性解决不一致性数据集成数据集成v多个数据库、多个数据库、Data CubeData Cube和文件系统的集成和文件系统的集成数据转换数据转换v规范化、聚集等规范化、聚集等13数据归约数据归约v在可能获得相同或相似结果的前提下，对数在可能获得相同或相似结果的前提下，对数据的容量进行有效的缩减据的容量进行有效的缩减数据离散化数据离散化v对于一个特定的连续属性，尤其是连续的数对于一个特定的连续属性，尤其是连续的数字属性，可以把属性值划分成若干区间，以字属性，可以把属性值划分成若干区间，以区间值来代替实际数据值，以减少属性值的区间值来代替实际数据值，以减少属性值的个数个数.14一、数据清理一、数据清理1 1、数据记录中的空缺值、数据记录中的空缺值忽略整个元组忽略整个元组手工填入空缺的值手工填入空缺的值v枯燥、费时，可操作性差，不推荐使用枯燥、费时，可操作性差，不推荐使用使用一个全局的常量填充空缺数值使用一个全局的常量填充空缺数值v给定一个固定的属给定一个固定的属性值代表：性值代表：Unknown Unknown、NullNull等等v简单，但是没有意义简单，但是没有意义15使用属性的平均值填充空缺数值使用属性的平均值填充空缺数值v简单方便、挖掘结果容易产生不精确的结果简单方便、挖掘结果容易产生不精确的结果使用与给定元组同一个类别的所有样本的平均使用与给定元组同一个类别的所有样本的平均值值v分类非常重要，尤其是分类指标的选择分类非常重要，尤其是分类指标的选择使用最有可能的值予以填充使用最有可能的值予以填充v利用回归、基于推导的使用贝叶斯形式化的利用回归、基于推导的使用贝叶斯形式化的方法的工具或者判定树归纳确定方法的工具或者判定树归纳确定v利用属性之间的关系进行推断，保持了属性利用属性之间的关系进行推断，保持了属性之间的联系之间的联系162 2、消除噪音、消除噪音噪音数据噪音数据:一个度量（指标）变量中的随机错误或者偏差一个度量（指标）变量中的随机错误或者偏差处理噪音数据：处理噪音数据：分箱方法、聚类方法、线性回归、人机分箱方法、聚类方法、线性回归、人机结合共同检测结合共同检测分箱（分箱（BinningBinning）方法）方法:v基本思想：基本思想：通过考察相邻数据的值，来平滑存储数据通过考察相邻数据的值，来平滑存储数据的值，用的值，用“箱的深度箱的深度”表示不同的箱里有相同个数的数表示不同的箱里有相同个数的数据，用据，用“箱的宽度箱的宽度”来表示每个箱值的取值区间为常数。来表示每个箱值的取值区间为常数。v基本步骤：基本步骤：首先，对数据进行排序，并分配到具有相同宽度首先，对数据进行排序，并分配到具有相同宽度/深深度的不同的度的不同的“箱子箱子”中中其次，通过箱子的平均值、中值、或者边界值等来其次，通过箱子的平均值、中值、或者边界值等来进行平滑处理进行平滑处理17分箱分箱方法举例方法举例对数据进行排序对数据进行排序:4,8,9,15,21,21,24,25,26,:4,8,9,15,21,21,24,25,26,28,29,3428,29,34对数据进行分割对数据进行分割(相同深度相同深度):):v-Bin 1:4,8,9,15-Bin 1:4,8,9,15v-Bin 2:21,21,24,25-Bin 2:21,21,24,25v-Bin 3:26,28,29,34-Bin 3:26,28,29,34根据根据binbin中的平均值进行离散化中的平均值进行离散化:v-Bin 1:9,9,9,9-Bin 1:9,9,9,9v-Bin 2:23,23,23,23-Bin 2:23,23,23,23v-Bin 3:29,29,29,29-Bin 3:29,29,29,29通过不同分箱方法求解的平滑数据值，就是同一箱中通过不同分箱方法求解的平滑数据值，就是同一箱中4 4个数的存储数据的值。个数的存储数据的值。18基于聚类分析的平滑处理基于聚类分析的平滑处理19二、数据集成二、数据集成数据集成的概念数据集成的概念v将多个数据源中的数据结合起来存放在一将多个数据源中的数据结合起来存放在一个一致的数据存储中个一致的数据存储中v数据源包括：多个数据库、多维数据库和数据源包括：多个数据库、多维数据库和一般的文件一般的文件v数据集成也是数据仓库建设中的一个重要数据集成也是数据仓库建设中的一个重要问题问题20数据集成的内容数据集成的内容v模式集成模式集成利用数据库和数据仓库的元数据信息利用数据库和数据仓库的元数据信息主要工作是识别现实世界中的实体定义，判断数主要工作是识别现实世界中的实体定义，判断数据源中的有关属性是不是指同一个实体据源中的有关属性是不是指同一个实体v冗余数据的处理冗余数据的处理v检测和解决数值冲突检测和解决数值冲突对于现实世界中的同一实体，来自于不同数据源对于现实世界中的同一实体，来自于不同数据源的属性值可能不同的属性值可能不同主要原因：不同的数据表示、度量单位、编码方主要原因：不同的数据表示、度量单位、编码方式以及语义的不同式以及语义的不同211 1、模式集成、模式集成数据类型冲突数据类型冲突v性别：性别：CharChar（M M、F F）、）、IntergerInterger（0 0、1 1）v日期：日期：DateDate、DateTimeDateTime、StringString数据标签冲突：解决同名异义、异名同义数据标签冲突：解决同名异义、异名同义v学生成绩、分数学生成绩、分数度量单位冲突度量单位冲突v学生成绩学生成绩百分制：百分制：100 0100 0五分制：五分制：A A、B B、C C、D D、E E字符表示：优、良、及格、不及格字符表示：优、良、及格、不及格概念不清概念不清v最近交易额：前一个小时、昨天、本周、本月？最近交易额：前一个小时、昨天、本周、本月？222 2、冗余数据的处理、冗余数据的处理从多个数据源中抽取不同的数据，容易导致数从多个数据源中抽取不同的数据，容易导致数据的冗余据的冗余v相同的属性在不同的数据源中是不同的命名相同的属性在不同的数据源中是不同的命名 方式。方式。v有些属性可以从其它属性中导出，有些属性可以从其它属性中导出，例如：销售额单价例如：销售额单价销售量销售量v元组级的元组级的“重复重复”，也是数据冗余的一个重要方面，也是数据冗余的一个重要方面减少冗余数据，可以大大提高数据挖掘的性能减少冗余数据，可以大大提高数据挖掘的性能3 3、检测和解决数值冲突检测和解决数值冲突v不同的度量单位造成同一实体属性值不同不同的度量单位造成同一实体属性值不同23三、数据转换三、数据转换平滑处理平滑处理:从数据中消除噪音数据从数据中消除噪音数据聚集操作聚集操作:对数据进行汇总和聚集操作（如聚对数据进行汇总和聚集操作（如聚集日销售数据），通常用于集日销售数据），通常用于数据立方体的构建数据立方体的构建数据概化：数据概化：构建概念层次，缩小数据量构建概念层次，缩小数据量v例：市例：市-省省-国家，年龄国家，年龄数据规范化数据规范化:将数据集中到一个较小的范围之将数据集中到一个较小的范围之中中v例：将例：将0-1000-100空间映射到空间映射到0,10,1之间之间属性构造：属性构造：根据原有属性构造新的属性，以帮根据原有属性构造新的属性，以帮助提高精度和对高维数据结构的理解助提高精度和对高维数据结构的理解v例：例：Area=Width Height24四、数据归约的提出四、数据归约的提出在数据仓库中可能保存在数据仓库中可能保存TBTB级的数据，大数据量级的数据，大数据量的数据挖掘，可能需要大量的时间来完成整的数据挖掘，可能需要大量的时间来完成整个数据的数据挖掘。个数据的数据挖掘。数据归约数据归约v在可能获得相同或相似结果的前提下，对在可能获得相同或相似结果的前提下，对数据的容量进行有效的缩减数据的容量进行有效的缩减25数据归约的方法数据归约的方法v数据立方体聚集：数据立方体聚集：聚集操作作用于立方体中的聚集操作作用于立方体中的数据数据,有利于进行多层次的数据分析有利于进行多层次的数据分析v减少数据维度（维归约）：减少数据维度（维归约）：可以检测并删除不可以检测并删除不相关、弱相关或者冗余的属性或维相关、弱相关或者冗余的属性或维v数据压缩：数据压缩：应用数据编码或变换，以便得到数应用数据编码或变换，以便得到数据的归约或压缩表示，分为有损压缩（如字符据的归约或压缩表示，分为有损压缩（如字符串压缩）和无损压缩（如影像文件的压缩）。串压缩）和无损压缩（如影像文件的压缩）。v数值归约：数值归约：用替代的、较小的数据表示替换或用替代的、较小的数据表示替换或估计数据估计数据26数据立方体是一类多维矩阵，让用户从多个角度探索和分析数据数据立方体是一类多维矩阵，让用户从多个角度探索和分析数据集，通常是一次同时考虑三个因素（维度）。数据立方体中的数集，通常是一次同时考虑三个因素（维度）。数据立方体中的数据是已经过处理并聚合成立方形式。因此，通常不需要在数据立据是已经过处理并聚合成立方形式。因此，通常不需要在数据立方体中进行计算。这也意味着我们看到数据立方体中的数据并不方体中进行计算。这也意味着我们看到数据立方体中的数据并不是实时的、动态的数据。是实时的、动态的数据。27五、数据离散化和概念层次五、数据离散化和概念层次数据离散化数据离散化v对于一个特定的连续属性，可以把属性值划分对于一个特定的连续属性，可以把属性值划分成若干区间，以区间值来代替实际数据值，以成若干区间，以区间值来代替实际数据值，以减少属性值的个数。减少属性值的个数。概念层次概念层次v利用高层的概念（如儿童、青年、中年、老年利用高层的概念（如儿童、青年、中年、老年等）来代替低层的实际数据值（实际年龄），等）来代替低层的实际数据值（实际年龄），以减少属性值的个数。以减少属性值的个数。28数据预处理的形式数据预处理的形式数据清理数据清理数据集成数据集成数据转换数据转换数据归约数据归约29步骤步骤3 3：模式发现：模式发现模式发现：模式发现：模型构造的过程主要包括：选择模型构造的过程主要包括：选择适用的挖掘技术、建立培训数据和测试数据、适用的挖掘技术、建立培训数据和测试数据、利用培训数据采用相应的算法建立模型、模型利用培训数据采用相应的算法建立模型、模型解释、模型评估和检验。解释、模型评估和检验。30步骤步骤4 4：解释评估：解释评估模式兴趣度的度量模式兴趣度的度量：一种是客观度量，例如对：一种是客观度量，例如对于形如于形如的关联规则客观度量通常采用的关联规则客观度量通常采用支持度和置信度来定义。另一种是主观度量，支持度和置信度来定义。另一种是主观度量，实际上是用户的一种主观预感，认为合理的或实际上是用户的一种主观预感，认为合理的或认为出乎意料的，给出模式是否有趣的结论认为出乎意料的，给出模式是否有趣的结论数据挖掘数据挖掘的完全性：数据挖掘能否挖掘出所有的完全性：数据挖掘能否挖掘出所有有趣的模式。有趣的模式。317.1.4 数据挖掘基本方法数据挖掘基本方法本节只阐述与种基本任务相关的方法，它本节只阐述与种基本任务相关的方法，它们是分类、聚类、关联分析和时间序列们是分类、聚类、关联分析和时间序列32 一、分类一、分类分类：分类：是对数据的一个重要抽象，从机器学习是对数据的一个重要抽象，从机器学习的观点看，分类是一种监督学习，即根据应用的观点看，分类是一种监督学习，即根据应用的需要确定分类的类别，通过对训练数据的分的需要确定分类的类别，通过对训练数据的分类学习归纳出分类规则，利用测试数据对模型类学习归纳出分类规则，利用测试数据对模型的准确率进行测试，再对数据进行分类操作。的准确率进行测试，再对数据进行分类操作。典型算法：典型算法：包括决策树、最近邻法包括决策树、最近邻法(K-(K-Nearest Neighbor,Nearest Neighbor,简称简称KNNKNN）、平均法（）、平均法（k-k-MeanMean）、支持向量机（）、支持向量机（Support Vector Support Vector Machine,Machine,简称简称SVMSVM）、向量空间模型（）、向量空间模型（Vector Vector Space Model,Space Model,简称简称VSMVSM）、贝叶斯网络算法）、贝叶斯网络算法(Bayesian Network)(Bayesian Network)、神经网络算法、神经网络算法(Neural(Neural Network),Network),等等等等。33 决策树分类方法：决策树分类方法：决策树（又称判定树）：决策树（又称判定树）：是一种类似二叉树或是一种类似二叉树或多叉树的树结构。树中的每个非叶节点对应于多叉树的树结构。树中的每个非叶节点对应于训练样本集中一个非类别属性的测试，非叶节训练样本集中一个非类别属性的测试，非叶节点的每个分枝对应属性的一个测试结果，每个点的每个分枝对应属性的一个测试结果，每个叶子节点则代表一个类或类分布。从根节点到叶子节点则代表一个类或类分布。从根节点到叶子节点的一条路径形成一条分类规则。决策叶子节点的一条路径形成一条分类规则。决策树可以很方便地转化为分类规则，是一种非常树可以很方便地转化为分类规则，是一种非常直观的分类模式表示形式。直观的分类模式表示形式。34 决策树算法构成：决策树算法构成：由树根开始对该对象的属性由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象达某个叶结点，此叶结点代表的类即为该对象所处的类。所处的类。35 信息增益值的计算：信息增益值的计算：设设S是是s个数据样本的集个数据样本的集合。假定类标号属性具有合。假定类标号属性具有m个不同值，定义个不同值，定义m个不同类个不同类Ci(i=1,2,m)。设。设si是类是类Ci中的样本中的样本数。数。1、对于一个给定的样本分类所需的、对于一个给定的样本分类所需的期望信息期望信息由下式给出：由下式给出：其中其中Pi是任意样本属于是任意样本属于Ci的概率，并用的概率，并用si/s估估计。计。36 2.2.设属性设属性A A具有具有v v个不同的值个不同的值a1,a2,a1,a2,av.,av.用属用属性性A A将将S S划分为划分为v v个子集个子集s1,s2,s1,s2,sv,sv，sjsj包含这包含这样一些样本，它们在样一些样本，它们在A A上具有值上具有值ajaj。设。设S Sijij是子集是子集S Sj j中类中类cici的样本数。由的样本数。由A A划分成划分成子集的熵子集的熵由下式由下式给出给出:373 3、计算信息增益、计算信息增益由期望信息和熵值可以得到对应的信息增益值。由期望信息和熵值可以得到对应的信息增益值。属性属性A A的信息增益由下式给出：的信息增益由下式给出：具有最高信息增益的属性选作给定集合具有最高信息增益的属性选作给定集合S的测的测试属性。创建一个节点，并以该属性标记，对试属性。创建一个节点，并以该属性标记，对属性的每个值创建分枝，并据此划分样本。属性的每个值创建分枝，并据此划分样本。38例：根据如下数据集构造决策树模型例：根据如下数据集构造决策树模型。根据表根据表7-1 All Electronics7-1 All Electronics顾客数据库数据顾客数据库数据元组训练集。元组训练集。39类标号属性类标号属性buy_computer有两个不同的值（即有两个不同的值（即yes,no）。）。40解：解：1、计算给定样本分类所需的、计算给定样本分类所需的期望信息期望信息I(S1,S2)=I(9,5)=9/14*log2(9/14)5/14*log2(5/14)=0.940412、计算每个属性的熵、计算每个属性的熵计算计算age的熵：的熵：计算计算age属性给定属性给定对于给定的子集对于给定的子集S Sj j的期望信息：的期望信息：其中，其中，P Pijij=S=Sijij/S/Sj j是样本属于类是样本属于类CiCi的概率。的概率。age=“40”:s13=3,s23=2,I(s13,s23)=0.971E(age)=5/14*I(s11,s21)+4/14*I(S12,S22)+5/14*I(S13,S23)=0.69443 3、计算信息增益、计算信息增益属性属性A的信息增益由下式给出：的信息增益由下式给出：Gain(age)=I(S1,S2)E(age)=0.940 0.694=0.246同样方法得到计算每个属性的信息增益同样方法得到计算每个属性的信息增益:Gain(income)=0.029,Gain(student)=0.151,Gain(credit_rating)=0.048,具有最高信息增益的属性选作给定集合具有最高信息增益的属性选作给定集合S的测试属的测试属性。创建一个节点，并以该属性标记，对属性的性。创建一个节点，并以该属性标记，对属性的每个值创建分枝，并据此划分样本。每个值创建分枝，并据此划分样本。4445 决策树示意图决策树示意图46二、聚类二、聚类分类是按照指定类别将数据集进行划分的一种技术，分类是按照指定类别将数据集进行划分的一种技术，是有指导的学习。而聚类也是要对数据集进行分析并是有指导的学习。而聚类也是要对数据集进行分析并划分，但划分的类别是未知的，是一种无指导的学习。划分，但划分的类别是未知的，是一种无指导的学习。聚类聚类(簇簇)：聚类生成的组为簇，簇是数据对象的集合。聚类生成的组为簇，簇是数据对象的集合。v簇内部任意两个对象之间具有较高的相似度簇内部任意两个对象之间具有较高的相似度v而属于不同簇的两个对象间具有较高的相异度。而属于不同簇的两个对象间具有较高的相异度。聚类分析：聚类分析：是对物理的或抽象的对象按相似程度集合是对物理的或抽象的对象按相似程度集合分组的过程。分组的过程。聚类分析的数据挖掘功能：聚类分析的数据挖掘功能：如：模式识别，对如：模式识别，对WEBWEB日志日志的数据进行挖掘，汽车保险业。的数据进行挖掘，汽车保险业。典型算法：典型算法：包括包括BIRCHBIRCH算法、算法、CURECURE算法、算法、DBSCANDBSCAN算法、算法、K-pototypesK-pototypes算法、算法、CLARANSCLARANS算法、算法、CLIQUECLIQUE算法，等等。算法，等等。47三、关联规则三、关联规则关联分析是数据挖掘中较早引起兴趣的一关联分析是数据挖掘中较早引起兴趣的一种数据分析方法，种数据分析方法，关联规则反映一个事物关联规则反映一个事物与其它事物之间的相互依存性和关联性，与其它事物之间的相互依存性和关联性，如果两个事物或者多个事物之间存在一定如果两个事物或者多个事物之间存在一定的关联关系，那么其中一个事物就能够通的关联关系，那么其中一个事物就能够通过其他事物预测到。例：购物篮分析。过其他事物预测到。例：购物篮分析。48关联规则的基本概念关联规则的基本概念设设T T为一组交易数据的集合，记为为一组交易数据的集合，记为T Tt1,t2,t1,t2,tm,tm，m m是交易数据的数目。其中，是交易数据的数目。其中，ti(1 i m)ti(1 i m)是每笔交易的数据，每笔交是每笔交易的数据，每笔交易中包含若干数据项，易中包含若干数据项，I I是交易是交易T T中数据项的集中数据项的集合记为合记为I Ii1i1，i2,i2,inin，n n是数据项的数目。是数据项的数目。设有数据项集设有数据项集X X和和Y(X,Y Y(X,Y I I，且，且XYXY)。如果存在一笔交易中既含如果存在一笔交易中既含X X数据项集又含数据项集又含Y Y数据数据项集，则称项集，则称X=YX=Y在此交易中成立，定义支持度在此交易中成立，定义支持度如下：如下：49支持度：支持度：支持度支持度:表示表示X=YX=Y在在T T交易数据中出现的普遍交易数据中出现的普遍程度。是指程度。是指“T T中包含中包含X X Y Y的事务的百分的事务的百分比比”，也可以看作是概率，也可以看作是概率P(XY)P(XY)的估计。因的估计。因此规则的支持度表示规则在事务集合此规则的支持度表示规则在事务集合T T中使用中使用的频繁程度。的频繁程度。50定义定义置置信度如下：信度如下：一个规则一个规则X X Y Y的置信度是指的置信度是指“既包含了既包含了X X又又包含了包含了Y Y的事务的数量占所有包含了的事务的数量占所有包含了X X的事务的的事务的百分比百分比”。这可以看作是条件概率。这可以看作是条件概率P(Y|X)P(Y|X)的一的一个估计。个估计。强关联规则：强关联规则：同时满足最小支持度阈值和最小同时满足最小支持度阈值和最小置信度阈值的规则称作强关联规则。置信度阈值的规则称作强关联规则。51事物集例子事物集例子交易数据交易数据数据项数据项t1A,B,C,Dt2A,Bt3A,D,Et4B,Ct5A,B,C关联规则关联规则支持度支持度可信度可信度A=B6075B=A6075B=C6075C=B60100关联规则集合（关联规则集合（s 50,c75）52四、时间序列四、时间序列时间序列：时间序列：将某一指标在不同时间上的不同数将某一指标在不同时间上的不同数值，按照时间的先后顺序排列而成的数列。值，按照时间的先后顺序排列而成的数列。时间序列数据挖掘：时间序列数据挖掘：通过描述历史数据随时间通过描述历史数据随时间变化的规律，进而完成预测未来行为等决策性变化的规律，进而完成预测未来行为等决策性工作。是指不同交易之间的数据关联。例：天工作。是指不同交易之间的数据关联。例：天气预报，股票信息预测。气预报，股票信息预测。典型算法：典型算法：包括包括AprioriAllAprioriAll算法、算法、AprioriSomeAprioriSome算法、算法、SPADESPADE算法、算法、PrefixSpanPrefixSpan算算法、法、SPAMSPAM算法等。算法等。53 9.2 数据挖掘与国家安全数据挖掘与国家安全9.2.1 国家安全国家安全国家安全国家安全:是对主权国家的生存发展受威是对主权国家的生存发展受威胁程度的界定，即国家生存和发展没有胁程度的界定，即国家生存和发展没有或很少受到重大威胁的状态，就是国家或很少受到重大威胁的状态，就是国家安全的客观界定。安全的客观界定。549.2.2 数据挖掘在国家安全中的应用数据挖掘在国家安全中的应用20042004美国联邦政府会计总署报告美国联邦政府会计总署报告显示，美显示，美国政府部门积极参与或正在筹划的数据挖掘项国政府部门积极参与或正在筹划的数据挖掘项目为目为199199个，其中个，其中1414个项目明确用于抓捕恐怖个项目明确用于抓捕恐怖分子和预防恐怖袭击。分子和预防恐怖袭击。恐怖主义信息感知（恐怖主义信息感知（TIATIA）计划）计划 国防高级工程研究局（国防高级工程研究局（DARPADARPA）于）于20022002年年1 1月成立月成立信息感知办公室（信息感知办公室（IAOIAO），并着手实施），并着手实施TIATIA计划。计划。计算机辅助乘客筛选系统计算机辅助乘客筛选系统(CAPPS II)(CAPPS II)基于规则的系统，确定乘客是否需要额外安全筛选。基于规则的系统，确定乘客是否需要额外安全筛选。安全飞行系统安全飞行系统。55567.3 数据挖掘与数字安全数据挖掘与数字安全1.1.网络入侵检网络入侵检测测 网络入侵表现网络入侵表现为攻击者取得了进入系统或多次进入为攻击者取得了进入系统或多次进入系统的能力，或取得了访问系统中资源的能力，或取得系统的能力，或取得了访问系统中资源的能力，或取得了在系统中运行自己程序的能力。了在系统中运行自己程序的能力。目的目的是取得使用系统是取得使用系统的存储能力、处理能力以及访问其存储内容的权力，或的存储能力、处理能力以及访问其存储内容的权力，或者作为进入其他系统的跳板，或者是想破坏这个系统。者作为进入其他系统的跳板，或者是想破坏这个系统。1986 1986年，美国斯坦福国际研究所（年，美国斯坦福国际研究所（SRISRI）首次提出了）首次提出了一种抽象入侵模型，其主要过程包括两步：一种抽象入侵模型，其主要过程包括两步：v获取目标系统信息获取目标系统信息：可能是目标系统无意间提供的：可能是目标系统无意间提供的或是攻击者使用分析工具获得的。或是攻击者使用分析工具获得的。v网络攻击网络攻击：利用操作系统或通信协议的安全漏洞来：利用操作系统或通信协议的安全漏洞来进行。进行。5657例：采用时间序列数据挖掘方法分析网络攻击行为。例：采用时间序列数据挖掘方法分析网络攻击行为。表表71 网络连接记录网络连接记录timestsampdurationserviceSrc_hostdst_hostSrcbytesdst_bytesflag01：01：000httphost1victim00S001：02：000httphost2victim00S001：03：000httphost3victim00S001：04：000httphost4victim00S0 表表72 序列规则实例序列规则实例序列规则序列规则含义含义(service=http，flag=S0，dst_host=victim)，(service=http，flag=S0，dst_host=victim)(service=http，flag=S0，dst_host=victim)0.95,0.03,295%的时间内，伴随着的时间内，伴随着victim主机上两次主机上两次带有带有S0标志的标志的http连接，在连接，在2s内会出现第内会出现第三次相同的连接，这样的模式在三次相同的连接，这样的模式在3%的数的数据中出现据中出现57587.4 敏感数据的有限泄露敏感数据的有限泄露 1.敏感数据敏感数据 所谓敏感数据就是指不希望其他用户看见所谓敏感数据就是指不希望其他用户看见的数据。的数据。当原始数据对敏感数据完全隐藏后，可能当原始数据对敏感数据完全隐藏后，可能会导致部分的知识不能挖掘出来，或者挖掘产会导致部分的知识不能挖掘出来，或者挖掘产生新的知识。生新的知识。58592.随机偏移量方法随机偏移量方法 RAgrawal提出一种通过加随机偏移量来对提出一种通过加随机偏移量来对原始数据进行变换，从而保护敏感数据的方法，原始数据进行变换，从而保护敏感数据的方法，主要有两种类型的变换。主要有两种类型的变换。v 归类法归类法:把数据分成几个不相交的类，一般把数据分成几个不相交的类，一般按照间隔进行划分。范围可以是连续的，也按照间隔进行划分。范围可以是连续的，也可以是离散的，只要各类不相交。可用于隐可以是离散的，只要各类不相交。可用于隐藏个人信息。藏个人信息。v 转换法转换法：设有：设有n个原始数据值个原始数据值x1,x2,xn,分分别在其上加上别在其上加上n个随机变量个随机变量y1,y2,yn，将，将原始数据隐藏后得到原始数据隐藏后得到n个变换后的值。个变换后的值。59607.5 关联规则的隐藏关联规则的隐藏受限关联规则受限关联规则就是指不希望通过挖掘技术被发现就是指不希望通过挖掘技术被发现的规则集合，与受限关联规则相关的事务称为的规则集合，与受限关联规则相关的事务称为敏敏感事务，感事务，敏感事务中与受限关联规则相关的项称敏感事务中与受限关联规则相关的项称为为敏感项。敏感项。关联规则隐藏的目的关联规则隐藏的目的就是保护受限关联规则不被就是保护受限关联规则不被发现，同时其他非受限关联规则受到最低限度的发现，同时其他非受限关联规则受到最低限度的影响。影响。利用数据清洗，通过对事务数据项集的修改使关利用数据清洗，通过对事务数据项集的修改使关联规则的支持度和置信度低于给定的阈值，从而联规则的支持度和置信度低于给定的阈值，从而使给定的关联规则得到隐藏。使给定的关联规则得到隐藏。6061在对原始数据库中的数据进行清洗之后，可能在对原始数据库中的数据进行清洗之后，可能会产生以下两个问题：会产生以下两个问题：v丢失规则：丢失规则：一部分规则的隐藏会导致其他规一部分规则的隐藏会导致其他规则的隐藏。则的隐藏。v 产生新的规则：产生新的规则：对于原数据库中原不存在的对于原数据库中原不存在的一些规则，在对受限关联规则集受进行隐藏一些规则，在对受限关联规则集受进行隐藏后出现了，也就是产生了新规则。后出现了，也就是产生了新规则。6162例：例：对对P54P54表表中所示的交易数据，为了隐藏中所示的交易数据，为了隐藏B B=C C规则，所以删除事务规则，所以删除事务t5t5，那么关联规则，那么关联规则A A=B B和和B B=A A也被隐藏了，其关联规则集合如下也被隐藏了，其关联规则集合如下表所示。表所示。删除事务删除事务t5后的关联规则集合后的关联规则集合（s 50,c75）关联规则关联规则支持度支持度可信度可信度C=B501006263例：例：对对P54P54表表中所示的交易数据，如果添加事中所示的交易数据，如果添加事务务t6(A,B,D)t6(A,B,D)，那么会增加关联规则，那么会增加关联规则D D=A A，其，其关联规则集合如下表所示。关联规则集合如下表所示。增加事务增加事务t后的关联规则集合后的关联规则集合（s 50,c75）关联规则关联规则支持度支持度可信度可信度A=B66.7%80%B=A66.7%80%C=B50%100%D=A50%100%6364关联规则的隐藏方法，从清洗对象的不同，一关联规则的隐藏方法，从清洗对象的不同，一般可以归纳为两种：般可以归纳为两种：v数据共享策略：数据共享策略：对原始数据本身进行修改，对原始数据本身进行修改，包括对涉及受限关联规则的事务进行移出操包括对涉及受限关联规则的事务进行移出操作，或对事务中的项直接删除、添加或修改，作，或对事务中的项直接删除、添加或修改，然后把清洗后的安全数据共享。然后把清洗后的安全数据共享。v模式共享策略：模式共享策略：对所挖掘到的关联规则集进对所挖掘到的关联规则集进行相关清洗后，再共享。行相关清洗后，再共享。6465数据共享策略包括四种。数据共享策略包括四种。1 1、基于项的约束：基于项的约束：从一组涉及受限关联规则集的从一组涉及受限关联规则集的事务中移出部分项集，从而使得受限关联规则事务中移出部分项集，从而使得受限关联规则的支持度或置信度低于安全阈值的要求，其具的支持度或置信度低于安全阈值的要求，其具体过程为：体过程为：1 1）对数据库）对数据库D D中的每一个事务，检测其是否敏感中的每一个事务，检测其是否敏感事务，如果事务，如果“不是不是”，则把事务数据直接拷贝，则把事务数据直接拷贝到清洗过的数据库到清洗过的数据库D D中；否则，对事务进行中；否则，对事务进行标注。标注。2 2）对于标注为敏感的事务，选择与受限关联规则）对于标注为敏感的事务，选择与受限关联规则有关系的项，根据预先设定的阈值有关系的项，根据预先设定的阈值 ，决定，决定是否对这些项进行隐藏。是否对这些项进行隐藏。6566隐藏关联规则的核心思想是如果要隐藏关联规隐藏关联规则的核心思想是如果要隐藏关联规则则X=Y X=Y，就要：，就要：l提高提高X X的支持度，而不是的支持度，而不是XYXY的支持度。的支持度。l或者降低或者降低XYXY的支持度。的支持度。例：例：对于对于I=A,B,C I=A,B,C，如果有事务，如果有事务T(T(l0l)l0l)，其意思是，在事务，其意思是，在事务T T中包含事务项中包含事务项A A和和C C。改变支持度的方法就是把事务项从。改变支持度的方法就是把事务项从1 1变为变为0 0或者或者0 0变为变为1 1。这些可以参考具体的算法。这些可以参考具体的算法。6667例：例：D D是原始事务集，是原始事务集，DlDl和和D2D2分别表示两个清分别表示两个清洗后的事务集，在事务中的项发生变化后，从洗后的事务集，在事务中的项发生变化后，从事务集中挖掘出的关联规则也会发生变化。事务集中挖掘出的关联规则也会发生变化。基于项的约束的一个示例基于项的约束的一个示例TIDDD1D2T1111111101T2111111111T3111111111T4110110110T5100110110T610110110167682、基于项的添加：基于项的添加：针对某些事务添加一些无关项，针对某些事务添加一些无关项，造成原始事务数据库已有信息的修改，不过，造成原始事务数据库已有信息的修改，不过，这种策略容易造成规则的新生。这些无关项通这种策略容易造成规则的新生。这些无关项通常称为噪音，在得到反馈结果时需要适量地排常称为噪音，在得到反馈结果时需要适量地排除噪音的影响。显然，挖掘结果的有效性依赖除噪音的影响。显然，挖掘结果的有效性依赖于添加的噪音量。这种方法可以提高数据的安于添加的噪音量。这种方法可以提高数据的安全性，但会降低结果的精确性，在对数据结果全性，但会降低结果的精确性，在对数据结果要求不高时可以采用。要求不高时可以采用。68693 3、基于项的转换：、基于项的转换：对原始事务中的数据项进行转对原始事务中的数据项进行转换，要求转换后数据语义完整、数据内的统计换，要求转换后数据语义完整、数据内的统计表完整。这种方法一般不会影响数据挖掘的结表完整。这种方法一般不会影响数据挖掘的结果。果。6970例：例：是某医院信息系统数据库中的病例表。是某医院信息系统数据库中的病例表。如果直接将元数据呈现在数据挖掘者面前，那如果直接将元数据呈现在数据挖掘者面前，那么很容易暴露病人的隐私信息，所以对表的属么很容易暴露病人的隐私信息，所以对表的属性名进行转换。性名进行转换。病历表的元数据的转换病历表的元数据的转换属性号属性号旧属性名旧属性名新属性名新属性名1病人病人编号号000102性性别000203年年龄000304发热体温体温000405淋巴淋巴细胞数胞数000507071例：例：是某医院信息系统数据库中的病例表。是某医院信息系统数据库中的病例表。除了对属性名保护之外，对属性值也要通过转除了对属性名保护之外，对属性值也要通过转换方法进行保护，如下表，这样才能保证数据换方法进行保护，如下表，这样才能保证数据挖掘者只能挖掘出关联规则，但是对于关联规挖掘者只能挖掘出关联规则，但是对于关联规则所表达的意思不了解。则所表达的意思不了解。病历表数据的转换病历表数据的转换属性属性旧属性旧属性值表示表示新属性新属性值表示表示性性别F或或M0或或1年年龄0100之间的整数之间的整数在原在原值上乘上乘2再加再加100发热体温体温一位小数一位小数在原在原值上乘上乘10再加再加271724 4、基于项的模糊：、基于项的模糊：对一些包含敏感规则的事务对一些包含敏感规则的事务中的数据项作未知标记中的数据项作未知标记(变成变成unknown)unknown)而不而不是删除事务，这样一些己知项值就变成未知是删除事务，这样一些己知项值就变成未知的，相应降低了规则的支持度和置信度，从的，相应降低了规则的支持度和置信度，从而减少了敏感规则的泄露。而减少了敏感规则的泄露。7273小结小结重点介绍了数据挖掘的定义、数据挖掘的过程包括数重点介绍了数据挖掘的定义、数据挖掘的过程包括数据选择、数据预处理、模式发现和解释评估。另外介据选择、数据预处理、模式发现和解释评估。另外介绍了数据挖掘的基本方法。绍了数据挖掘的基本方法。对数据挖掘在国家安全和数字安全领域中的应用和相对数据挖掘在国家安全和数字安全领域中的应用和相关技术进行简要介绍。关技术进行简要介绍。为了保证数据挖掘的安全性，可以敏感数据进行隐藏，为了保证数据挖掘的安全性，可以敏感数据进行隐藏，不过敏感数据的完全隐藏会导致部分知识无法挖掘产不过敏感数据的完全隐藏会导致部分知识无法挖掘产生，所以敏感数据的隐藏和知识的获取之间需进行权生，所以敏感数据的隐藏和知识的获取之间需进行权衡。衡。关联规则发现是数据挖掘中最常用的方法之一，为了关联规则发现是数据挖掘中最常用的方法之一，为了避免受限关联规则的暴露，也要进行适当的隐藏才能避免受限关联规则的暴露，也要进行适当的隐藏才能避免被挖掘出来。避免被挖掘出来。73