文本挖掘算法总结(共7页)

1、精选优质文档-倾情为你奉上专心-专注-专业文本数据挖掘算法应用小结文本数据挖掘算法应用小结1、基于概率统计的贝叶斯分类2、ID3 决策树分类3、基于粗糙集理论 Rough Set 的确定型知识挖掘4、基于 k-means 聚类5、无限细分的模糊聚类 Fuzzy Clustering6、SOM 神经元网络聚类7、基于 Meaning 的文本相似度计算8、文本模糊聚类计算9、文本 k-means 聚类10、文本分类11、关联模式发现12、序列模式发现13、PCA 主成分分析1、基于概率统计的贝叶斯分类、基于概率统计的贝叶斯分类算法概述算法概述：贝叶斯公式是由英国数学家( Thomas Bayes

2、1702-1763 )创造，用来描述两个条件概率之间的关系，比如 P(A|B) 为当“B”事件发生时“A”事件发生的概率，按照乘法法则：P(AB)=P(A)*P(B|A)=P(B)*P(A|B)，可导出贝叶斯公式：P(A|B)=P(B|A)*P(A)/P(B)贝叶斯分类基本思想为：设决策变量为 D，D1，D2，Di，Dk 为 n 条记录组成的样本空间 S 的一个划分，将 n 条记录划分成 k 个记录集合，如果以 P(Di)表示事件 Di 发生的概率，且 P(Di) 0 ( i=1，2，k)。对于任一事件 x，P(x)0，则有：贝叶斯分类的基本原理，就是利用贝叶斯条件概率公式，将事件 X 视为多

3、个条件属性 Cj 各种取值的组合，当 x 事件发生时决策属性 Di 发生的条件概率。贝叶斯分类是一种概率型分类知识挖掘方法，不能百分之百地确定 X 事件发生时 Di 一定发生。解决问题解决问题：预测所属分类的概率。通过已知 n 条样本集记录，计算各种条件属性组发生的概率，得出“贝叶斯分类”规则，给定一个未知“标签”记录，选择最大概率为其所属“分类” 。2、ID3 决策树分类决策树分类算法概述：算法概述：ID3 算法是 J. Ross Quinlan 在 1975 提出的分类算法，当时还没有“数据挖掘”的概念。 该算法以信息论为基础， 以信息熵和信息增益度来确定分枝生成决策树 D-Tree。 I

4、D3算法以决策树 D-Tree 构建分类知识模型，D-Tree 中最上面的节点为根节点 Root，每个分支是一个新的决策节点，或者是树的叶子。每个决策节点代表一个问题或决策，每一个叶子节点代表一种可能的分类结果， 沿决策树在每个节点都会遇到一个测试， 对每个节点上问题的不同取值导致不同的分支，最后会到达一个叶子节点为确定所属分类。精选优质文档-倾情为你奉上专心-专注-专业解决问题解决问题：预测所属分类。通过已知样本集记录，生成一颗“分类知识树” ， 给定一个未知“标签”记录，通过“分类知识树”来确定其所属分类。3、基于粗糙集理论、基于粗糙集理论 Rough Set 的确定型知识挖掘的确定型知识

5、挖掘算法概述：算法概述：1982 年波兰学者 Z. Paw lak 提出了粗糙集理论 Rough Sets Theory，它是一种刻划不完整性和不确定性的数学工具，能有效分析不精确、不一致（Inconsistent)、不完整（Incomplete) 等各种不完备信息，利用数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。粗糙集理论是继概率论、模糊集、证据理论之后的又一个处理不确定性事物的数学工具。 粗糙集理论是建立在分类机制的基础上的， 它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一被划分的集合称为概念。 其主要思想是利用已

6、知的知识库， 将不精确或不确定的知识用已知的知识库中的知识来（近似） 刻画。解决问题解决问题： 预测所属分类。 粗糙集分类将样本空间 S 划分为上近似集 （Upper approximation)、下近似集（Lower approximation） 、边界集（Boundary region)，挖掘条件属性 C 与决策属性D 集合所包含的不可分记录（不能再细分，该集合中的所有记录都属于某一决策属性 Di 的取值） ，这些记录形成不可辨识的关系（Indiscernibility relation)，由此确定分类规则：IF THEN 即，如果满条件 C，则其所属分类为 Di。IF 中的条件 C 可以

