第四周聚类分析与关联规则 - ToStu

1、1聚类分析聚类分析: 基本概念与方法基本概念与方法n聚类分析: 基本概念n划分方法n基于密度的方法n层次方法n基于网格的方法n聚类方法评估nSummary12什么是聚类分析?n聚类: 把数据对象划分成子集的过程, 每个子集是一个簇簇(cluster)n簇中的对象彼此相似n但与其他簇中的对象不相似n聚类分析（数据分割）n找到数据之间的相似性，将相似的数据对象划分到一个簇中n无监督学习: 没有预先定义的类标签 (通过观察学习 vs. 通过示例学习: 监督学习)n典型应用n作为一种独立的工具来洞察数据的分布n作为其他算法的一个预处理步骤聚类分析：基本概念n 物以类聚，人以群分！聚类分析自动地实现了。

2、物以类聚，人以群分！聚类分析自动地实现了。4聚类分析的应用n生物学: 基因n信息检索: 文件聚类n市场营销: 帮助经理人发现客户的典型特征，从而有针对性的制定营销策略n城市规划: 根据房屋类型，地理位置对房屋分组n经济学: 市场研究n信用卡欺诈质量: 好的聚类是什么样?n一个好的聚类方法会产生高质量的聚类n高的类内相似度: 簇内紧密结合n低的类间相似度: 簇间截然不同n聚类方法的质量取决于n方法所采用的相似性度量n方法的实施n方法发现一些隐藏模式的能力5聚类分析中需要考虑的方面n划分准则n单一层vs.层次划分 (通常需要多层次的划分)n簇的分离性n簇是互斥的 (如, 一个客户只属于一个组) v

3、s. 不互斥的 (如, 一个文档可能与多个主题有关)n相似性度量n基于距离 (如, 欧氏距离) vs. 基于连接性 (如, 基于密度或连通性)n聚类空间n整个数据空间 (对于低维数据集有用) vs. 子空间 (常用于高维聚类)6需求和挑战n可伸缩性n不只在小数据集上运行良好，在大型数据集的样本上也可以n处理不同属性类型的能力n数值, 二元, 标称(分类), 序数, 或者这些属性类型的混合n基于约束的聚类n用户给定输入限制n使用领域知识决定输入参数n可解释性和可用性n其他n发现任意形状的簇n处理噪声数据的能力n增量聚类和对输入次序不敏感n聚类高维数据的能力7主要的聚类方法n划分方法: n给定一个

4、n个对象的集合，划分方法构建数据的k个分区，其中每个分区表示一个簇，并且k=n。n典型方法: k-means, k-medoids, CLARANSn层次方法: n通过一些规则创建一个数据集的层次分解n典型方法: Diana, Agnes, BIRCH, CAMELEONn基于密度的方法: n基于连接性和密度函数n典型方法: DBSACN, OPTICS, DenCluen基于网格的方法: n把对象空间量化为有限个单元，形成一个网格结构n典型方法: STING, WaveCluster, CLIQUE89聚类分析聚类分析: 基本概念与方法基本概念与方法n聚类分析: 基本概念n划分方法n基于密度

5、的方法n层次方法n基于网格的方法n聚类方法评估nSummary9划分算法: 基本概念n划分方法: 将n个数据对象的数据集D划分成k个分区，使得同一个簇中的对象是“相似的”，不同簇中的对象是“相异的”。n给定参数k, 找到k 个簇的划分，使得划分准则最优n全局最优: 需要穷举所有可能的划分n启发式方法: 渐渐地提高聚类质量，逼近局部最优解，如k-均值 和 k-中心点 算法nk-均值: 每个簇用簇的中心代表nk-中心点: 每个簇用簇中其中一个对象代表10划分方法中相似性或相异性度量n对象p Ci与该簇的代表ci之差用dist(p, ci)度量，其中dist(x,y)是两个点x和y之间的欧氏距离。簇

