文本挖掘算法总结

文本数据挖掘算法应用小结

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(AB)为当“B”事件发生时“A”事件发生得概率，按照乘法法

则：

P(AAD)=P(A)*P(D|A)=P(B)*F(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)o对于任一事件x,P(x)>0,则有：

X汽X14)网4)

贝叶斯分类得基本原理,就就是利用贝叶斯条件概率公式,将事件X视为多个条件属性Cj各

种取值得组合，当x事件发生时决策属性Di发生得条件概率。贝叶斯分类就是一种概率型分

类知识挖掘方法，不能百分之百地确定X事件发生时Di一定发生。

解决问题：预测所属分类得概率。通过已知n条样本集记录，计算各种条件属性组发生得概率,

得出''贝叶斯分类”规则，给定一个未知“标签”记录，选择最大概率为其所属‘'分类

2>ID3决策树分类

算法概述：ID3算法就是J、RossQuinlan在1975提出得分类算法，当时还没有“数据挖掘”

得概念。该算法以信息论为基址，以信息炳与信息增益度来确定分枝生成决策树D-Tree。ID3

算法以决策树D-Tree构建分类知识模型，D-Tree中最上面得节点为根节点Root,每个分支就

是一个新得决系节点，或者就是树得叶子。每个决爱节点代表一个问题或决赛.每一个叶子节

点代表一种可能得分类结果，港决策树在每个节点都会遇到一个测试，对每个节点上问题得

不同取值导致不同得分支，最后会到达一个叶子节点为确定所属分类。

解决问题：预测所属分类。通过已知样本集记录，生成一颗“分类知识树”，给定一个未知“标

签”记录，通过“分类知识树”来确定其所属分类。

3、基于粗糙集理论RoughSet得确定型知识挖掘

算法概述：1982年波兰学者LPawlak提出了粗糙集理论RoughSetsTheory,它就是一

种刻划不完圣性与不确定性得数学工具，能有效分析不精确、不一致（Inconsistent）、不完

整（Inplete）等各种不完备信息，利用数据进行分析与推理，从中发现隐含得知识，揭示潜在

得规律。粗糙集理论就是继概率论、模糊集、证据理论之后得又一个处理不确定性事物得数

学工具。粗槎集理论就是建立在分类机制将基础上得，它将分类理解为在特定空间上得等价

关系，而等价关系构成了对该空间得划分。粗糙集理论将知识理解为对数据得划分，每一被划

分得集合称为概念。其主要思想就是利用已知得知识库，将不料确或不确定得知识用已知得

知识库中得知识来（近似）刻画。

解决问题：预测所属分类。粗槌集分类将样本空间S划分为上近似集（Upperapproximation）

下近似集（Lowerapproximation）＞边界集（Boundaryregion）,挖掘条件属性C与决策属性

D集合所包含得不可分记录（不能再细分，该集合中得所有记录都属于某一决策属性Di得取

值），这些记录形成不可耕汛得关系（IndiscernibiIityrelation）,由此确定分类规

则：

IF〈条件属性C成立,THEN＜决策属性Di发生》

即，如果满条件C,则其所属分类为Di。IF中得条件C可以就是单一条件，也可以就是组合

and（并且）组合条件。

BIC给出得就是“最小分类规则”。所谓“最小分类规则”就是.最少得条件组合。例如一个

人属于“高”、“富”、“帅”，条件为：“身高”、“财富”、“工资性收入”、“财产性收入”、“产

业收入“、“脸型”、“眼睛大小”、“鼻梁形状”、“英俊”等条件来判别，通过“粗糙集”分类

计算，得出最小分类规则可能就是

“IF财富＞=XXX1and身高＞=185cmand相貌=英俊”

其她条件可以忽略不计，这就就是“最小分类规则”。

“粗糙集”分类规则为“百分之百确定型”分类规则，这就是对样本集得统计结果，如果出现

非“样本集”中出现过得条件变量属性，将无法得出“粗糙集”,可转而使用概率型“贝叶斯

分类”进行计算。

4、基于k-means聚类

