文本挖掘算法总结.docx

该【文本挖掘算法总结 】是由【guoxiachuanyue】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【文本挖掘算法总结 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实用文档.
文本数据挖掘算法应用小结
1、基于概率统计的贝叶斯分类
2、ID3决策树分类
3、基于粗糙集理论RoughSet确实定型知识挖掘
4、基于k-means聚类
5、无限细分的模糊聚类FuzzyClustering
6、SOM神经元网络聚类
7、基于Meaning的文本相似度计算
8、文本模糊聚类计算
9、文本k-means聚类
10、文本分类
11、关联模式发现
12、序列模式发现
13、PCA主成分分析
1、基于概率统计的贝叶斯分类
算法概述:贝叶斯公式是由英国数学家(ThomasBayes1702-1763)创」造,用来描述两个条件概率之间的关系,比方P(AIB)为当“B〃事件发生时“A〃事件发生的概率,按照乘法法那么:
P(AnB)=P(A)*P(BIA)=P(B)*P(AIB),可导出
贝叶斯公式: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,那么有:
41壬严吨
贝叶斯分类的根本原理,就是利用贝叶斯条件概率公式,将事件X视为多个条件属性Cj各种取值的组合,当X事件发生时决策属性Di发生的条件概率。贝叶斯分类是一种概率型分类知识挖掘方法,不能百分之百地确定X事件发生时Di一定发生。
解决问题:预测所属分类的概率。通过n条样本集记录,计算各种条件属性组发生的概率,得出“贝叶斯分类〃规那么,给定一个未知“标签〃记录,选择最大概率为其所属“分类〃。
2、ID3决策树分类
算法概述:,当时还没有“数据挖掘〃的概念。该算法以信息论为根底,以信息熵和信息增益度来确定分枝生成决策树D-Tree。ID3算法以决策树D-Tree构建分类知识模型,D-Tree中最上面的节点为根节点Root,每个分支是一个新的决策节点,或者是树的叶子。每个决策节点代表一个问题或决策,每一个叶子节点代表一种可能的分类结果,沿决策树在每个节点都会遇到一个测试,对每个节点上问题的不同取值导致不同的分支,最后会到达一个叶子节点为确定所属分类。
实用文档.
湿虛VESto
解决问题:预测所属分类。通过样本集记录,生成一颗“分类知识树〃,给定一个未知“标签〃记录,通过“分类知识树〃来确定其所属分类。
3、基于粗糙集理论RoughSet确实定型知识挖掘
算法概述:1982年波兰学者乙Pawlak提出了粗糙集理论RoughSetsTheory,它是一种刻划不完整性和不确定性的数学工具,能有效分析不精确、不一致〔Inconsistent)、不完整〔Incomplete)等各种不完备信息,利用数据进行分析和推理,从中发现隐含的知识,揭示潜在的规律。粗糙集理论是继概率论、模糊集、证据理论之后的又一个处理不确定性事物的数学工具。粗糙集理论是建立在分类机制的根底上的,它将分类理解为在特定空间上的等价关系,而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分,每一被划分的集合称为概念。其主要思想是利用的知识库,将不精确或不确定的知识用的知识库中的知识来〔近似〕刻画。
解决问题:预测所属分类。粗糙集分类将样本空间S划分为上近似集〔Upperapproximation)、下近似集〔Lowerapproximation〕、边界集〔Boundaryregion),挖掘条件属性C与决策属性D集合所包含的不可分记录〔不能再细分,该集合中的所有记录都属于某一决策属性Di的取值〕,这些记录形成不可辨识的关系〔Indiscernibilityrelation),由此确定分类规那么:IF<条件属性C成立〉THEN<决策属性Di发生〉
即,如果满条件C,那么其所属分类为DioIF中的条件C可以是单一条件,也可以是组合and〔并且、组合条件。
BIC给出的是“最小分类规那么〃。所谓“最小分类规那么〃是,最少的条件组合。例如一个人属于“高〃、“富〃、“帅〃,条件为:“身高〃、“财富〃、“工资性收入〃、“财产性收入〃、“产业收入〃、“脸型〃、“眼睛大小〃、“鼻梁形状〃、“英俊〃等条件来判别,通过
“粗糙集〃分类计算,得出最小分类规那么可能是
“IF财富〉=XXX1and身高〉=185cmand相貌=英俊〃
其他条件可以忽略不计,这就是“最小分类规那么〃。
“粗糙集〃分类规那么为“百分之百确定型〃分类规那么,这是对样本集的统计结果,如果出现非“样本集〃中出现过的条件变量属性,将无法得出“粗糙集〃,可转而使用概率型“贝叶斯分类〃进行计算。
4、基于k-means聚类
算法概述:给定一个包括n条记录、每条记录有m个属性的样本集,再给出分类数k,要求将样本集中的记录,按记录间的相似性大小〔或距离远近〕,将相似性最大〔或距离最近〕的记录划分到k个类中,相同分类中记录间的距离要尽可能地小,而分类之间的距离要尽可能地大。
实用文档.
BIC改良了常规的k-means聚类算法,在聚类过程中,同时计算分类质量〔类内均差、类
间均距和元〕,并求解最优聚类max•{更}。
解决问题:将n条记录聚成k个分类。对n个样本集记录,指定分类个数k,为k个分类指定初始迭代记录为k个分类中心,通过计算其他记录对k个分类中心的距离,对不断变换分类、变换类中心,收敛都当分类不再变化时,计算结束。由此,将n个样本集记录分配到k个分类中,得到k个分类中心指标。
5、无限细分的模糊聚类FuzzyClustering
算法概述:在实际解决聚类问题时,很多数事物是“模糊〃的,其特征属性A无法确进行量化,如:人的相貌、人与人之间的关系、人的性格、购置商品的意愿等,这就需要用模糊数学来进行相似性计算。模糊数学是伴随着上世纪五六十年代兴起的控制论、信息论、系统论〔俗称“老三论〃〕而形成的一种决策方法,是美国加利福尼亚大学伯克利分校LotfiZadeh教授于1965年创立的。
模糊聚类根本计算步骤为:
〔1〕将样本集中的n条记录变换成nxn的模糊相似矩阵;
〔2〕通过传递包卷积计算将模糊相似矩阵变换成等价相似矩阵;
〔3〕最后通过入截矩阵将n条记录分成1-n个分类。
K-means聚类需事先确定聚类数k,而模糊聚类FuzzyClustering无需事先确定聚类数k,可以从最小的k=1〔所有学录为1个分类〕,到k=n〔所有学录各为1个分类〕。
解决问题:将n条记录聚成1-n个分类。模糊聚类FuzzyClustering算法完全基于数据自然状况进行聚类,可产生聚类的解集合C(k=1,2,,,,,n),因此,可以在解集合中求解最优聚类max{「‘},这对观察分析样本集的数据性态非常有用,可供观察不同情况下的“聚类〃状况。
6、SOM神经元网络聚类
算法概述:人类对事物的认知是一个不断积累的过程,通过对事物的观察,不断地认识和修正因果关系,最后逐渐稳定为认知规那么。医学证明,人眼的视网膜、脊髓和海马中存一种侧抑制现象,即,当一个神经细胞兴奋后,会对其周围的神经细胞产生抑制作用。这种侧抑制使神经细胞之间呈现出竞争,开始时可能多个细胞同时兴奋,但一个兴奋程度最强的神经细胞对周围神经细胞的抑制作用也最强,其结果使其周围神经细胞兴奋程度减弱,从而该神经细胞是这次竞争的“胜者〃,其它神经细胞在竞争中失败。
1981年芬兰学者kohonen提出一个称为自组织特征映射〔SelfOrganizationFeatureMap-SOM或SOFM〕网络,前述大脑神经细胞兴奋规律等,在该网络中都得到了反响。在竞争层神经元之间的连线,它们是模拟生物神经网络层内神经元相互抑制现象的权值,这类抑制性权值满足一定的分布关系,如距离近的抑制强,距离远的抑制弱。
实用文档.
输出挾式
*
输心式
通过上述可知,SOM聚类算法设计的核心思想是表达神经元在认知过程中的3个特性:
〔1〕根据样本比拟,逐步积累、不断修正、渐近稳定特性?
〔2〕神经元之间的侧抑由近到远、逐步衰弱制特性?
〔3〕神经元兴奋区域随认知次数逐步缩小范围特性?
BIC采用欧氏距离作为输入模式Xi与各输出神经元Wj之间的相似度,选择具有最小距离的神经元为兴奋神经元;采用〔1-ti/tm〕作为学习衰减函数,其中ti为当前学习次数〔第几次样本训练〕,tm为总的学习数,以此来表达上述特性“1”采用〔1-ti/T〕、C/Wij作为神经元侧抑制函数,其中C为设定的常数、Wij为被选中的神经元与其他神经元最远距离,来表达上述特性“2”、“3”。
解决问题:将n条记录按m个输出神经元聚成m个分类。模仿人类的学习方法,对事物的认识是一个由浅入深、逐步学习、修正的过程,将对各种要素组态的认识逐步稳定到认知领域,由此进行“聚类〃。
7、基于Meaning的文本相似度计算
算法概述:给出一组n个文档D{-iSS},BIC为每个文档计算出一组最
具有代表性的词组“八二…"…;.},同时,计算出:相互间内容接近度及接近序列。
BIC的Meaning挖掘与自动搜索不同于现有Baidu、Google人工输入关键词的搜索方式,现有搜索引擎不考虑语义和语境,只考虑词W与文档D的包含关系'■和词在文档内的频数TF,因此,关键词的搜索与文档内容无关。
例如:“姚明〃是中国篮球的骄傲,但“姚明〃还投身于公益事业,如果在搜索引擎中输入“姚明〃,不见得搜索的文档内容只包含与篮球相关的内容,还可能包括公益及其他包含'姚明〃的文档,可见,关键词搜索具有不确定性。如果在搜索引擎输入一组词{“姚明〃、“得分〃、“篮板〃},搜出文档是篮球比赛内容的概率更大,显然,〉形成的交集缩小了搜索范围,但组词{“姚明〃、“得分〃、“篮板〃}是经过人思考给出的。
BIC通过计算得出文档代表词组P…相当于人工输入{“姚
明〃、“得分〃、“篮板〃},同时计算词"在句子中语序关系的发生概率与马尔科夫链,因此,能够更好地确定搜索词的语义和语境,通过对文档间的相关性〔接近度〕进行聚类计算,可按Meaning“接近度〃进行自动搜索而无需人工干预,并随文档内容的变化而自动跟踪Meaning变化,使搜索更加准确、更加自动化,让搜索“随用户的心而动〃。
BIC可用于基于Meaning计算的搜索、舆情分析、特定情报分析、垂直搜索和相似内容推荐等文本挖掘。
实用文档.
解决问题:计算两个文本的相似度。
8、文本模糊聚类计算
算法概述:基于模糊聚类算法,BIC首先计算将n个文本组成相似矩阵入〔第i个文本文档对第j个文本文档的相似度〕然后将相似矩阵变成模糊相似矩阵勺,通过求模糊相似矩阵的等价矩阵和截矩阵,将n个文本文档分成1-n个分类,同时,按相同分类中的文本具有最接近的内容相似度Min{〔},不同文本分类间具有最大差异Max{J},来求解按文本内容进行最优分类方案。
解决问题:在不确定将文本划分成几类的情况下,将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个文本按内容相似度进行分类,同时挖掘出各个分类的“分类代表词组〃,以后,用户任意给出一个文本,BIC将根据其对各个“分类代表词组〃的相似度,选择最相似的分类MaxSim{i},将该待分类文档分配到MaxSim{i}类。
解决问题:在已经完成文本聚类的情况下,将不确定的文本划分到“分类〃中。
11、关联模式发现
算法概述:关联分析的目的是挖掘隐藏的关联(Association)模型,最著名的关联模式应用是挖掘“购物篮〃问题,是从发现购置行中,发现商品之间的关联关系。
给定一组交易记录:
交境ID+1
商品声
商品m
帝品E
匸
商品
橘子Q
香蕉Q
■小|“m
平果Q
牛肉心
-%
香水
皮包
*■皮鞋■
帽子心
dQ4pQQ
■■■■■
P
P
pa
卫*
P
每笔交易ID包含m个商品,"'•},n条记录组成二维表,构成矩阵,
c
BIC可计算得出任意两商品:组合的Confidence(A->B)=P(A|B)置信度和支持度
Support(A->B)=P(AUB),可用于分析商品之间的关联性“购物篮〃问题。
BIC的关联模式发现是一个快速、交互式Apriore计算过程:从发现最根本的2个Item关联高频项集开始,计算支持度Support(A->B)=P(AUB)和置信度Confidence(A->B)=P(A|B),逐步计算和发现2、3、4—Item关联频繁项集。
因为:
〔1〕任何求解高频关联事务T中的项数Item必然大于等于2,如果只有1个Item不存在关联;
实用文档.
〔2〕任何交易记录T中无论有多少个Item组合,如果存在大于2个Item的高频组合,都必然存在2关联的高频真子集。
如:交易记录T1={Item1,Item2},交易记录T2={Item1,Item3,Item4,Item2},那么T1为T2的非空真子集T1CT2。
所以,如果存在3关联的高频Item组合,必然存在2关联的高频组合;如果存在4关联的Item高频组合,必然存在3关联高频组合…。BIC就是通过最根本的2关联高频项集发现开始,逐步缩小记录集合,逐步发现所有任意数量Item组合的高频项集。因此,BIC的关联计算是一个快速、交互式计算的Apriore算法。
解决问题:从样本集中发现有较强“置信度〞的关联规那么。
12、序列模式发现算法概述:算法原理同“关联分析〞,但统计点在于事物〔或商品购置〕发生的先后序列。如商品购置行为预测:汽车改装爱好者,购置某种品牌增压器的人,很多人后来还购置了活塞环、又购置了某品牌机油…,通过序列分析,发现其购置序列、预测下一步购置行为;如疾病诊断:患有某种疾病的人,先出现A病症、后出现B病症、又出现C病症…,通过出现病症的序列分析,发现疾病发生、开展的序列模式,对疾病进行诊断;
如Web访问行为模式发现:每个IP访问网站都是一个Web会话Session,每个Session由一系列的URL序列组成,通过Session计统计得到高频URL序列,预测用户的访问行为;不限于上述例子,还包括生物进化序列模式、DNA序列、地震、火灾、战争冲突爆发序列模式预测等,序列规律是大量存在的,只要有足够的统计数据,都可以通过BIC发现最率并进行预测。
序列模式发现与关联模式发现在算法上很相似,但序列模式强调Item的先后顺序,而关联模式发现不关心顺序,只看是否在一个事物T中2个Item〔或多个〕是否同时出现。
BIC的序列模式发现是一个快速、交互式Apriore计算过程:从发现2个Item序列高频序列开始,计置信度Confidence(A->B)=P(A|B),逐步计算和发现2、3、4^Item序列频繁序列。因为:
〔1〕任何求解高频序列事务T中的项数Item必然大于等于2,如果只有1个Item不存在关联;
〔2〕任何事务记录T中无论有多少个Item序列组合,如果存在大于2个Item的高频序列组合,都必然存在2序列的高频序列真子集。
如:事务序列记录T1={Item1,Item2},事务序列记录T2={Item1,Item3,Item4,Item2},那么T1为T2的非空真子集T1CT2。
所以,如果存在3个Item序列的高频Item组合,必然存在2序列的高频序列组合,如果存在4个Item的咼频序列组合,必然存在3咼频序列组合…。BIC就是通过最根本的2序列高频序列发现开始,逐步缩小记录集合,逐步发现所有任意数量Item组合的高频序列组合。因此,BIC的序列计算是一个*快速、交互式计算的Apriore算法。
解决问题:序列模式发现的目的是挖掘事务发生、开展的序列(Sequencing)模式,从样本集发现有较强“置信度〞的序列规那么。
13、PCA主成分分析
算法概述:假设一个事物由多种因素构成,设有n个样本,每个样本共有m个属性〔指标、构成要素〕,构成一个nXm阶的成分数据矩阵,
兀11
…心
盹1
…仏
.仙
PCA算法的目的是:
实用文档.
〔1〕降低维度
当矩阵X的维数m较大时,在m维空间中考察问题比拟麻烦,需要降低维度,在不影响对事物评价的根底上,选择较少的几个主要指标P〔p<m〕来代替原来较多的变量指标m。
〔2〕消除变量间的相关性
〔3〕分析指标体系中各个指标的对事物的区分性。衡量一个事物好坏由多个指标所决定,但指标对事物的区分性有强弱之分,通过PCA计算,可以分析哪些指标有更好的区分性,哪些指标的区分性较弱。
PCA解决算法原理:
PCA算法的核心是,将非实对称矩阵X变成实对称矩阵A,求矩阵A的特征值和特征向量,特征值为P个指标,特征向量为P个指标对原来m个指标的荷载参数。BIC采用Jacobi〔雅可比〕方法来求特征值和特征向量。
Jacobi方法的根本理论是,对于一实对称矩阵A,必有一正交矩阵U,使得〔一上1二巴
可以证明,如果,那么矩阵D为矩阵A的相似矩阵,相似矩阵具有相同的特征值和特征向量。Jacobi方法通过平一系列的面旋转变换来求,变换过程中,
让非对角线上的元素逐步变小,对角线上的元素逐渐变大,最后将矩阵D中非对角线上的元素变成0〔或趋近于0〕,对角线上的元素li是矩阵A的特征值,正交阵U的第j列是A的属于li的特征向量,以此求解矩阵A的特征值和特征向量。
解决问题:
PCA可广泛用于事物要素〔指标〕分析。任何一个事物都是由多个指标组成,包括商业行为、医学诊断、药理分析、生产质量控制、生产工艺设计、经济分析,甚至是军事、外交事物等。人们需要掌握,构成事物的要素〔指标〕与事物的结果是什么关系?哪些是主要指标?哪些是次要指标?指标和指标之间存在什么关系?PCA通过一组样本集的计算分析,就可以精确答复这些问题。