1、数据挖掘导论数据挖掘导论Pang-ningTan,MichaelStieinbach,andVipinKumar著著PearsonEducationLTD.人民邮电出版社人民邮电出版社2022-6-8数据挖掘导论22022-6-8数据挖掘导论3主要参考书主要参考书nJiawei Han, Micheline Kamber and Jian PeinData Mining: Concepts and Techniqus (third Edition),nMonrgan Kaufmann Publishers Inc., 2012n范明范明, 孟小峰译孟小峰译n数据挖掘数据挖掘:概念与技术（第二版
2、）概念与技术（第二版）n机械工业出版社机械工业出版社, 20072022-6-8数据挖掘导论42022-6-8数据挖掘导论52022-6-8数据挖掘导论6Jiawei Hann在数据挖掘领域做出杰出贡献的郑州大学校友在数据挖掘领域做出杰出贡献的郑州大学校友韩家炜韩家炜第第1章章 绪论绪论英文幻灯片制作：英文幻灯片制作： Tan, Steinbach, Kumar中文幻灯片编译：范明中文幻灯片编译：范明2022-6-8数据挖掘导论8为什么挖掘数据？为什么挖掘数据？(商业商业)n大量数据被收集大量数据被收集,存储在数据库存储在数据库数据数据仓库中仓库中nWeb data, e-commercenp
3、urchases at department/grocery storesnBank/Credit Card transactionsn计算机越来越便宜，功能越来越计算机越来越便宜，功能越来越强大强大n竞争压力越来越大竞争压力越来越大 nProvide better, customized services for an edge (e.g. in Customer Relationship Management)2022-6-8数据挖掘导论9为什么挖掘数据？为什么挖掘数据？(科学科学)n数据以极快的速度收集和存储数据以极快的速度收集和存储 (GB/hour)nremote sensors o
4、n a satellitentelescopes scanning the skiesnmicroarrays generating gene expression datanscientific simulations generating terabytes (千兆字节千兆字节) of datan传统的技术难以处理这些传统的技术难以处理这些 raw datan数据挖掘可能帮助科学家数据挖掘可能帮助科学家nin classifying and segmenting datanin Hypothesis Formation2022-6-8数据挖掘导论10挖掘大型数据集：动机挖掘大型数据集：动机
5、n常常有些信息常常有些信息“隐藏隐藏”在数据中在数据中, 并非显而易见的并非显而易见的n人分析需要数周人分析需要数周数月数月, 才能发现有用的信息才能发现有用的信息n许多数据根本未曾分析过许多数据根本未曾分析过0500,0001,000,0001,500,0002,000,0002,500,0003,000,0003,500,0004,000,00019951996199719981999The Data Gap2022-6-8数据挖掘导论11什么是数据挖掘什么是数据挖掘n许多不同定义许多不同定义n本书定义本书定义n在大型数据存储库中，自动地发现有用信息的过程。在大型数据存储库中，自动地发现有
6、用信息的过程。 nExploration & analysis, by automatic or semi-automatic means, of large quantities of data in order to discover meaningful patternsnJiawei Han的定义的定义n从大型数据集中提取有趣的从大型数据集中提取有趣的 ( (非平凡的非平凡的, , 蕴涵的蕴涵的, , 先前未知的先前未知的并且是潜在有用的并且是潜在有用的) ) 信息或模式信息或模式n一个类似于一个类似于Jiawei Han的定义的定义nNon-trivial extraction of
7、 implicit, previously unknown and potentially useful information from data2022-6-8数据挖掘导论12什么什么( (不不) )是数据挖掘是数据挖掘l What is Data Mining?Certain names are more prevalent in certain US locations (OBrien, ORurke, OReilly in Boston area)Group together similar documents returned by search engine according
8、to their context (e.g. Amazon rainforest, A,) l What is not Data Mining? Look up phone number in phone directory Query a Web search engine for information about “Amazon”2022-6-8数据挖掘导论13数据挖掘与数据挖掘与KDDn数据挖掘与知识发现数据挖掘与知识发现 n数据挖掘是数据库中知识发现（数据挖掘是数据库中知识发现（knowledge discovery in database, KDD）不可缺少的一部分）不可缺少的一部
9、分nKDD是将未加工的数据转换为有用信息的整个过程是将未加工的数据转换为有用信息的整个过程 2022-6-8数据挖掘导论14引发数据挖掘的挑战引发数据挖掘的挑战1 n可伸缩可伸缩n海量数据集越来越普遍海量数据集越来越普遍n数千兆字节数千兆字节(terabytes)n为处理海量数据，算法必须是可伸缩的（为处理海量数据，算法必须是可伸缩的（scalable）n可伸缩可能还需要新的数据结构，以有效的方式访问个别记录可伸缩可能还需要新的数据结构，以有效的方式访问个别记录n例如，当要处理的数据不能放进内存时，可能需要非内存算法例如，当要处理的数据不能放进内存时，可能需要非内存算法n使用抽样技术或开发并行
10、和分布算法也可以提高可伸缩程度使用抽样技术或开发并行和分布算法也可以提高可伸缩程度 2022-6-8数据挖掘导论15挑战挑战2n高维性高维性n具有数以百计或数以千计属性的数据集具有数以百计或数以千计属性的数据集 n生物信息学：涉及数千特征的基因表达数据生物信息学：涉及数千特征的基因表达数据 n不同地区温度测量：维度（特征数）的增长正比于测量的次数不同地区温度测量：维度（特征数）的增长正比于测量的次数 n为低维数据开发的数据分析技术不能很好地处理高维数据为低维数据开发的数据分析技术不能很好地处理高维数据 n某些数据分析算法，随着维度（特征数）的增加，计算复杂性迅速某些数据分析算法，随着维度（特征
11、数）的增加，计算复杂性迅速增加增加 2022-6-8数据挖掘导论16挑战挑战3n异种数据和复杂数据异种数据和复杂数据n传统的数据分析方法只处理包含相同类型属性的数据集传统的数据分析方法只处理包含相同类型属性的数据集n非传统的数据类型的出现需要能够处理异种属性的技术非传统的数据类型的出现需要能够处理异种属性的技术n半结构化文本和超链接的半结构化文本和超链接的Web页面集页面集n具有序列和三维结构的具有序列和三维结构的DNA数据数据n地球表面不同位置上的时间序列测量值（温度、气压等）的气地球表面不同位置上的时间序列测量值（温度、气压等）的气象数据象数据n数据中的联系数据中的联系n如时间和空间的自相
12、关性、图的连通性、半结构化文本和如时间和空间的自相关性、图的连通性、半结构化文本和XML文档中元素之间的父子联系文档中元素之间的父子联系 2022-6-8数据挖掘导论17挑战挑战4n数据的所有权与分布数据的所有权与分布 n数据地理上分布在属于多个机构的资源中数据地理上分布在属于多个机构的资源中n需要开发分布式数据挖掘技术需要开发分布式数据挖掘技术n分布式数据挖掘算法面临的主要挑战包括分布式数据挖掘算法面临的主要挑战包括n(1) 如何降低执行分布式计算所需的通信量？如何降低执行分布式计算所需的通信量？n(2) 如何有效地统一从多个资源得到的数据挖掘结果？如何有效地统一从多个资源得到的数据挖掘结果
13、？n(3) 如何处理数据安全性问题？如何处理数据安全性问题？ 2022-6-8数据挖掘导论18挑战挑战5n非传统的分析非传统的分析n传统的统计学方法：假设传统的统计学方法：假设-检验模式检验模式n提出一种假设，设计实验来收集数据，然后针对假设分析数据提出一种假设，设计实验来收集数据，然后针对假设分析数据n当前的数据分析任务常常需要产生和评估数以千计的假设当前的数据分析任务常常需要产生和评估数以千计的假设n希望自动地产生和评估假设导致了一些数据挖掘技术的开发希望自动地产生和评估假设导致了一些数据挖掘技术的开发n数据挖掘所分析的数据集通常不是精心设计的实验的结果数据挖掘所分析的数据集通常不是精心设
14、计的实验的结果n代表数据的时机性样本（代表数据的时机性样本（opportunistic sample）而不是随机样本）而不是随机样本（random sample）n数据集常常涉及非传统的数据类型和数据分布数据集常常涉及非传统的数据类型和数据分布 2022-6-8数据挖掘导论19数据挖掘的起源数据挖掘的起源 n数据挖掘是多学科交叉领域数据挖掘是多学科交叉领域n利用了来自如下一些领域的思想：利用了来自如下一些领域的思想：n统计学的抽样、估计和假设统计学的抽样、估计和假设检验检验n人工智能、模式识别和机器人工智能、模式识别和机器学习的搜索算法、建模技术学习的搜索算法、建模技术和学习理论和学习理论n数
15、据库系统提供有效的存储、数据库系统提供有效的存储、索引和查询处理支持索引和查询处理支持 n分布式技术也能帮助处理海分布式技术也能帮助处理海量数据量数据n最优化、进化计算、信息论、最优化、进化计算、信息论、信号处理、可视化和信息检信号处理、可视化和信息检索索 Machine Learning/Pattern RecognitionStatistics/AIData MiningDatabase systems2022-6-8数据挖掘导论20 数据挖掘任务数据挖掘任务 n预测预测vs.描述描述n预测预测(Prediction)n根据其他属性的值，预测特定属性的值根据其他属性的值，预测特定属性的值
16、n描述描述(Description)n导出概括数据中潜在联系的模式导出概括数据中潜在联系的模式 2022-6-8数据挖掘导论21数据挖掘任务数据挖掘任务n分类（分类（Classification） Predictiven回归（回归（Regression） Predictiven关联规则发现（关联规则发现（Association Rule Discovery） Descriptiven序列模式发现（序列模式发现（Sequential Pattern Discovery） Descriptiven聚类（聚类（Clustering） Descriptiven异常异常/偏差检测（偏差检测（Anomal
17、y/Deviation Detection） Predictive2022-6-8数据挖掘导论22分类分类: :定义定义n给定一批记录给定一批记录-训练集训练集 (training set )nEach record contains a set of attributes, one of the attributes is the class label (类标号类标号) .n任务任务: 建立一个模型建立一个模型(model )n类标号属性是其他属性值的函数类标号属性是其他属性值的函数n目标目标: previously unseen records should be assigned a
18、class as accurately as possible.nA test set (检验集检验集) is used to determine the accuracy of the model. nUsually, the given data set is divided into training and test sets, with training set used to build the model and test set used to validate it2022-6-8数据挖掘导论23分类分类: :例子例子TidRefundMaritalStatusTaxable
19、IncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10categoricalcategoricalcontinuousclassRefundMaritalStatusTaxableIncomeCheatNoSingle75K?YesMarried50K?NoMarried150K?YesDivorced90K
20、?NoSingle40K?NoMarried80K?10TestSetTraining SetModelLearn Classifier2022-6-8数据挖掘导论24分类分类: :应用应用1 1nDirect MarketingnGoal: nReduce cost of mailing by targeting a set of consumers likely to buy a new cell-phone product.nApproach:nUse the data for a similar product introduced before. nWe know which cus
21、tomers decided to buy and which decided otherwise. This buy, dont buy decision forms the class attribute.nCollect various demographic, lifestyle, and company-interaction related information about all such customers.nType of business, where they stay, how much they earn, etc.nUse this information as
22、input attributes to learn a classifier model.2022-6-8数据挖掘导论25分类分类: :应用应用2 2nFraud DetectionnGoal: nPredict fraudulent cases in credit card transactions.nApproach:nUse credit card transactions and the information on its account-holder as attributes.nWhen does a customer buy, what does he buy, how oft
23、en he pays on time, etcnLabel past transactions as fraud or fair transactions. This forms the class attribute.nLearn a model for the class of the transactions.nUse this model to detect fraud by observing credit card transactions on an account.2022-6-8数据挖掘导论26分类分类: :应用应用3 3nSky Survey CatalogingnGoal
24、: To predict class (star or galaxy) of sky objects, especially visually faint ones, based on the telescopic survey images (from Palomar Observatory).n3000 images with 23,040 x 23,040 pixels per image.nApproach:nSegment the image. nMeasure image attributes (features) - 40 of them per object.nModel th
25、e class based on these features.nSuccess Story: Could find 16 new high red-shift quasars, some of the farthest objects that are difficult to find!2022-6-8数据挖掘导论27分类分类: :应用应用3 3Attributes: Image features, Characteristics of light waves received, etc.EarlyIntermediateLateData Size: 72 million stars, 2
26、0 million galaxies Object Catalog: 9 GB Image Database: 150 GB Class: Stages of FormationCourtesy: http:/aps.umn.edu2022-6-8数据挖掘导论28回归回归n回归回归(regression)nPredict a value of a given continuous valued variable based on the values of other variables, assuming a linear or nonlinear model of dependency.n
27、Greatly studied in statistics, neural network fields.nExamples:nPredicting sales amounts of new product based on advertising expenditure.nPredicting wind velocities as a function of temperature, humidity, air pressure, etc.nTime series prediction of stock market indices2022-6-8数据挖掘导论29关联规则关联规则:定义定义n
28、关联规则关联规则(association rule)nGiven a set of records each of which contain some number of items from a given collection;nProduce dependency rules which will predict occurrence of items based on occurrences of other items.TIDItems1Bread, Coke, Milk2Beer, Bread3Beer, Coke, Diaper, Milk4Beer, Bread, Diape
29、r, Milk5Coke, Diaper, MilkRules Discovered: Milk - Coke Diaper, Milk - Beer2022-6-8数据挖掘导论30关联规则关联规则:应用应用1nMarketing and Sales Promotion:nLet the rule discovered be Bagels, - Potato ChipsnPotato Chips as consequent = Can be used to determine what should be done to boost its sales.nBagels in the antec
30、edent = Can be used to see which products would be affected if the store discontinues selling bagels.nBagels in antecedent and Potato chips in consequent = Can be used to see what products should be sold with Bagels to promote sale of Potato chips!2022-6-8数据挖掘导论31关联规则关联规则:应用应用2nSupermarket shelf man
31、agement.nGoal: nTo identify items that are bought together by sufficiently many customers.nApproach: nProcess the point-of-sale data collected with barcode scanners to find dependencies among items.nA classic rule -nIf a customer buys diaper and milk, then he is very likely to buy beer.nSo, dont be
32、surprised if you find six-packs stacked next to diapers!2022-6-8数据挖掘导论32聚类聚类: 定义定义nGiven a set of data points, each having a set of attributes, and a similarity measure among them, find clusters such thatnData points in one cluster are more similar to one another.nData points in separate clusters ar
33、e less similar to one another.nSimilarity Measures:nEuclidean Distance if attributes are continuous.nOther Problem-specific MeasuresIntracluster distancesare minimizedIntercluster distancesare maximized2022-6-8数据挖掘导论33聚类聚类: 应用应用1nMarket Segmentation:nGoal: nsubdivide a market into distinct subsets o
34、f customers where any subset may conceivably be selected as a market target to be reached with a distinct marketing mix.nApproach: nCollect different attributes of customers based on their geographical and lifestyle related information.nFind clusters of similar customers.nMeasure the clustering qual
35、ity by observing buying patterns of customers in same cluster vs. those from different clusters. 2022-6-8数据挖掘导论34聚类聚类: 应用应用2nDocument Clustering:nGoal: nTo find groups of documents that are similar to each other based on the important terms appearing in them.nApproach: nTo identify frequently occurr
36、ing terms in each document. Form a similarity measure based on the frequencies of different terms. Use it to cluster.nGain:n Information Retrieval can utilize the clusters to relate a new document or search term to clustered documents2022-6-8数据挖掘导论35文档聚类文档聚类: 例例nClustering Points: 3204 Articles of L
37、os Angeles Times.nSimilarity Measure: nHow many words are common in these documents (after some word filtering).CategoryTotalArticlesCorrectlyPlacedFinancial555364Foreign341260National27336Metro943746Sports738573Entertainment3542782022-6-8数据挖掘导论36异常检测异常检测n任务：识别其特征显著不同于其他数据的观测值任务：识别其特征显著不同于其他数据的观测值n这
38、样的观测值称为异常点（这样的观测值称为异常点（anomaly）或离群点（）或离群点（outlier）n发现真正的异常点，而避免错误地将正常的对象标注为异常点发现真正的异常点，而避免错误地将正常的对象标注为异常点n应用应用n信用卡欺诈检测信用卡欺诈检测n网络入侵检测网络入侵检测数据挖掘的应用数据挖掘的应用2022-6-8数据挖掘导论38数据挖掘的应用数据挖掘的应用n数据库分析和决策支持数据库分析和决策支持n市场分析和管理市场分析和管理n针对销售针对销售(target marketing), 顾客关系管理顾客关系管理, 购物篮分析购物篮分析, 交叉销交叉销售售(cross selling), 市场
39、分割市场分割(market segmentation)n风险分析与管理风险分析与管理n预测预测, 顾客关系顾客关系, 改进保险改进保险, 质量控制质量控制, 竞争能力分析竞争能力分析n欺骗检测与管理欺骗检测与管理n其它应用其它应用n文本挖掘文本挖掘 (新闻组新闻组, email, 文档资料文档资料)n流数据挖掘流数据挖掘(Stream data mining)nWeb挖掘挖掘.nDNA 数据分析数据分析2022-6-8数据挖掘导论39市场分析与管理市场分析与管理(1)n用于分析的数据源在哪用于分析的数据源在哪?n信用卡交易信用卡交易, 会员卡会员卡, 打折优惠卷打折优惠卷, 顾客投诉电话顾客投
40、诉电话, (公共公共) 生活时尚研生活时尚研究究n针对销售针对销售(Target marketing)n找出顾客群找出顾客群, 他们具有相同特征他们具有相同特征 : 兴趣兴趣, 收入水平收入水平, 消费习惯消费习惯, 等等.n确定顾客随时间变化的购买模式确定顾客随时间变化的购买模式n个人帐号到联合帐号的转变个人帐号到联合帐号的转变: 结婚结婚, 等等.n交叉销售分析交叉销售分析(Cross-market analysis)n产品销售之间的关联产品销售之间的关联/相关相关 n基于关联信息的预测基于关联信息的预测2022-6-8数据挖掘导论40市场分析与管理市场分析与管理(2)n顾客分类顾客分类(
41、Customer profiling)n数据挖掘能够告诉我们什么样的顾客买什么产品数据挖掘能够告诉我们什么样的顾客买什么产品(聚类或分类聚类或分类)n识别顾客需求识别顾客需求n对不同的顾客识别最好的产品对不同的顾客识别最好的产品n使用预测发现什么因素影响新顾客使用预测发现什么因素影响新顾客n提供汇总信息提供汇总信息n各种多维汇总报告各种多维汇总报告n统计的汇总信息统计的汇总信息 (数据的中心趋势和方差数据的中心趋势和方差)2022-6-8数据挖掘导论41法人分析和风险管理法人分析和风险管理n财经规划和资产评估财经规划和资产评估n现金流分析和预测现金流分析和预测n临时提出的资产评估临时提出的资产
42、评估n交叉组合交叉组合(cross-sectional) 和时间序列分析和时间序列分析 (金融比率金融比率(financial-ratio), 趋势分析趋势分析, 等等.)n资源规划资源规划 :n资源与开销的汇总与比较资源与开销的汇总与比较n竞争竞争:n管理竞争者和市场指导管理竞争者和市场指导n对顾客分类和基于类的定价对顾客分类和基于类的定价n在高度竞争的市场调整价格策略在高度竞争的市场调整价格策略2022-6-8数据挖掘导论42欺骗检测和管理欺骗检测和管理(1)n应用应用n广泛用于健康照料广泛用于健康照料, 零售零售, 信用卡服务信用卡服务, 电讯电讯 (电话卡欺骗电话卡欺骗), 等等.n方
43、法方法n使用历史数据建立欺骗行为模型使用历史数据建立欺骗行为模型, 使用数据挖掘帮助识别类似的实例使用数据挖掘帮助识别类似的实例n例例n汽车保险汽车保险: 检测这样的人检测这样的人, 他他/她假造事故骗取保险赔偿她假造事故骗取保险赔偿n洗钱洗钱: 检测可疑的金钱交易检测可疑的金钱交易 (US Treasurys Financial Crimes Enforcement Network) n医疗保险医疗保险 : 检测职业病患者检测职业病患者, 医生和介绍人圈医生和介绍人圈2022-6-8数据挖掘导论43欺骗检测和管理欺骗检测和管理(2)n检测不适当的医疗处置检测不适当的医疗处置n澳大利亚健康保险
44、会澳大利亚健康保险会(Australian Health Insurance Commission) 发发现许多全面的检查是请求做的现许多全面的检查是请求做的, 而不是实际需要的而不是实际需要的 (每年节省每年节省100万万澳元澳元).n检测电话欺骗检测电话欺骗n电话呼叫模式电话呼叫模式: 通话距离通话距离, 通话时间通话时间, 每天或每周通话次数每天或每周通话次数. 分析偏离分析偏离期望的模式期望的模式.n英国电讯英国电讯(British Telecom)识别频繁内部通话的呼叫者的离散群识别频繁内部通话的呼叫者的离散群, 特特别是移动电话别是移动电话, 超过数百万美元的欺骗超过数百万美元的欺
45、骗. n零售零售n分析家估计分析家估计, 38%的零售业萎缩是由于不忠诚的雇员造成的的零售业萎缩是由于不忠诚的雇员造成的.2022-6-8数据挖掘导论44其它应用其它应用n运动运动nIBM Advanced Scout分析分析NBA的统计数据的统计数据 ( 阻挡投篮阻挡投篮, 助攻助攻, 和犯规和犯规 ) 获得了对纽约小牛队获得了对纽约小牛队(New York Knicks)和迈艾米热队和迈艾米热队( Miami Heat )的竞争优势的竞争优势n天文天文n借助于数据挖掘的帮助借助于数据挖掘的帮助,JPL 和和 Palomar Observatory 发现了发现了22 颗类颗类星体星体(qua
46、sars)nInternet Web Surf-AidnIBM Surf-Aid 将数据挖掘算法用于有关交易的页面的将数据挖掘算法用于有关交易的页面的Web访问日志访问日志, 以发现顾客喜爱的页面以发现顾客喜爱的页面, 分析分析Web 销售的效果销售的效果, 改进改进Web 站点的组织站点的组织, 等等.2022-6-8数据挖掘导论45数据挖掘界简史数据挖掘界简史n1989 IJCAI Workshop on Knowledge Discovery in Databases (Piatetsky-Shapiro)nKnowledge Discovery in Databases (G. Pia
47、tetsky-Shapiro and W. Frawley, 1991)n1991-1994 Workshops on Knowledge Discovery in DatabasesnAdvances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)n1995-1998 International Conferences on Knowledge Discovery in Databases and Data Mining (K
48、DD95-98)nJournal of Data Mining and Knowledge Discovery (1997)n1998 ACM SIGKDD, SIGKDD1999-2001 conferences, and SIGKDD ExplorationsnMore conferences on data miningnPAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, etc.2022-6-8数据挖掘导论46参考文献源参考文献源nData mining and KDD (SIGKDD member CDROM):nConference procee
49、dings: KDD, and others, such as PKDD, PAKDD, etc.nJournal: Data Mining and Knowledge DiscoverynDatabase field (SIGMOD member CD ROM):nConference proceedings: ACM-SIGMOD, ACM-PODS, VLDB, ICDE, EDBT, DASFAAnJournals: ACM-TODS, J. ACM, IEEE-TKDE, JIIS, etc.nAI and Machine Learning:nConference proceedin
50、gs: Machine learning, AAAI, IJCAI, etc.nJournals: Machine Learning, Artificial Intelligence, etc.nStatistics:nConference proceedings: Joint Stat. Meeting, etc.nJournals: Annals of statistics, etc.nVisualization:nConference proceedings: CHI, etc.nJournals: IEEE Trans. visualization and computer graph