算法概述：给定一个包括n条记录、每条记录有m个属性得样本集，再给出分类数k,要求将

样本集中得记录，按记录间得相似性大小（或距离远近），将相似性最大（或距离最近）得记录

划分到k个类中，相同分类中记录问得距离要尽可能地小，而分类之间得距离要尽可能地大。

BIC改进了常规得k-means聚类算法，在聚类过程中，同时计算分类质量（类内均差、类间均

距0炉与万），并求解最优聚类max｛万｝。

解决问题:将n条记录聚成k个分类。对n个样本集记录，指定分类个数k,为k个分类指定

初始迭代记录为k个分类中心，通过计算其她记录对k个分类中心得距离，对不断变换分类、

变换类中心，收敛都当分类不再变化时，计算结束。由此，将n个样本集记录分配到k个分类

中，得到k个分类中心指标。

5、无限细分得模糊聚类FuzzyClustering

算法概述：在实际解决聚美问题时，很多数事物就是“模糊”得，其特征属性A无法确进行量

化，如：人得相貌、人与人之间得关系、人得性格、购买商品得意愿等，这就需要用模糊数学

来进行相似性计算。模糊数学就是伴甑着上世纪五六十年代兴起得控制论、信息论、系统论

（俗称“老三论”）而形成得一种决装方法，就是美国加利福尼亚大学伯克利分校LotfiZadeh

教授于1965年创立得。

模糊聚类基本计算步骤为：

⑴将样本集中得n条记录变换成nxn得模拗相似矩阵；

⑵通过传递包卷积计算将模糊相似矩阵变换成等价相似矩阵；

⑶最后通过入极矩阵将n条记录分成1-n个分类。

Kmeans聚美需事先确定聚美数k,而模糊聚美「uzzyCIustering无需事先确定聚美数k,可

以从最小得k=1（所有学习集中得n条记录为1个分类），到k=n（所有学习集中得n条记录各

为1个分类）。

解决问题：将n条记录聚成1-n个分类。模糊聚类FuzzyClustering算法完全基于数据自然

状况进行聚类，可产生聚类得辞集合C"（k=1,2,,,,,n）,因此，可以在解集合中求解最优

聚类max｛C｝，这对现察分析样本集得数据性态非常有用，可供视察不同情况下得“聚

类”状况。

6、S0M神经元网络聚类

算法概述：人类对事物得认知就是一个不断积累得过程，通过对事物得现察，不断地认识与修

正因果关系，最后逐渐稳定为认知规则。医学证明，人眼得视网膜、奔髓与海马中存一种侧抑

制现象，即，当一个神经细胞兴奋后，会对其周围得神经细胞产生抑制作用。这种侧抑制使神

经细胞之间呈现出竞争，开始时可能多个细胞同时兴奋，但一个兴奋程度最强得神经细胞对

周围神经细胞得抑制作用也最强，其结果使其周围神经细胞兴奋程度减弱，从而该神经细胞

就是这次竞争得“胜者”，其它神经细胞在竞争中失败。

1981年芬兰学者kohonen提出一个称为自组织特征映射（SelfOrganizationFeature

Map-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｛01，D1,,,Dn｝,BIC为每个文档计算出一组最

具有代表性得词组。｛讨，琢.｝,同时，计算出。相互间内容接近度及接

近序列。

BIC得Meaning挖掘与自动搜索不同于现有Baidu、Google人工揄入关犍词得搜索方式，现

有搜索引擎不考虑语义与语境，只考虑词W与文档D得包含关系WW0；与词在文档内得频

数TF,因此，关犍词得搜索与文档内容无关。

例如：“姚明”就是中国篮球得骄傲，但“姚明”还投身于公益事业，如果在搜索引擎中榆入

“姚明”，不见得搜索得文档内容只包含与篮球相关得内容,还可能包括公益及其她包含“姚

明”得文档，可见，关键词搜索具有不确定性。如果在搜索引擎输入一组词｛“姚明”、“得分”、

