数据挖掘原理与应用-以石油勘探开发为例 课件 第6-10章 聚类分析 - 网络数据挖掘

第六章聚类分析·6.1聚类分析概念·6.2聚类分析算法分类·6.3聚类分析中的数据类型·6.4层次聚类方法·6.5划分聚类方法·6.6综合案例6.1聚类分析概念聚

类

分

析

概

念聚类是一种无监督分类法:没有预先指定的类别；

聚类分析中“类”的特征：聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分聚类的数目和结构都没有事先假定簇（Cluster）:一个数据对象的集合在同一个类中，对象之间具有相似性；不同类的对象之间是相异的。聚

类

分

析

概

念聚类分析（群分析、簇群分析）把一个给定的数据对象集合分成不同的簇；

所谓聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能的小，类内相似性尽量大的过程。典型的应用作为一个独立的分析工具，用于了解数据的分布；也可作为其它算法的一个数据预处理步骤；（如某商业应用往往先对用户数据进行聚类，根据聚类结果将每个簇定义为一个类，然后再基于这些训练分类模型，用于判别新用户的类型。）孤立点挖掘—异常分析聚

类

分

析

概

念聚类分析原理介绍

聚类方法的目的是寻找数据中：潜在的自然分组结构（astructureof“natural”grouping）感兴趣的关系（relationship）聚

类

分

析

概

念聚类分析原理介绍什么是自然分组结构？我们看看以下的例子：有16张牌如何将他们分为一组一组的牌呢？聚

类

分

析

概

念聚类分析原理介绍分成四组每组里花色相同组与组之间花色相异AKQJ花色相同的牌为一副Individualsuits聚

类

分

析

概

念聚类分析原理介绍符号相同的的牌Likefacecards分成四组符号相同的牌为一组AKQJ聚

类

分

析

概

念聚类分析原理介绍分成两组颜色相同的牌为一组AKQJ颜色相同的配对Blackandredsuits聚

类

分

析

概

念聚类分析原理介绍大配对和小配对Majorandminorsuits这个例子告诉我们，分组的意义在于我们怎么定义并度量“相似性”Similar因此衍生出一系列度量相似性的算法AKQJ聚

类

分

析

概

念聚类基本原理一个好的聚类方法要能产生高质量的聚类结果——簇，包括高的簇内相似性(intra-clustersimilarity)和低的簇间相似性(inter-clustersimilarity)。聚

类

分

析

概

念什么是一个好的聚类方法？判断一个聚类方法质量的好坏依赖于用于该聚类方法的相似度度量具体实现方法能否发现部分或所有隐藏模式“物以类聚”聚

类

分

析

概

念主要应用例1：数据挖掘聚类数据的基本概况特征抽取或分类聚类在数据挖掘中可以作为其他算法的预处理步骤，获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率，或将聚类结果用于进一步关联分析，以获得进一步的有用信息；聚

类

分

析

概

念主要应用例2：在商业上聚类分析可以帮助市场分析人员从客户基本资料数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。聚

类

分

析

概

念主要应用通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析或者孤立点挖掘。集中分析：这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景；孤立点挖掘：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。含有孤立点的数据分布聚

类

分

析

概

念要求根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。典型要求可以通过以下几个方面来刻画：可伸缩性：指聚类算法不论对于小数据集还是对于大数据集，都应是有效的。具有较高伸缩性的算法有：WaveCluster、ROCK

等聚

类

分

析

概

念要求能发现任意形状的簇：许多聚类算法经常使用欧几里得距离（欧氏距离）来作为相似性度量方法，但基于这样的距离度量的算法趋向于发现具有相近密度和尺寸的球状簇。对于一个可能是任意形状的簇的情况，提出能发现任意形状簇的算法是很重要的。2D距离3D距离聚

类

分

析

概

念要求在决定输入参数的时候，尽量不需要特定的领域知识：聚类结果对于输入的参数很敏感。如果算法的参数依赖于领域特定的知识，那么就会降低算法的可迁移性，还会导致用户负担加重和质量难以控制。聚

类

分

析

概

念要求能够处理噪声和异常：聚

类

分

析

概

念要求对输入数据对象的顺序不敏感：聚

类

分

析

概

念要求能处理高维数据：既可处理属性较少的数据，又能处理属性较多的数据。很多聚类算法擅长处理低维数据，一般只涉及两维到三维，我们对两、三维数据的聚类结果很容易直观地判断聚类的质量。但是，高维数据聚类结果的判断就不那样直观了。数据对象在高维空间的聚类是非常具有挑战性的，尤其是考虑到这样的数据可能高度偏斜并且非常稀疏。聚

类

分

析

概

念要求能产生一个好的、能满足用户指定约束的聚类结果：在实际应用当中可能需要在各种约束条件下进行聚类。既要找到满足特定的约束，又要具有良好聚类特性的数据分组是一项具有挑战性的任务。聚

类

分

析

概

念要求结果是可解释的、可理解的和可用的。可视化聚类。为了聚类可视化，可以使用最流行的降维方法之一，即PCA和t-SNE。PCA：t-SNE：6.2聚类分析算法分类聚

类

分

析

算

法

分

类不同标准按照聚类标准按照聚类算法所处理的数据类型按照聚类的尺度按照聚类算法的思路聚

类

分

析

算

法

分

类按照聚类标准统计聚类方法：

统计聚类算法基于对象之间的几何距离进行聚类。这种聚类算法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分。因此，它要求所有的数据必须预先给定，而不能动态地增加新的数据对象。

聚

类

分

析

算

法

分

类按照聚类标准概念聚类方法：

概念聚类算法基于对象具有的概念进行聚类。这里的距离不再是传统方法中的几何距离，而是根据概念的描述来确定的。典型的概念聚类或形成方法有COBWEB、OLOC和基于列联表的方法。以COBWEB为例：聚

类

分

析

算

法

分

类按照聚类算法所处理的数据类型数值型数据聚类算法：

数值型数据聚类算法所分析的数据的属性为数值数据，因此可对所处理的数据直接比较大小。目前，大多数的聚类算法都是基于数值型数据的。聚

类

分

析

算

法

分

类按照聚类算法所处理的数据类型离散型数据聚类算法：

由于数据挖掘的内容经常含有非数值的离散数据，近年来人们在离散型数据聚类算法方面做了许多研究，提出了一些基于此类数据的聚类算法，如k模(k-mode)、ROCK、CACTUS、STIRR等。聚

类

分

析

算

法

分

类按照聚类算法所处理的数据类型混合型数据聚类算法：