6、Ci的质量可以用簇内变差 度量，它是Ci中所有对象和形心ci之间的误差的平方和，定义为n其中，E是数据集中所有对象的误差的平方和；p是空间中的点，表示给定的数据对象；ci是簇Ci的形心（p和ci都是多维的）。换言之，对于每个簇中的每个对象，求对象到其簇中心距离的平方，然后求和。1121)(iCpkicpEi聚类分析：划分方法k-均值n +K-均值 聚类方法：一种基于形心的技术n给定参数 k, k-均值 算法通过以下四步骤实施:n划分数据对象到k 个非空子集n对于当前划分，计算每个簇的中心 (如簇的均值点)n最开始，在D中随机地选择k个对象，每个对象代表一个簇的中心n对剩下的每个对象，根据其与各

7、个簇中心的欧氏距离，将它分配到最相似的簇 n回到第2步，直到各簇中对象的分配不再改变13k-均值算法+k=3初始数据集任意指定三个簇的中心点更新聚类中心，重新划分对象更新聚类中心重新划分对象如果需要，继续循环输入输入：k: 簇的数目； D: 包含n个对象的数据集输出输出：k个簇的集合方法方法：(1) 从D中任意选择k个对象作为初始簇中心(2) repeat(3) 根据簇中对象的均值，将每个对象分配到最相似的簇；(4) 更新簇均值，即重新计算每个簇中对象的均值(5) Until不再发生变化K-均值 方法的变异n大多数k-均值方法的变异方法主要在以下方面不同n初始k个均值的选择n相异性度量方法n计

8、算类均值的策略15nk-均值算法对离群点!n一个具有非常大的值的对象会严重地扭曲簇的均值nk-中心点: 不采用簇中对象的均值均值作为参照点，而是挑选簇中最中心的数据对象最中心的数据对象（中心点）作为参照点。01234567891001234567891001234567891001234567891016k-均值算法的问题17PAM: 一种典型的k-中心点算法总代价 = 20012345678910012345678910K=2任意选择k个对象作为初始中心点分配每个剩余的对象到离它最近的中心点所代表的簇随机选择一个非中心点的对象Oramdom计算用Oramdom 代替原中心点的总代价01234

9、5678910012345678910总代价 = 26如果聚类质量提高了, 则Oramdom 替换原来中心点.一直循环知一直循环知道不再发生道不再发生改变改变012345678910012345678910k-中心点聚类方法算法：k-中心点。PAM,一种基于中心点或中心对象进行划分的k-中心点算法输入：k: 结果簇的个数。D: 包含n个对象的数据集合。输出：k个簇的集合。方法：(1)从D中随机选择k个对象作为初始的代表对象或种子；(2)repeat(3) 将每个剩余的对象分配到最近的代表对象所代表的簇；(4) 随机地选择一个非代表对象orandom；(5) 计算用orandom代替代表对象oj

10、的总代价S；(6) if S 0, 重复以上过程m 次, 对不同的k值，比较总体质量度量，并选取最佳拟合数据的簇数45测定聚类质量n两种方法: 外在 vs. 内在n外在: 监督方法, 即, 有基准可用n将基准与聚类进行比较，以评估聚类n内在: 无监督方法, 即, 没有基准可用n通过考虑簇的分离情况评估聚类的好坏46测定聚类质量: 外在方法n聚类质量度量: 给定基准Cg ，对聚类C赋予一个评分Q(C, Cg). nQ 是有效的，如果它满足如下4项基本标准n簇的同质性簇的同质性: 簇越纯，聚类越好n簇的完全性簇的完全性: 如果两个对象属于相同的类别，则它们应该被分配到相同的簇n碎布袋碎布袋: 把一

11、个异种对象放入一个纯的簇中应该比放入碎布袋中受更大的“处罚”(碎布袋, 称为“杂项” 或者 “其他”)n小簇保持性小簇保持性: 把小类别划分成小片比将大类别划分成小片更有害4748聚类分析聚类分析: 基本概念与方法基本概念与方法n聚类分析: 基本概念n划分方法n基于密度的方法n层次方法n基于网格的方法n聚类方法评估n小结48SummarynCluster analysis groups objects based on their similarity and has wide applicationsnMeasure of similarity can be computed for var

12、ious types of datanClustering algorithms can be categorized into partitioning methods, hierarchical methods, density-based methods, grid-based methods, and model-based methodsnK-means and K-medoids algorithms are popular partitioning-based clustering algorithmsnBirch and Chameleon are interesting hi

13、erarchical clustering algorithms, and there are also probabilistic hierarchical clustering algorithmsnDBSCAN, OPTICS, and DENCLU are interesting density-based algorithmsnSTING and CLIQUE are grid-based methods, where CLIQUE is also a subspace clustering algorithmnQuality of clustering results can be

14、 evaluated in various ways 4950挖掘频繁模式, 关联和相关性: 基本概念和方法n基本概念n频繁项集挖掘方法n序列模式挖掘n小结n几个基本概念：n数据项：设I=i1, i2, , im是常数的集合，其中m是任意有限的正整数常量，每个常数ik(k=1, 2, , m)称为一个数据项。n项集：由I中的数据项组成的集合，即X是I的子集nk-项集：一个大小为k的项集(包含有k项，如A、B为2-项集，A、C、D为3-项集)n一个交易T：是由在I中的数据项所构成的集合，即T是I的子集51基本概念: 频繁项集n项集X在事务数据库DB中出现的次数占总事务的百分比叫做项集的支持度n如

15、果项集的支持度超过用户给定的最小支持度阈值就称该项集是频繁项集(大项集)52基本概念: 频繁项集TidItems10A, C, D20B, C, E30A, B, C, E40B, E设X为一个由多个项目构成的集合，称为项集，如10中的A、C、D，当且仅当X是T的子集时我们说事务T包含X53基本概念: 频繁项集n项集: 项的集合nk-项集: 包含k个项的项集 X = x1, , xkn项集X的频度、支持度计数(绝对支持度): 一个项集X的出现频度, 即包含项集的事务数n相对支持度, s, 是一个事务包含项集X的概率n一个项集X 是频繁的 ，如果X的相对支持度不小于最小支持度阈值Customer

16、buys diaperCustomerbuys bothCustomerbuys beerTidItems bought10Beer, Nuts, Diaper20Beer, Coffee, Diaper30Beer, Diaper, Eggs40Nuts, Eggs, Milk50Nuts, Coffee, Diaper, Eggs, Milkn关联规则是形如 的蕴含式，其中X是I的子集，Y是I的子集，且XY=，则X称为规则的条件，Y称为规则的结果n如果事务数据库D中有s%的事务包含X Y，则称关联规则 的支持度为s%n支持度是指项集X和Y在数据库D中同时出现的概率54基本概念: 关联规则n

17、进行关联规则挖掘时，要求用户给出两个阈值：n最小支持度(频度)s;n最小置信度c。n表示： support ( ) =min_sup confidence ( ) =min_conf 的关联规则称为强规则；否则称为弱规则。n数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。55基本概念: 关联规则56基本概念: 关联规则假定 最小支持度 minsup = 50%, 置信度阈值 minconf = 50%频繁项集: Beer:3, Nuts:3, Diaper:4, Eggs:3, Beer, Diaper:3Customerbuys diaperCu

18、stomerbuys bothCustomerbuys beerNuts, Eggs, Milk40Nuts, Coffee, Diaper, Eggs, Milk50Beer, Diaper, Eggs30Beer, Coffee, Diaper20Beer, Nuts, Diaper10Items boughtTidn关联规则: (还有许多!)nBeer Diaper (60%, 100%)nDiaper Beer (60%, 75%)n关联规则挖掘就是要从大量的潜在的规则库中寻找出满足支持度和置信度阈值的所有规则。n关联规则挖掘过程：n第一步：寻找频繁项集。第一步：寻找频繁项集。根据定义

19、，这些项集出现的频度不小于预先定义的最小额度。(找出满足定义的频繁项集)n第二步：由频繁项集产生关联规则第二步：由频繁项集产生关联规则。根据定义，这些规则必须满足最小支持度和最小置信度。(从频繁项集生成关联规则)57基本概念: 关联规则n根据不同的分类标准，关联规则有多种分类方法：n根据规则中所处理的数据类型分类n根据规则中涉及的数据维数分类n根据规则中数据的抽象层次分类n其它58基本概念: 关联规则分类n根据规则中所处理的数据类型，可以分为：n布尔关联规则：处理的数据都是离散的，如尿布啤酒n量化关联规则：在关联规则中加入数量信息得到的规则。如职业=“学生” 收入=“01000”。59根据规则

20、中所处理的数据类型分类n根据规则中涉及的数据维数，可以分为：n单维关联规则：只涉及数据表的一个字段。如尿布啤酒n多维关联规则：涉及数据表的多个字段。如性别=“女”职业=“护士”，是二维关联规则；又如：年龄=“2030” 职业=“学生”购买=“电脑”，是三维关联规则。60根据规则中涉及的数据维数分类n根据规则中数据的抽象层次，可以分为：n单层关联规则，所有的变量都是细节数据，没有层次之分，如IBM台式机HP打印机n多层关联规则，发生关联的数据可能位于同一层次，也可能位于不同的层次。如：台式机HP打印机。61根据规则中数据的抽象层次分类62挖掘频繁模式, 关联和相关性: 基本概念和方法n基本概念n

21、频繁项集挖掘方法n序列模式挖掘n小结n问题发现：项目的个数成指数增长：从5个项目的集合得到31个项目集合（忽略空集）n关联规则挖掘过程：n第一步：寻找频繁项集。第一步：寻找频繁项集。根据定义，这些项集出现的频度不小于预先定义的最小额度。n第二步：由频繁项集产生关联规则第二步：由频繁项集产生关联规则。根据定义，这些规则必须满足最小支持度和最小置信度。63Apriori算法描述n找出频繁项集的算法可以很简单，但代价很高n简单的方法是：简单的方法是：对出现在事务中的所有项目集进行计数。n给定一个大小为m的项目集合，共有2m个子集，去掉空集，则潜在的频繁项集数为2m-1.随着项目数的增多，潜在的频繁项

22、集数成爆炸性增长。(当m=5，为31个；但m=30，变成1073741823个)n解决问题的难点：解决问题的难点：如何高效确定所有频繁项集。n大部分关联规则算法都利用巧妙的方法来减少要大部分关联规则算法都利用巧妙的方法来减少要计数的项目集。计数的项目集。64Apriori算法：(1)寻找频繁项集65闭频繁项集和极大频繁项集n解决方法: 挖掘闭频繁项集和极大频繁项集n一个项集X 是闭的 如果X是频繁的，且不存在真超项集 Y ? X, Y与X在D中具有相同的支持度计数。n一个项集X 是极大频繁项集 如果X是频繁的，且不存在超项集Y使得 Y ? X并且Y在D中是频繁的66n练习. DB = , nM

23、in_sup = 1.n闭频繁项集是什么?n: 1n: 2n极大频繁项集是什么?n: 1闭频繁项集和极大频繁项集n先验性质先验性质：如果一个项集S是频繁的(项集S的出现频度大于最小频度)，那么S的任意非空子集也是频繁的。反之，如果一个项集S的某个非空子集不是频繁的，则这个项集也不可能是频繁的。n举例：如果 beer, diaper, nuts 是频繁的, 则beer, diaper也是频繁的。n举例：如果一个交易包含A、B，则它必然也包含A、B的所有子集；反过来，如果A或B不是频繁项集，即A或B的出现频度小于最小频度，则A、B的出现频度也一定小于最小频度，因此A、B也不可能是频繁项集。67Ap

24、riori算法：(1)寻找频繁项集68nApriori 剪枝性质: 如果一个项目集是不频繁的，则不需要生成它的任何超集来作为它的候选集，因为它们也一定是不频繁的。nApriori性质基于如下事实: 根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即sup(I)min_sup。如果将项A添加到I，则结果项集(即IA)不可能比I更频繁出现。因此， IA也不是频繁的，即sup(I A) =min_conf，则输出规则s(r-s)。其中，support_count为支持度，min_conf为置信度。Apriori算法：(2)由频繁项集找出关联规则73n根据前述计算得到的频繁项集

25、为B, C, E。n获得所有非空子集B、C、B、E、C、E、B、C、En产生的关联规则：Apriori算法：(2)由频繁项集找出关联规则TidItems10A, C, D20B, C, E30A, B, C, E40B, E规则置信度置信度BCE2/2=100%BEC2/3=66%CEB2/2=100%BCE2/3=66%CBE2/3=66%EBC2/3=66%74Apriori 算法Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support endreturn k Lk;75挖掘频繁模式, 关联和相关性: 基本概念和方法n基本概念n频繁项集挖掘方法n序列