文本挖掘算法总结

《文本挖掘算法总结》由会员分享，可在线阅读，更多相关《文本挖掘算法总结（12页珍藏版）》请在装配图网上搜索。

1、文本挖掘算法总结（总7页）文本数据挖掘算法应用小结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 1702-1763 )创造，用来描 述两个条件概率之间的关系，比

2、如P(A|B)为当“B”事件发生时“A”事件发生 的概率，按照乘法法则：P(A A B)=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, 则有：SI功二严咖贝叶斯分类的基本原理，就是利用贝叶斯条件概率公式，将事件X视为多个条件属性Cj各种取值的组合，当x事件发生时决策属性Di发生

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

4、是树的叶子。每 个决策节点代表一个问题或决策，每一个叶子节点代表一种可能的分类结果， 沿决策树在每个节点都会遇到一个测试，对每个节点上问题的不同取值导致不 同的分支，最后会到达一个叶子节点为确定所属分类天充參云YES凤tJ中解决问题： 预测所属分类。通过已知样本集记录，生成一颗“分类知识树”， 给 定一个未知“标签”记录，通过“分类知识树”来确定其所属分类。3、基于粗糙集理论Rough Set的确定型知识挖掘算法概述：1982年波兰学者乙Paw lak提出了粗糙集理论Rough Sets Theory，它是一种刻划不完整性和不确定性的数学工具，能有效分析不精确、不一致(Inconsistent

5、)、不完整(Incomplete)等各种不完备信息，利用数据进行分析和 推理，从中发现隐含的知识，揭示潜在的规律。粗糙集理论是继概率论、模糊 集、证据理论之后的又一个处理不确定性事物的数学工具。粗糙集理论是建立 在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关 系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一被划 分的集合称为概念。其主要思想是利用已知的知识库，将不精确或不确定的知 识用已知的知识库中的知识来(近似) 刻画。解决问题：预测所属分类。粗糙集分类将样本空间S划分为上近似集(Upper approximatio n)、下近似集(Lower appr

6、oximation)、边界集(Boundary region)，挖掘条件属性C与决策属性D集合所包含的不可分记录(不能再细 分，该集合中的所有记录都属于某一决策属性Di的取值)，这些记录形成不可 辨识的关系(Indiscernibility relation)，由此确定分类规则：IF V条件属性C成立THEN V决策属性Di发生即，如果满条件C,则其所属分类为Di。IF中的条件C可以是单一条件，也可 以是组合and (并且)组合条件。BIC给出的是“最小分类规则”。所谓“最小分类规则”是，最少的条件组合。例如 一个人属于“高”、“富”、“帅”，条件为：“身高”、“财富”、“工资性收入”、“财产

7、 性收入”、“产业收入”、“脸型”、“眼睛大小”、“鼻梁形状”、“英俊”等条件来判 别，通过“粗糙集”分类计算，得出最小分类规则可能是“IF财富=XXX1 and身高=185cm and相貌=英俊” 其他条件可以忽略不计，这就是“最小分类规则”。“粗糙集”分类规则为“百分之百确定型”分类规则，这是对样本集的统计结果，如 果出现非“样本集”中出现过的条件变量属性，将无法得出“粗糙集”，可转而使用 概率型“贝叶斯分类”进行计算。4、基于k-means聚类算法概述：给定一个包括n条记录、每条记录有m个属性的样本集，再给出分 类数k,要求将样本集中的记录，按记录间的相似性大小（或距离远近），将 相似性

8、最大（或距离最近）的记录划分到k个类中，相同分类中记录间的距离 要尽可能地小,而分类之间的距离要尽可能地大。BIC改进了常规的k-means聚类算法，在聚类过程中，同时计算分类质量（类内均差、类间均距匚和片），并求解最优聚类max 。解决问题：将n条记录聚成k个分类。对n个样本集记录，指定分类个数k，为 k个分类指定初始迭代记录为k个分类中心，通过计算其他记录对k个分类中心 的距离，对不断变换分类、变换类中心，收敛都当分类不再变化时，计算结 束。由此，将n个样本集记录分配到k个分类中，得到k个分类中心指标。5、无限细分的模糊聚类 Fuzzy Clustering算法概述：在实际解决聚类问题时，

9、很多数事物是“模糊”的，其特征属性A无 法确进行量化，如：人的相貌、人与人之间的关系、人的性格、购买商品的意 愿等，这就需要用模糊数学来进行相似性计算。模糊数学是伴随着上世纪五六 十年代兴起的控制论、信息论、系统论（俗称“老三论”）而形成的一种决策方 法，是美国加利福尼亚大学伯克利分校Lotfi Zadeh教授于1965年创立的。 模糊聚类基本计算步骤为：（1）将样本集中的n条记录变换成n x n的模糊相似矩阵；（2）通过传递包卷积计算将模糊相似矩阵变换成等价相似矩阵；（3）最后通过入截矩阵将n条记录分成1-n个分类。K-means聚类需事先确定聚类数k,而模糊聚类Fuzzy Clusteri

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