混合型数据聚类算法是能同时处理数值数据和离散数据的聚类算法，这类聚类算法通常功能强大，但性能往往不尽人意。混合型数据聚类算法的典型算法为k原型(k-prototypes)算法。混合型数据的相似度计算比较复杂，需要考虑不同类型数据的权重和转换。聚

类

分

析

算

法

分

类按照聚类的尺度基于距离的聚类算法：

距离是聚类分析常用的分类统计量。常用的距离定义有欧氏距离和马氏距离。许多聚类算法都是用各式各样的距离来衡量数据对象之间的相似度，如k-means、k-medoids、BIRCH、CURE等算法。单个样本的马氏距离：两个样本(维度)之间的马氏距离，显然如果两个样本是独立同分布，马氏距离就变成了欧氏距离：聚

类

分

析

算

法

分

类按照聚类的尺度基于密度的聚类算法：

从广义上说，基于密度和基于网格的算法都可算作基于密度的算法。此类算法通常需要规定最小密度门限值。算法同样适用于欧几里得空间和曼哈坦空间，对噪声数据不敏感，可以发现不规则的类，但当类或子类的粒度小于密度计算单位时，会被遗漏。聚

类

分

析

算

法

分

类按照聚类的尺度基于互连性的聚类算法：

基于互连性(LinkageBased)的聚类算法通常基于图或超图模型。它们通常将数据集映像为图或超图，满足连接条件的数据对象之间画一条边，高度连通的数据聚为一类。属于此类的算法有：ROCK、CHAMELEON、ARHP、STIRR、CACTUS等。此类算法可适用于任意形状的度量空间，聚类的质量取决于链或边的定义，不适合处理太大的数据集。当数据量大时，通常忽略权重小的边，使图变稀疏，以提高效率，但会影响聚类质量。聚

类

分

析

算

法

分

类按照聚类算法的思路层次法(HierarchicalMethods)：

层次方法对给定数据对象集合进行层次的分解。根据层次的分解方法，层次方法又可以分为凝聚的和分裂的。聚

类

分

析

算

法

分

类按照聚类算法的思路层次法(HierarchicalMethods)：

层次方法对给定数据对象集合进行层次的分解。根据层次的分解方法，层次方法又可以分为凝聚的和分裂的。聚

类

分

析

算

法

分

类按照聚类算法的思路划分法(PartitioningMethods)：

给定一个n个对象或者元组的数据库，划分方法构建数据的k个划分，每个划分表示一个簇，并且k≤n。它将数据划分为k个组，同时满足如下的要求：每个组至少包含一个对象；每个对象必须属于且只能属于一个组。划分法在数据集上进行一层划分。对于一个给定的k，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好。属于该类的聚类算法有：k-means、k-medoids、k-mode、k-prototypes、PAM、CLARA、CLARANS等。聚

类

分

析

算

法

分

类按照聚类算法的思路基于密度的算法(DensitybasedMethods)：

基于密度的算法与其他方法的一个根本区别是：它不是用各式各样的距离作为分类统计量，而是看数据对象是否属于相连的密度域，属于相连密度域的数据对象归为一类。基于密度的算法能够克服基于距离的算法只能发现“类圆形”聚类的缺点。其主要思想是：只要临近区域的密度超过某个阈值，就继续聚类。通过不断地寻找被低密度分割的高密度区域来达到聚类的目的。可以用于消除数据中的噪声，发现任意形状的簇。如DBSCAN属于密度聚类算法。聚

类

分

析

算

法

分

类按照聚类算法的思路基于网格的算法(GridbasedMethods)：

基于网格的算法首先将数据空间划分成为有限个单元(Cell)的网格结构，所有的处理都是以单个单元为对象的。这样处理的一个突出优点是处理速度快，通常与目标数据库中记录的个数无关，只与划分数据空间的单元数有关。但此算法处理方法较粗放，往往影响聚类质量。代表算法有STING、CLIQUE、WaveCluster、DBCLASD、OptiGrid算法。聚

类

分

析

算

法

分

类按照聚类算法的思路基于模型的算法(ModelbasedMethods)：

基于模型的算法给每一个簇假定一个模型，然后去寻找能够很好地满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其他函数。它的一个潜在的假定是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方案：统计的方案和神经网络的方案。基于统计学模型的算法有COBWEB、Autoclass，基于神经网络模型的算法有SOM。6.3聚类分析中的数据类型聚类分析中的数据类型基本数据结构

聚类分析中的数据类型基本数据结构相异度矩阵（差异矩阵）是一个“对象-对象”结构，存放n个对象两两之间的近似性（差异性），采用n*n的矩阵形式表示。聚类分析中的数据类型基本数据结构相异度矩阵（差异矩阵）：

其中d(i,j)表示对象i和对象j之间的差异（或不相似程度）。通常d(i,j)为一个非负数；当对象i和对象j非常相似或彼此“接近”时，该数值接近0；该数值越大，就表示对象i和对象j越不相似。由于有d(i,j)=d(j,i)且d(i,i)=0，所以，矩阵呈现出上三角或下三角的形式。聚类分析中的数据类型注意：数据矩阵通常称为双模（two-mode）矩阵：行和列分布表示不同的实体；相异度矩阵常被称为单模（one-mode）矩阵：行和列表示同一实体。许多聚类算法都是以相异度矩阵为基础计算的，所以如果数据是以数据矩阵的形式给出的，则需要首先转换为相异度矩阵，才可以利用聚类算法来处理。聚类分析中的数据类型注意：

由于各变量表示样品的各种性质，往往使用不同的度量单位，其观测值也可能相差十分悬殊。这样，绝对值大的变量其影响可能会湮没绝对值小的变量，使后者应有的作用得不到反映。为了确保各变量在分析中的地位相同，往往需要对数据进行标准化变换。聚类分析中的数据类型例6.2假设A、B、C三种岩石在摆球硬度统计中的弹次、钻进时效指标中的金刚石钻进两个变量上的值如下表6.1。钻进时效指标有“m·h-1”和“mm·h-1”两种单位。案例摆球弹次（次）钻进指标（m·h-1）钻进指标（mm·h-1）A353.103100B423.003000C302.902900聚类分析中的数据类型例6.2表给出了基于摆球弹次和钻进指标的两种单位，使用简单欧式距离方法进行相似性测度的结果，距离越小的个案，说明相似程度越高，越可能聚为一类。当单位为“m·h-1”时，A-C之间的距离最小，说明两者的相似性最高，其次为A-B、B-C；而若以单位“mm·h-1”进行测量，那A-C之间的相似性就变为了最低的，A-B、B-C的相似性近似，这意味着钻进指标在聚类中起主导作用。案例钻进指标（m·h-1）钻进指标（mm·h-1）A-B7.00100.24A-C5.49200.06B-C12.00100.72聚类分析中的数据类型标准化最常见的标准化方法就是Z标准化，也叫标准差标准化，这种方法给予原始数据的均值(Mean)和标准差(StandardDeviation)进行数据的标准化。

