第4章 数据挖掘高级方法

第四章数据挖掘高级方法,主要内容,商务智能与数据挖掘,高等教育出版社2020/6/7,4.1高级聚类分析,一、基于概率模型的聚类分析,商务智能与数据挖掘,高等教育出版社2020/6/7,引例：实际的网店评论中，不同的产品受到的评论或多或少；客户一次在线购物可能购买多个产品，故一个评论可能涉及多种产品；客户发表的评论可能不止涉及产品本身，还会涉及卖家的服务、物流、售后等。,1.模糊集,给定一个对象集，是的模糊集，它把中的每一个对象都映射成一个属于的到之间的隶属度。一个模糊集形式地可以用一个函数：，建模。,例，一种笔记本电脑的销售量越大，该笔记本电脑就越流行。在某网店中，给定一种笔记本电脑的销售量，可以使用如下公式来计算的流行程度：,商务智能与数据挖掘,高等教育出版社2020/6/7,函数pop()定义了一个流行的笔记本电脑的模糊集。假设有种笔记本电脑、，它们的销量分别是50、1320、860、270，则这4种笔记本电脑的模糊集是（0.05），（1），（0.86），（0.27），括号中是流行程度（隶属度）。将模糊集的概念用在聚类上：给定对象集合，一个簇就是对象的一个模糊集。这种簇称为模糊簇。因此，一个聚类包含多个模糊簇。给定对象集1，n，可以用划分矩阵wij（，）表示个模糊簇1，k的模糊聚类。其中，ij是i在模糊簇j的隶属度。由模糊簇的概念可知，划分矩阵应该满足以下三个条件。,商务智能与数据挖掘,高等教育出版社2020/6/7,接下来回到网店评论的例子。假设某笔记本电脑网店有6个评论。表4-1显示了这些评论中的关键词。,根据关键词，将这些评论分成两个模糊簇1和2。1是关于笔记本电脑性能的评论，而2是关于笔记本电脑待机时间的评论，则划分矩阵为M=101023130101,这里用关键词“性能”“上网快”和“CPU”作为簇1的特征，而“待机长”和“电池耐用”作为簇2的特征。对于评论i和簇j（，），wij定义为wij=|i|(12)|在这个模糊聚类的例子中，评论分别以隶属度23和13属于簇1和2。,商务智能与数据挖掘,高等教育出版社2020/6/7,下面用误差平方和（SSE）评估模糊聚类对数据集描述的好坏。考虑对象集1，n和k个簇1，k的模糊聚类，wij（，）为划分矩阵。设1，k分别为簇，的中心。这里，中心可以定义为平均值或中心点，或者用仅限于具体应用的其他方法定义。如第3章所讨论的，对象与其被指派到的簇的中心之间的距离或相似度可以用来度量该对象属于簇的程度。将这一思想扩充到模糊聚类：对于任意对象i和簇j，隶属度ij且用dist（i，j）表示对象i与簇j中心的距离（即度量i属于簇j的程度），其中dist（）是欧几里得距离。由于一个对象可能参与多个簇，所以用隶属度加权的到簇中心的距离平方和捕获对象拟合聚类的程度。,对象i的误差平方和（SSE）由下式给出：SSE(oi)=,其中，参数（）控制隶属度的影响，p的值越大，隶属度的影响越大。簇j的误差平方和是SSE(Cj)=,最后，聚类C的误差平方和定义为SSE(C)=,聚类的误差平方和可以用来度量模糊聚类对数据集的拟合程度。,商务智能与数据挖掘,高等教育出版社2020/6/7,2.概率簇,假设聚类分析的目标数据集存在隐藏的类（簇），那么该数据集可以看作该隐藏类实例的一个样本。聚类分析导出的簇是使用数据集推断出来的，并且旨在逼近隐藏的类。因此，从统计学讲，可以假定隐藏的类是数据空间上的一个分布，可以使用概率密度函数（或分布函数）精确地表示。这种隐藏的类称为概率簇（probabilisticcluster）。假设想通过聚类分析找出个概率簇1，k。对于个对象的数据集，可以把看作这些簇的可能实例的一个有限样本。从概念上讲，可以假定按照如下方法形成：每个簇j（）都与一个实例从该簇抽样的概率j相关联。通常将1，k作为问题设置的一部分给定，并且=，确保所有对象都由个簇产生。这里，参数捕获了关于簇的相对总体的背景知识。,然后，运行以下两个步骤，产生D的一个对象。这些步骤总共执行n次，产生D的n个对象1，n。,（1）根据概率1，k选择一个簇j。（2）根据j的概率密度函数fj，选择一个簇j的实例。,商务智能与数据挖掘,高等教育出版社2020/6/7,为了将数据集D聚类为所需的k个簇，基于概率模型的聚类分析通过推导得到k个概率簇，使得根据这k个概率簇，利用以上数据产生过程最有可能产生数据集D。,接下来的一个重要问题是，如何度量k个概率簇的集合和它们的概率产生观测数据集的似然。考虑k个概率簇1，k的集合，k个簇的概率密度函数分别为1，k，而它们的概率分别为1，k。对象，由簇（）产生的概率为（|）（）。因此，由簇的集合产生的概率为P（|C）=j=1()假定对象是独立产生的，因此对于个对象的数据集，有P(D|C)=(|)=()在给定(|）后，对数据集进行基于概率模型的聚类分析的任务，就转化为找出个概率簇组成集合，使得(|）最大化。但是，概率簇的概率密度函数可能是任意复杂形式，这给最大化(|）带来了难度。为此，一般假定概率密度函数是一个参数分布。假设，是个分布的参数，则上式可以改写为(|)=(|)=(|),商务智能与数据挖掘,高等教育出版社2020/6/7,其中，(|)是使用参数，由第个分布产生的概率。如上所述，使用参数概率分布模型，解决概率簇的概率密度函数多样性给最大化(|）带来难度的问题。为此，对数据集进行基于概率模型的聚类分析的任务，就转化为推导最大化的参数集。,3.期望最大化算法,计算模糊聚类和基于概率模型的聚类均可以采用期望最大化算法，下面介绍这类方法的一般原理。首先回忆一下第章讨论过的-均值聚类问题和-均值算法。-均值算法是一种迭代算法，它每次迭代包括两个步骤：期望步（-步）：给定当前的簇中心，每个对象都被指派到距离簇中心最近的簇中。这里，期望每个对象都属于最近的簇。最大化步（-步）：给定簇指派，对于每个簇，利用算法调整其中心，使得指派到该簇中的对象到该簇中心的距离之和最小。也就是说，将指派到一个簇中的对象的相似度最大化。-均值算法迭代执行这两步，直到不能再改进聚类。由于-均值聚类是模糊聚类的一种特例，所以可以采用这一迭代过程来处理模糊聚类和基于概率模型的聚类。一般而言，期望最大化（expectation-maximization，EM）算法不断逼近统计模型参数的最大似然或最大后验估计。,商务智能与数据挖掘,高等教育出版社2020/6/7,因此，期望最大化算法在解决模糊或基于概率模型的聚类问题时，一般从初始参数集出发，不断迭代，直到聚类收敛或迭代的改变足够小（小于一个预先设定的阈值），也就是聚类不能再改善为止。具体而言，每次迭代由两步组成：根据当前的模糊聚类或概率簇的参数，把对象指派到簇中。计算聚类或簇参数，或构建新聚类或簇，使模糊聚类的误差平方和或基于概率模型的聚类的期望似然最小。这里以下图所示的数据集中的个点（图中显示了点的坐标）为例，使用期望最大化算法计算两个模糊聚类。,图模糊聚类的数据集,现随机地选择两个点，如=，作为两个簇，的初始中心。第一次迭代执行期望步和最大化步的细节如下。,商务智能与数据挖掘,高等教育出版社2020/6/7,在期望步中，计算所有点属于各个簇的隶属度。对于点，分别以隶属权重,和,把指派到和中。其理由是，如果靠近，并且dist（,）小，则关于的隶属度应该高。也可以规范化隶属度，使得一个对象的隶属度之和等于。对于点，有，即互斥地属于。对于点，有，。对于点，有，4145+41，4545+41。其他点的隶属度显示在下表所示的划分矩阵中。,表4-2算法前3次迭代的中间结果,商务智能与数据挖掘,高等教育出版社2020/6/7,在期望步中，根据划分矩阵重新计算簇的中心，使误差平方和最小化。新的中心应该调整为,其中，1，2。在这个例子中，,并且，,重复进行该迭代，其中每次迭代包含一个期望步和一个最大化步。表4-2显示了前3次迭代的结果。当簇中心收敛或变化足够小时算法停止。,二、高维数据聚类分析,商务智能与数据挖掘,高等教育出版社2020/6/7,接下来考虑聚类高维数据的问题，当数据的维度很高时应用在低维聚类中的距离度量可能被噪声所左右。先通过一个例子来看看在低维聚类中频繁使用的传统距离度量方法在高维数据上是否有效。表4-3显示了3位顾客购买10种商品Pi（110）的情况。如果顾客购买了某种商品，则对应的位被设置为1，否则为0。计算顾客之间的欧几里得距离，容易看出：dist（，)=dist（，)=dist（，）2根据欧几里得距离，这3个对象彼此之间的相似度（或相异性）完全一样。然而，直接观察可以发现B与C的相似度应该比B与A的相似度更高，因为B和C都购买了商品P10。,商务智能与数据挖掘,高等教育出版社2020/6/7,由此看出，在高维数据空间中，传统的距离度量方法可能没有效果。这种距离度量方法可能被一些维度上的噪声所左右。因此，使用低维的聚类方法发现的高维空间上的簇可能是错误的，低维的聚类方法应用于高维空间是不可靠的。因此，要重新考虑高维数据空间中的聚类方法。在高维空间中聚类，人们除了希望发现簇，还希望找到确定该簇的属性集（或者说这些属性与该簇密切相关）。因此，聚类高维数据的任务除了搜索簇，还要确定它们存在的子空间（属性集）。完成这个任务主要有两种方法。一种是子空间聚类方法，它搜索存在于给定高维数据空间的子空间中的簇，其中子空间用整个空间中的属性子集定义。另一种是维归约方法，它试图构造更低维的空间，并在这种空间中搜索簇。这种方法通常可以通过组合原数据的一些维度，构造新的维度。,1.子空间聚类方法,子空间聚类方法是在高维数据空间中发现子空间中的簇，目前已有许多子空间聚类方法，下面主要介绍双聚类方法。假设一个淘宝电商收集了顾客对产品的评价数据，并使用这些数据向顾客推荐产品。该数据可以用顾客产品矩阵建模，其中每行代表一位顾客，每列代表一种产品。矩阵的每个元素代表一位顾客对一种产品的评价，它可能是评分分（例如，喜欢、,有点喜欢、不喜欢）或购买态度（例如，买或不买产品）。顾客产品矩阵可以在两个维度上进行分析：顾客维和产品维。把每位顾客看作一个对象，把每种产品看作一个属性，还可以同时在顾客和产品上挖掘聚类。这样的簇包含顾客的一个子集，并且涉及产品的一个子集。例如，淘宝电商对于发现都喜欢同一组产品的顾客群特别感兴趣。这个簇是顾客产品矩阵的一个子矩阵，其中所有的元素都具有较高的值。有了这个簇，淘宝电商可以向与该簇中的顾客相似的新顾客推荐产品。淘宝电商还可以向顾客推荐与该簇涉及的产品相似的新产品。顾客产品矩阵中的双簇通常具有如下特点。只有少量顾客参与一个簇。一个簇只涉及少量产品。一位顾客可能参与多个簇，也可能完全不参与任何簇。一种产品可能被多个簇所涉及，也可能完全不被任何簇所涉及。人们的目的是把双聚类用于顾客产品矩阵，挖掘满足以上要求的簇。从上面的例子可以看到，双簇是一个子矩阵，其中对象（基因）和属性（条件）都遵循一致的模式。可以基于这种模式定义不同双簇的类型。具有常数值的双簇：是由基因子集，和条件子集，构成的子矩阵，对于和，该矩阵中的元素ij，其中c是常数。,商务智能与数据挖掘,高等教育出版社2020/6/7,行上具有常数值的双簇：是由基因子集，和条件子集，构成的子矩阵，使得对于和，该矩阵中的元素iji，其中i是行i的调节量。具有相干值的双簇：是由基因子集，和条件子集，构成的子矩阵，使得对于和，该矩阵中的元素iji，其中i和分别是行i和列j的调节量。相干演变的双簇：是由基因子集，和条件子集，构成的子矩阵，使得对于1，2和1，2，有（1121）（1222）。上面的双簇类型定义只考虑了理想情况。在实际的数据集中，这样完美的双簇很罕见。当它们确实存在时，它们通常很小。随机噪声可能影响ij的读数，因而阻止了双簇以完美的形状出现。在含有噪声的数据中发现双簇的方法主要有两种。一种是基于最优化的方法执行迭代搜索。在每次迭代中，具有最高显著性得分的子矩阵被识别为双簇。这一过程在用户指定的条件满足时终止。考虑到计算开销，通常使用贪心搜索算法，找到局部最优的双簇。一种是枚举方法，它使用一个容忍阈值表示被挖掘的双簇对噪声的容忍度，并试图枚举所有满足要求的作为双簇的子矩阵。下面以簇和Maple算法为例解释这些思想。,商务智能与数据挖掘,高等教育出版社2020/6/7,商务智能与数据挖掘,高等教育出版社2020/6/7,（1）使用簇算法最优化。对于一个由基因子集，和数据子集，构成的子矩阵，第i行的平均值是eiJ=1|其中，J是子矩阵E的列数。对称地，第j列的平均值是eIj=1|其中，I是子矩阵E的行数。子矩阵所有元素的平均值是eIJ=1|,=1|=1|作为双簇的子矩阵的质量可以用平均平方残基来度量：H(I，J)=1|,（)2如果（，），则称子矩阵是一个双簇，其中，是一个阈值。当时，是一个具有相干值的完美双簇。通过设置，用户可以指定相对于完美双簇，每个元素的平均噪声容忍度，因为在上式中，每个元素上的残基是residue()=极大双簇是一个双簇，使得不存在另一个由和构成的双簇，且至少有一个真包含成立。找出最大的极大双簇的计算量是巨大的，因此可以使用启发式贪心搜索算法来得到局部最优的簇。,商务智能与数据挖掘,高等教育出版社2020/6/7,该算法的运行分以下两个阶段。第一阶段为删除阶段。当矩阵的平均平方残基超过时，迭代地删除行和列。在每次迭代中，对于行，计算平均平方残基：d(i)=1|（)2此外，对于列，计算平均平方残基：d(j)=1|（)2删除具有最大平均平方残基的行或列。这一阶段结束时，得到一个由和构成的子矩阵，它是一个双簇。然而，该子矩阵可能不是极大双簇。第二阶段为增加阶段。在该阶段中，只要满足双簇的要求，就迭代地扩展删除阶段得到的双簇。在每次迭代中，考虑不在当前双簇中的所有行和所有列，计算它们的平均平方残基。平均平方残基最小的行或列被添加到当前双簇中。这个贪心搜索算法只能发现一个双簇。为了找到多个不严重重叠的双簇，可以多次运行该算法。每次运行输出一个双簇后，用随机数替换输出双簇中的元素。尽管该贪心搜索算法也许既不能找到最优的双簇，也不能找出所有的双簇，但是即便在大矩阵上它的运行速度也很快。（2）使用aple算法枚举所有的双簇。如上所述，一个由基因子集，和条件子集，构成的子矩阵是具有相干值的双簇，当且仅当对于任意1，2和1，2，有11211222。,商务智能与数据挖掘,高等教育出版社2020/6/7,对于任意的子矩阵，可以定义score为-score11211222=|(11-21)-(12-22)|一个子矩阵E是一个簇（对于基于模式的簇），E的每个矩阵的score都最多为，其中是一个阈值，用于说明以完美双簇为参考标准，用户对噪声的容忍度。这里，score控制双簇中每个元素上的噪声，而平均平方残基捕获了平均噪声。簇有一个有趣的性质：是一个簇，则的所有（，）子矩阵也都是簇。这种单调性使得人们可以得到非冗余簇的简洁表示。如果一个簇是极大的，那么该簇将不能在添加了更多的行或列之后，仍然保持簇的性质。为了避免冗余，只需要计算所有的极大簇即可，而无须计算所有的p簇。Maple算法是一种枚举所有极大簇的算法。它采用集合枚举树和深度优先策略，系统地枚举条件的各种组合。对于每个条件组合，Maple算法找出基因的最大子集，使得由和构成的子矩阵是簇。如果不是其他簇的子矩阵，则是一个极大簇。如果存在大量的条件组合，Maple算法将使用簇的单调性剪去许多无效果的条件组合。对于一个条件组合，如果不存在基因子集，使得由和构成的子矩阵是一个簇，则不必再考虑的任何超集。,商务智能与数据挖掘,高等教育出版社2020/6/7,此外，仅当对于的每个子集（），都是簇时，才考虑把作为簇的候选。Maple算法还利用一些剪枝策略来加快枚举，并保持返回所有极大簇的完全性。例如，当考察当前由和构成的簇，Maple算法收集所有可能添加的以扩展该簇的基因和条件。如果这些候选基因和条件与和一起构成了一个已经找到的簇的子矩阵，则和的任何超集的搜索都可以被剪枝。Maple算法中对极大簇的枚举类似于闭频繁项集挖掘算法（LOSET）。因此，Maple算法借用了深度优先框架和频繁模式挖掘的模式增长方法中剪枝技术的思想。这是频繁模式挖掘和聚类分析可以共享类似技术和思想的一个范例。Maple算法及其他枚举所有双簇的算法的一个优点是，它们保证结果的完全性，并且不丢失任何重叠的双簇。然而，这种枚举算法面临的一个难题是，如果矩阵变得非常大，如包含数十万顾客和数百万种产品的顾客产品矩阵，那么这些算法就会非常耗时。,2.维归约方法,子空间聚类方法试图在原数据空间的子空间中发现簇。在某些情况下，构造一个新的空间，而不是使用原数据空间的子空间效果更好。这就是聚类高维数据的维归约方法的动机。维归的方法有多种，最直接的方法是对数据集使用特征选择和提取方法，但仅使用特征提取不一定能检测出聚类结构，所以需要将特征提取和聚类方法结合起来。,商务智能与数据挖掘,高等教育出版社2020/6/7,谱聚类方法就是这样一种方法。Ng-Jordan-Weiss（NJW）算法是一种谱聚类方法。下面考察该框架的各个步骤。对谱聚类算法进行考察时，要注意用于Ng-Jordan-Weiss算法的特殊条件。给定数据对象1，n的集合，以及每两个对象之间的距离dist（i，j）（，）和期望的簇数，谱聚类方法的步骤如下。（1）使用距离度量计算相似矩阵（affinitymatrix），使得wij=()2其中，是缩放参数，控制相似度ij随dist（i，j）增加而降低的速度。在Ng-Jordan-Weiss算法中，ii被设置为。（2）使用相似矩阵，导出矩阵A（），导出的方法可能不同。Ng-Jordan-Weiss算法定义一个对角矩阵，其中ii是的第行之和，即ii=1ij然后，设置矩阵为A=D-1/2WD-1/2（3）找出矩阵的前个特征向量。一个方阵的特征向量是非零向量，与该矩阵相乘后，它仍然与原向量成比例。严格地说，向量是矩阵的特征向量，如果，则其中的称为对应的特征值。这一步基于相似矩阵，从导出个新的维度。通常，比原数据空间的维度数小得多。Ng-Jordan-Weiss算法计算矩阵的具有最大特征值的个特征向量1，k,商务智能与数据挖掘,高等教育出版社2020/6/7,（4）使用前个特征向量，把原数据映射到由前个特征向量定义的新空间，并运行诸如均值算法这样的聚类算法找出个簇。Ng-Jordan-Weiss算法把个最大的特征向量按列堆积在一起形成特征向量空间矩阵12k。通过规范化使得其每行都具有单位长度，形成矩阵，即Yij=12然后，把的每一行看作空间k中的一个点，并运行-均值算法（或其他用于划分的算法），把这些点聚类成个簇。（5）根据变换后的点被指派到步骤（4）得到的簇中的情况，把原数据对象指派到这些簇中。在Ng-Jordan-Weiss算法中，原数据对象i被指派到第j个簇中，当且仅当矩阵的第i行被指派到步骤（4）得到的第j个簇中。,三、图和网络数据聚类分析,商务智能与数据挖掘,高等教育出版社2020/6/7,图和网络数据日益增多，对图进行聚类分析的需求也随之增多。图聚类的一个应用例子是对科学出版物的作者关系进行挖掘。这些作者形成一个社会网络，其中作者是顶点，如果两位作者合作发表了一个出版物，则用一条边连接他们。此外，两位作者之间的边一般携带权重，表示两位作者（两端的顶点）合作发表了多少科学出版物，该权重可以理解为作间的合作强度。因此，该网络是一个加权图。聚类该图可以提供对作者社区与合作模式的洞察。图聚类的思路是，把图切割成若干片，片内的顶点很好地互连，而不同片内的顶点以很弱的方式连接，这样一个片就是一个簇。对于图（，），割（cut）（，）是图的顶点集的一个划分，使得并且。割的割集是边的集合（，），。割的大小是割集的边数。对于加权图，割的大小是割集的边的加权和。需要说明的是，图中两个顶点相似度的度量不能使用余弦距离等方法，需要考虑新的方法。这里介绍一种简单的相似度度量测地距离。测地距是两个顶点之间最短路径的边数。对于图中两个非连通的顶点，测地距离被定义为无穷大。,商务智能与数据挖掘,高等教育出版社2020/6/7,在聚类中，需要选择特定的割导出图中的簇。对于所涉及的割集中的一条边的每个顶点，大部分与相连接的边都属于一个簇。令deg（）为的度数，即连接到的边数。割（，）的稀疏性定义为=(),|如果一个割的稀疏性不大于其他任何割的稀疏性，则称这个割是最稀疏的。一个图可能有多个最稀疏的割。最稀疏的割试图最小化跨越划分的边数，并且平衡划分的大小。考虑图（，）上的聚类，它把该图划分成个簇。通过聚类的模块性（modularity）评估聚类的质量，将其定义为Q=|其中，i是第个簇的顶点之间的边数，i是第个簇的顶点的度数和。图的聚类的模块性是指落入簇中的边占所有边的比例与簇中顶点的度数占所有顶点度数的比例之差。模块性最大意味着图聚类最佳。从理论上讲，许多图聚类问题都可以看作在图中找最好的割，如最稀疏的割。然而，在实践中它还面临着以下挑战。（1）高计算开销。许多图割问题的计算开销都很大。最稀疏的割问题是问题，在大图上找出最优解是不现实的，需要在计算效率与结果质量之间寻求平衡。,商务智能与数据挖掘,高等教育出版社2020/6/7,（2）复杂的图。图可能比这里介绍的更为复杂，如涉及权重和或环。（3）高维性。图可能有许多顶点。在相似矩阵中，顶点用向量表示（矩阵中的一行），其维度是图中的顶点数。因此，图聚类方法必须能够处理高维数据。（4）稀疏性。大图通常是稀疏的，即在平均情况下，每个顶点只与少量其他顶点相连接。由大的稀疏图得到的矩阵可能也是稀疏的。有两类图聚类方法可以处理以上难题。一类使用聚类高维数据的方法，而另一类是专门为图聚类设计的。第一类方法基于一般的高维数据聚类方法。它们使用相似度度量方法（如测地距离）从图中提取相似矩阵，然后在相似矩阵上使用一般的聚类方法发现簇。第二类方法是专门用于图的方法。它们搜索图，找出良连通的成分作为簇。下面介绍一种称为SCAN（structuralclusteringalgorithmfornetworks，网络的结构聚类算法）的算法。给定无向图（，），对于顶点，的邻域是(u)（，）。使用结构情境相似度的思想，SCAN用规范化的公共邻域大小来度量两个顶点，之间的相似度，即(,)=|()()|()|()|其中，(）表示顶点及其相邻顶点组成的集合。该计算值越大，两个顶点越相似。SCAN算法使用相似度阈值定义簇隶属关系。对于顶点，的-邻域,定义为(）(）（，）。的-邻域包含的所有近邻，它们与的结构情境相似度至少为。在SCAN算法中，若()（其中是点数阈值），则是核心顶点。SCAN算法通过核心顶点产生簇；若顶点在核心顶点的-邻域内，则与在相同的簇中。SCAN算法遍历所有顶点，直到所有的簇都不能进一步增长。从定义可以看出，若(），顶点可以从核心点直接到达，则簇中的所有顶点都是相连的。也就是说，簇是最大的连通顶点集（集合中的每对顶点都是相连的）。可能存在顶点不属于任何簇的情况，假设顶点的邻域()包含来自多个簇的顶点，则称为中心（hub）。若一个顶点不属于任何簇，也不是中心，则它是离群点。SCAN算法如下。输入：图（，），相似度阈值，点数阈值。输出：簇的集合。方法：设置中所有的顶点为未标记的。forall未标记的顶点doif是核心顶点then产生一个新的簇标识把所有(）插入队列,商务智能与数据挖掘,高等教育出版社2020/6/7,whiledo中的第一个顶点可以直接从到达的顶点集foralldoif不是未标记的或被标记为nonmemberthen把当前的簇标识赋予endifif是未标记的then把插入队列endifendfor从中移出endwhileelse把标记为nonmemberendifendfor,商务智能与数据挖掘,高等教育出版社2020/6/7,forall标记为nonmember的顶点doif，()：和具有不同的簇标识then标记为中心else标记为离群点endifendforSCAN算法发现图的一个割，其中的每个簇都是一个顶点集。SCAN算法的时间复杂性关于边数是线性的。在大的稀疏图上，边数与顶点数是在同一数量级上。因此，在大的稀疏图上SCAN算法具有较好的可伸缩性。,商务智能与数据挖掘,高等教育出版社2020/6/7,四、具有约束的聚类分析,商务智能与数据挖掘,高等教育出版社2020/6/7,在前面所有对聚类方法的讨论中，都没有对聚类设置任何约束。但是，在实际应用中，很多聚类方法是需要考虑约束条件的。而在考虑约束条件的同时也需要考虑遵守约束的程度：一种约束是硬性的，违反该约束的聚类是不可接受的；另一种约束是软性的，违反该约束的聚类是不可取的，但是在找不到更好的解时还可以接受。,1.处理硬性约束,处理硬性约束的一般策略是在聚类的指派过程中严格遵守约束。下面以划分聚类为例来说明这一思想。给定一个数据集和实例上的约束的集合（即必须联系约束或不能联系约束），通过扩充-均值算法满足硬性约束，带约束的-均值算法称为COP-k-均值算法，它按照以下方法进行处理。（1）对必须联系约束产生超实例。计算必须联系约束的传递闭包。这里可以将所有的必须联系约束看作一个等价关系。该闭包给出一个或多个对象子集，其中一个子集中的所有对象都必须被指派到一个簇中。为了表示这种子集，把该子集的所有对象都用平均值取代。超实例还携带权重，它是超实例代表的对象数。这一步之后，必须联系约束已得到满足。,商务智能与数据挖掘,高等教育出版社2020/6/7,（2）进行修改后的-均值聚类。在-均值聚类中，对象被指派到最近的中心。如果最近中心指派违反不能联系约束，则为了遵守约束，把-均值聚类的中心指派过程修改为最近的候选中心指派。因为COP-k-均值算法确保每一步都不违反任何约束，因此它不需要回溯。它是一种贪心算法，只要约束之间不存在冲突，它将产生满足所有约束的聚类。,2.处理软性约束,进行具有软性约束的聚类是一个优化问题。当聚类违反软性约束时，在聚类上施加一个惩罚。因此，聚类的最优化目标包含两部分：优化聚类质量和最小化违反约束的惩罚。总体目标函数是聚类质量得分和惩罚得分的组合。为了解释这一点，还以划分聚类为例。给定一个数据集和实例上的软性约束的集合，利用CVQE（constrainedvectorquantizationerror）算法进行-均值聚类。CVQE使用的目标函数是-均值算法中所用的距离和，用违反约束惩罚加以调整，具体方法如下。（1）违反必须联系的惩罚。如果对象和上存在必须联系约束，但是它们被分别指派到不同的簇1和2中，则该约束被违反。作为结果，簇中心1和2之间的距离dist（，）被作为惩罚得分而被加到目标函数中。,（2）违反不能联系的惩罚。如果对象和上存在不能联系约束，但是它们被指派到共同的中心，则该约束被违反，和之间的距离dist（，）被作为惩罚得分而被加到目标函数中。,4.2高级分类分析,一、用后向传播分类分析,商务智能与数据挖掘,高等教育出版社2020/6/7,后向传播（backpropagation，BP）是一种神经网络算法。神经网络的优点有三个：一是对其影响较小；二是在缺乏属性与类之间联系的知识时，仍能对数据进行模式分类；三是它们非常适合连续值的输入和输出。当前，神经网络在手写字符识别、病理和实验医学、训练计算机朗读等领域有着广泛的应用。此外，神经网络被应用于提取规则中。另一方面，神经网络也有缺点。一是它需要很长的训练时间；二是它需要大量的参数，而且通常这些参数主要靠经验确定；三是神经网络的可解释性差。,1.多层前馈神经网络,后向传播算法一般使用多层前馈（multilayerfeed-forward）神经网络。多层前馈神经网络由一个输入层、一个或多个隐藏层和一个输出层组成，如图4-2所示。,商务智能与数据挖掘,高等教育出版社2020/6/7,图4-2展示了多层前馈神经网络的结构。多层前馈神经网络的每一层都由一些单元组成，它的输入是每个训练元组的观测属性。这些输入通过输入层，加权后提供给称为隐藏层的神经网络第二层。然后该隐藏层单元的输出可以作为输入传输给另一个隐藏层，诸如此类，形成一个多层结构。最后，由神经网络最后一个隐藏层的加权输出作为构成输出层的单元的输入。需要注意的是，隐藏层的数量是任意的，但在实际中，一般只用一个隐含层。输入层的单元称为输入单元。有时将隐藏层和输出层的单元称为神经节点（neurodes，源于符号生物学）或输出单元。图4-2所示的多层前馈神经网络具有一个隐藏层和一个输出层，因此称之为两层神经网络。需要说明的是，这里没有计入输入层，因为输入层只用来将输入传递给下一层。由于该神经网络各层的权重不回送到输入单元，或前一层的输出单元，所以称该神经网络是前馈的。另外，如果每个单元都向下一层的每个单元提供输入，则该神经网络是全连接的。每个输出单元的输入是前一层单元输出的加权和，并将一个非线性（激活）函数作用于该加权输入。当给定足够多的隐藏单元和足够多的训练样本时，多层前馈神经网络可以逼近任意函数。,商务智能与数据挖掘,高等教育出版社2020/6/7,后向传播通过迭代地处理训练元组，将每个元组的网络预测与已知的目标值相比较进行学习。目标值可以是训练元组的已知类标号（对于分类问题）或者是连续值（对于预测）。对于每个训练样本，修改权重以使得网络预测和已知目标值之间的均方误差最小。这种修改“后向”进行，即由输出层，经由每个隐藏层，到第一个隐藏层（因此称之为后向传播）。一般而言，权重将最终收敛，学习过程停止。（1）初始化权重。网络的权重被初始化为很小的随机数（例如，由-1.0到1.0，或由-0.5到0.5）。每个单元都有一个相关联的偏倚（bias）偏倚也需要初始化为很小的随机数。在初始化权重后，每个训练元组迭代以下步骤。（2）向前传播输入。首先，将训练元组通过网络的输入层输入，输入通过输入单元，不发生变化。即输入单元的输出等于它的输入。然后，计算隐藏层和输出层的每个单元的净输入和输出，如图4-3所示。图4-3给出了一个隐藏层或输出层单元的计算模式：用其输入的线性组合计算。具体而言，每个单元都有许多输入（上一层单元的输出），每个连接都有一个权重，连接该单元的每个输入乘以其对应的权重，然后求和。给定隐藏层或输出层的单元，到单元的净输入为=+,2.后向传播,商务智能与数据挖掘,高等教育出版社2020/6/7,其中，ij是从上一层的单元到单元的连接的权重；是上一层的单元的输出；而是单元的偏倚。偏倚充当阈值，用来改变单元的活性。,对于隐藏层和输出层的每个单元取其净输入，然后将激活（activation）函数作用于它。该函数象征该单元所代表的神经元的活性，Sigmoid（形）函数（又称为逻辑激活函数）是一种常见的激活函数。给定单元的净输入，则单元的输出用下式计算：=+j该函数又称为挤压函数（squashingfunction），因为它将一个较大的输入值域映射到10的范围内。该函数是非线性的，并且是可微的，使得后向传播算法可以对非线性可分的分类问题建模。对于每个隐藏层和输出层，需要计算每个输出。一般地，为减少计算量，需要为每个单元存储这些输出。,商务智能与数据挖掘,高等教育出版社2020/6/7,（）向后传播误差。通过更新权重和反映网络预测误差的偏倚，向后传播误差。对于输出层单元，误差Errj用下式计算：Errjj（）(）其中，是单元的实际输出，而是单元给定训练元组的已知目标值。需要注意的是，(）是Sigmoid函数的导数。为了计算隐藏层单元的误差，考虑下一层中连接单元的单元的误差加权和。隐藏层单元的误差是Errjj（）其中，jk是从下一个较高层中的单元到单元的连接权重，而是单元的误差。通过更新权重和偏倚反映误差的传播。其中，权重用式ijErrji和式ijijij更新，其中，ij是权重ij的改变量。后向传播使用梯度下降法搜索权重的集合。这些权重拟合训练数据，使得样本的网络预测与己知目标值之间的均方误差最小。变量是学习率，其值通常取0.01.0之间的常数。学习率有助于避免陷入决策空间的局部极小，并有助于找到全局最小。学习率低，则学习慢。而学习率太高，则可能出现在不适当的解之间摆动的情况。一般可以将学习率设置为，其中是已对训练集迭代的次数。偏倚由式（)Errj和式更新。其中，是偏倚的改变量。,商务智能与数据挖掘,高等教育出版社2020/6/7,需要注意的是，权重和偏倚有两种更新策略。一种是实例更新（caseupdate），每处理一个样本就更新权重和偏倚。另一种策略称为周期更新（epochupdate），权重和偏倚的增量累积到变量中，使得在处理完训练集中的所有元组之后再更新权重和偏倚。这其中扫描训练集的一次迭代是一个周期。理论上，后向传播的数学推导使用周期更新，而这里则采用实例更新，因为在实践中，实例更新更普遍，它通常能产生更准确的结果。（4）终止条件。如果达到以下条件之一，则训练停止。前一迭代或周期中，所有的权重改变量都小于某个指定的阈值。前一迭代或周期中，误分类的元组百分比小于某个指定的阈值。超过预先指定的迭代（周期）数。在实际应用中，权重收敛可能需要数十万个周期。为了使用训练过的网络对未知元组分类，把该元组输入训练过的网络，计算每个单元的净输入和输出（不需要计算误差和或它们的后向传播）。如果每类都有一个输出节点，则具有最高输出值的节点决定的类标号，如果只有一个输出节点，则输出值大于或等于0.5可以将其视为正类元组，而输出值小于0.5可以将其视为负类元组。,二、支持向量机,商务智能与数据挖掘,高等教育出版社2020/6/7,支持向量机（supportvectormachine，SVM）是一种对线性和非线性数据进行分类的方法。它使用一种非线性映射，把原输入数据映射到高维空间，在该空间，它搜索最佳分离超平面（即将一个类的元组与其他类分离的“决策边界”），以将两个类的数据分开。支持向量机的分类原理是：使用足够高维的、合适的非线性映射，两个类的数据总可以被超平面分开。支持向量机使用支持向量（“基本”训练元组）和边缘（由支持向量定义）发现该超平面。在应用支持向量机对数据进行分类时，面临着两种情况，一种是数据线性可分的情况，另一种是数据非线性可分的情况。,1.数据线性可分的情况,为了解释支持向量机，先讨论最简单的两类问题，即只有两个线性可分类的分类情况。设给定的数据集为（1，1），（2，2），（|D|，|D|），其中X|D|也是训练元组，具有类标号|D|。每个|D|可以取值1或1（即|D|1，1），分别代表两个不同的类。接下来，考虑只有两个属性1和的数据。由于该二维数据是线性可分的，因此可以在该空间中画一条直线，把+1类的元组与-1类的元组分开。满足需求的分割直线有无限条，但要从中找出“最好的”一条，即划,商务智能与数据挖掘,高等教育出版社2020/6/7,分元组具有最小分类误差的那一条。推广到一般的维空间，则要用最佳分离超平面来划分元组。那么如何找到最佳分离超平面呢？支持向量机通过搜索最大边缘超平面（maximummarginalhyperplane，）来处理该问题。由于具有较大边缘的超平面在对未来数据元组的分类时比具有较小边缘的超平面更准确，因此在支持向量机中搜索具有最大边缘的超平面，即最大边缘超平面。最大边缘超平面相关联的边缘给出类之间的最大分离性。分离超平面可以记为WX+b=0其中，是权重向量，即1，2，n；是属性个数；是标量，即偏倚。还是考虑只有两个属性1和2的数据，则训练元组是二维元组（1，2），其中1和2分别是在属性1和2上的值。如果把看作附加的权重，则可以把分离超平面改写成01122这样，位于分离超平面上方的点满足01122类似地，位于分离超平面下方的点满足01122调整和，使得定义边缘“侧面”的超平面可以记为H1:011221对于i1H-1:011221对于i-1,商务智能与数据挖掘,高等教育出版社2020/6/7,也就是说，落在1上或其上方的元组都属于+1类，而落在-1上或其下方的元组都属于-1类。结合以上两式得到i（01122）1落在超平面1或-1即定义边缘的“侧面”）上的任意训练元组都使上式的等号成立，称为支持向量（supportvector）。从本质上讲，支持向量是最难分类的训练元组，它给出了最多的分类信息，并且定义了边缘和最大边缘超平面。可以改写上式将它变换成一个称为被约束的（凸）二次最优化问题。这种方法使用拉格朗日公式改写上式，并使用Karush-Kuhn-Tucker（KKT）条件求解。如果数据很少（例如，少于2000个训练元组），则可以使用任何求解被约束的（凸）二次最优化问题的最优化软件包来找出支持向量和最大边缘超平面。对于大型数据，可以使用特殊的、更有效的训练支持向量机的算法。这些细节已经超出了本书的范围。一旦找出支持向量和最大边缘超平面（注意，支持向量定义最大边缘超平面），就有了一个训练后的支持向量机。最大边缘超平面是一个线性类边界，因此对应的支持向量机可以用来对线性可分的数据进行分类。这种训练后的支持向量机称为线性支持向量机。可以使用训练后的支持向量机对检验元组（即新元组）进行分类。根据上面提到的拉格朗日公式，最大边缘超平面可以改写成决策边界d(XT)=1+0,商务智能与数据挖掘,高等教育出版社2020/6/7,其中，i是支持向量i的类标号，T是检验元组，i（拉格朗日乘子）和0是由前面的二次最优化或支持向量机算法自动确定的数值参数，而是支持向量的个数。给定检验元组T，将它代入上式，然后检查结果的符号，看检验元组落在超平面的哪一侧。如果该符号为正，则T落在最大边缘超平面上或其上方，意味着支持向量机预测T属于+1类。如果该符号为负，则T落在最大边缘超平面上或其下方，意味着支持向量机预测T属于-1类。在考虑非线性可分的情况之前，还有两件重要的事情需要注意。学习后的分类器的复杂度由支持向量数刻画而不是由数据的维数刻画。因此，与其他方法相比，支持向量机不太容易拟合。支持向量是基本或临界的训练元组，它们距离决策边界（最大边缘超平面）最近。如果删除其他元组并重新训练，则会发现相同的分离超平面。此外，利用支持向量数可以计算SVM分类器的期望误差率的上界，这同样独立于数据的维度。具有少量支持向量的支持向量机具有很好的泛化性能，即使在数据的维度很高时也是如此。,商务智能与数据挖掘,高等教育出版社2020/6/7,2.数据非线性可分的情况,如果数据不是线性可分的，前面研究的线性支持向量机就不能找到可行解。这需要扩展线性支持