数据挖掘系统 第一部分.doc

第一部分数据挖掘的基础知识一、数据、信息、知识与智慧人类的各项活动都是基于人类的智慧和知识，即对外部世界的观察和了解，做出正确的判断和决策以及采取正确的行动，而数据仅仅是人们用各种工具和手段观察外部世界所得到的原始材料，它本身没有任何意义。从数据到知识再到智慧，需要经过分析加工处理精炼的过程。（1） 数据是原材料，它只是描述发生了什么事，并不能构成决策或行动的可靠基础。（2） 通过对数据进行分析找出其中的关系，赋予数据以某种意义和关联，这就形成所谓信息。信息虽然给出了数据中一些有一定意义的东西，但它往往和人们需要完成的任务没有直接的联系，也还不能作为判断、决策和行动的依据。（3） 对信息进行再加工，即进行更深入的归纳分析，方能获得更有用的信息，即知识。而所谓知识，可定义为“信息块中的一组逻辑联系，其关系是通过上下文或过程的贴近度发现的”。从信息中理解其模式，即形成知识。在大量知识积累基础上，总结出原理和法则，就形成所谓智慧。二、数据挖掘的定义与流程OLAP（On Line Analytical processing）是一种进行实时分析和产生相应报表的在线分析工具，允许用户以交互方式浏览数据仓库（data warehousing，它是为了便于分析针对特定主题（subject-oriented）的集成化的、时变的（time-variant）即提供存贮510年或更长时间的数据，这些数据一旦存入就不再发生变化）内容，并对其中数据进行多维分析，且能及时地从变化和不太完整的数据中提取出与企业经营活动密切相关的信息。OLAP是数据分析手段的一大进步，以往的分析工具所能得到的报告结果只能回答“什么”（what），而OLAP的分析结果能回答“为什么”（why）。但OLAP分析过程是建立在对用户深藏在数据中的某种知识有预感的和假设的前提下，由用户指导的信息分析与知识发现过程。对于数据仓库中埋藏的丰富的、不为用户所知的有用信息和知识，就需要有基于计算机与信息技术的智能化自动工具，来帮助挖掘隐藏在数据中的各类知识。这类工具不应基于用户假设，而应能自身生成多种假设；再用数据仓库（或大型数据库）中的数据进行检验或验证；然后返回用户最有价值的检验结果。此外这类工具还应能适应现实世界中数据的多种特性（即量大、含噪音、不完整、动态、稀疏性、异质、非线性等）。数据挖掘，又称为数据库中知识发现（Knowledge Discovery from Database，简称KDD），它是一个从大量数据中抽取挖掘出未知的，有价值的模式或规律等知识的复杂过程。数据挖掘的全过程包括：l 数据清洗（data clearning），其作用就是清除数据噪音和与挖掘主题明显无关的数据；l 数据集成（data integration），其作用就是将来自多数据源中的相关数据组合到一起；l 数据转换（data transformation），其作用就是将数据转换为易于数据挖掘的数据存储形式；l 数据挖掘（data mining），它是知识挖掘的一个基本步骤，其作用就是利用智能方法挖掘数据模式或规律知识；l 模式评估（pattern evaluation），其作用就是根据一定评估标准（interesting measures）从挖掘结果筛选出有意义的模式知识；l 知识表示（knowledge presentation）其作用就是利用可视化和知识表达技术，向用户展示所挖掘出的相关知识。三、数据挖掘与其它计算机工具的区别l KDD和机器学习都是从数据中提取知识，那么两者有什么区别呢？KDD是从现实世界中存在的一些具体数据中提取知识，这些数据在KDD出现之前早已存在；而机器学习所使用的数据是专门为机器学习而特别准备的数据，这些数据在现实世界中也许毫无意义。由于KDD使用的数据来自实际的数据库，而且所要处理的数据量可能很大，因此KDD中的学习算法的效率和可扩充性就显得尤为重要；此外，KDD所处理的数据由于来自现实世界，数据的完整性、一致性和正确性都很难保证，如何将这些数据加工成学习算法可以接收的数据？也是数据挖掘研究与开发时需要进行深入研究的问题；再者，KDD可以利用目前数据库所取得的研究成果来加快学习过程，提高学习效率。最后一点就是，由于KDD处理的数据来自于实际的数据库，而与这些数据库有关的还有其他一些背景知识，这些背景知识的合理运用也会提高学习算法的效率。l KDD与数据库报表工具有什么区别？数据库报表制作工具是将数据库中的某些数据抽取出来，经过一些数学运算，最终以特定的格式呈现给用户，而KDD则是对数据背后隐藏的特征和趋势进行分析，最终给出关于数据的总体特征和发展趋势。报表工具也许能够给出上学期考试未通过及成绩优秀的学生的有关情况。但它不能找出那些考试未通过及成绩优秀的学生在哪些方面有些什么不同的特征，而数据挖掘通过对相关数据的分析，以发现影响学生成绩的各种因素，就可以给出两者之间的差别。l 数据挖掘与OLAP有何区别呢？OLAP是由用户驱动的，一般是由分析人员预先设定一些假设，然后使用OLAP工具去帮助验证这些假设，它提供了可使分析人员很方便地进行数据分析的手段；而数据挖掘则是通过对数据的分析来自动产生一些假设，人们可以在这些假设的基础上更有效地进行决策。四、数据挖掘功能及知识类型l 概念描述：定性与对比一个概念常常是对一个包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑基本情况的概述总结就会获得所售电脑基本情况的一个整体概念（如：基本上为PIII以上的兼容机）。对含有大量数据的数据集合进行概述性（summarized）的总结并获得简明（concise）、准确（precise）的描述，这种描述就称为概念描述（concept description）。获得概念描述的方法主要有以下两种：（1）利用更为广义的属性，对所分析数据进行概要总结（data characterization）；其中被分析的数据就称为目标数据集（target class）；（2）对两类所分析的数据特点进行对比并对对比结果给出概要性总结（data discrimination）；而其中两类被分析的数据集分别被称为目标数据集和对比数据集（contrasting class）。数据概要总结（data characterization）就是利用数据描述属性中更广义的（属性）内容对其进行归纳描述。其中被分析的数据，常常可以通过简单的数据库查询来获得。如：对我校的讲师情况进行概要总结（给出概念描述）。数据概要总结通常都用更广义的关系表（generalization relations）或特征描述规则（characteristic rules）来加以输出表示。在数据集对比概要总结中所使用的挖掘方法与单一数据集概要总结所使用的方法基本相同；其结果输出形式也很类似，只是对比概要总结加入了对比描述因子以帮助区分目标数据集与对比数据集的对比情况。对比数据概要总结的输出结果也常常采用表格形式或对比规则形式（discriminate rules）来加以描述；l 关联分析关联分析（association analysis）就是从给定的数据集发现频繁出现的项集模式知识（又称为关联规则，association rules）。关联分析广泛用于市场营销、事务分析等应用领域。通常关联规则具有：形式，即“ ”；其中和均为属性值（属性值）形式。关联规则表示“数据库中的满足中条件的记录（tuples）也一定满足中的条件”。l 分类与预测分类（classification）就是找出一组能够描述数据集合典型特征的模型（或函数），以便能够分类识别未知数据的归属或类别（class），即将未知事例映射到某种离散类别之一。分类模型（或函数）可以通过分类挖掘算法从一组训练样本数据（其类别归属已知）中学习获得。分类挖掘所获的分类模型可以采用多种形式加以描述输出。其中主要的表示方法有：分类规则（IF-THEN）、决策树（decision trees）、数学公式（mathematical formulae）和神经网络。分类通常用于预测未知数据实例的归属类别（有限离散值），如一个银行客户的信用等级是属于A级、B级还是C级。但在一些情况下，需要预测某数值属性的值（连续数值），这样的分类就被称为预测（predication）。尽管预测既包括连续数值的预测，也包括有限离散值的分类；但一般还是使用预测（predication ）来表示对连续数值的预测；而使用分类来表示对有限离散值的预测。l 聚类分析聚类分析（clustering analysis）与分类预测方法明显不同之处在于，后者所学习获取分类预测模型所使用的数据是已知类别归属（class-labeled data），属于有教师监督学习方法；而聚类分析（无论是在学习还是在归类预测时）所分析处理的数据均是无（事先确定）类别归属，类别归属标志在聚类分析处理的数据集中是不存在的。究其原因很简单，它们原来就不存在，因此聚类分析属于无教师监督学习方法。聚类分析中，首先需要根据“各聚集（clusters）内部数据对象间的相似度最大化；而各聚集（clusters）对象间相似度最小化”的基本聚类分析原则，以及度量数据对象之间相似度的计算公式，将聚类分析的数据对象划分为若干组（groups）。因此一个组中数据对象间的相似度要比不同组数据对象间的相似度要大。每一个聚类分析所获得的组就可以视为是一个同类别归属的数据对象集合，更进一步从这些同类别数据集，又可以通过分类学习获得相应的分类预测模型（规则）。此外通过反复不断地对所获得的聚类组进行聚类分析，还可获得初始数据集合的一个层次结构模型。l 异类分析一个数据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。那些不符合大多数数据对象所构成的规律（模型）的数据对象就被称为异类（outlier）。之前许多数据挖掘方法都在正式进行数据挖掘之前就将这些异类作为噪声或意外而将其排除在数据挖掘的分析处理范围之内。但在一些应用场合，如各种商业欺诈行为的自动检测，小概率发生的事件（数据）往往比经常发生的事件（数据）更有挖掘价值。对异类数据的分析处理通常就称为异类挖掘。数据中的异类可以利用数理统计方法分析获得，即利用已知数据所获得的概率统计分布模型，或利用相似度计算所获得的相似数据对象分布，分析确认异类数据。而偏离检测就是从数据已有或期望值中找出某些关键测度显著的变化。l 演化分析数据演化分析（evolution analysis）就是对随时间变化的数据对象的变化规律和趋势进行建模描述。这一建模手段包括：概念描述、对比概念描述、关联分析、分类分析、时间相关数据（time-related）分析（这其中又包括：时序数据分析、序列或周期模式匹配，以及基于相似性的数据分析）五、数据挖掘结果的评估问题一：一个模式有价值的因素是什么？答：（1）易于用户理解；（2）对新数据或测试数据能够确定有效程度；（3）具有潜在价值；（4）新奇的。一个有价值的模式就是知识。此外还有一些评价模式价值的客观标准，这些标准是基于所挖掘出模式的结构或统计特征。例如对于关联规则的一个客观评价标准就是支持率（support），它表示满足相应关联规则的事务记录占总记录数的比率；尽管客观评价方法能够帮助识别一些有意义的模式知识，但也仍然需要结合一些主观评价措施方可有效反映用户的需求和兴趣。例如商场主观对描述常在商场购买商品顾客的特征模型很感兴趣；而对商场雇员的表现特征模型却兴趣不大。再者许多根据客观评价标准是有价值的模式知识却只是普通的常识知识（实际无价值）。主观价值评估标准是建立在用户对数据的信念基础上，这些评估标准基于所发现模式是否是意外的或与用户信念相左，或能够提供决策支持而确定的。而意料之中模式是有价值的则是指它能够帮助确认用户想要认可的一个假设。问题二：一个数据挖掘算法能否产生所有有价值的模式（知识）？即指数据挖掘算法的完全性。答：期望数据挖掘算法能够产生所有可能模式是不现实的。实际上一个（模式）搜索方法可以利用有趣性评价标准来帮助缩小模式的搜索范围。因此通常只需要保证挖掘算法的完全性就可以了。关联规则的挖掘算法就是这样的一个例子。问题三：一个数据挖掘算法能否只产生有价值的模式（知识）？这也是数据挖掘算法的一个最优化问题。一般当然希望数据挖掘算法仅挖掘有价值的模式（知识），但这是一个较为棘手的最优化高效搜索问题，至今尚没有好的解决方法。评估所挖掘模式的趣味性（interestingness）标准对于有效挖掘出具有应用价值数据挖掘的模式知识是十分重要的。这些标准可以直接帮助指导挖掘算法获取有实际应用价值的模式知识，以及有效摒弃无意义的模式。更为重要的是这些模式评估标准将积极指导整个知识发现过程，通过及时消除无前途的搜索路径，提高挖掘的有效性。六、数据挖掘系统分类l 根据所挖掘的数据库进行分类：如果按数据模型进行分类，就会有关系类型、事务类型、面向对象类型、对象关系类型和数据仓库类型等数据挖掘系统。如果按照所处理数据类型进行划分，就会有空间数据类型、时序数据类型、文本类型和多媒体类型等数据挖掘系统，或互联网挖掘系统。其他的系统类型还包括：异构数据挖掘系统和历史数据挖掘系统。l 根据所挖掘的知识进行分类：可以