聚类分析中的数据类型标准化极差标准化，极差⼜称范围误差或全距(Range)，以R表⽰，是用来表示统计数据中的变异量数(MeasuresofVariation)，其最⼤值与最⼩值之间的差距，即最⼤值减最⼩值后所得之数据。

聚类分析中的数据类型标准化极差正规化，与极差标准化类似，极差正规化使用最小值而不是均值。变换后的数据最小为0，最大为1，其余在区间[0，1]内。聚类分析中的数据类型数值型数据的相异性度量在标准化之后，或在无需标准化的特定应用中，由数值所描述对象之间的差异（或相似）程度可以通过计算相应两个对象之间距离来确定。最常用的距离计算公式就是欧氏距离(Euclideandistance)：另一个常用的距离计算方法就是Manhattan距离：聚类分析中的数据类型数值型数据的相异性度量欧氏距离和Manhattan距离均满足距离函数的有关数学性质(要求)：n非负性：d(i,j)>=0，表示对象之间距离为非负数的一个数值。n同一性：d(i,j)=0，当且仅当i=j，表示对象自身之间距离为零。n对称性：d(i,j)=d(j,i)，表示对象之间距离是对称函数。n直递性：d(i,j)<=d(i,h)+d(h,j)，表示对象自身之间距离满足“两边之和不小于第三边”的性质。聚类分析中的数据类型数值型数据的相异性度量Minkowski距离是欧式距离和Manhattan距离的一个推广：若每个变量均可被赋予一个权值，以表示其所代表属性的重要性。那么带权的欧氏距离计算公式就是：聚类分析中的数据类型数值型数据的相异性度量除计算距离外，还有相似系数法比较数据相异性，两个对象间的相似系数也可有多种定义形式如：夹角余弦法、相关系数法。①夹角余弦

两变量的夹角余弦定义为：聚类分析中的数据类型数值型数据的相异性度量夹角余弦法将两变量和的夹角余弦定义为：②相关系数两变量的相关系数定义为：聚类分析中的数据类型其他类型变量相似性值二值变量（二元变量）如果认为所有的二值变量的权值均相同，那么就能得到一个2*2的条件表：同样的基于对称二值变量所计算相应的相似（或差异）性就称为是不变相似性(InvariantSimilarity)，因为无论如何对相应二值变量进行编码并不影响到它们相似（或差异）性的计算结果。简单匹配函数：给定一个二元变量，如果认为取1值比取0值所表示的情况更重要，则这样的二元变量被认为是单性的（好像只有一个状态）。基于这样的二元变量的相似度被称为非恒定的相似度。对象i10合计对象j1qrq+r0sts+t合计q+sr+tp聚类分析中的数据类型例题6.3假设一个油气田岩石可钻分级测试记录表如表所示，表中所描述的属性(变量)分别为:name，“回次长度/m”>1，“可钻性/m·h-1”<1，“test-1”，“test-2”，“test-3”和“test-4”。其中，name作为(岩石)对象的标识，其它变量均为非对称二元变量。name回次长度/m”>1可钻性/m·h-1”<1test-1test-2test-3test-4泥灰岩Y(1)N(0)P(1)N(0)N(0)N(0)火山凝灰岩Y(1)N(0)P(1)N(0)P(1)N(0)辉长岩Y(1)Y(1)N(0)N(0)N(0)N(0)聚类分析中的数据类型例题6.3name回次长度/m”>1可钻性/m·h-1”<1test-1test-2test-3test-4泥灰岩Y(1)N(0)P(1)N(0)N(0)N(0)火山凝灰岩Y(1)N(0)P(1)N(0)P(1)N(0)辉长岩Y(1)Y(1)N(0)N(0)N(0)N(0)根据非对称属性（变量）计算不同对象（岩石）之间的距离（差异性），计算结果如下：由于辉长岩和火山凝灰岩之间的距离最大，因此不大可能得的是同一可钻等级的岩石，而泥灰岩和火山凝灰岩之间的距离最小，因此可能是同一可钻等级的岩石。6.4层次聚类方法层次聚类方法层次方法层次聚类方法是通过将数据组织为若干组并形成一个组的树来进行聚类的。凝聚层次方法：也称自底向上方法，一开始将每个对象作为单独的一组，然后相继地合并相近的对象或组，直到所有的组合并为一个，或达到某个终止条件，代表：AGNES算法；分裂层次方法：也称自顶向下方法，一开始所有对象置于一个簇中，在迭代的每一步，一个簇被分裂为更小的簇，直到最终每个对象单独为一个簇，或达到某个终止条件，代表：DIANA算法。层

次

聚

类

方

法层次方法最短距离法：又称单连接法或最近邻连接法。下式定义了类与类之间的距离为两类最近样本间的距离：最长距离法：又称完全连接法或最远紧邻连接法，类与类之间的距离定义为两类最远样本间的距离：层

次

聚

类

方

法层次方法中间距离法（medianmethod）：如假定在聚类的过程中两个类G1和G2合并成一个新类GN=(G1,G2)。则GN和其它任一类G3的距离可定义为G1G2G3三角形中线的平方，中间距离进行聚类时,一般都采用距离的平方。类间距离定义为：类平均距离法(AverageLinkageMethod)：计算类间所有样本点的平均距离，如图6.10所示，该法利用了所有样本的信息，被认为是较好的系统聚类法。层

次

聚

类

方

法层次方法重心法(CentroidMethod)：类与类间的距离用各自重心间的欧式距离表示，如图6.11所示。优点是对异常值不敏感，结果更稳定。层次聚类方法层次方法离差平方和法（ward’smethod）：类内离差平方和（类中各样品到类重心（均值）的平方欧式距离之和）最小，类间最大，如图所示。聚类过程中使小类内离差平方和增加最小的两小类应首先合并为一类。特点是对异常值很敏感；对较大的类倾向产生较大的距离，从而不易合并，较符合实际需要。层次聚类方法最短距离法

又称单连接法或最近邻连接法

定义类与类之间的距离为两类最近样本间的距离，即最短距离法：DKL=d23层

次

聚

类

方

法例6.4

假定5个对象间的距离如下表所示，试用最短距离法的凝聚层次聚类，并画出树状图（Dengrogram）。编号1234512345004045471550层

次

聚

类

方

法将2和5合并成一个新类{2，5}

再求{2，5}和1，3，4之间的距离

