无监督学习

1第四章无监督学习监督学习与无监督学习监督学习：发现数据属性和类别属性之间的关联模式。并通过利用这些模式用来预测未知数据实例的类别属性。无监督学习：数据没有目标属性。发现数据中存在的内在结构。2聚类聚类（Clustering）是一种发现数据中的相似群（聚类，clusters）的技术。处于相同聚类的数据实例彼此相似，处于不同聚类中的实例则彼此不同。聚类通常被称为无监督学习。在聚类中那些表示数据类别的分类或分组信息没有事先给出。由于历史的原因，聚类和无监督学习的关系更加紧密，甚至被认为是同义词。事实上，关联规则挖掘也是无监督学习。本章主要介绍聚类算法。3聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程。一个聚类就是一些数据实例的集合这个集合中的元素彼此相似；与其他聚类中的元素不同。聚类的相关文献中，一个数据实例有时被称作对象——数据实例很可能代表现实世界中的一个对象。有时也被称作数据点——数据实例可以被看作是r维空间中的一个点，其中r表示数据的属性个数。4.1基本概念4引例如下图所示，一个二维数据集，由三组数据点（聚类）组成。5聚类的目的来自不同应用领域的真实实例。实例1：根据身材把人分组的方法通常就采用聚类。T恤分“小号”、“中号”、“大号”。为每个顾客量身定做：太贵仅一种型号的T恤：大多数人不合身。实例2：在营销学中，对客户进行分割，为每组客户指定一个套营销策略，也是采用聚类来完成。6实例3：对给定文本，需要根据它们内容的相似性来进行组织。建立一个主题层次。事实上，聚类是数据挖掘技术中应用最广泛的技术之一。发展历史长，应用领域广泛。比如：医学类、心理学、植物学、社会学、生物学、营销学、保险、图书馆等。近年来，在线文档的快速发展，文本聚类研究成为关注的重点。7聚类的概述聚类算法划分聚类层次聚类…（密度聚类）距离函数（相似性或相异性）：度量两个数据点（对象）的相似程度。聚类评价类内差异（聚类内部距离）：最小化类间差异（聚类外部距离）：最大化聚类结果的质量与算法、距离函数和应用领域有很大关系。8k-均值算法是划分聚类算法。k-均值算法根据某个距离函数反复地把数据分入k个聚类中。设数据点（或实例）的集合D为{x1,x2,…,xn}，其中，xi=(xi1,xi2,…,xir)是实数空间XRr中的向量。并且r表示数据的属性数目（数据空间维数）。k-均值算法把给定的数据划分为k个聚类。每个聚类中有一个聚类的中心（也称聚类中心），它用来表示某个聚类，这个中心是聚类中所有数据点的均值。K是由用户指定的。4.2k-均值聚类9k-均值算法给定k，k-均值算法执行步骤：随机选取k个数据点作为初始聚类中心。计算每个数据点与各个中心之间的距离，把每个数据点分配给距离它最近的聚类中心。数据点分配以后，每个聚类的聚类中心会根据聚类现有的数据点重新计算。这个过程将不断重复知道满足某个终止条件为止。10算法内容11终止条件没有（或最小数目）数据点被重新分配给不同的聚类。没有（或最小数目）聚类中心再发生变化。误差平方和（sumofsquarederror，SSE）局部最小。其中，Ci表示第j个聚类，mj是聚类Cj的聚类中心（Cj中所有数据点的均值向量），dist(x,mj)表示数据点x和聚类中心mj之间的距离。kjCjjdistSSE12),(xmx(1)12举例1314距离计算在那些均值能被定义和计算的数据集上均能使用k-均值算法。在欧式空间，聚类均值可以使用如下公式：数据点与聚类中心的距离使用如下公式：15算法举例：下面给出一个样本事务数据库，并对它实施k-平均算法。序号属性1属性2111221312422543653744854设n=8，k=2，执行下面的步骤：第一次迭代：假定随机选择的两个对象，如序号1和序号3当作初始点，分别找到离两点最近的对象，并产生两个簇{1，2}和{3，4，5，6，7，8}对于产生的簇分别计算平均值，得到平均值点。对于{1，2}，平均值点（1.5,1）；对于{3，4，5，6，7，8}，平均值点（3.5,3）16第二次迭代：通过平均值调整对象所在的簇，重新聚类，即将所有点按离平均值点（1.5,1）和（3.5,3）最近的原则重新分配。得到两个簇：{1,2,3,4}和{5,6,7,8}重新计算簇平均值点，得到新的平均值点为：（1.5,1.5）和（4.5,3.5）第三次迭代：通过平均值调整对象所在的簇，重新聚类，即将所有点按离平均值点1.5,1.5）和（4.5,3.5）最近的原则重新分配。得到两个簇：{1,2,3,4}和{5,6,7,8}发现没有出现重新分配，准则函数收敛，程序结束。17下图给出了该例子整个过程中平均值计算和簇生成的过程和结果。迭代次数平均值簇1平均值簇2产生的新簇新平均值簇1新平均值簇21(1,1)(1,2){1,2},{3,4,5,6,7,8}(1.5,1)(3.5,3)2(1.5,1)(3.5,3){1,2,3,4},{5,6,7,8}(1.5,1.5)(4.5,3.5)3(1.5,1.5)(4.5,3.5){1,2,3,4},{5,6,7,8}(1.5,1.5)(4.5,3.5)18k-均值可以执行硬盘上的数据每一次循环，算法扫描数据一次聚类中心可以在每次循环中增量计算。k-均值在处理大规模数据时（内存不足以容纳这些数据）十分有用。需要控制循环次数实际应用中，需要设置一个限制次数(50)这不是最好的方法，还有其他的算法，比如:BIRCH。4.2.2k-均值算法的硬盘版本19K-均值硬盘版算法20优势简单：容易被理解，同时也容易被实现。效率：时间复杂度为O(tkn)。其中，n是数据点个数；k是聚类的个数；t是循环次数由于k和t通常都远远小于n，k-均值算法被认为相对于数据点的数目来说是线性的。K-均值算法是聚类算法中最流行的一种算法。4.2.3优势与劣势21劣势算法只能用于那些均值能够被定义的数据集上。对于范畴数据，有一种k-均值算法的变体——k-模算法，用于聚类范畴数据。用户需要事先指定聚类数目k。算法对于异常值十分敏感。异常值是指数据中那些与其他数据点相隔很远的数据点。异常值可能是数据采集时产生的错误或者一些具有不同值的特殊点。22异常值问题23解决异常值问题一种方法：在聚类过程中去除那些比其他任何数据点离聚类中心都要远的数据点。安全起见，我们需要在多次循环中监控这些潜在的异常值，随后再决定是否删除它们。另一个方法：随机采样。因为在采样过程中，我们仅仅只选择很少一部分的数据点，因此选中异常值的概率将会很小。我们可以先用采样点进行预先聚类，然后把其他数据点分配给这些聚类（剩下的数据点分配给那些距离它最近的聚类中心/分类/半监督的学习）。24劣势（续）算法对于初始种子十分敏感。25如果选择不同的种子：比较好的结果。事实上，还有很多其他方法用来选择初始种子。见书P9326劣势（续）算法不适合发现那些形状不是超维椭圆体（或超维球体）的聚类。27K-均值算法总结虽然k-均值算法有不足，但它仍是在实践中采用最为广泛的算法。其他聚类算法也有它们的一系列不足之处。没有直接的证据证明哪一种算法在整体表现上优于k-均值算法。虽然其他聚类算法在某些特殊数据下的表现优于k-均值算法。比较不同聚类算法的优劣是一个很难的任务。没有人知道正确的聚类结果是什么。28对于数据中的聚类需要寻找一种方法来表示这些聚类。某些应用中，只需直接输出聚类中的数据点即可。而有的应用，特别是决策相关应用中，聚类结果需要用一种压缩和可理解的方式表示。有利于对聚类结果的评价。4.3聚类的表示29用聚类中心来表示每个聚类是使用最广泛的聚类表示方法计算聚类的半径和标准差来确定聚类在各个维上的伸展度。聚类中心表示法对于那些高维球体形状的聚类来说已经足够。但如果聚类被拉长了或者是其他形状的话，聚类中心表示就可能不太适合。4.3.1聚类的一般表示方法30利用分类模型来表示聚类同一聚类中的所有数据点被看作是具有相同类别标识的，如聚类标识。通过在数据上执行某个监督学习算法来发现分类模型。31利用聚类中最为常见的值来表示聚类这种方法通常在对范畴属性进行聚类时采用（k-模聚类）。它同样是文本聚类中的重要方法，比如：使用一个较小的集合：每个类中高频词来表示这个类。324.3.2任意形状的聚类超维椭圆体或超维球体形状的聚类容易使用聚类中心以及聚类的伸展度（标准差）、规则或者它们的组合来表示。任意形状的聚类是很难用它们来表示的。（一般分别输出每个聚类中的数据点）聚类中心不适合在高维空间中使用。K-均值聚类在低维空间中更适用。比如：划分两个聚类等。334.4层次聚类生成一系列嵌套的聚类树（也叫树状图）34层次聚类的两种方法合并（自下而上）聚类：从树状图的最底层开始构建聚类树。合并最相似（距离最近）的聚类来形成上一层中的聚类。整个过程当全部数据点都合并到一个聚类中时停止。分裂（自上而下）聚类：从一个包含全部数据点的聚类开始。根节点聚类分裂成一些子聚类。每个子聚类在递归地继续向下分裂。直到出现只包含一个数据点的单节点聚类出现时停止。35合并聚类它比分裂聚类算法应用得更广泛。起初，每一个数据点形成一个聚类（或叫节点）合并具有最短距离的聚类/节点继续合并直到所有节点都在一个聚类中为止。36合并聚类算法37算法举例38算法举例：下面给出一个样本事务数据库，并对它实施合并聚类算法。序号属性1属性2111212321422534635744845设n=8，用户输入的终止条件为两个簇，执行下面的步骤：初始簇：{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}第一步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后，1，2点合并为一个簇。39第二步：对第一步合并后的簇计算簇间距离，找出距离最近的两个簇进行合并（合并聚类算法中计算两个簇间的相似度可由这个两不同簇距离最近的数据点对的相似度来确定）。经计算，选择最近的簇距离1，确定{3}{4}合并为一簇。第三步：按第二步的操作方式，对{1,2}{3,4}{5}{6}{7}{8}计算6个簇间距离，找出距离最近的两个簇进行合并。经计算，选择最近的簇距离1，确定{5}{6}合并为一簇。40第四步：同样按第二步的操作，{7}{8}合并为一簇，得到{1,2}{3,4}{5,6}{7,8}第五步：分别计算簇之间的距离，合并{1,2}{3,4}为一簇（两簇中，{1}{3}的距离为1，即可合并）第六步：分别计算簇{1,2,3,4}{5,6}{7,8}的距离，合并{5,6}{7,8}为一簇，得到{1,2,3,4}{5,6,7,8}两个簇，由于数目已经达到了用户输入的条件，程序结束。41下图给出了该例子整个过程中簇间距离计算和簇合并的过程和结果。步骤最近的簇距离最近的两个簇合并后的新簇11{1}{2}{1,2}{3}{4}{5}{6}{7}{8}21{3}{4}{1,2}{3,4}{5}{6}{7}{8}31{5}{6}{1,2}{3,4}{5,6}{7}{8}41{7}{8}{1,2}{3,4}{5,6}{7,8}51{1,2}{3,4}{1,2,3,4}{5,6}{7,8}61{5,6}{7,8}{1,2,3,4}{5,6,7,8}42两个聚类之间的距离计算层次聚类中计算两个聚类之间的距离方法有很多。在不同的算法中可以用不同方法去确定两个聚类之间的距离。单链接方法全链接方法平均链接方法聚类中心方法…434.4.1单链接方法两个聚类之间的距离是两个聚类中距离最近的两个数据点（来自不同聚类的数据点）之间的距离。单链接方法适合于寻找那些形状怪异的聚类。但是它对数据中的噪声非常敏感。链接两个自然聚类的噪音数据点的