“篮板”｝，搜出文档就是篮球比赛内容得概,率更大，显然，叫n形成得交集缩小了搜索范

围，但组词（“姚明”、“得分”、“篮板”）就是经过人思考给出将。

BIC通过计笄得出文档代表词组A｛讨，w；,,，w；,,,以，｝,相当于人工输入｛“姚明，

“得分”、“篮板”｝,同时计算词用在句子中语序关系得发生概率与马尔科夫犍，因此，能

够更好地确定搜索词得语义与语境，通过对文档间得相关性（接近度）进行聚类计算，可按

Meaning“接近度”进行自动捏索而无需人工干预，并随文档内容得变化而自动跟踪Meaning

变化，使搜索更加准确、更加自动化，让搜索“随用户得心而动:

BIC可用于基于Meaning计算将搜索、舆情分析、特定情报分析、垂直搜索与相似内容推荐

等文本挖掘。

解决问题：计算两个文本得相似度。

8、文本模糊聚类计算

算法概述：基于模撷聚类算法,BIC首先计算将n个文本组成相似矩阵(第i个文本文档

对第j个文本文档得相似度)，然后将相似矩阵"。变成模糊相似矩阵飞，通过求模糊相

似矩阵,二得等价矩阵与截矩阵，将n个文本文档分成1-n个分类，同时，按相同分类中得文

本具有最接近得内容相似度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个文本按内容相似

度进行分类，同时挖掘出各个分类得“分类代表词组”，以后，用户任意给出一个文本,BIC将

根据其对各个“分类代表词组”得相似度，选择最相似得分类MaxSim{i},将该待分类文档分

配到MaxSim{i}类。

解决问题：在已经完成文本聚美得情况下，招■不确定得文本划分到“分类”中。

11、关联模式发现

算法概述：关联分析得目得就是挖掘隐藏得关联(Association)模型，最著名得关联模式应

用就是挖掘“购物篮”问题，就是从发现购买行中，发现商品之间得关联关系。

给定一组交易记录：

交易ID~福品I*3商品:*1商品V3........商品《

橘子“香蕉Q苹果一牛肉〃

香水••皮包皮珪帽子/

Q~~5

.........."*5

*AP

P

每笔交易ID包含m个商品{G，02，，，，3…Cm},n条记录组成二维表，构成矩阵,BIC可

计算得出任意两商品J组合得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关联得高频真子集。

如：交易记录Tk(Itend,Item2),交易记录T2={ltem1,Item3,Item4,Item2},则T1为T2得非

空其子集T《T2°

所以，如果存在3关联得高频Item组合，必然存在2关联得高频组合；如果存在4关联得Item

高频组合，必然存在3关联高频组合…。BIC就就是通过最基本得2关联高频项集发现开始，

逐步缩小记录集合，逐步发现所有任意数量Item组合得高频项集。因此，BIC得关联计算就

是一个快速、交互式计算得Apriore算法。

解决问题：从样本集中发现有较强“置信度”得关联规处I。

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序列频繁序

列。

因为：

⑴任何求解高频序列事务T中得项数Item必然大于等于2,如果只有1个Item不存在关联；

⑵任何事务记录T中无论有多少个Item序列组合,如果存在大于2个Item得高频序列组合，

都必然存在2序列得高频序列其子集。

如：事务序列记录T1={ltem1,ltem2},事务序列记录T2={ltem1,Item3,Item4,Item2),T1

为T2得非空真子集T1UT2。

所以，如果存在3个Item序列得高频Item组合，必然存在2序列得高频序列组合，如果存在

4个Item得高频序列组合,必然存在3高频庠列组合…。BIC就就是通过最基本得2庠列高

频序列发现开始，逐步缩小记录集合，逐步发现所有任意数量Item组合得高频序列组合。因

此，BIC得序列计算就是一个*快速、交互式计算得Apriore算法。

解决问题：序列模式发现得目得就是挖掘事务发生、发展得序列(Sequencing)模式，从样本

集发现有较强“置信度”得序列规则。

13、PCA主成分分析

算法概述：假设一个事物由多种因索