d{2,5}1=min{d21,d51}=min{6,7}=6

d{2,5)3=min{d23,d53}=min{4,5}=4d{2,5)4=min{d24,d54}=min{4,5}=4编号{2,5}134{2,5}134004204350层

次

聚

类

方

法编号{2,5}{1,3}4{2,5}{1,3}4040430

在这4个类中，最靠近的两个类是1和3，合并成{1，3}，再求{1，3}到{2，5}的距离：d{1,3}{2,5}=min{d1{2,5},d3{2,5}}=4再求{1，3}到4的距离：d{1,3}4=min{d14,d34}=3层

次

聚

类

方

法编号{2,5}{1,3,4}{2,5}{1,3,4}040层

次

聚

类

方

法

层

123425134

最短距离的树状图层

次

聚

类

方

法

层

123425134

最短距离的树状图层

次

聚

类

方

法

层次的方法缺陷：

一旦一个步骤（合并或分裂）完成，就不能被撤销或修正，因此产生了改进的层次聚类方法，如BRICH，CURE，ROCK，Chameleon。层

次

聚

类

方

法改进的层次方法BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)使用聚类特征(ClusteringFeature,CF)树的多阶段聚类，是为大量数值数据聚类设计的。它使用聚类特征来概括一个类，使用聚类特征树来表示聚类的层次结构。CURE（ClusteringUsingRepresentatives）方法针对大型数据库的一种新颖的层次聚类算法，该算法选择基于重心和基于代表对象方法之间的中间策略。SudipnoGuha等1999年提出的一个著名的面向分类属性数据的凝聚层次聚类算法ROCK(RObustClusteringusinglinKs)，其突出贡献是采用公共近邻（链接）数的全局信息作为评价数据点间相关性的度量标准，而不是传统的基于两点间距离的局部度量函数。Chameleon（变色龙）是一种层次聚类算法，采用动态建模来确定一对簇之间的相似度。簇的相似度由如下评估：（1）簇中对象的连接情况；（2）簇的邻近性。也就是说如果两个簇的互联性都很高并且它们之间又靠的很近就将其合并。6.5划分聚类方法划

分

聚

类

方

法划分方法给定包含n个数据对象的数据库和所要形成的聚类个数k，划分算法将对象集合划分为k份（k≤n），其中每个划分均代表一个聚类。所形成的聚类将使得一个客观划分标准（常称为相似函数，如距离）最优化；从而使得一个聚类中的对象是“相似”的；而不同聚类中的对象是“不相似”的。遵循的是全局最优原则，需要穷举所有可能的划分。划分聚类方法给定一个包含n个对象的集合，构建数据的K个分区。大部分分割方法是基于距离的，所以只能发现球类簇。划

分聚类方法划分方法的特点Ø发现球状互斥的簇Ø基于距离Ø可以用均值或者中心点代表簇的中心Ø对中小规模数据有效划

分

聚

类

方

法划分方法（K-means）K-means聚类又称K-平均算法，是MacQueen提出的一种无监督的聚类算法，它在最小化误差函数的基础上将样本集划分为预定的类数k。划

分

聚

类

方

法K-means步骤可视化初始化散点图

初始化聚类中心迭代10次，聚类中心轨迹

最终聚类效果划

分

聚

类

方

法示例

假设空间数据对象分布如图5-5(a)所示，设是k＝3，也就是需要将数据集划分为3个簇（聚类）。图5-5k-means算法聚类过程示意描述划

分聚类方法示例

根据算法5.1，从数据集中任意选择三个对象作为初始聚类中心(图(a)中这些对象被标上了“+”)，其余对象则根据与这三个聚类中心(对象)的距离，根据最近距离原则，逐个分别聚类到这三个聚类中心所代表的(3个)聚类中，由此获得了如图(a)所示的三个聚类(以虚线圈出)。划

分聚类方法示例

在完成第一轮聚类之后，各聚类中心发生了变化。继而更新3个聚类的聚类中心(图(b)中这些对象被标上了“十”)，也就是分别根据各聚类中的对象重新计算相应聚类的(对象)均值。根据所获得的3个新聚类中心，以及各对象与这三个聚类中心的距离，(根据最近距离原则)对所有对象进行重新归类。有关变化情况如图(b)所示(已用粗虚线圈出)。划

分聚类方法示例

再次重复上述过程就可获得如图(c)所示的聚类结果(已用实线圈出)，这时由于各聚类中的对象(归属)已不再变化，整个聚类结束。算法的特点：只适用于聚类均值有意义的场合，在某些应用中，如：数据集中包含符号属性时，直接应用k-means算法就有问题；用户必须事先指定k的个数；对噪声和孤立点数据敏感，少量的该类数据能够对聚类均值起到很大的影响；通常以局部最优结束。不适合发现非凸形状的簇，或者大小差别很大的簇划

分

聚

类

方

法基于密度的聚类方法DBSCAN算法是一种基于高密度联通区域的聚类算法，它将类簇定义为高密度相连点的最大集合。它本身对噪声不敏感，并且能发现任意形状的类簇。基本思想为：如果一个对象在它半径为ℇ的邻域中至少包含有MinPts个对象，那么该区域被认为是密集的。为了明确这样的密集区域，该算法涉及到有关密度的一系列定义，进而根据这些定义来确定密集区域，即确定各个类并隔离出异常值。划

分

聚

类

方

法基于密度的聚类方法n

ε−近邻：

一个给定对象的ε半径内的近邻就称为该对象的ε−近邻；n对象阈值： 一个对象的ε−近邻中数据对象阈值；n核对象： 若一个对象的ε−近邻至少包含一定数目（MinPts）的对象，该对象就称为核对象；n直接密度可达： 给定一组对象集，若对象为另一个对象的ε−近邻且为核对象，那么就说是从可以“直接密度可达”；划

分

聚

类

方

法基于密度的聚类方法

划

分

聚

类

方

法划分方法（DBSCAN）DBSCAN是一个基于高密度连接区域的密度聚类方法，该算法将具有足够高密度的区域划分为簇，它定义簇为密度相连的点的最大集合。DBSCAN通过检查数据库中每个点的ε−近邻，不断生长足够高密度区域来寻找聚类，能够在带有“噪声”的空间数据库中发现任意形状的聚类。划

分

聚

类

方