11、象,即,当一个神经细胞兴奋后,会对其周 围的神经细胞产生抑制作用。这种侧抑制使神经细胞之间呈现出竞争,开始时 可能多个细胞同时兴奋,但一个兴奋程度最强的神经细胞对周围神经细胞的抑 制作用也最强,其结果使其周围神经细胞兴奋程度减弱,从而该神经细胞是这 次竞争的“胜者”,其它神经细胞在竞争中失败。1981年芬兰学者kohonen提出一个称为自组织特征映射(Self Organization Feature Map-SOM或SOFM)网络，前述大脑神经细胞兴奋规律等，在该网络 中都得到了反应。在竞争层神经元之间的连线,它们是模拟生物神经网络层内 神经元相互抑制现象的权值,这类抑制性权值满足一定的分布

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

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

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

15、对文档间的相关性（接近度）进行聚类计算，可按Meaning“接近度”进行自动搜索而无需人工干 预，并随文档内容的变化而自动跟踪Meaning变化，使搜索更加准确、更加自 动化，让搜索“随用户的心而动”。BIC可用于基于Meaning计算的搜索、舆情分析、特定情报分析、垂直搜索和 相似内容推荐等文本挖掘。解决问题：计算两个文本的相似度。8、文本模糊聚类计算算法概述：基于模糊聚类算法，BIC首先计算将n个文本组成相似矩阵厂（第 i个文本文档对第j个文本文档的相似度），然后将相似矩阵6变成模糊相似 矩阵；，通过求模糊相似矩阵】的等价矩阵和截矩阵，将n个文本文档分成 1-n个分类，同时，按相同分类中的

16、文本具有最接近的内容相似度Min, 不同文本分类间具有最大差异Max ： ，来求解按文本内容进行最优分类方 案。解决问题：在不确定将文本划分成几类的情况下，将n个文本聚成1-n个分 类，以此来观察“聚类”效果。9、文本k-means聚类算法概述：基于k-means聚类，在BIC平台上，用户上传或输入n个文本，确 定希望分类数量k和k个分类样本，BIC将以k个样本作为初始迭代点进行k- means聚类计算，将n个文本分成k个分类。解决问题：在已经确定了 k个分类的情况下，将文本划分到k个分类”中。10、文本分类算法概述：通过“文本模糊聚类”或“文本k-means”聚类，BIC不仅将n个文本按 内

17、容相似度进行分类，同时挖掘出各个分类的“分类代表词组”，以后，用户任 意给出一个文本， BIC 将根据其对各个“分类代表词组”的相似度，选择最相似的 分类MaxSimi，将该待分类文档分配到MaxSimi类。解决问题： 在已经完成文本聚类的情况下，将不确定的文本划分到“分类”中。11、关联模式发现算法概述：关联分析的目的是挖掘隐藏的关联(Association)模型，最著名的关 联模式应用是挖掘“购物篮”问题，是从发现购买行中，发现商品之间的关联关给定一组交易记录：交易ID+1商品+商品胡育品川匸橘子Q香蕉1“ rn 平果Q香水皮包+：皮鞋帽子心dQQPQQ QQPQQPp4屮*每笔交易ID包

18、含m个商品八 , n条记录组成二维表，构成 矩阵，BIC可计算得出任意两商品匚组合的Confidence(A-B)=P(A I B)置信度 和支持度Support(A-B)=P(A U B)，可用于分析商品之间的关联性“购物篮”问 题。BIC的关联模式发现是一个快速、交互式Apriore计算过程：从发现最基本的2 个Item关联高频项集开始，计算支持度Support(A-B)=P(A U B)和置信度 Confidence(A-B)=P(A | B)，逐步计算和发现2、3、4-Item关联频繁项集。 因为：(1) 任何求解高频关联事务T中的项数Item必然大于等于2,如果只有1个 Item不存

19、在关联；(2) 任何交易记录T中无论有多少个Item组合，如果存在大于2个Item的高 频组合,都必然存在 2 关联的高频真子集。如：交易记录 T1=Item1， Item2，交易记录 T2=Item1， Item3， Item4， Item2，则T1为T2的非空真子集T1 T2。所以，如果存在3关联的高频Item组合，必然存在2关联的高频组合；如果存 在 4 关联的 Item 高频组合,必然存在 3 关联高频组合。 BIC 就是通过最基本 的 2关联高频项集发现开始,逐步缩小记录集合,逐步发现所有任意数量 Item组合的高频项集。因此，BIC的关联计算是一个快速、交互式计算的Apriore算