7、是单一条件，也可以是组合 and（并且）组合条件。BIC 给出的是“最小分类规则” 。所谓“最小分类规则”是，最少的条件组合。例如一个人属于“高” 、 “富” 、 “帅” ，条件为： “身高” 、 “财富” 、 “工资性收入” 、 “财产性收入” 、 “产业收入” 、 “脸型” 、 “眼睛大小” 、 “鼻梁形状” 、 “英俊”等条件来判别，通过“粗糙集”分类计算，得出最小分类规则可能是“IF 财富=XXX1 and 身高=185cm and 相貌=英俊”其他条件可以忽略不计，这就是“最小分类规则” 。“粗糙集”分类规则为“百分之百确定型”分类规则，这是对样本集的统计结果，如果出现非“样本集”中

8、出现过的条件变量属性，将无法得出“粗糙集” ，可转而使用概率型“贝叶斯分类”进行计算。4、基于、基于 k-means 聚类聚类算法概述：算法概述：给定一个包括 n 条记录、每条记录有 m 个属性 的样本集，再给出分类数 k，要求将样本集中的记录，按记录间的相似性大小（或距离远近） ，将相似性最大（或距离最近）的记录划分到 k 个类中， 相同分类中记录间的距离要尽可能地小， 而分类之间的距离要尽可能地大。精选优质文档-倾情为你奉上专心-专注-专业BIC 改进了常规的 k-means 聚类算法，在聚类过程中，同时计算分类质量（类内均差 、类间均距和） ，并求解最优聚类 max。解决问题解决问题：将

9、 n 条记录聚成 k 个分类。对 n 个样本集记录，指定分类个数 k，为 k 个分类指定初始迭代记录为 k 个分类中心， 通过计算其他记录对 k 个分类中心的距离， 对不断变换分类、变换类中心，收敛都当分类不再变化时，计算结束。由此，将 n 个样本集记录分配到 k个分类中，得到 k 个分类中心指标。5、无限细分的模糊聚类、无限细分的模糊聚类 Fuzzy Clustering算法概述：算法概述：在实际解决聚类问题时，很多数事物是“模糊”的，其特征属性 A 无法确进行量化，如：人的相貌、人与人之间的关系、人的性格、购买商品的意愿等，这就需要用模糊数学来进行相似性计算。模糊数学是伴随着上世纪五六十年

10、代兴起的控制论、信息论、系统论 （俗称 “老三论” ） 而形成的一种决策方法， 是美国加利福尼亚大学伯克利分校 Lotfi Zadeh教授于 1965 年创立的。模糊聚类基本计算步骤为：（1）将样本集中的 n 条记录变换成 n x n 的模糊相似矩阵；（2）通过传递包卷积计算将模糊相似矩阵变换成等价相似矩阵；（3）最后通过截矩阵将 n 条记录分成 1-n 个分类。K-means 聚类需事先确定聚类数 k，而模糊聚类 Fuzzy Clustering 无需事先确定聚类数 k，可以从最小的 k=1（所有学习集中的 n 条记录为 1 个分类） ，到 k=n（所有学习集中的 n 条记录各为 1 个分类

11、） 。解决问题：解决问题：将 n 条记录聚成 1-n 个分类。模糊聚类 Fuzzy Clustering 算法完全基于数据自然状况进行聚类，可产生聚类的解集合(k=1,2,n)，因此，可以在解集合中求解最优聚类max，这对观察分析样本集的数据性态非常有用，可供观察不同情况下的“聚类”状况。6、SOM 神经元网络聚类神经元网络聚类算法概述算法概述：人类对事物的认知是一个不断积累的过程，通过对事物的观察，不断地认识和修正因果关系，最后逐渐稳定为认知规则。医学证明，人眼的视网膜、脊髓和海马中存一种侧抑制现象，即，当一个神经细胞兴奋后，会对其周围的神经细胞产生抑制作用。这种侧抑制使神经细胞之间呈现出竞

12、争， 开始时可能多个细胞同时兴奋， 但一个兴奋程度最强的神经细胞对周围神经细胞的抑制作用也最强， 其结果使其周围神经细胞兴奋程度减弱， 从而该神经细胞是这次竞争的“胜者” ，其它神经细胞在竞争中失败。1981 年芬兰学者 kohonen 提出一个称为自组织特征映射 （Self Organization Feature Map-SOM或 SOFM）网络，前述大脑神经细胞兴奋规律等，在该网络中都得到了反应。在竞争层神经元之间的连线， 它们是模拟生物神经网络层内神经元相互抑制现象的权值， 这类抑制性权值满足一定的分布关系，如距离近的抑制强，距离远的抑制弱。精选优质文档-倾情为你奉上专心-专注-专业通