法基于网格的方法基于网格聚类方法利用多维网格数据结构。它将空间划分为有限数目的单元，以构成一个可以进行聚类分析的网格结构。这种方法的主要特点就是处理时间与数据对象数目无关，仅依赖于量化空间中每一维上的单元数目，因此基于网格聚类方法处理时间很短。下面是其中两种代表算法：STING将空间划分为方形单元。不同层次的方形单元对应不同层次的分辨率。这些单元构成了一个层次结构：高层次单元被分解形成一组低层次单元。有关各网格单元属性的统计信息（如均值、最大、最小）可以事先运算和存储。这些信息将在查询处理用到。CLIQUE给定一个大规模多维数据点，数据空间中的数据点通常并不是均匀分布的。聚类识别稀疏和“拥挤”空间区域（unit），以便发现数据集的整个分布；若一个unit所包含数据点中的一部分超过了输入模型参数，那么这个unit就是密集的。方法中，一个聚类被定义为连接的密集的最大集合。划

分

聚

类

方

法

基于模型的聚类方法试图对给定数据与某个数学模型达成最佳拟合。这类方法基于数据都是有一个内在的混合概率分布假设来进行的，通常假定数据具备一定的概率分布，并通过优化给定的数据，使其适应某些数学模型，并基于此产生聚类。基于模型聚类方法主要有两种：统计方法和神经网络方法。神经网络聚类方法是将每个聚类描述成一个例证（exemplar）。每个例证作为聚类的一个“典型”；它不必与一个示例或对象相对应。可以根据新对象与哪个例证最相似（基于某种距离计算方法）而将它分派到相应的聚类中。可以通过聚类的例证来预测分派到该聚类的一个对象的属性。划

分

聚

类

方

法模糊聚类算法FCM在一些没有确定支持的情况中，聚类可以引入模糊逻辑概念。对于模糊集来说，一个数据点都是以一定程度属于某个类，也可以同时以不同的程度属于几个类。常用的模糊聚类算法是1973年提出的模糊C平均值(FuzzyC-Means，FCM)算法，经常用于模式识别。FCM算法采用误差平方和函数作为聚类准则函数，即FCM试图最小化误差的平方和。划

分

聚

类

方

法例6.8Iris鸢尾花数据集是常用的分类实验数据集，其内包含3类分别为山鸢尾（Iris-setosa）、变色鸢尾（Iris-versicolor）和维吉尼亚鸢尾（Iris-virginica），共150条记录，每类各50个数据，每条记录都有4项特征：花萼长度、花萼宽度、花瓣长度、花瓣宽度，以上四个特征的单位都是厘米（cm）划

分

聚

类

方

法例6.8初始化和更新隶属度矩阵划

分

聚

类

方

法例6.8计算聚类中心划

分

聚

类

方

法例6.8模糊c均值聚类算法总框架划

分

聚

类

方

法例6.8使用FCM聚类鸢尾花数据集结果6.6综合案例综

合

案

例各省消费性支出的聚类数据2011年全国31个省级行政区的城镇居民家庭人均消费性支出的8个主要指标的数据。根据这些数据，把31个省用k均值聚类法分成4到5类。综

合

案

例各省消费性支出的聚类数据综

合

案

例各省消费性支出的聚类用快速聚类法分成4类

因为各列都是某一类别的消费的平均值，所以是可比的，不需要进行标准化处理。如果各列不可比而且方差相差比较悬殊，则应该进行标准化处理，比如每列除以标准差，每列除以极差，每列改成秩统计量，等等。综

合

案

例各省消费性支出的聚类用快速聚类法分成4类综

合

案

例各省消费性支出的聚类用散点图矩阵表现分类效果综

合

案

例各省消费性支出的聚类用散点图矩阵表现分类效果综

合

案

例各省消费性支出的聚类用主成分图表现分类

因为聚类的数据是多元的，所以难以用普通散点图表现聚类结果。可以计算数据的主成分分析，用前两个主成分作散点图并用不同颜色表示不同类别。综

合

案

例各省消费性支出的聚类用星图验证分类

因为聚类的数据是多元的，所以难以用普通散点图表现聚类结果。可以计算数据的主成分分析，用前两个主成分作散点图并用不同颜色表示不同类别。综

合

案

例各省消费性支出的聚类分类个数的考察

作解释变差比例的图形。从图形看2大类比较好。综

合

案

例陶器考古聚类

数据集pottery包含了对罗马统治时期英国的5个窑出土的陶器的化学测量数据。这5个窑分别处于3个不同地区。用k均值法聚类。综

合

案

例陶器考古聚类——散点图矩阵综

合

案

例陶器考古聚类

各个变量的方差：方差的差别较大，应进行标准化。可以每列除以标准差。综

合

案

例陶器考古聚类基于相关阵计算主成分，作前两个主成分的散点图：从主成分看明显分成3组，恰好是5个窑所在的三个地区。综

合

案

例陶器考古聚类用k均值聚类，对不同的类数计算解释百分比，作图显示：可以看出分成3类以后再增加分类的效益明显降低。综

合

案

例陶器考古聚类可以看出，分类1由1号窑组成，分类2由2、3号窑组成，分类3由4、5号窑组成，这3个分类恰好对应了5个窑所在的3各地区。作k均值聚类，按各类中心的变量值对类别重新编号，这样可以使得聚类的编号有稳定结果。对比kiln和clus_new的值：clus_new1234512100002012200300055综

合

案

例陶器考古聚类按分类作主成分图：·基本概念·关联规则挖掘方法·挖掘频繁项集的模式增长方法·多种关联规则挖掘·关联模式评估7.1基本概念基

本

概

念含义找出所有包含B的规则找出所有包含A的规则找出所有包含AB的规则找出最好的K挑规则AB目的从数据库中发现频繁出现的多个相关联数据项的过程。

关联规则最早是由Agrawal等人于1993年针对购物篮分析问题提出的。不同商品的联系规则分析顾客购买习惯[Agrawal.1993.MiningAssociationRulesbetweenSetsofItemsinLargeDatabases]基

本

概

念1.项目集设I={i1,i2,…,im}是数据项（项目）的集合，即项目集，简称项集(Itemset)。2.事务数据库D是事务数据库，其中每个事务T是数据项I的子集，即T⸦I。每一个事务有一个标识符，称作TID，即D可以表示为{T1,T2,T3……}。3.k-项集k-项集是指集合中包含k个项的项集。如：{肥皂，毛巾}是一个2-项集。基

本

概

念基

本

概

念例题7-1购物篮的例子某商店里所有商品构成项目集I={牛奶，面包，鸡蛋，牙膏，肥皂，酸奶}购物记录组成一个事务数据库D={T1,T2,T3,T4,T5,T6}该库有6个事务，每个事务是I的子集T1={牛奶，面包，鸡蛋}是3-项集。TIDItemsT1牛奶，面包，鸡蛋T2牛奶，面包，牙膏，肥皂T3牙膏，面包，肥皂T4牙膏，肥皂T5牛奶，面包，鸡蛋，酸奶T6牛奶，面包，牙膏基

