《数据挖掘常用算法概述ppt.ppt》由会员分享，可在线阅读，更多相关《数据挖掘常用算法概述ppt.ppt（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关联分析关联规则挖掘的提出l 关联规则挖掘的典型案例：购物篮问题l 在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将所购买的商品放入到自己的购物篮中。l 通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯l 哪些物品经常被顾客购买？l 同一次购买中，哪些商品经常会被一起购买？l 一般用户的购买过程中是否存在一定的购买时间序列？l 具体应用：利润最大化l 商品货架设计：更加适合客户的购物路径l 货存安排：实现超市的零库存管理l 用户分类：提供个性化的服务其他典型应用l 相关文献的收集l 购物篮=文档（Document）l 项 目=单词（Word）l 相关网站的收集l 购物篮
2、=词句（Sentences）l 项 目=链接文档（Document）什么是关联规则挖掘?l 关联规则挖掘l 简单的说，关联规则挖掘发现大量数据中项集之间有趣的关联l 在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。l 应用l 购物篮分析、交叉销售、产品目录设计、loss-leaderanalysis、聚集、分类等。关联规则挖掘形式化定义l 给定:l 交易数据库l 每笔交易是：一个项目列表(消费者一次购买活动中购买的商品)l 查找:l 所有描述一个项目集合与其他项目集合相关性的规则l 应用l*护理用品(商店应该怎样提高护理用品的销售？)
3、l 家用电器*(其他商品的库存有什么影响?)l 在产品直销中使用附加邮寄其它相关概念l 包含k 个项目的集合，称为k-项集l 项集的出现频率是包含项集的事务个数，称为项集的频率、支持计数或者计数l 关联规则的基本形式：前提条件 结论 支持度,置信度l buys(x,“diapers”)buys(x,“beers”)0.5%,60%l major(x,“CS”)takes(x,“DB”)grade(x,“A”)1%,75%关联规则兴趣度的度量值：支持度l 推导出的数据间的相关性可称为规则（或模式），对规则兴趣度的描述采用支持度、置信度概念。l 支持度（Support）：规则X Y 在交易数据库D
4、 中的支持度是交易集中包含X 和Y 的交易数与所有交易数之比，记为support(X Y)，即support(X Y)=|T:X Y T，T D|/|D|，它是概率P（X Y），具体表示为：S S=总交易数 总交易数同时包含项目集 同时包含项目集X X 和 和 Y Y 的交易数 的交易数购买商品Y的交易同时购买商品X和Y的交易购买商品X的交易关联规则兴趣度的度量值：置信度l 置信度（Confidence），规则X Y 在交易集中的置信度是指包含X 和Y 的交易数与包含X 的交易数之比，记为confidence(X Y)，即confidence(X Y)=|T:X Y T，T D|/|T:X T
5、，T D|，它是概率P（X|Y），具体表示为：l 最小支持度和最小置信度用户（分析员）不关心可信程度太低的规则，因而用户需要输入两个参数：最小支持度和最小置信度。C C=购买商品 购买商品X X的交易数 的交易数同时购买商品 同时购买商品X X和 和Y Y的交易数 的交易数购买商品Y的交易同时购买商品X和Y的交易购买商品X的交易支持度和置信度举例l 零售商场销售分析：l 数据项为商品，记录集合为交易记录集合l 规则为：“购买商品X 的顾客，同时购买商品Y”，即X Y；l 设最小支持度为0.3；最小置信度也为0.3。l 分析结果：频繁项集及其基本特征l 频繁项集的定义l 如果项集满足最小支持度，
6、则称之为频繁项集（高频项集）l 频繁项集的基本特征l 任何频繁项集的子集均为频繁项集。例如：ABC 是频繁项集，则AB、AC、BC 均为频繁项集l 在数据库表分区的情况下，一个项集是频繁的，则至少在一个分区内是频繁的关联规则挖掘的种类l 布尔vs.数值型关联(基于 处理数据的类型)l 性别“女”职业“秘书”1%,75%布尔型关联规则l 性别“女”收入=20001%,75%数值型关联规则l 单维vs.多维 关联l age(x,“30.39”)income(x,“42.48K”)buys(x,“PC”)1%,75%l buys(x,“Book”)buys(x,“Pen”)buys(x,“Ink”)
7、1%,75%l 单层vs.多层 分析l 那个品种牌子的啤酒与那个牌子的尿布有关系?l 各种扩展l 相关性、因果分析l 关联并不一定意味着相关或因果l 最大模式和闭合相集l 添加约束l 如,哪些“小东西”的销售促发了“大家伙”的买卖？关联规则挖掘的基本过程l 找出所有的频繁项集F，其中对于任何的Z F，在交易集合D 中至少s%的事务包含Zl 根据置信度和频繁项集F,产生关联规则。具体方法如下：l conf(X Y)=supp(X)/supp(X Y)l 如果conf(X Y)c 成立，则产生X Y 的规则,因为:l supp(X Y)=supp(X Y)s 且l conf(X Y)cl 因此关联
8、规则的挖掘可以转换为频繁项集的挖掘和频繁项集之间的关联。关联规则挖掘：一个例子l 对于A C：l support=support(A、C)=50%l confidence=support(A、C)/support(A)=66.6%l 最小值尺度 50%l 最小可信度 50%关联规则挖掘的优缺点l 优点l 它可以产生清晰有用的结果l 它支持间接数据挖掘l 可以处理变长的数据l 它的计算的消耗量是可以预见的l 缺点l 当问题变大时，计算量增长得厉害l 难以决定正确的数据l 容易忽略稀有的数据查找频繁项集Apriori算法l 查找具有最小支持度的频繁项集是关联规则挖掘最为重要的步骤l Apriori
9、 算法是目前最有影响力的一个算法，在1994 年，由R.Agrawal,S.Srikant 提出l 该算法基于频繁项集的特征：如果项集l=i1,i2,in 是频繁的，当且仅当项集的所有子集均为频繁项集.也就是说，如果supp(l)s，当且仅当supp(l)s,l ll 因此，我们可以采用层次顺序的方法来实现频繁项集的挖掘。首先，挖掘一阶频繁项集L1。在此基础上，形成二阶候选项集，挖掘二阶频繁项集。依此类推。Apriori算法l 连接:用Lk-1自连接得到Ckl 剪枝:一个k-项集，如果它的一个k-1 项集（它的子集）不是频繁的，那他本身也不可能是频繁的。l 伪代码:l Ck:长度为k 的候选项
10、集l Lk:长度为k 的频繁项集l L1=frequentitems;for(k=1;Lk!=;k+)dobeginCk+1=从Lk生成候选项集;对于数据库中的任一交易tdo 如果t 中包含Ck+1中所包含的项集，则计数加1Lk+1=Ck+1 中超过最小支持度的频繁项集endreturn kLk;Apriori算法 例子数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 DApriori 够快了吗?性能瓶颈l Apriori 算法的核心:l 用频繁的(k1)-项集生成候选的频繁k-项集l 用数据库扫描和模式匹配计算候选集的支持度l Apriori 的瓶颈:候选集生成l 巨大的候选集:l
11、 104 个频繁1-项集要生成107 个候选2-项集，并且累计和检查它们的频繁性l 要找长度为100 的频繁模式，如a1,a2,a100,你必须先产生2100 1030 个候选集l 重复扫描数据库：l 如果最长的模式是n 的话，则需要(n+1)次数据库扫描关联规则结果显示(Table Form)关联规则可视化Using Rule Graph扩展知识：多层关联规则l 项通常具有层次l 底层的项通常支持度也低l 某些特定层的规则可能更有意义l 交易数据库可以按照维或层编码l 可以进行共享的多维挖掘食品面包牛奶脱脂奶光明 统一酸奶 白黄扩展知识：多维关联规则l 单维关联规则（维内关联规则）l 关联规
12、则中仅包含单个谓词（维）l 通常针对的是事务数据库buys(X,“milk”)buys(X,“bread”)l 多维关联规则：规则内包含2 个以上维/谓词l 维间关联规则(不重复谓词)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)l 混合维关联规则(存在重复谓词)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)分类与预测本章内容l 分类与预测的基本概念l 决策树分类l 实例：移动通信客户流失分析系统l 神经网络l 其他分类方法l 预测（回归）建立模型过程历史数据模型建模记录集合预测数学公式规则集合
13、l 分类l 为一个事件或对象进行归类l 预测分类标签（离散值）l 基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据进行分类l 分类模型：分类器（分类函数、分类规则等）l 预测:l 对连续或者有序的值进行建模和预测（回归方法）l 典型应用l 客户/用户分类l 信用评分l 目标营销l 医疗诊断l 分类和预测分类的相关概念l 训练集（TrainingSet）：由一组数据库记录或者元组构成，每个记录由有关字段值组成特征向量，这些字段称为属性。l 用于分类的属性称为标签属性。标签属性也就是训练集的类别标记。l 标签属性的类型必须是离散的，而且标签属性的可能值的数目越少越好。分类的两
14、个步骤l 模型创建:对一个已经事先确定的类别创建模型l 每个元组属于一个事先确定的类别，使用分类标签属性予以确定l 用于创建模型的数据集叫:训练集。单个元组称为训练样本l 模型可以用分类规则，决策树，或者数学方程的形式来表达。l 模型使用:用创建的模型预测未来或者类别未知的记录l 估计模型的准确率l 使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较l 准确率：l 测试集和训练集是独立的。分类过程：模型创建（学习过程）训练集分类算法IF rank=professorOR years 6THEN tenured=yes 模型分类过程:使用模型模型测试集未知数据(Jeff,Profes
15、sor,4)Tenured?本章内容l 分类与预测的基本概念l 决策树分类l 实例：移动通信客户流失分析系统l 神经网络l 其他分类方法l 预测（回归）使用决策树进行分类l 决策树l 一个树型的结构l 内部节点上选用一个属性进行分裂（决策节点）l 每个分叉都是分裂的一个部分l 叶子节点表示一个分布l 节点的子节点个数跟算法相关age?student?credit rating?no yes fair excellent40no no yesyesyes30.40决策树分类的特点l 优点l 容易生成可以理解的规则l 计算量相对来说不大l 可以处理离散和连续字段l 可以清晰显示哪些字段比较重要l
16、缺点l 对连续性的字段难以预测l 类别太多的时候，错误的可能性会加大l 一般情况下，标签属性的个数有限决策树的生成与使用l 决策树生成算法分成两个步骤l 树的生成l 开始，数据都在根节点l 递归的进行数据分割l 树的修剪l 去掉一些可能是噪音或者异常的数据l 决策树使用:对未知数据进行分割l 按照决策树上采用的分割属性逐层往下，直到一个叶子节点训练集ID3算法决策树结果：“buys_computer”age?overcaststudent?credit rating?no yesfairexcellent40no no yes yesyes30.40决策树算法l 基本算法（贪心算法）l 自上而
17、下分而治之的方法l 开始时，所有的数据都在根节点l 属性都是种类字段(如果是连续的，将其离散化)l 所有记录用所选属性递归的进行分割l 属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)l 停止分割的条件l 一个节点上的数据都是属于同一个类别l 没有属性可以再用于对数据进行分割几种经典算法介绍l CARTl min(P(c1),P(c2)l 2P(c1)P(c2)l P(c1)logP(c1)+P(c2)logP(c2)C4.5(ID3)l C4.5(ID3)l 对种类字段处理时，缺省是对每个值作为一个分割l Gain和GainRatiol CHAIDl 在
18、Overfitting前停止树的生成l 必须都是分类属性l 选择分割。X2检验从树中生成分类规则l 用IF-THEN这种形式来表现规则l 每个叶子节点都创建一条规则l 每个分割都成为一个规则中的一个条件l 叶子节点中的类别就是Then的内容l 规则对于人来说更容易理解l 例子l IFage=“=30”ANDstudent=“no”THENbuys_computer=“no”l IFage=“40”ANDcredit_rating=“excellent”THENbuys_computer=“yes”l IFage=“=30”ANDcredit_rating=“fair”THENbuys_comp
19、uter=“no”本章内容l 分类与预测的基本概念l 决策树分类l 实例：移动通信客户流失分析系统l 神经网络l 其他分类方法l 预测（回归）应用背景与问题定义l 背景l 在移动通信领域，客户流失成为通信运营企业关注的焦点l 通信业务产生的海量、珍贵数据为数据挖掘的研究提供了坚实的基础l 把数据挖掘理论应用于移动通信领域的客户流失分析，进而为通信企业的实际业务提供指导是一项具有挑战性的工作l 定义l 客户流失分析，就是利用数据挖掘等分析方法，对已流失客户过去一段时间的通话、缴费等信息进行分析，提炼出流失客户的行为特征，利用这些特征预测在网客户的流失倾向 按真实比例抽取，可能掩盖流失用户的特征
20、解决方法：“样本放大”数据预处理抽样分割抽样原始数据（流失概率3.2%）抽样采样后（流失概率25%）合并10,000310,000300,00050%20:15,00015,00020,000流失非流失数据预处理时间相关属性属性序列S1用户标识性别年龄入网品牌 1月份通话时长2月份通话时长 6月份通话时长 1月份话费 6月份话费 是否流失属性序列Sn“静态”属性 流失标志解决方法：生成汇总属性（求和、取均值等）生成“趋势属性”，如由属性序列S1生成属性“通话时长趋势”问题：决策树算法缺乏处理时间相关属性的能力，致使效率下降数据预处理生成趋势属性把每个月通话时长Y视为月份X（取值从1到6）的线性
21、函数，即Y=+X，系数作为属性“通话时长趋势”的取值，从而把求趋势属性的问题转化为简单的线形回归问题，数据预处理生成趋势属性（续）实际应用中，发现各个月份的数值对趋势属性的影响不同，可以对各个月份指定不同的权重w作为新生成的趋势属性，可以进一步转换成离散值，如，显著上升、小幅上升、持平、小幅下降、显著下降例如：1到6月份权重分别取1、1、1、2、3、4决策树示例通话次数=20品牌话费金额神州行 全球通 流失=25 流失 非流失 非流失用户ID通话次数 品牌 话费金额 流失标志139*884 23全球通23品牌 非流失神州行 全球通第一步：建立决策树第二步：预测流失20,80 0.2通话次数=2
22、0品牌消费金额神州行10,30 0.25 10,50 0.167全球通2,23 0.088,7 0.53=254,36 0.1品牌6,14 0.3神州行全球通1,8 0.115,6 0.45Cx,y k%x:流失用户数y:未流失用户数k:流失概率 k=x/(x+y)A决策树算法数据结构主要内容l 分类与预测的基本概念l 决策树分类l 实例：移动通信客户流失分析系统l 神经网络l 其他分类方法l 预测（回归）神经网络技术l 生物神经系统的计算模拟(实际上是一个很好的学习系统的例子)l 海量并行计算技术使得性能大大提高l 最早的神经网络算法为 1959由Rosenblatt提出l 基本结构神经元结
23、构 k-f加权和 输入向量X输出 y激活函数 权重向量 ww0w1wnx0 x1xn多层感知系统Output nodesInput nodesHidden nodesOutput vectorInput vector:xiwij计算实例l 一个训练样本X=1,0,1,输出为1l X1=1,x2=0,x3=1,w14=0.2,w15=-0.3,w24=0.4,w25=0.1,w34=-.5,w35=0.2,w46=-0.3,w56=-0.2,l 偏置值:节点4:-0.4,节点5:0.2,节点6:0.1l 学习率设为0.9l 节点4:输入值:w14*x1+w24*x2+w34*x3+节点4的偏置=
24、1*0.2+0.4*0-0.5*1-0.4=-0.7输出值:可得0.332l 同理:节点5输入值0.1,输出值0.525l 节点6:输入值:w46*o4+w56*o5+节点6的偏置=-0.3*0.332-0.2*0.525+0.1=-0.105输出值:0.474计算实例误差计算l 节点6:0.474*(1-0.474)*(1-0.474)=0.1311l 节点5:0.525*(1-0.525)*0.1311*(-0.2)=-0.0065l 同理节点4误差为:-0.0087更新权值和偏置值l W46:-0.3+(0.9)(0.1311)(0.332)=-0.261l 其他Wij同理l 节点6的偏
25、置:0.1+(0.9)*(0.1311)=0.218l 其他偏置同理终止条件l 对所有样本作一次扫描称为一个周期l 终止条件:对前一周期所有Wij的修改值都小于某个指定的阈值;或超过预先指定的周期数.l 防止训练过度前馈神经网络l 前馈网络的表达能力l 布尔函数。任何布尔函数可以被具有两层单元的网络准确表示，尽管对于最坏的情况，所需隐藏单元的数量随着网络输入数量的增加指数级增长。l 连续函数。任何有界的连续函数可以由一个两层的网络以任意小的误差逼近。这个理论适用于隐藏层使用sigmoid单元、输出层使用（非阈值的）线性单元的网络。所需的隐藏单元数量依赖于要逼近的函数。l 任意函数。任意函数可以
26、被一个有三层单元的网络以任意精度逼近。与前面相同，输出层使用线性单元，两个隐藏层使用sigmoid单元，每一层所需的单元数量一般不确定。神经网络特点l 优点l 有很强的非线性拟合能力，可映射任意复杂的非线性关系。l 学习规则简单，便于计算机实现。l 具有很强的鲁棒性、记忆能力以及强大的自学习能力。l 缺点l 最严重的问题是没能力来解释自己的推理过程和推理依据。l 不能向用户提出必要的询问，而且当数据不充分的时候，神经网络就无法进行工作。l 把一切问题的特征都变为数字，把一切推理都变为数值计算，其结果势必是丢失信息。l 理论和学习算法还有待于进一步完善和提高。应用l 适合神经网络学习的问题 l
27、实例是用很多“属性-值”对表示的。l 目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量。l 训练数据可能包含错误。l 可容忍长时间的训练。l 可能需要快速求出目标函数值。l 人类能否理解学到的目标函数是不重要的。实验l 使用Clementine 进行神经网络分类挖掘（工具使用参见补充教材）主要内容l 分类与预测的基本概念l 决策树分类l 实例：移动通信客户流失分析系统l 神经网络l 其他分类方法l 预测（回归）其它分类方法l 贝叶斯（Bayesian）分类l k-临近分类l 基于案例的推理l 遗传算法l 粗糙集理论l 模糊集方法分类的准确性：评估错误率l 数据分区:训练
28、-测试数据l 将一个数据集合分成两个独立的数据集。例如：训练数据(2/3),测试数据(1/3)l 通常应用于大量数据样本的数据集l 交叉验证l 将一个数据集合分成若干个子样本集l 用k-1个子样本作为训练数据，1个子样本作为测试数据l 每一个数据集合具有合适的宽度分类的准确性：混淆矩阵l 混淆矩阵（confusionmatrix）用来作为分类规则特征的表示，它包括了每一类的样本个数，包括正确的和错误的分类。l 主对角线给出了每一类正确分类的样本的个数，非对角线上的元素则表示未被正确分类的样本个数实际的类预测的类A类 B类 C类 总计A类 45 2 3 50B类 10 38 2 50C类 4 6
29、 40 50总计59 46 45 1503 个类的混淆矩阵分类的准确性：收益图查全率分析图：X轴：按离网倾向评分从大到小排序后的客户占目标客户人数的百分比；Y轴：前x%的客户中被准确预测为离网的客户占目标客户中离网总人数的百分比，即查全率。Lift分析图：X轴：按离网倾向评分从大到小排序后的客户占目标客户人数的百分比；Y轴：命中率的提升倍数。聚类分析聚类分析l 什么是聚类分析?l 划分方法（PartitioningMethods）l 分层方法l 基于密度的方法l 异常分析应用聚类分析的例子l 市场销售:帮助市场人员发现客户数据库中不同群体，然后利用这些知识来开展一个目标明确的市场计划；l 土地
30、使用:在一个陆地观察数据库中标识那些土地使用相似的地区；l 保险:对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；l 城市规划:根据类型、价格、地理位置等来划分不同类型的住宅；l 地震研究:根据地质断层的特点把已观察到的地震中心分成不同的类；如何评价一个好的聚类方法?l 一个好的聚类方法要能产生高质量的聚类结果簇，这些簇具备以下两个特征：l 簇内极大相似性l 簇间极小相似性l 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；l 聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；聚类分析中的数据类型l 如何度量对象间的距离？l 欧几里德距离 l 曼哈顿
31、距离 l 明考斯基距离聚类分析l 什么是聚类分析?l 划分方法（PartitioningMethods）l 分层方法l 基于密度的方法l 异常分析划分方法:基本概念l 划分方法:将一个包含n个数据对象的数据库组织成k个划分（k=n），其中每个划分代表一个簇（Cluster）。l 给定一个k，要构造出k个簇，并满足采用的划分准则：l 全局最优:尽可能的列举所有的划分；l 启发式方法:k-均值和k-中心点算法l k-均值(MacQueen67):由簇的中心来代表簇；l k-中心点或PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw87):每个簇由簇中的某个数
32、据对象来代表。K-均值算法l 给定k，算法的处理流程如下:1.随机的把所有对象分配到k个非空的簇中；2.计算每个簇的平均值，并用该平均值代表相应的簇；3.将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；4.回到第二步，直到不再有新的分配发生。K-均值算法图示K-均值算法例子l Given:2,4,10,12,3,20,30,11,25,k=2l 随机指派均值:m1=3,m2=4l K1=2,3,K2=4,10,12,20,30,11,25,m1=2.5,m2=16l K1=2,3,4,K2=10,12,20,30,11,25,m1=3,m2=18l K1=2,3,4,10,K2=
33、12,20,30,11,25,m1=4.75,m2=19.6l K1=2,3,4,10,11,12,K2=20,30,25,m1=7,m2=25K-均值算法l 优点l 相对高效的:算法复杂度O(tkn),其中n是数据对象的个数,k是簇的个数,t是迭代的次数，通常k,tn.l 算法通常终止于局部最优解；l 缺点l 只有当平均值有意义的情况下才能使用，对于标称字段不适用；l 必须事先给定要生成的簇的个数；l 对“噪声”和异常数据敏感；l 不能发现非凸面形状的数据。聚类分析l 什么是聚类分析?l 划分方法（PartitioningMethods）l 分层方法l 基于密度的方法l 基于网格的方法l 异
34、常分析层次方法l 采用距离作为衡量聚类的标准。该方法不需要指定聚类的个数，但用户可以指定希望得到的簇的数目作为一个结束条件。Step 0Step 1 Step 2 Step 3 Step 4bdceaa bd ec d ea b c d eStep 4Step 3 Step 2 Step 1 Step 0聚集(AGNES)分裂(DIANA)层次聚类方法讨论l 层次方法的主要缺点：l 没有良好的伸缩性:时间复杂度至少是O(n2)l 一旦一个合并或分裂被执行，就不能修复；l 综合层次聚类和其它的聚类技术：l BIRCH(1996):使用CF-tree动态调整子聚类的质量。l CURE(1998):
35、从聚类中选择分布“好”的数据点，并以指定的比例向聚类中心收缩。l CHAMELEON(1999):利用动态建模技术进行层次聚类。聚类分析l 什么是聚类分析?l 划分方法（PartitioningMethods）l 分层方法l 基于密度的方法l 异常分析定义l 两个参数：l：邻域的最大半径l MinPts：数据对象-邻域内最少的数据个数l 给定对象集合Dl 邻域N(p):对象p的半径为内的区域，即q D|dist(p,q)=l 核心对象：q D，|N(q)|MinPtsl 从对象q到对象p是直接密度可达的：p N(q)且|N(q)|MinPtspqMinPts=5=1 cm定义（续）l 从对象q
36、到对象p关于和MinPts是密度可达的：存在对象链p1，p2，pn，并且p1=q，pn=p，piD，从pi到pi+1关于和MinPts是直接密度可达的（非对称）l 对象p和q关于和MinPts密度相连：存在对象o D，使得从o到对象p和q关于和MinPts密度可达（对称）p qopqp1DBSCAN基本思想l 簇：基于密度可达性，密度相连对象的最大集合l 噪音：不在任何簇中的对象l 边界对象：在簇中的非核心对象，即至少从一个核心对象直接可达核心对象边界点噪音=1cmMinPts=5DBSCAN算法1）任意选择没有加簇标签的点p2）如果|N(P)|MinPts，则p 是核心对象，找到从p 关于和
37、MinPts 密度可达的所有点。形成一个新的簇，给簇内所有的对象点加簇标签。3）如果p是边界点,则处理数据库的下一点4）重复上述过程，直到所有的点处理完毕=1cmMinPts=5不足和改进l 只能发现密度相仿的簇l 对用户定义的参数 和MinPts敏感l 计算复杂度为O(n2)l 采用R-树等空间索引技术，计算复杂度为o(nlogn)图示l A和B被认为是噪音l C1和C2两个簇合并了聚类分析l 什么是聚类分析?l 划分方法（PartitioningMethods）l 分层方法l 基于密度的方法l 异常分析异常分析l 孤立点：与数据的其他部分不同的数据对象l 一个人的噪音是另一个人的信号l 信用卡欺诈探测、收入极高或极低的客户分区、医疗分析l 孤立点挖掘l 在给定的数据集合中定义什么样的数据为不一致的l 找到一个有效的方法来挖掘孤立点l 统计学方法l 基于距离的方法l 基于偏移的方法实验l 使用Clementine 进行聚类挖掘（工具使用参见补充教材）休息