第七讲文本分类与聚类课件

第七讲第七讲 文本的分类与聚类文本的分类与聚类分类问题：分类问题：一般是指事先确定好类别，然后将集合中的元素分别划分到相应类一般是指事先确定好类别，然后将集合中的元素分别划分到相应类 别中的问题。别中的问题。例如例如事先确定的类别：事先确定的类别：圆圆矩形矩形三角形三角形聚类问题：聚类问题：一般是指没有事先确定好类别，而是根据集合中各元素的某些特点一般是指没有事先确定好类别，而是根据集合中各元素的某些特点 而形成的分类（即子集）。而形成的分类（即子集）。例如例如 这里的分类这里的分类或聚类由于视觉或聚类由于视觉特征明显，所以特征明显，所以容易进行。容易进行。分类与聚类示例分类与聚类示例聚类聚类圆圆矩形矩形三角形三角形 显然这里的分类或聚类是在相似概念下进行的。并且事显然这里的分类或聚类是在相似概念下进行的。并且事物的分类或聚类均是按事物的特征进行的。物的分类或聚类均是按事物的特征进行的。问题是待分类或问题是待分类或聚类对象的特征是什么？如何识别？又如何计算相似度？聚类对象的特征是什么？如何识别？又如何计算相似度？分类分类例如：例如：1、2、3、4、5、6、7、8、9 聚类结果如下：聚类结果如下：1、3、7、82、4、65、9这是按什么特征进行的聚类呢？这是按什么特征进行的聚类呢？文本分类文本分类 文本分类：文本分类：即根据给定文本的内容，将其判别为事先确定的若干个文本类即根据给定文本的内容，将其判别为事先确定的若干个文本类别中的某一类或某几类的过程。别中的某一类或某几类的过程。例如，按文本所涉及的主题或话题可事先分为体育、政治、经济、艺术、例如，按文本所涉及的主题或话题可事先分为体育、政治、经济、艺术、文学、科普等类别。文学、科普等类别。显然，某些文本类别的确定，就是人也会产生分歧。这里的显然，某些文本类别的确定，就是人也会产生分歧。这里的问题是文本分问题是文本分类的特征是什么？类的特征是什么？目前，绝大多数的研究和应用均以词汇作为文本分类的特征。即首先对文目前，绝大多数的研究和应用均以词汇作为文本分类的特征。即首先对文本进行切词，去掉与分类关联不大的词汇（如停用词）（也称为特征选择），本进行切词，去掉与分类关联不大的词汇（如停用词）（也称为特征选择），然后按分类算法进行分类。可见，文本分类某种程度上也是词汇的分类问题。然后按分类算法进行分类。可见，文本分类某种程度上也是词汇的分类问题。特征选择：特征选择：是指按某准则从众多原始特征中选择部分最能反映模式类别的是指按某准则从众多原始特征中选择部分最能反映模式类别的相关特征。其目的是提高分类精确，且能减少特征维数。相关特征。其目的是提高分类精确，且能减少特征维数。特征选择特征选择 一种方法为一种方法为人工确定人工确定，如，如体育：足球、篮球、斯诺克、奥运、体育：足球、篮球、斯诺克、奥运、NBA、博尔特、博尔特、政治：选举、议会、民主、独裁、专制、政治：选举、议会、民主、独裁、专制、经济：财政、税收、宏观调控、汇率、人民币、经济：财政、税收、宏观调控、汇率、人民币、艺术：油画、剪纸、贝多芬、摇滚、艺术：油画、剪纸、贝多芬、摇滚、1、该方法人的工作是较大，且需要领域专家的参与；、该方法人的工作是较大，且需要领域专家的参与；在以下的讨论中设在以下的讨论中设 C 表示类别集合，表示类别集合，Ci 表示其中的一个类别。表示其中的一个类别。t 表示词汇。表示词汇。目前，文本特征自动选择的常见方法有：词频函数、信息增益、互信息、目前，文本特征自动选择的常见方法有：词频函数、信息增益、互信息、2统计等。统计等。而这些方法一般需要一个统计（或训练）样本集，即针对每一个类而这些方法一般需要一个统计（或训练）样本集，即针对每一个类别事先确定一个对应的文本集合，然后从文本集合中统计（或学习）出所需的别事先确定一个对应的文本集合，然后从文本集合中统计（或学习）出所需的特征结果。也可考虑所获得的特征可随着应用的进行而动态的调整，称为具有特征结果。也可考虑所获得的特征可随着应用的进行而动态的调整，称为具有学习功能。学习功能。C1C2CN2、选择结果不便于进行动态调整，除非人工不断地进行该工作；、选择结果不便于进行动态调整，除非人工不断地进行该工作；3、据报道，该方法并不比其他的自动方法效果好多少。、据报道，该方法并不比其他的自动方法效果好多少。基于词频函数的分类特征选择基于词频函数的分类特征选择基本思想：基本思想：将在一个类别集合中出现频率较高的词汇作为分类的特征词汇。将在一个类别集合中出现频率较高的词汇作为分类的特征词汇。可借鉴可借鉴 tf-idf 加权策略的思想来进行词频统计。加权策略的思想来进行词频统计。式中，式中，tft 表示词表示词 t 在类别在类别 Ci 文本集中出现的频率，文本集中出现的频率，N 表示类别总数，表示类别总数，dft 表示包含词表示包含词 t 的类别个数。的类别个数。显然，某词显然，某词 t 在某一个类别文本中出现频率较高，而在其他类别的文本中在某一个类别文本中出现频率较高，而在其他类别的文本中几乎不出现，则该词对分类的贡献较大；若某词在所有类别的文本中均出现，几乎不出现，则该词对分类的贡献较大；若某词在所有类别的文本中均出现，则该词对分类几乎不起什么作用。则该词对分类几乎不起什么作用。由此，可设定一个阈值，由此，可设定一个阈值，TF(t,Ci)计算结果高于阈值的词汇则被选择出来计算结果高于阈值的词汇则被选择出来作为文本分类的特征词汇。作为文本分类的特征词汇。也可对上述所有的计算结果由大到小进行排序，然后选择出排序中的前若也可对上述所有的计算结果由大到小进行排序，然后选择出排序中的前若干个词汇作为文本分类的特征词汇。干个词汇作为文本分类的特征词汇。基于信息增益的分类特征选择基于信息增益的分类特征选择 基本思想：基本思想：借鉴信息论中的香农定理，通过考察词借鉴信息论中的香农定理，通过考察词 t 在类别在类别 Ci 中出现中出现或不出现的次数（概率）来衡量词或不出现的次数（概率）来衡量词 t 对类别的信息增益程度。对类别的信息增益程度。式中，式中，P(Ci)表示表示 Ci 类文档在语料库中出现的频率，类文档在语料库中出现的频率，P(t)表示语料库中包表示语料库中包含词含词 t 的文档的频率，的文档的频率，P(Ci|t)表示文档包含词表示文档包含词 t 时属于时属于 Ci 类的条件频率，类的条件频率，P(t)表示语料库中不包含词表示语料库中不包含词 t 的文档的频率，的文档的频率，P(Ci|t)表示文档不包含词表示文档不包含词 t 时属于时属于 Ci类的条件频率，类的条件频率，n 表示类别总数。表示类别总数。由此，可设定一个阈值，由此，可设定一个阈值，IG(t)计算结果高于阈值的词汇则被选择出来作为计算结果高于阈值的词汇则被选择出来作为文本分类的特征词汇。文本分类的特征词汇。可见，该方法考虑了词可见，该方法考虑了词 t 不出现时对文本类别的贡献。但据报道，这种贡不出现时对文本类别的贡献。但据报道，这种贡献往往远小于词献往往远小于词 t 不出现时所带来的干扰。不出现时所带来的干扰。也可对上述所有的计算结果由大到小进行排序，然后选择出排序中的前若也可对上述所有的计算结果由大到小进行排序，然后选择出排序中的前若干个词汇作为文本分类的特征词汇。干个词汇作为文本分类的特征词汇。基于互信息的分类特征选择基于互信息的分类特征选择基本思想：基本思想：通过计算词通过计算词 t 与类别与类别 Ci 之间的相关性来完成特征词的提取。之间的相关性来完成特征词的提取。式中，式中，A 表示属于表示属于 Ci 类别且包含词类别且包含词 t 的文档数，的文档数，N 表示语料中文档总数，表示语料中文档总数，B 表示不属于表示不属于 Ci 类别且包含词类别且包含词 t 的文档数，的文档数，C 表示属于表示属于 Ci 类但不包含词类但不包含词 t 的文的文档数。档数。根据以上计算结果，可采用下列两种方法之一来确定词根据以上计算结果，可采用下列两种方法之一来确定词 t 的互信息值。的互信息值。利用上述互信息计算结果，仍可采用前述两种阈值方法之一来选择文本分利用上述互信息计算结果，仍可采用前述两种阈值方法之一来选择文本分类特征词汇。类特征词汇。式中，式中，P(Ci)表示表示 Ci 类文档在语料库类文档在语料库中出现的频率。中出现的频率。基于基于2 2统计的分类特征选择统计的分类特征选择 基本思想：基本思想：与互信息类似，也通过计算词与互信息类似，也通过计算词 t 与类别与类别 Ci 之间的相关性，但之间的相关性，但计算方法却是借鉴了数理统计中计算方法却是借鉴了数理统计中2 的统计原理来进行。的统计原理来进行。式中，式中，N 表示语料库的文档总数，表示语料库的文档总数，A 表示属于表示属于 Ci 类别且包含词类别且包含词 t 的文档的文档数，数，B 表示不属于表示不属于 Ci 类别且包含词类别且包含词 t 的文档数，的文档数，C 表示属于表示属于 Ci 类但不包含词类但不包含词 t 的文档数，的文档数，D 表示不属于表示不属于 Ci 类也不包含词类也不包含词 t 的文档数。的文档数。仍根据上述计算结果，采用下列两种方法之一来确定词仍根据上述计算结果，采用下列两种方法之一来确定词 t 的最终统计值。的最终统计值。利用上述统计结果，采用前述两种阈值方法之一来选择文本分类特征词。利用上述统计结果，采用前述两种阈值方法之一来选择文本分类特征词。式中，式中，P(Ci)表示表示 Ci 类文档在语料库中类文档在语料库中出现的频率。出现的频率。基于朴素贝叶斯的分类算法基于朴素贝叶斯的分类算法基本思想：基本思想：计算待分类文本属于类别的概率。计算待分类文本属于类别的概率。式中，式中，d 表示待分类文本，表示待分类文本，P(Ci|d)表示待分类文本属于表示待分类文本属于 Ci 类别的概率，类别的概率，P(Ci)表示表示 Ci 类别的文档在语料库中出现的概率，类别的文档在语料库中出现的概率，K 表示待分类文本表示待分类文本 d 中特征词中特征词的个数，的个数，wj 表示待分类文本表示待分类文本 d 中的某一个特征词，中的某一个特征词，P(wj|Ci)表示特征词表示特征词 wj 在在Ci 类别中出现的概率。类别中出现的概率。P(Ci)与与 P(wj|Ci)可计算如下：可计算如下：其中其中 V 表示语料库中文档个数或指定的某确定值；表示语料库中文档个数或指定的某确定值；T 表示语料库中总的特表示语料库中总的特征词汇个数或指定的某确定值。征词汇个数或指定的某确定值。为了避免乘积项出现零，为了避免乘积项出现零，而采用的所谓平滑技术。而采用的所谓平滑技术。基于朴素贝叶斯的分类算法（续）基于朴素贝叶斯的分类算法（续）利用上述计算结果，可以得到待分类文本与每一个类别的概率值，根据该利用上述计算结果，可以得到待分类文本与每一个类别的概率值，根据该概率值完成分类任务，可采用以下两种方法之一：概率值完成分类任务，可采用以下两种方法之一：1、将待分类文本分配到最大概率值所对应的类别中；、将待分类文本分配到最大概率值所对应的类别中；2、或设定某阈值，将待分类文本分配到概率值大于该阈值的类别中。、或设定某阈值，将待分类文本分配到概率值大于该阈值的类别中。显然，为了方便计算，可事先计算出每一个特征词属于每一个类别的概率显然，为了方便计算，可事先计算出每一个特征词属于每一个类别的概率值。即形成以下矩阵。值。即形成以下矩阵。C1 C2 Cnt1t2tT该矩阵值的获得与应用：该矩阵值的获得与应用：1、利用事先准备好的语料库进行统计而获得，在应用中、利用事先准备好的语料库进行统计而获得，在应用中 该矩阵值一直保持不变；该矩阵值一直保持不变；2、开始时通过语料库而获得，在应用中当某待分类文档、开始时通过语料库而获得，在应用中当某待分类文档 d 加入某类别后，将文档加入某类别后，将文档 d 也视为该类别的一个语料也视为该类别的一个语料 文档来更新矩阵值。也称分类系统具有学习能力。更文档来更新矩阵值。也称分类系统具有学习能力。更 新可通过设定阈值自动进行，也可通过人来判定。新可通过设定阈值自动进行，也可通过人来判定。RocchioRocchio分类算法分类算法 Rocchio分类算法也称为相似度计算算法。分类算法也称为相似度计算算法。基本思想：基本思想：根据算术平均为每根据算术平均为每一个类别的文档集生成一个代表该类别的中心向量，利用待分类文档与每个类一个类别的文档集生成一个代表该类别的中心向量，利用待分类文档与每个类别的中心向量的相似度大小来完成分类。别的中心向量的相似度大小来完成分类。算法步骤：算法步骤：1、该算法需要将每一个文档表示成特征词汇的向量，可采用、该算法需要将每一个文档表示成特征词汇的向量，可采用tf-idf加权策略；加权策略；C1C2C3dC1C2C3d2、利用语料库文档向量采用算术平均值生成每一个类别的中心向量；、利用语料库文档向量采用算术平均值生成每一个类别的中心向量；3、为待分类文档生成特征词汇的向量；、为待分类文档生成特征词汇的向量；4、相似度计算可采用内积、向量夹角余弦等度量方法；、相似度计算可采用内积、向量夹角余弦等度量方法；5、按相似度大小或阈值来确定待分类文档分配到哪个或哪几个类别中；、按相似度大小或阈值来确定待分类文档分配到哪个或哪几个类别中；6、可考虑利用对新获得待分类文档的类别更新其中心向量值。、可考虑利用对新获得待分类文档的类别更新其中心向量值。KNNKNN分类算法分类算法 KNN分类算法也称为分类算法也称为 K 近邻算法。近邻算法。基本思想：基本思想：计算出待分类文档与语料库计算出待分类文档与语料库中最相似的中最相似的 K 篇文档，根据这篇文档，根据这 K 篇文档所属的类别情况来完成分类。篇文档所属的类别情况来完成分类。算法步骤：算法步骤：1、将语料库中的文档生成特征词汇的向量表示；、将语料库中的文档生成特征词汇的向量表示；式中，式中，P(d,Ci)表示待分类文档表示待分类文档 d 属于属于 Ci 类别的程度，类别的程度，dj 为为 KNN 集合中的集合中的某一个文档，某一个文档，sim(d,dj)表示待分类文档表示待分类文档 d 与文档与文档 dj 的相似度（该相似度可为内的相似度（该相似度可为内积或向量夹角余弦等指标）。积或向量夹角余弦等指标）。y(dj,Ci)表示当文档表示当文档 dj 属于属于 Ci 类别时取值为类别时取值为 1，否则取值为否则取值为 0。可见，该算法的分类原则是哪个（或哪几个）类别在待分类文档的可见，该算法的分类原则是哪个（或哪几个）类别在待分类文档的 K 个近个近邻集合中占优，则待分类文档就属于哪个（或哪几个）类别。邻集合中占优，则待分类文档就属于哪个（或哪几个）类别。2、将待分类文档生成特征词汇的向量；、将待分类文档生成特征词汇的向量；3、在语料库中选出与待分类文档最相似相似的、在语料库中选出与待分类文档最相似相似的 K 个文档，这个文档，这 K 篇文档的集合篇文档的集合 KNN 称为待分类文档称为待分类文档 d 的的 K 近邻；近邻；4、分类由下列确定：、分类由下列确定：KNNKNN分类算法示例分类算法示例dC1C2C3K=6dC1C2C3 注意，这里的占优并不是由文档数量的多少来决定的，而是由算法中给出注意，这里的占优并不是由文档数量的多少来决定的，而是由算法中给出的相似度之和的大小决定的。的相似度之和的大小决定的。显然，该算法中显然，该算法中 K 值的选择也是值得研究的。值的选择也是值得研究的。基于人工神经网络的分类算法基于人工神经网络的分类算法 基本思想：基本思想：利用语料库对人工神经网络进行训练。然后待分类文本作为网利用语料库对人工神经网络进行训练。然后待分类文本作为网络输出，从而得到分别结果。络输出，从而得到分别结果。t1t2tT人工神经网络人工神经网络C1C2Cn文档文档特征词特征词向量向量算法步骤：算法步骤：1、设计人工神经网络模型；、设计人工神经网络模型；类别类别输出输出2、初始化网络中各连接权值及神经元阈值为较小的随机数；、初始化网络中各连接权值及神经元阈值为较小的随机数；3、利用已知的语料库分类文档对网络进行训练，得到一个收敛的网络模型。、利用已知的语料库分类文档对网络进行训练，得到一个收敛的网络模型。4、将待分类文档作为网络输入，则网络端出值即为分类结果。、将待分类文档作为网络输入，则网络端出值即为分类结果。文本分类小结文本分类小结 关于文本分类的方法除了以上所介绍的基本方法之处，还存在着大量的改关于文本分类的方法除了以上所介绍的基本方法之处，还存在着大量的改进方法和新方法。如基于支持向量机分类算法、基于决策树分类算法、基于投进方法和新方法。如基于支持向量机分类算法、基于决策树分类算法、基于投票的分类算法、基于最大熵分类算法、基于决策规则的分类算法等等。票的分类算法、基于最大熵分类算法、基于决策规则的分类算法等等。许多方法需要数学、人工智能、数据挖掘等相关领域的知识背景。目前，许多方法需要数学、人工智能、数据挖掘等相关领域的知识背景。目前，许多方法和深入研究、融合和应用均可作为硕博论文的研究内容。许多方法和深入研究、融合和应用均可作为硕博论文的研究内容。目前，无论哪种算法都不可能做到目前，无论哪种算法都不可能做到100%的正确分类，据报道有些算法的的正确分类，据报道有些算法的分类准确率可达分类准确率可达80%90%。另外，文本分类的评测也是值得研究的课题。另外，文本分类的评测也是值得研究的课题。文本的聚类文本的聚类 如前所述，文本的聚类问题是不需要事先划分好类别，是在没有学习的条如前所述，文本的聚类问题是不需要事先划分好类别，是在没有学习的条件下对文本集合进行组织或划分的过程。件下对文本集合进行组织或划分的过程。基本思想：基本思想：将相似的文本划分到同一将相似的文本划分到同一个类中。个类中。常见的聚类方法有层次方法、划分方法、基于密度的方法、基于网格的方常见的聚类方法有层次方法、划分方法、基于密度的方法、基于网格的方法和基于模型的方法等。法和基于模型的方法等。由于聚类不需要训练过程，也不需要预先对文档集进行人工标注类别，因由于聚类不需要训练过程，也不需要预先对文档集进行人工标注类别，因而具有一定的灵活性和较高的自动化处理能力。而具有一定的灵活性和较高的自动化处理能力。自底向上的层次聚类算法自底向上的层次聚类算法 基本思想：基本思想：从单个文档出发，先将每一个文档视为单独的一类，然后反复从单个文档出发，先将每一个文档视为单独的一类，然后反复合并两个或多个合适的类别，直至满足停止条件。合并两个或多个合适的类别，直至满足停止条件。停止条件可以是聚类的类别个数，也可以由相似度的阈值来确定。停止条件可以是聚类的类别个数，也可以由相似度的阈值来确定。算法步骤：算法步骤：对于给定的文档集合对于给定的文档集合 D=d1、d2、dn 1、将、将 D 中的每一个文档视为一个类，即中的每一个文档视为一个类，即 Ci=di ，构成一个聚类，构成一个聚类 C=C1、C2、Cn；显然，该算法需将文档表显然，该算法需将文档表示成词汇的向量；另外还示成词汇的向量；另外还需解需解决两个类（即文档集合）之间决两个类（即文档集合）之间的相似性度量问题的相似性度量问题。如利用类。如利用类别子集的中心向量来度量。别子集的中心向量来度量。d1 d2 d3 d4 d5 d6若需将文档集聚为若需将文档集聚为3类，则结果为：类，则结果为：d4 d1、d2、d3 d5、d6 2、计算、计算 C 中每对类之间的相似度中每对类之间的相似度 sim(Ci,Cj)；3、将相似度最大的类对合并，构成新的聚类、将相似度最大的类对合并，构成新的聚类 C=C1、C2、Cn-1；4、重复、重复2、3步骤，直到步骤，直到 C 满足停止条件。满足停止条件。自顶向下的层次聚类算法自顶向下的层次聚类算法 基本思想：基本思想：先将整个文档集视为一个类别，按文档间的相似度构造一棵最先将整个文档集视为一个类别，按文档间的相似度构造一棵最小生成树，然后依次删除生成树中相似度最小的边，直至满足停止条件。小生成树，然后依次删除生成树中相似度最小的边，直至满足停止条件。停止条件可以是聚类的类别个数，也可以由相似度的阈值来确定。停止条件可以是聚类的类别个数，也可以由相似度的阈值来确定。在数据结构中介绍了两种最小生成树算法，分别为在数据结构中介绍了两种最小生成树算法，分别为普里姆（普里姆（Prim）算）算法和克鲁斯卡尔（法和克鲁斯卡尔（Kruskal）算法）算法。后者算法的基本思想是：设连通网。后者算法的基本思想是：设连通网 N=(V,E)，令最小生成树，令最小生成树 T=(V,)，即每个顶点为一个连通分量。在，即每个顶点为一个连通分量。在 E 中选择相中选择相似度最大的边，若该边依附的顶点落在似度最大的边，若该边依附的顶点落在 T 中不同的连通分量上，则将该边加入中不同的连通分量上，则将该边加入T 中，否则舍去而选择下一条相似度最大的边。依次类推，直到中，否则舍去而选择下一条相似度最大的边。依次类推，直到 T 中所有顶点中所有顶点连通为止。下面是其示例：（假设有连通为止。下面是其示例：（假设有6个文档）个文档）d1d35d62d441d2d5d1d35d6d4d2d5433显然，若需聚为显然，若需聚为3类，则结果为类，则结果为 d2、d5、d1、d3、d4、d6。基于划分的基于划分的K-meansK-means聚类算法聚类算法 基本思想：基本思想：将整个文档集划分为将整个文档集划分为 K 类，首先随机选取类，首先随机选取 K 个文档作为类别的个文档作为类别的质心（即若干个文档的均值）进行迭代，每一轮选出一个与质心（即若干个文档的均值）进行迭代，每一轮选出一个与 K 个质心最相似的个质心最相似的文档，并将该文档划入相应的类别，重新计算该类别的质心。继续迭代，直到文档，并将该文档划入相应的类别，重新计算该类别的质心。继续迭代，直到处理完全部文档。处理完全部文档。算法步骤：算法步骤：1、从整个文档集、从整个文档集 D 中随机选择中随机选择 K 个文档作为初始质心个文档作为初始质心 C1、C2、CK 以及以及 初始划分，令初始划分，令 D=D C1、C2、CK；C1C2C3d4C2C3d4d1C1示例：示例：假定第假定第 1 次迭代次迭代 d4 与与 C1 最相似最相似 显然，该算法初始质心的选择对聚显然，该算法初始质心的选择对聚类结果有重要影响。类结果有重要影响。2、在、在 D 中选择出文档中选择出文档 di，使得，使得 maxi,j sim(di,Cj)，若文档，若文档 di 与质心与质心 Cj 最相最相 似，则将文档似，则将文档 di 划入划入 Cj 所对应的类别中，并重新计算所对应的类别中，并重新计算 Cj 的质心，再令的质心，再令 D=D di；3、重复步骤、重复步骤2，直到，直到 D 为空停止。为空停止。基于划分的基于划分的K-meansK-means聚类算法（续）聚类算法（续）为了得到更佳的聚类效果，还可采用以下方法对聚类结果进行选择。为了得到更佳的聚类效果，还可采用以下方法对聚类结果进行选择。1、利用、利用 K-means 算法求得一聚类结果；算法求得一聚类结果；2、计算目标函数、计算目标函数 ，n 为文档总个数；为文档总个数；3、重新生成一组初始质心，重复步骤、重新生成一组初始质心，重复步骤1、2。反复进行多次，从中选择出。反复进行多次，从中选择出 J 值值 最小的聚类结果作为最终聚类结果。最小的聚类结果作为最终聚类结果。可见，这并没有从根本上解决初始质心的选择问题，而是一种碰运气的做可见，这并没有从根本上解决初始质心的选择问题，而是一种碰运气的做法。目前，还没有一种有说服力的方法来确定初始质心。法。目前，还没有一种有说服力的方法来确定初始质心。另外，另外，K-means 聚类算法的另一个聚类算法的另一个缺点缺点是孤立点的干扰较为严重。所谓孤是孤立点的干扰较为严重。所谓孤立点是指该文档与其他文档立点是指该文档与其他文档“相距较远相距较远”（即相似度很低）。（即相似度很低）。该算法还有一个该算法还有一个缺点缺点就是必须事先给定聚类的类别个数。这在实际应用中就是必须事先给定聚类的类别个数。这在实际应用中往往也是一个难题。往往也是一个难题。据报道，该算法对凸型聚类有较好的效果。据报道，该算法对凸型聚类有较好的效果。基于划分的基于划分的K-medoidK-medoid聚类算法聚类算法 基本思想：基本思想：该算法与该算法与K-means算法的区别在于质心的选择方法不同。算法的区别在于质心的选择方法不同。1、K-means算法的质心为该类别中所有文档向量的均值（也称几何中心），算法的质心为该类别中所有文档向量的均值（也称几何中心），而该质心往往并不是某个存在的文档。而该质心往往并不是某个存在的文档。2、K-medoid算法是在算法是在K-means质心的基础上，计算该类别内每一个文档与质心的基础上，计算该类别内每一个文档与 K-means算法质心的相似度，选择相似度最大的文档作为该类别文档集合算法质心的相似度，选择相似度最大的文档作为该类别文档集合 的代表（也称为质心）。的代表（也称为质心）。C2C3d4d1C1 例如，在例如，在 K-means 算法中确定文档算法中确定文档 d1 与与 d4 为一个类别，为一个类别，其质心为其质心为 C1，此时分别计算文档，此时分别计算文档 d1、d4 与与 C1 的相似度，若的相似度，若 d4与与 C1 最相似，则选择文档最相似，则选择文档 d4 作为该类别的新质心。其余过程作为该类别的新质心。其余过程与与 K-means 算法相同，仅质心的选择方法不同。算法相同，仅质心的选择方法不同。C2C3d1C1该算法的目的是尽可能消除孤立点对聚类结果的影响。该算法的目的是尽可能消除孤立点对聚类结果的影响。基于密度的基于密度的DBSCANDBSCAN聚类算法聚类算法 基于密度的算法认为：基于密度的算法认为：类别就是向任意方向按相同密度扩张的连通区域。类别就是向任意方向按相同密度扩张的连通区域。1、主要考虑数据空间的密度、连通性与边界区问题；、主要考虑数据空间的密度、连通性与边界区问题；2、据报道，基于密度的聚类算法对于非凸、不规则形状有较好的聚类效果。、据报道，基于密度的聚类算法对于非凸、不规则形状有较好的聚类效果。DBSCAN算法的基本思想：算法的基本思想：一个类别集合除边界点以外，每个点在给定半一个类别集合除边界点以外，每个点在给定半径区域内必须包含不少于指定数量的邻接点。径区域内必须包含不少于指定数量的邻接点。1、在文本聚类问题中，这里的、在文本聚类问题中，这里的“点点”当然是指文档；当然是指文档；2、可以将文档、可以将文档 x 与文档与文档 y 相似度的倒数定义为彼此的相似度的倒数定义为彼此的“距离距离”，记作，记作 dist(x,y)。下面介绍几个定义：下面介绍几个定义：1、邻接对象集：邻接对象集：在给定对象半径内，一个对象在给定对象半径内，一个对象 p 的的邻接对象集记为邻接对象集记为 N(p)=q|dist(p,q)pN(p)2、核心对象：核心对象：即满足即满足 N(p)MinPts 的对象的对象 p。MinPts 表示半径表示半径内拥有最少其他对象的个数。内拥有最少其他对象的个数。如右图所示，若如右图所示，若 MinPts=4 则则 p 为核心对象；为核心对象；若若 MinPts=6 则则 p 不是核心对象。不是核心对象。基于密度的基于密度的DBSCANDBSCAN聚类算法（续）聚类算法（续）3、直接密度可达：直接密度可达：对于对象对于对象 q，若存在一个核心对象，若存在一个核心对象 p 使得使得 qN(p)，则称，则称 对象对象 q 是从对象是从对象 p 直接密度可达的。直接密度可达的。如右图，如右图，q 是从是从 p 直接密度可达的；直接密度可达的；q1 不是从不是从 p 直接密度可达的。直接密度可达的。pqq14、密度可达：密度可达：对于对象对于对象 q，若存在一条核心对象链，若存在一条核心对象链 p=p1,p2,p3,pn=q，其中，其中 pi+1 是从是从 pi 直接密度直接密度 可达的，可达的，pn 可以不是核心对象，则称对象可以不是核心对象，则称对象 q 是是 从对象从对象 p 密度可达的。密度可达的。如右图所示，如右图所示，MinPts=4。q 是从是从 p 密度可达的。密度可达的。q5、密度相连：密度相连：若存在对象若存在对象 h，使得对象，使得对象 p 和和 q 是从是从 h 密度可密度可 达的，则称达的，则称 p 和和 q 是密度相连的。是密度相连的。如下图所示。如下图所示。hpq密度可达密度可达密度可达密度可达密度相连密度相连即密度相连是对称的。即密度相连是对称的。基于密度的基于密度的DBSCANDBSCAN聚类算法步骤聚类算法步骤 给定数据对象集合给定数据对象集合 D、参数、参数和和 MinPts，DBSCAN算法描述如下：算法描述如下：1、在、在 D 中任取一对象中任取一对象 p，进行区域查询；，进行区域查询；2、若、若 N(p)MinPts，则查找所有从，则查找所有从 p 密度可达的对象，将这些对象和密度可达的对象，将这些对象和 p 一一 起形成一个类别；否则将起形成一个类别；否则将 p 暂时标记为噪声。暂时标记为噪声。3、在、在 D 中取下一个没有划分类别且没有标记为噪声的对象，重复步骤中取下一个没有划分类别且没有标记为噪声的对象，重复步骤2。直到。直到 所有对象都被处理为止。所有对象都被处理为止。噪声噪声 显然，该算法的效果受参数显然，该算法的效果受参数和和 MinPts 影响较大。实际应用时这两个参数影响较大。实际应用时这两个参数值并不容易确定，参数的求解方法也是值得研究的。值并不容易确定，参数的求解方法也是值得研究的。DBSCAN：Density-Based Spatial Clustering of Application with Noise基于密度的基于密度的DENCLUEDENCLUE聚类算法聚类算法 DENCLUE：DENsity-based CLUstEring。基本思想：基本思想：每个数据点和其他每个数据点和其他数据点之间存在一定的影响关系，通过所谓的密度吸引点来进行聚类，密度吸数据点之间存在一定的影响关系，通过所谓的密度吸引点来进行聚类，密度吸引点是全局密度函数的局部最大点。引点是全局密度函数的局部最大点。d1d2d3f(x,y)函数函数 f(x,y)称为对象称为对象 x 和和 y 之间的之间的影响函数影响函数，描，描述了两个对象之间的相互影响关系。述了两个对象之间的相互影响关系。原则上影响函数可以是任意函数，但需满足自反原则上影响函数可以是任意函数，但需满足自反和对称性质。和对称性质。常用影响函数有方波影响函数和高斯影响函数：常用影响函数有方波影响函数和高斯影响函数：1、方波影响函数：方波影响函数：2、高斯影响函数：高斯影响函数：由影响函数来由影响函数来定义对象的密度定义对象的密度：可见，每个对象都可见，每个对象都有一个密度值。如左图有一个密度值。如左图d2的密度值大于的密度值大于d1、d1的密度值大于的密度值大于d3。基于密度的基于密度的DENCLUEDENCLUE聚类算法基本思想聚类算法基本思想下面以一维数据点为例，说明下面以一维数据点为例，说明DENCLUE聚类算法的基本思想。聚类算法的基本思想。diD(di)d密度吸引点：密度吸引点：即局部最大值即局部最大值梯度方向梯度方向dmdk孤立点或噪声孤立点或噪声 首先查找密度最大值的点（如首先查找密度最大值的点（如 dm），计算其他点的梯度，将其梯度指向），计算其他点的梯度，将其梯度指向dm 点的对象（如点的对象（如 d1 和和 d2）与）与 dm 点一起划分同一个类别；再将梯度指向点一起划分同一个类别；再将梯度指向 d1 或或 d2 的对象也划入同一类别；依此类推。当没有对象划入该类别后，再在剩余的对的对象也划入同一类别；依此类推。当没有对象划入该类别后，再在剩余的对象中查找密度最大的点（如象中查找密度最大的点（如 dk），重复以上过程。），重复以上过程。定义：定义：密度吸引：密度吸引：若存在序列若存在序列 x=x0,x1,x2,xn=x*，其中，其中，x*为密度为密度吸引点，吸引点，xi-1 的梯度在的梯度在 xi 方向上，则称方向上，则称 x 是被是被 x*密度吸引的。密度吸引的。d1d2密度阈值密度阈值基于密度的基于密度的DENCLUEDENCLUE聚类算法步骤聚类算法步骤DENCLUE算法步骤：算法步骤：1、给定密度阈值，在对象集合、给定密度阈值，在对象集合 D 中去除密度小于阈值的孤立点，仍记为中去除密度小于阈值的孤立点，仍记为 D；2、在、在 D 中查找密度值最大的对象点中查找密度值最大的对象点 dm；3、计算所有被、计算所有被 dm 密度吸引的对象集合密度吸引的对象集合 C，C 即为一个聚类结果的类别；即为一个聚类结果的类别；4、D=D C；5、重复步骤、重复步骤2、3、4，直至，直至 D 为空停止。为空停止。注意，实际应用时的梯度与密度吸引计算是在高维空间上的计算，它们并注意，实际应用时的梯度与密度吸引计算是在高维空间上的计算，它们并没有良好的可视化效果，需要抽象的空间想象能力。没有良好的可视化效果，需要抽象的空间想象能力。据报道，该算法实践效果较好。能够应付大量噪声数据以及聚类结果的不据报道，该算法实践效果较好。能够应付大量噪声数据以及聚类结果的不规则形状。规则形状。另外，该算法的关键是密度函数的确定。如采用高斯影响函数，则其中的另外，该算法的关键是密度函数的确定。如采用高斯影响函数，则其中的对象间对象间“距离距离”的定义以及参数值的给定对算法的效果影响较大。的定义以及参数值的给定对算法的效果影响较大。文本聚类小结文本聚类小结1、显然，文本的分类与聚类是一种基于语义的理解过程，而目前自然语言理、显然，文本的分类与聚类是一种基于语义的理解过程，而目前自然语言理 解的研究虽不断深入，但与人类智能的理解还存在着较大差距。这是目前解的研究虽不断深入，但与人类智能的理解还存在着较大差距。这是目前 文本分类、聚类以及检索问题的发展瓶颈。文本分类、聚类以及检索问题的发展瓶颈。2、还有许多文本聚类算法，如基于人工神经网络模型的、自组织映射模型的、还有许多文本聚类算法，如基于人工神经网络模型的、自组织映射模型的 等等，但效果都不尽理想。等等，但效果都不尽理想。3、聚类效果的评价也是值得研究的。、聚类效果的评价也是值得研究的。4、聚类结果的表示与描述也是个难题。与分类不同，聚类是事先不确定或不、聚类结果的表示与描述也是个难题。与分类不同，聚类是事先不确定或不 知道类别，那么聚类的结果中每一个类别是什么意思？该聚类结果说明了知道类别，那么聚类的结果中每一个类别是什么意思？该聚类结果说明了 什么？能否形成描述一个类别的文本摘要？什么？能否形成描述一个类别的文本摘要？信息过滤信息过滤信息过滤：信息过滤：一般是指根据用户提供的过滤需求，从动态变化的信息流中自动识一般是指根据用户提供的过滤需求，从动态变化的信息流中自动识 别出满足用户个性化需求的信息。别出满足用户个性化需求的信息。若信息的载体是文本，也就是文本过滤问题。若信息的载体是文本，也就是文本过滤问题。信息过滤的两种方式：信息过滤的两种方式：1、从动态信息流中过滤出满足用户需求的信息，提交给用户；、从动态信息流中过滤出满足用户需求的信息，提交给用户；2、从动态信息流中过滤掉不希望用户见到的信息，对用户进行屏蔽。、从动态信息流中过滤掉不希望用户见到的信息，对用户进行屏蔽。信息过滤与信息检索的主要区别：信息过滤与信息检索的主要区别：1、信息检索是根据动态变化的用户查询请求从静态的数据集中检索出满足用、信息检索是根据动态变化的用户查询请求从静态的数据集中检索出满足用 户需求的信息；户需求的信息；2、信息过滤是根据静态的过滤需求从动态的信息流中检索出满足过滤条件的、信息过滤是根据静态的过滤需求从动态的信息流中检索出满足过滤条件的 信息，要么提交给用户，要么对用户进行屏蔽。信息，要么提交给用户，要么对用户进行屏蔽。信息过滤与信息分类的联系：信息过滤与信息分类的联系：1、可将过滤需求视为信息分类的类别定义；、可将过滤需求视为信息分类的类别定义；2、信息过滤的过程可视为信息分类的过程。、信息过滤的过程可视为信息分类的过程。文本过滤的若干应用文本过滤的若干应用1、屏蔽网页、屏蔽网页 可对整个网页或网页的部分内容进行屏蔽。一种方法是建立一个所谓的敏可对整个网页或网页的部分内容进行屏蔽。一种方法是建立一个所谓的敏感词集合，由网页中所包容的词来确定该网页是否被屏蔽；另一种方法是建立感词集合，由网页中所包容的词来确定该网页是否被屏蔽；另一种方法是建立一个被屏蔽文档集合，凡与该集合中的文档相似度很高的文档做屏蔽处理。一个被屏蔽文档集合，凡与该集合中的文档相似度很高的文档做屏蔽处理。2、垃圾邮件过滤、垃圾邮件过滤 在邮件系统中，可建立垃圾邮件的过滤规则。如邮件中含有大量广告、宣在邮件系统中，可建立垃圾邮件的过滤规则。如邮件中含有大量广告、宣传性质的信息（如免费、促销等）、建立邮箱地址黑名单、超过一定阈值的群传性质的信息（如免费、促销等）、建立邮箱地址黑名单、超过一定阈值的群发邮件、含不良信息、违反国家法规或欺骗性信息的邮件等等。发邮件、含不良信息、违反国家法规或欺骗性信息的邮件等等。3、发贴内容的过滤、发贴内容的过滤 在论坛性质的网站上，建立发贴内容的过滤规则。将不希望出现的贴子过在论坛性质的网站上，建立发贴内容的过滤规则。将不希望出现的贴子过滤出来，以做其他处理。如拒绝发表、建立滤出来，以做其他处理。如拒绝发表、建立IP地址黑名单、关闭其帐号、甚至地址黑名单、关闭其帐号、甚至向公安机关举报等等。向公安机关举报等等。除了这种负面信息的过滤，有没有正面的应用呢？除了这种负面信息的过滤，有没有正面的应用呢？p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后谢谢你的到来学习并没有结束，希望大家继续努力Learning Is Not Over.I Hope You Will Continue To Work Hard演讲人：XXXXXX 时 间：XX年XX月XX日