本

概

念频繁项集和关联规则

基

本

概

念频繁项集和关联规则设X={牛奶，面包}X的支持计数Support_count(X)=4X的支持度：Support(X)=4/6=66.6%TIDItemsT1牛奶，面包，鸡蛋T2牛奶，面包，牙膏，肥皂T3牙膏，面包，肥皂T4牙膏，肥皂T5牛奶，面包，鸡蛋，酸奶T6牛奶，面包，牙膏基

本

概

念频繁项集和关联规则1.频繁项集（大项集）支持度超过（包括等于）用户或领域专家设定的最小支持度阈值的项集。2.最大频繁项集（最大项集）频繁项集的所有超级都不是频繁项集。研究频繁模式得到关联规则和其他联系实际应用规则和联系基

本

概

念频繁项集和关联规则关联规则X

Y[s%,c%]

关联规则的前件关联规则的后件关联规则的支持度关联规则的置信度X

I，Y

I，X∩Y=

基

本

概

念频繁项集和关联规则关联规则的支持度频繁规则X

Y在事务数据库D中成立，有s%的事务包含X∪Y（即项集X和Y的并），即D中事务包含X∪Y的百分比，则称关联规则X

Y的支持度为s%，也就是支持度是一个概率值，表示为：Support(X

Y)=P(X∪Y)=(Support_count(X∪Y))/(|D|)基

本

概

念频繁项集和关联规则关联规则的置信度在规则X

Y在事务数据库D中的置信度为c%，表示D中包含X的事务同时也包含Y事务的百分比，也就是条件概率P(Y|X)，表示为：Confidence(X

Y)=P(Y│X)=(Support(X∪Y))/(Support(X))=(Support_count(X∪Y))/(Support_count(X))基

本

概

念例题7-2规则度量在例7-1购物篮中求出关联规则{牛奶}

{面包}（常写为规则：牛奶

面包）的支持度与置信度。TIDItemsT1牛奶，面包，鸡蛋T2牛奶，面包，牙膏，肥皂T3牙膏，面包，肥皂T4牙膏，肥皂T5牛奶，面包，鸡蛋，酸奶T6牛奶，面包，牙膏基

本

概

念例题7-2

Support(牛奶

面包)=P（牛奶∪面包）=4/6=66.6%Support(面包

牛奶)=P（面包∪牛奶）=4/6=66.6%Confidence(牛奶

面包)=p(面包│牛奶)=(P(牛奶∪面包))/(P(牛奶))=4/4=100%Confidence(面包

牛奶)=p(牛奶│面包)=(P(牛奶∪面包))/(P(面包))=4/5=80%即两个关联规则形式化表示为：牛奶

面包[66.6%,100%]；面包

牛奶[66.6%,80%]。TIDItemsT1牛奶，面包，鸡蛋T2牛奶，面包，牙膏，肥皂T3牙膏，面包，肥皂T4牙膏，肥皂T5牛奶，面包，鸡蛋，酸奶T6牛奶，面包，牙膏基

本

概

念关联规则挖掘的应用商业领域金融行业网络安全Web挖掘辅助医疗诊断7.2关联规则挖掘方法关联规则挖掘方法关联规则挖掘基本过程通过用户指定最小支持度和最小置信度寻找强关联规则的过程。可以划分为两个子问题：频繁项集的产生找出事务数据集D中的所有频繁项集关联规则的产生在所有频繁项集中找出置信度不小于最小置信度的关联规则关联规则挖掘方法Apriori先验性质频繁项集的核心是计数超集的计数≤子集的计数1、频繁项集的任何子集也一定是频繁的。例如：项集{A，C}是频繁项集

{A}和{C}也为频繁项集。2、非频繁项集的超集一定是非频繁的。例如：项集{D}不是频繁项集

{A，D}和{C，D}也不是频繁项集。关联规则挖掘方法Apriori算法通常，Apriori算法分两步进行，Lk表示K项集的频繁集连接步Lk-1生成Lk的候选集剪枝步剪裁不符合最小支持度的候选项Lk-1与Lk-1进行连接使用先验性质关联规则挖掘方法Apriori算法逐层搜索的迭代方法Ck是Lk的超集关联规则挖掘方法例题7-3Apriori算法。为后面书写方便和说明问题，将例7-1中商品集I简记为：I={I1，I2，I3，I4，I5，I6}，有6个事务，即|D|=6，如表7.2所示。假设最小支持计数阈值为2，相当于最小支持度阈值为2/9=22%。TIDItemsT1I1，I2，I3T2I1，I2，I4，I5T3I2，I4，I5T4I4，I5T5I1，I2，I3，I6T6I1，I2，I4关联规则挖掘方法例题7-3关联规则挖掘方法Apriori算法—关联规则生成

关联规则挖掘方法例题7-4TIDItemsT1I1，I2，I3T2I1，I2，I4，I5T3I2，I4，I5T4I4，I5T5I1，I2，I3，I6T6I1，I2，I4生成关联规则。在例7-3产生的频繁项集中，对于频繁项集X={I1,I2,I3}（支持度计数为2），可以通过X产生哪些关联规则？X的非空真子集有{I1}、{I2}、{I3}、{I1，I2}、{I1，I3}、{I2，I3}，其频繁支持计数分别为：4、5、2、4、2、2。关联规则挖掘方法例题7-4结果关联规则如下，每个都列出置信度。I1

{I2，I3}，Confidence=2／4=50％I2

{I1，I3}，Confidence=2／5=40％{I1，I2}

I3，Confidence=2／4=50％I3

{I1，I2}，Confidence=2／2=100％{I1，I3}

I2，Confidence=2／2=100％{I2，I3}

I1，Confidence=2／2=100％如果最小置信度阈值为70％，则后面三个规则满足条件，即强关联规则。关联规则挖掘方法Apriori算法的特点1Apriori算法是一个迭代算法。2数据采用水平组织方，即数据按照{事务编号，项目集}的形式组织。3可以利用Apriori先验性质进行优化。4适合事务型数据库（或集）的关联规则挖掘。5适合稀疏数据集，也就是频繁项集长度稍小的数据集。关联规则挖掘方法Apriori算法的缺点1多次扫描事务数据集D，需要很大的I/O负载。2可能产生巨大数量的候选项集。关联规则挖掘方法Apriori算法的改进思路—散列(Hash)技术1995年，Park等提出了一种基于散列（Hash）技术产生频繁项集的算法，把扫描的项集散列到不同的Hash桶中优点：每个频繁项集最多只可能放在一个特定的桶里，帮助有效压缩候选k-项集C_k(k>1)所占用的空间。桶地址0123456桶计数2126242桶内容{I1,I4}{I1,I4}{I1,I5}