13、过上述可知，SOM 聚类算法设计的核心思想是体现神经元在认知过程中的 3 个特性：（1）根据样本比较，逐步积累、不断修正、渐近稳定特性？（2）神经元之间的侧抑由近到远、逐步衰弱制特性？（3）神经元兴奋区域随认知次数逐步缩小范围特性？BIC 采用欧氏距离作为输入模式 Xi 与各输出神经元 Wj 之间的相似度，选择具有最小距离的神经元为兴奋神经元；采用（1-ti/tm）作为学习衰减函数，其中 ti 为当前学习次数（第几次样本训练） ，tm 为总的学习数，以此来体现上述特性“1” ； 采用（1-ti/T） 、C/Wij 作为神经元侧抑制函数，其中 C 为设定的常数、Wij 为被选中的神经元与其他神经

14、元最远距离，来体现上述特性“2” 、 “3” 。解决问题解决问题：将 n 条记录按 m 个输出神经元聚成 m 个分类。模仿人类的学习方法，对事物的认识是一个由浅入深、逐步学习、修正的过程，将对各种要素组态的认识逐步稳定到认知领域，由此进行“聚类” 。7、基于、基于 Meaning 的文本相似度计算的文本相似度计算算法概述算法概述： 给出一组 n 个文档 D， BIC 为每个文档计算出一组最具有代表性的词组，同时，计算出相互间内容接近度及接近序列。BIC 的 Meaning 挖掘与自动搜索不同于现有 Baidu、Google 人工输入关键词的搜索方式，现有搜索引擎不考虑语义和语境，只考虑词 W

15、与文档 D 的包含关系和词在文档内的频数 TF，因此，关键词的搜索与文档内容无关。例如： “姚明”是中国篮球的骄傲，但“姚明”还投身于公益事业，如果在搜索引擎中输入“姚明” ， 不见得搜索的文档内容只包含与篮球相关的内容， 还可能包括公益及其他包含 “姚明”的文档，可见，关键词搜索具有不确定性。如果在搜索引擎输入一组词 “姚明” 、 “得分” 、 “篮板”，搜出文档是篮球比赛内容的概率更大，显然 ，形成的交集缩小了搜索范围，但组词 “姚明” 、 “得分” 、 “篮板”是经过人思考给出的。BIC 通过计算得出文档代表词组，相当于人工输入 “姚明” 、 “得分” 、 “篮板”，同时计算词在句子中语

16、序关系的发生概率与马尔科夫链，因此， 能够更好地确定搜索词的语义和语境， 通过对文档间的相关性 （接近度） 进行聚类计算，可按 Meaning“接近度”进行自动搜索而无需人工干预，并随文档内容的变化而自动跟踪Meaning 变化，使搜索更加准确、更加自动化，让搜索“随用户的心而动” 。BIC 可用于基于 Meaning 计算的搜索、舆情分析、特定情报分析、垂直搜索和相似内容推荐精选优质文档-倾情为你奉上专心-专注-专业等文本挖掘。解决问题：解决问题：计算两个文本的相似度。8、文本模糊聚类计算、文本模糊聚类计算算法概述：算法概述：基于模糊聚类算法，BIC 首先计算将 n 个文本组成相似矩阵（第

17、i 个文本文档对第 j 个文本文档的相似度） ，然后将相似矩阵变成模糊相似矩阵，通过求模糊相似矩阵的等价矩阵和截矩阵，将 n 个文本文档分成 1-n 个分类，同时，按相同分类中的文本具有最接近的内容相似度 Min， 不同文本分类间具有最大差异 Max， 来求解按文本内容进行最优分类方案。解决问题解决问题：在不确定将文本划分成几类的情况下，将 n 个文本聚成 1-n 个分类，以此来观察“聚类”效果。9、文本、文本 k-means 聚类聚类算法概述：算法概述：基于 k-means 聚类，在 BIC 平台上，用户上传或输入 n 个文本，确定希望分类数量 k 和 k 个分类样本，BIC 将以 k 个样

18、本作为初始迭代点进行 k-means 聚类计算，将 n 个文本分成 k 个分类。解决问题：解决问题：在已经确定了 k 个分类的情况下，将文本划分到 k 个“分类”中。10、文本分类、文本分类算法概述算法概述：通过“文本模糊聚类”或“文本 k-means”聚类，BIC 不仅将 n 个文本按内容相似度进行分类，同时挖掘出各个分类的“分类代表词组” ，以后，用户任意给出一个文本，BIC 将根据其对各个“分类代表词组”的相似度，选择最相似的分类 MaxSimi，将该待分类文档分配到 MaxSimi类。解决问题：解决问题：在已经完成文本聚类的情况下，将不确定的文本划分到“分类”中。11、关联模式发现、关