20、解决问题：从样本集中发现有较强“置信度”的关联规则。12、序列模式发现 算法概述：算法原理同“关联分析”，但统计点在于事物（或商品购买）发生的 先后序列。如商品购买行为预测：汽车改装爱好者，购买某种品牌增压器的人，很多人后 来还购买了活塞环、又购买了某品牌机油，通过序列分析，发现其购买序 列、预测下一步购买行为；如疾病诊断：患有某种疾病的人，先出现A症状、后出现B症状、又出现C症 状，通过出现症状的序列分析，发现疾病发生、发展的序列模式，对疾病进 行诊断；如Web访问行为模式发现：每个IP访问网站都是一个Web会话Session，每个 Session由一系列的URL序列组成，通过Session

21、计统计得到高频URL序列， 预测用户的访问行为；不限于上述例子，还包括生物进化序列模式、DNA序列、地震、火灾、战争冲 突爆发序列模式预测等，序列规律是大量存在的，只要有足够的统计数据，都 可以通过BIC发现最率并进行预测。序列模式发现与关联模式发现在算法上很相似，但序列模式强调Item的先后顺 序，而关联模式发现不关心顺序，只看是否在一个事物T中2个Item （或多 个）是否同时出现。BIC的序列模式发现是一个快速、交互式Apriore计算过程：从发现2个Item序列高频序列开始，计置信度Confidence(A-B)=P(A I B),逐步计算和发现2、3、4Item序列频繁序列。因为：(

22、1) 任何求解高频序列事务T中的项数Item必然大于等于2,如果只有1个Item不存在关联；(2) 任何事务记录T中无论有多少个Item序列组合，如果存在大于2个Item 的高频序列组合,都必然存在 2 序列的高频序列真子集。如：事务序列记录T1=Item1， Item2，事务序列记录T2=Item1， Item3，Item4，Item2，贝T1为T2的非空真子集T1 T2。所以，如果存在3个Item序列的咼频Item组合，必然存在2序列的咼频序列组 合，如果存在4个Item的咼频序列组合，必然存在3咼频序列组合。BIC就 是通过最基本的 2序列高频序列发现开始,逐步缩小记录集合,逐步发现所有

23、 任意数量Item组合的高频序列组合。因此，BIC的序列计算是一个*快速、交 互式计算的Apriore算法。解决问题：序列模式发现的目的是挖掘事务发生、发展的序列(Sequencing)模 式,从样本集发现有较强“置信度”的序列规贝。13、PCA 主成分分析算法概述：假设一个事物由多种因素构成，设有n个样本，每个样本共有m个 属性(指标、构成要素)，构成一个nxm阶的成分数据矩阵，兀11 闷？ X戡二=两1兀2與mIDIDIXtun_PCA算法的目的是：(1)降低维度当矩阵X的维数m较大时，在m维空间中考察问题比较麻烦，需要降低维 度，在不影响对事物评价的基础上，选择较少的几个主要指标P (p

24、 m)来代 替原来较多的变量指标 m。( 2 )消除变量间的相关性(3) 分析指标体系中各个指标的对事物的区分性。衡量一个事物好坏由多个指 标所决定，但指标对事物的区分性有强弱之分，通过PCA计算，可以分析哪些 指标有更好的区分性，哪些指标的区分性较弱。PCA解决算法原理：PCA算法的核心是，将非实对称矩阵X变成实对称矩阵A,求矩阵A的特征值 和特征向量，特征值为P个指标，特征向量为P个指标对原来m个指标的荷载 参数。BIC采用Jacobi (雅可比)方法来求特征值和特征向量。Jacobi方法的基本理论是，对于一实对称矩阵A，必有一正交矩阵U，使 得丁上丄厂，可以证明，如果丁m，则矩阵d为矩阵

25、a的相似矩 阵，相似矩阵具有相同的特征值和特征向量。Jacobi方法通过平一系列的面旋 转变换来求丁上匚、少，变换过程中，让非对角线上的元素逐步变小，对角线 上的元素逐渐变大，最后将矩阵D中非对角线上的元素变成0 (或趋近于 0),对角线上的元素li是矩阵A的特征值，正交阵U的第j列是A的属于li 的特征向量，以此求解矩阵A的特征值和特征向量。解决问题：PCA可广泛用于事物要素（指标）分析。任何一个事物都是由多个指标组成，包括商业行为、医学诊断、药理分析、生产质量控制、生产工艺设计、经济分析，甚至是军事、外交事物等。人们需要掌握，构成事物的要素（指标）与事物的结果是什么关系哪些是主要指标哪些是次要指标指标和指标之间存在什么关系PCA通过一组样本集的计算分析，就可以精确回答这些问题。