{I2,I3}{I2,I3}

{I2,I4}{I4,I5}{I2,I4}{I4,I5}{I4,I5}{I2,I4}{I2,I5}{I2,I5}{I1,I2}{I1,I2}{I1,I2}{I1,I2}{I1,I3}{I1,I3}关联规则挖掘方法Apriori算法的改进思路—数据划分只需要两次扫描数据集关联规则挖掘方法Apriori算法的改进思路—事务压缩事务压缩：压缩未来迭代扫描的事务数，减少在后面的循环中所需要扫描的交易记录数。具体方法：由于不包含任何频繁k-项集的事务是不可能包含任何频繁(k+1)-项集的。可以加上标记或删除，不再需要。关联规则挖掘方法Apriori算法的改进思路—采样在给定数据集D的一个子集S上挖掘，通过牺牲精度来换取有效性提高算法精度使用比最小支持度低的支持度阈值来找出局部于S的频繁项集Ls关联规则挖掘方法Apriori算法的改进思路—动态项集计数将数据库划分为用开始点标记的块，在扫描的不同点添加候选项集。优点：可以在任何开始点添加新的候选项集。算法需要的数据库扫描比Apriori算法少。7.3模式增长方法

FP-Growth模

式

增

长

方

法从Apriori到FP-Tree产生大量的候选项集需要多遍扫描数据库Apriori不会产生候选项集直接从FP-Tree中提取频繁项集采用分治策略FP-TreeFP-Tree的构建输入：D事务数据库；

最小支持度阈值Minsupport。输出：FP-Tree树。算法过程：扫描事务数据库D一次，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列成L，L是频繁项列表。创建FP-Tree的根结点,标注其为NULL。对D中的每个事务T，进行以下操作：选择T中的频繁项，根据

L中的次序进行降序排列模

式

增

长

方

法例题7-6构建FP-tree示例。对于一个给定的事务数据库，扫描一次数据库，确定每个1-项集的支持度计数，去掉非频繁项集（本例中假设最小支持度阈值为20%，支持度计数为2）。并将频繁1-项集按照支持度计数降序排列。初始，FP-tree仅包含一个根结点，用符号null标记。随后，用如下方法扩充FP-tree。去掉非频繁1-项集TIDItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3按支持度降序排列模

式

增

长

方

法例题7-6第二次扫描数据库，按支持度递减的顺序，为每个事务创建一个分枝。TIDItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3T1={I2,I1,I5}T2={I2,I4}所有事务模

式

增

长

方

法FP-Growth算法举例项条件模式基I5{(I2,I1:1),(I2,I1,I3:1)}I4{(I2,I1:1),(I2:1)}I3{(I2,I1:2),(I2:2),(I1:2)}I1{(I2:4)}筛选合并项条件FP-treeI5<I2:2,I1:2>I4<I2:2>I3<I2:4,I1:2>,<I1:2>I1<I2:4>条件模式基：前缀路径：当前计数裁剪模

式

增

长

方

法FP-Growth算法举例项条件FP-treeI5<I2:2,I1:2>I4<I2:2>I3<I2:4,I1:2>,<I1:2>I1<I2:4>组合生成的频繁模式(I2,I5:2),(I1,I5:2),(I2,I1,I5:2)(I2,I4:2)(I2,I3:4),(I1,I3:4),(I2,I1,I3:2)(I2,I1:4)频繁项集：条件FP-tree的所有非空真子集+当前项模

式

增

长

方

法FP-Growth算法优点没有生成候选项集；对数据库扫描次数少；FP-Tree是一个高度压缩的结构，存储量用于挖掘频繁项集的所有信息；对于某些事务数据集，FP-Growth算法比Apriori算法要快几个数量级。模

式

增

长

方

法FP-Growth算法缺点如果生成的条件FP-tree非常茂盛（在最坏情况下，是一颗满前缀树），则算法的性能显著下降；内存开销大；只能用于挖掘单维的布尔关联规则。模

式

增

长

方

法7.4辛普森悖论辛

普

森

悖

论辛普森悖论是一个统计推断中的悖论，它表明当数据被分成不同的子组时，这些子组中的结果可能与整体的结果相反。观察到的联系可能受其他混淆因素的影响，在某些情况下，隐藏的变量可能会导致观察到的一对变量之间的联系出现不一样的结果（即没有对条件考虑全面）。辛

普

森

悖

论例题7-9辛普森悖论。考虑电视（TV）销售和健身器销售之间的联系，如右表所示。关联规则’买TV

买健身器材’的置信度是99/180=55%，而规则’不买TV

买健身器材’的置信度是54/120=45%。这些规则暗示，购买了电视的顾客比那些没有购买电视的顾客更可能购买健身器。

买健身器不买健身器总数买TV9981180不买TV5466120

153147300电视和健身器销售之间的2路相依表辛

普

森

悖

论例题7-9大学生和在职人员的电视与健身器销售情况然而，进一步深入分析表明这些商品的销售取决于顾客是大学生或还是在职人员。右表汇总了大学生和在职人员购买电视和健身器之间的联系，其中大学生和在职人员的支持度计数的总和等于表中显示的频度。而且，更多是在职人员而不是大学生购买了这些商品。

买健身器不买健身器总数大学生买TV1910不买TV43034在职人员买TV9872170不买TV503686例题7-9辛

普

森

悖

论对于大学生：Confidence(买TV

买健身器)=1/10=10%Confidence(不买TV

买健身器)=4/34=11.8%对于在职人员：Confidence(买TV

买健身器)=98/170=57.7%Confidence(不买TV

买健身器)=50/86=58.1%可以看到，对于每一组顾客，不买电视的顾客更可能购买健身器，这与先前由包含两组顾客的数据得到的结论恰好相反，这就是辛普森悖论现象。即使使用其他度量（如相关性、兴趣因子）仍然发现在组合数据情况下购买电视和健身器之间存在正相关，但是在分层数据情况下却存在负相关。石油勘探中的辛普森悖论辛

普

森

悖

论在石油勘探中，岩石属性的测量通常需要对地质层进行划分，而同一种岩石在不同的划分下可能呈现出不同的物理特征和产油能力，这就容易导致辛普森悖论的出现。例如在下表中，当涉及到不同油藏类型时，平均孔隙度和平均渗透率之间的关系可能会出现辛普森悖论。区块编号储量（亿桶）油藏类型平均孔隙度（%）平均渗透率（mD）0012.5裂缝性储层4-100.01-10021.8砂岩储层20-30100-100000033.7页岩油藏2-60.0001-0.10044.1碳酸盐岩储层5-150.1-100051.6混合储层2-200.1-1000石油勘探中存在辛普森悖论的示例数据辛