19、联模式发现算法概述算法概述：关联分析的目的是挖掘隐藏的关联(Association) 模型，最著名的关联模式应用是挖掘“购物篮”问题，是从发现购买行中，发现商品之间的关联关系。给定一组交易记录：每笔交易 ID 包含 m 个商品，n 条记录组成二维表，构成 矩阵，BIC 可计算得出任意两商品组合的 Confidence(A-B)=P(A | B)置信度和支持度Support(A-B)=P(AU B)，可用于分析商品之间的关联性“购物篮”问题。BIC 的关联模式发现是一个快速、交互式 Apriore 计算过程：从发现最基本的 2 个 Item 关联高频项集开始，计算支持度 Support(A-B)

20、=P(A U B)和置信度 Confidence(A-B)=P(A | B)，精选优质文档-倾情为你奉上专心-专注-专业逐步计算和发现 2、3、4Item 关联频繁项集。因为：（1） 任何求解高频关联事务 T 中的项数 Item 必然大于等于 2， 如果只有 1 个 Item 不存在关联；（2）任何交易记录 T 中无论有多少个 Item 组合，如果存在大于 2 个 Item 的高频组合，都必然存在 2 关联的高频真子集。如：交易记录 T1=Item1，Item2，交易记录 T2=Item1，Item3，Item4，Item2，则 T1 为T2 的非空真子集 T1T2。所以，如果存在 3 关联的

21、高频 Item 组合，必然存在 2 关联的高频组合；如果存在 4 关联的Item 高频组合， 必然存在 3 关联高频组合。 BIC 就是通过最基本的 2 关联高频项集发现开始，逐步缩小记录集合，逐步发现所有任意数量 Item 组合的高频项集。因此，BIC 的关联计算是一个快速、交互式计算的 Apriore 算法。解决问题：解决问题：从样本集中发现有较强“置信度”的关联规则。12、序列模式发现、序列模式发现算法概述：算法概述：算法原理同“关联分析” ，但统计点在于事物（或商品购买）发生的先后序列。如商品购买行为预测：汽车改装爱好者，购买某种品牌增压器的人，很多人后来还购买了活塞环、又购买了某品牌

22、机油，通过序列分析，发现其购买序列、预测下一步购买行为；如疾病诊断：患有某种疾病的人，先出现 A 症状、后出现 B 症状、又出现 C 症状，通过出现症状的序列分析，发现疾病发生、发展的序列模式，对疾病进行诊断；如 Web 访问行为模式发现：每个 IP 访问网站都是一个 Web 会话 Session，每个 Session 由一系列的 URL 序列组成，通过 Session 计统计得到高频 URL 序列，预测用户的访问行为；不限于上述例子，还包括生物进化序列模式、DNA 序列、地震、火灾、战争冲突爆发序列模式预测等，序列规律是大量存在的，只要有足够的统计数据，都可以通过 BIC 发现最率并进行预测

23、。序列模式发现与关联模式发现在算法上很相似，但序列模式强调 Item 的先后顺序，而关联模式发现不关心顺序，只看是否在一个事物 T 中 2 个 Item（或多个）是否同时出现。BIC 的序列模式发现是一个快速、交互式 Apriore 计算过程：从发现 2 个 Item 序列高频序列开始，计置信度 Confidence(A-B)=P(A | B)，逐步计算和发现 2、3、4Item 序列频繁序列。因为：（1） 任何求解高频序列事务 T 中的项数 Item 必然大于等于 2， 如果只有 1 个 Item 不存在关联；（2）任何事务记录 T 中无论有多少个 Item 序列组合，如果存在大于 2 个

24、Item 的高频序列组合，都必然存在 2 序列的高频序列真子集。如：事务序列记录 T1=Item1，Item2，事务序列记录 T2=Item1，Item3，Item4，Item2，则 T1 为 T2 的非空真子集 T1T2。所以，如果存在 3 个 Item 序列的高频 Item 组合，必然存在 2 序列的高频序列组合，如果存在 4 个 Item 的高频序列组合，必然存在 3 高频序列组合。BIC 就是通过最基本的 2 序列高频序列发现开始，逐步缩小记录集合，逐步发现所有任意数量 Item 组合的高频序列组合。因此，BIC 的序列计算是一个*快速、交互式计算的 Apriore 算法。解决问题解决问题：序列模式发现的目的是挖掘事务发生、发展的序列 (Sequencing)模式，从样本集发现有较强“置信度”的序列规则。13、PCA 主成分分析主成分分析算法概述算法概述：假设一个事物由多种因素构成，设有 n 个样本，每个样本共有 m 个属性（指标、构成要素） ，构成一