普

森

悖

论石油勘探中的辛普森悖论总结总之，由于不同油藏类型的特征不同，它们在平均孔隙度和平均渗透率方面的取值范围也不同。裂缝性储层通常具有狭窄的裂缝和微小的孔隙空间，但裂缝可以提供高渗透率的流体通道；相比之下，页岩油藏通常具有极低的孔隙度和渗透率，但高含油饱和度和大量的有机质可以实现高储量和高采收率。因此，在进行石油勘探时，对于不同油藏类型的数据，需要分别进行分析和处理，以充分考虑到样本分布和地质差异等多种因素。在实践中，通常会采用分类统计、参数优化和模型建立等方法，以减少辛普森悖论对石油勘探决策的影响。老师全屏第八章文本抽取算法·01潜在语义分析LSA应用背景·02创建Term-DocumentMatrix·03TF-IDF修改权重·04SVD矩阵分析·05相似度计算·06文献检索·07SVD数学基础8.1潜在语义分析LSA应用背景潜在语义分析LSA应用背景什么是LSA语义分析

LSA(LatentSemanticAnalysis)通过分析文章来挖掘文章的潜在意思或语义(concepts)目的是解决如何通过搜索词/关键词(searchwords)定位出相关文章基本原理是将文章和单词等映射到语义空间(conceptspace)上，并在该空间进行对比分析什么是Term-DocumentMatrix以下矩阵展现了单词(term)和文档(document)之间的关系，称为

Term-DocumentMatrix。潜在语义分析LSA应用背景潜在语义分析LSA应用背景LSA的一个重要假设每个单词假设只有一个意思潜在语义分析LSA应用背景实例这里有

10个跟“oil”相关的文档，这些文档都有共同一个索引词（indexword）。一个索引词可以是符合以下条件的任意单词：1)出现在两个或以上的文档中；2)非停用词：词意不过于一般，如“and”,“the”等，这些词对文章的语义并没起到突出的作用，因此应该被过滤掉。选取了以下10个标题进行实验。8.2创建Term-DocumentMatrix创建Term-DocumentMatrix生成初始Term-DocumentMatrix从文本中过滤非英文字母字符；过滤停用词；相同词根单词归一；词汇统计和排序，生成Term-DocumentMatrix。生成初始Term-DocumentMatrix初始矩阵中每一行对应一个词，每列对应一篇文章，

M个词和

N篇文章可以表示为一个

M*N的矩阵。创建Term-DocumentMatrix生成初始Term-DocumentMatrix创建Term-DocumentMatrix8.3TF-IDF修改权重TF-IDF修

改

权

重什么是TF-IDF在

LSA算法中，Term-DocumentMatrix一般会进行加权调整其中稀少词的权重会大于一般性的单词TF-IDF是最常用的度量指标(TermFrequency-InverseDocumentFrequency)TF：一个文档里出现的高频词更能代表该文档IDF：term在多个文档里出现，就不能成为该文档的独有特征TF-IDF修

改

权

重如何计算TF-IDF

𝑛𝑡,𝑑表示索引词𝑡在文档𝑑中出现的次数，因此分母表示所有索引词在文档中出现的次数之和。

分子|𝐷|表示文档的数量，分母表示索引词𝑡出现的文档数量。

TF-IDF修

改

权

重实例

其中𝑛𝑡,𝑑表示索引词𝑡在文档𝑑中出现的次数，因此分母表示所有索引词在文档中出现的次数之和。TF-IDF修

改

权

重实例

其中分子|𝐷|表示文档的数量，分母表示索引词𝑡出现的文档数量。TF-IDF修

改

权

重实例

TF-IDF修

改

权

重结论从公式得知，单词的词频越高，且包含该单词的文章越少，则相应的

TF-IDF值越大。

8.4SVD矩阵分析SVD

矩

阵

分

析了解SVD当Term-DocumentMatrix创建完成，使用

SVD算法进行矩阵分析SVD通过强调强的相关关系并过滤掉噪声来实现矩阵降维经过压缩后，少量有用的维度或语义模式被留下，大量噪声将被过滤掉SVD

矩

阵

分

析SVD实现原理算法将矩阵分解成3个矩阵r=rank(X)<=min(m,n)U：每个单词在语义空间的坐标

VT：每篇文章在语义空间的坐标Σ表示Term-DocumentMatrix语义空间的有效维度是多少SVD

矩

阵

分

析SVD实现原理在很多情况下，前10%甚至更少的奇异值的平方和就占全部奇异值平方和的90%以上前k个奇异值来近似描述矩阵一般取90%SVD

矩

阵

分

析实例SVD

矩

阵

分

析实例只取权重大的前几维，忽略噪声文档的第0维表示文档长度单词的第0维表示出现该词的文档数量中心化：每列都减去第0维均值形成稠密矩阵，增加内存和计算量避免中心化忽略第0维SVD

矩

阵

分

析实例SVD

矩

阵

分

析实例SVD

矩

阵

分

析实例8.5相似度计算相

似

度

计

算计算相似度前面已经将单词和文档进行向量化，下面可以计算向量之间的相似度。

相

似

度

计

算实例相

似

度

计

算实例相

似

度

计

算实例相

似

度

计

算实例相

似

度

计

算实例8.6文献检索文

献

检

索实例

文

献

检

索

综

合

案

例实例当输入查询词时，可以根据这些词构建一个文档，查询与之语义最相近的文档综

合

案

例实例

文

献

检

索最后，计算相似度。实例8.7SVD数学基础SVD

数

学

基

础特征分解

𝜆1

≥

𝜆2

≥...≥

𝜆𝑛𝑤1,𝑤2,...𝑤𝑛

A为方阵：正交

A不是方阵：

奇异值分解SVDSVD求解SVD

数

学

基

础𝐴=𝑈𝛴𝑉𝑇⇒𝐴𝑇

=𝑉𝛴𝑈𝑇⇒𝐴𝑇𝐴=𝑉𝛴𝑈𝑇𝑈𝛴𝑉𝑇

=𝑉𝛴2𝑉𝑇（𝑈𝑇𝑈=𝐼,𝛴𝑇

=𝛴）将𝐴𝑇𝐴中的所有特征向量张成𝑛×𝑛的矩阵𝑉，就是SVD公式中的𝑉矩阵𝑉中的每个特征向量叫做𝐴的右奇异向量对方阵𝐴𝑇𝐴进行特征分解，得到特征值和特征向