文本挖掘算法总结

第一篇：文本挖掘算法总结

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

1、基于概率统计的贝叶斯分类

2、ID3 决策树分类

3、基于粗糙集理论Rough Set的确定型知识挖掘

4、基于k-means聚类

5、无限细分的模糊聚类Fuzzy Clustering

6、SOM神经元网络聚类

7、基于Meaning的文本相似度计算

8、文本模糊聚类计算

9、文本k-means聚类

10、文本分类

11、关联模式发现

12、序列模式发现

13、PCA主成分分析

1、基于概率统计的贝叶斯分类

算法概述：贝叶斯公式是由英国数学家(Thomas Bayes 1702-1763)创造，用来描述两个条件概率之间的关系，比如 P(A|B)为当“B”事件发生时“A”事件发生的概率，按照乘法法则：

P(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，则有：

贝叶斯分类的基本原理，就是利用贝叶斯条件概率公式，将事件X视为多个条件属性Cj各种取值的组合，当x事件发生时决策属性Di发生的条件概率。贝叶斯分类是一种概率型分类知识挖掘方法，不能百分之百地确定X事件发生时Di一定发生。

解决问题：预测所属分类的概率。通过已知n条样本集记录，计算各种条件属性组发生的概率，得出“贝叶斯分类”规则，给定一个未知“标签”记录，选择最大概率为其所属“分类”。

2、ID3 决策树分类

算法概述：ID3算法是J.Ross Quinlan在1975提出的分类算法，当时还没有“数据挖掘”的概念。该算法以信息论为基础，以信息熵和信息增益度来确定分枝生成决策树D-Tree。ID3算法以决策树D-Tree构建分类知识模型，D-Tree中最上面的节点为根节点Root，每个分支是一个新的决策节点，或者是树的叶子。每个决策节点代表一个问题或决策，每一个叶子节点代表一种可能的分类结果，沿决策树在每个节点都会遇到一个测试，对每个节点上问题的不同取值导致不同的分支，最后会到达一个叶子节点为确定所属分类。

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

3、基于粗糙集理论Rough Set的确定型知识挖掘

算法概述：1982年波兰学者Z.Paw lak 提出了粗糙集理论Rough Sets Theory，它是一种刻划不完整性和不确定性的数学工具，能有效分析不精确、不一致（Inconsistent)、不完整（Incomplete)等各种不完备信息，利用数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。粗糙集理论是继概率论、模糊集、证据理论之后的又一个处理不确定性事物的数学工具。粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一被划分的集合称为概念。其主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来（近似）刻画。解决问题：预测所属分类。粗糙集分类将样本空间S划分为上近似集（Upper approximation)、下近似集（Lower approximation）、边界集（Boundary region)，挖掘条件属性C与决策属性D集合所包含的不可分记录（不能再细分，该集合中的所有记录都属于某一决策属性Di的取值），这些记录形成不可辨识的关系（Indiscernibility relation)，由此确定分类规则： IF <条件属性C成立> THEN <决策属性Di发生>

即，如果满条件C，则其所属分类为Di。IF中的条件C可以是单一条件，也可以是组合and（并且）组合条件。

BIC给出的是“最小分类规则”。所谓“最小分类规则”是，最少的条件组合。例如一个人属于“高”、“富”、“帅”，条件为：“身高”、“财富”、“工资性收入”、“财产性收入”、“产业收入”、“脸型”、“眼睛大小”、“鼻梁形状”、“英俊”等条件来判别，通过“粗糙集”分类计算，得出最小分类规则可能是

“IF 财富>=XXX1 and 身高>=185cm and 相貌=英俊” 其他条件可以忽略不计，这就是“最小分类规则”。

“粗糙集”分类规则为“百分之百确定型”分类规则，这是对样本集的统计结果，如果出现非“样本集”中出现过的条件变量属性，将无法得出“粗糙集”，可转而使用概率型“贝叶斯分类”进行计算。

4、基于k-means聚类

算法概述：给定一个包括n条记录、每条记录有m个属性 的样本集，再给出分类数k，要求将样本集中的记录，按记录间的相似性大小（或距离远近），将相似性最大（或距离最近）的记录划分到k个类中，相同分类中记录间的距离要尽可能地小，而分类之间的距离要尽可能地大。BIC改进了常规的k-means聚类算法，在聚类过程中，同时计算分类质量（类内均差、类间均距 和），并求解最优聚类max{ }。

解决问题：将n条记录聚成k个分类。对n个样本集记录，指定分类个数k，为k个分类指定初始迭代记录为k个分类中心，通过计算其他记录对k个分类中心的距离，对不断变换分类、变换类中心，收敛都当分类不再变化时，计算结束。由此，将n个样本集记录分配到k个分类中，得到k个分类中心指标。

5、无限细分的模糊聚类Fuzzy Clustering 算法概述：在实际解决聚类问题时，很多数事物是“模糊”的，其特征属性A无法确进行量化，如：人的相貌、人与人之间的关系、人的性格、购买商品的意愿等，这就需要用模糊数学来进行相似性计算。模糊数学是伴随着上世纪五六十年代兴起的控制论、信息论、系统论（俗称“老三论”）而形成的一种决策方法，是美国加利福尼亚大学伯克利分校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个分类）。

解决问题：将n条记录聚成1-n个分类。模糊聚类Fuzzy Clustering算法完全基于数据自然状况进行聚类，可产生聚类的解集合 max{

(k=1,2，，,n)，因此，可以在解集合中求解最优聚类 }，这对观察分析样本集的数据性态非常有用，可供观察不同情况下的“聚类”状况。

6、SOM神经元网络聚类

算法概述：人类对事物的认知是一个不断积累的过程，通过对事物的观察，不断地认识和修正因果关系，最后逐渐稳定为认知规则。医学证明，人眼的视网膜、脊髓和海马中存一种侧抑制现象，即，当一个神经细胞兴奋后，会对其周围的神经细胞产生抑制作用。这种侧抑制使神经细胞之间呈现出竞争，开始时可能多个细胞同时兴奋，但一个兴奋程度最强的神经细胞对周围神经细胞的抑制作用也最强，其结果使其周围神经细胞兴奋程度减弱，从而该神经细胞是这次竞争的“胜者”，其它神经细胞在竞争中失败。1981年芬兰学者kohonen提出一个称为自组织特征映射（Self Organization Feature 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{具有代表性的词组

}，BIC为每个文档计算出一组最，同时，计算出

相互间内容接近度及接近序列。

BIC的Meaning挖掘与自动搜索不同于现有Baidu、Google人工输入关键词的搜索方式，现有搜索引擎不考虑语义和语境，只考虑词W与文档D的包含关系

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

在句子中语序关系的发生概率与马尔科夫链，因此，能够更好地确定搜索词的语义和语境，通过对文档间的相关性（接近度）进行聚类计算，可按Meaning“接近度”进行自动搜索而无需人工干预，并随文档内容的变化而自动跟踪Meaning变化，使搜索更加准确、更加自动化，让搜索“随用户的心而动”。

BIC可用于基于Meaning计算的搜索、舆情分析、特定情报分析、垂直搜索和相似内容推荐等文本挖掘。

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

8、文本模糊聚类计算

算法概述：基于模糊聚类算法，BIC首先计算将n个文本组成相似矩阵档对第j个文本文档的相似度），然后将相似矩阵似矩阵

变成模糊相似矩阵

（第i个文本文，通过求模糊相 的等价矩阵和截矩阵，将n个文本文档分成1-n个分类，同时，按相同分类中的}，不同文本分类间具有最大差异Max{

}，来求解文本具有最接近的内容相似度Min{ 按文本内容进行最优分类方案。

解决问题：在不确定将文本划分成几类的情况下，将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包含m个商品{BIC可计算得出任意两商品

}，n条记录组成二维表，构成 矩阵，组合的Confidence(A->B)=P(A | 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不存在关联；

（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算法。

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

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的非空真子集T1⊆T2。

所以，如果存在3个Item序列的高频Item组合，必然存在2序列的高频序列组合，如果存在4个Item的高频序列组合，必然存在3高频序列组合…。BIC就是通过最基本的2序列高频序列发现开始，逐步缩小记录集合，逐步发现所有任意数量Item组合的高频序列组合。因此，BIC的序列计算是一个*快速、交互式计算的Apriore算法。

解决问题：序列模式发现的目的是挖掘事务发生、发展的序列(Sequencing)模式，从样本集发现有较强“置信度”的序列规则。

13、PCA主成分分析

算法概述：假设一个事物由多种因素构成，设有n个样本，每个样本共有m个属性（指标、构成要素），构成一个n×m阶的成分数据矩阵，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，使得 可以证明，如果

，则矩阵D为矩阵A的相似矩阵，相似矩阵具有相同的特征

，变换过程中，让值和特征向量。Jacobi方法通过平一系列的面旋转变换来求非对角线上的元素逐步变小，对角线上的元素逐渐变大，最后将矩阵D中非对角线上的元素变成0（或趋近于0），对角线上的元素 li 是矩阵 A 的特征值，正交阵 U 的第 j 列是 A 的属于 li 的特征向量，以此求解矩阵A的特征值和特征向量。解决问题：

PCA可广泛用于事物要素（指标）分析。任何一个事物都是由多个指标组成，包括商业行为、医学诊断、药理分析、生产质量控制、生产工艺设计、经济分析，甚至是军事、外交事物等。人们需要掌握，构成事物的要素（指标）与事物的结果是什么关系？哪些是主要指标？哪些是次要指标？指标和指标之间存在什么关系？PCA通过一组样本集的计算分析，就可以精确回答这些问题。

第二篇：文本挖掘算法总结

文本数据挖掘算法应用小结 1、基于概率统计的贝叶斯分类   2、ID3 决策树分类  3、基于粗糙集理论Rough Set的确定型知识挖掘  4、基于k-means聚类  5、无限细分的模糊聚类Fuzzy Clustering   6、SOM神经元网络聚类  7、基于Meaning的文本相似度计算  8、文本模糊聚类计算  9、文本k-means聚类  10、文本分类  11、关联模式发现  12、序列模式发现  13、PCA主成分分析 1、基于概率统计的贝叶斯分类 算法概述：贝叶斯公式是由英国数学家(Thomas Bayes 1702-1763)创造，用来描述两个条件概率之间的关系，比如 P(A|B)为当“B”事件发生时“A”事件发生的概率，按照乘法法则：

P(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，则有：

贝叶斯分类的基本原理，就是利用贝叶斯条件概率公式，将事件X视为多个条件属性Cj各种取值的组合，当x事件发生时决策属性Di发生的条件概率。贝叶斯分类是一种概率型分类知识挖掘方法，不能百分之百地确定X事件发生时Di一定发生。

解决问题：预测所属分类的概率。通过已知n条样本集记录，计算各种条件属性组发生的概率，得出“贝叶斯分类”规则，给定一个未知“标签”记录，选择最大概率为其所属“分类”。

2、ID3 决策树分类 算法概述：ID3算法是J.Ross Quinlan在1975提出的分类算法，当时还没有“数据挖掘”的概念。该算法以信息论为基础，以信息熵和信息增益度来确定分枝生成决策树D-Tree。ID3算法以决策树D-Tree构建分类知识模型，D-Tree中最上面的节点为根节点Root，每个分支是一个新的决策节点，或者是树的叶子。每个决策节点代表一个问题或决策，每一个叶子节点代表一种可能的分类结果，沿决策树在每个节点都会遇到一个测试，对每个节点上问题的不同取值导致不同的分支，最后会到达一个叶子节点为确定所属分类。

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

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

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

IF <条件属性C成立> THEN <决策属性Di发生> 即，如果满条件C，则其所属分类为Di。IF中的条件C可以是单一条件，也可以是组合and（并且）组合条件。

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

“粗糙集”分类规则为“百分之百确定型”分类规则，这是对样本集的统计结果，如果出现非“样本集”中出现过的条件变量属性，将无法得出“粗糙集”，可转而使用概率型“贝叶斯分类”进行计算。

4、基于k-means聚类 算法概述：给定一个包括n条记录、每条记录有m个属性 的样本集，再给出分类数k，要求将样本集中的记录，按记录间的相似性大小（或距离远近），将相似性最大（或距离最近）的记录划分到k个类中，相同分类中记录间的距离要尽可能地小，而分类之间的距离要尽可能地大。

BIC改进了常规的k-means聚类算法，在聚类过程中，同时计算分类质量（类内均差、类间均距 和），并求解最优聚类max{ }。

解决问题：将n条记录聚成k个分类。对n个样本集记录，指定分类个数k，为k个分类指定初始迭代记录为k个分类中心，通过计算其他记录对k个分类中心的距离，对不断变换分类、变换类中心，收敛都当分类不再变化时，计算结束。由此，将n个样本集记录分配到k个分类中，得到k个分类中心指标。

5、无限细分的模糊聚类Fuzzy Clustering 算法概述：在实际解决聚类问题时，很多数事物是“模糊”的，其特征属性A无法确进行量化，如：人的相貌、人与人之间的关系、人的性格、购买商品的意愿等，这就需要用模糊数学来进行相似性计算。模糊数学是伴随着上世纪五六十年代兴起的控制论、信息论、系统论（俗称“老三论”）而形成的一种决策方法，是美国加利福尼亚大学伯克利分校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个分类）。

解决问题：将n条记录聚成1-n个分类。模糊聚类Fuzzy Clustering算法完全基于数据自然状况进行聚类，可产生聚类的解集合(k=1,2，，,n)，因此，可以在解集合中求解最优聚类max{  }，这对观察分析样本集的数据性态非常有用，可供观察不同情况下的“聚类”状况。

6、SOM神经元网络聚类 算法概述：人类对事物的认知是一个不断积累的过程，通过对事物的观察，不断地认识和修正因果关系，最后逐渐稳定为认知规则。医学证明，人眼的视网膜、脊髓和海马中存一种侧抑制现象，即，当一个神经细胞兴奋后，会对其周围的神经细胞产生抑制作用。这种侧抑制使神经细胞之间呈现出竞争，开始时可能多个细胞同时兴奋，但一个兴奋程度最强的神经细胞对周围神经细胞的抑制作用也最强，其结果使其周围神经细胞兴奋程度减弱，从而该神经细胞是这次竞争的“胜者”，其它神经细胞在竞争中失败。

1981年芬兰学者kohonen提出一个称为自组织特征映射（Self Organization Feature 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{ }，BIC为每个文档计算出一组最具有代表性的词组，同时，计算出相互间内容接近度及接近序列。

BIC的Meaning挖掘与自动搜索不同于现有Baidu、Google人工输入关键词的搜索方式，现有搜索引擎不考虑语义和语境，只考虑词W与文档D的包含关系 和词在文档内的频数TF，因此，关键词的搜索与文档内容无关。

例如：“姚明”是中国篮球的骄傲，但“姚明”还投身于公益事业，如果在搜索引擎中输入“姚明”，不见得搜索的文档内容只包含与篮球相关的内容，还可能包括公益及其他包含“姚明”的文档，可见，关键词搜索具有不确定性。如果在搜索引擎输入一组词 {“姚明”、“得分”、“篮板”}，搜出文档是篮球比赛内容的概率更大，显然，形成的交集缩小了搜索范围，但组词 {“姚明”、“得分”、“篮板”}是经过人思考给出的。

BIC通过计算得出文档代表词组，相当于人工输入 {“姚明”、“得分”、“篮板”}，同时计算词 在句子中语序关系的发生概率与马尔科夫链，因此，能够更好地确定搜索词的语义和语境，通过对文档间的相关性（接近度）进行聚类计算，可按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包含m个商品{}，n条记录组成二维表，构成 矩阵，BIC可计算得出任意两商品 组合的Confidence(A->B)=P(A | 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不存在关联；

（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算法。

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

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的非空真子集T1⊆T2。

所以，如果存在3个Item序列的高频Item组合，必然存在2序列的高频序列组合，如果存在4个Item的高频序列组合，必然存在3高频序列组合…。BIC就是通过最基本的2序列高频序列发现开始，逐步缩小记录集合，逐步发现所有任意数量Item组合的高频序列组合。因此，BIC的序列计算是一个*快速、交互式计算的Apriore算法。

解决问题：序列模式发现的目的是挖掘事务发生、发展的序列(Sequencing)模式，从样本集发现有较强“置信度”的序列规则。

13、PCA主成分分析 算法概述：假设一个事物由多种因素构成，设有n个样本，每个样本共有m个属性（指标、构成要素），构成一个n×m阶的成分数据矩阵，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，使得，可以证明，如果，则矩阵D为矩阵A的相似矩阵，相似矩阵具有相同的特征值和特征向量。Jacobi方法通过平一系列的面旋转变换来求，变换过程中，让非对角线上的元素逐步变小，对角线上的元素逐渐变大，最后将矩阵D中非对角线上的元素变成0（或趋近于0），对角线上的元素 li 是矩阵 A 的特征值，正交阵 U 的第 j 列是 A 的属于 li 的特征向量，以此求解矩阵A的特征值和特征向量。

解决问题：

PCA可广泛用于事物要素（指标）分析。任何一个事物都是由多个指标组成，包括商业行为、医学诊断、药理分析、生产质量控制、生产工艺设计、经济分析，甚至是军事、外交事物等。人们需要掌握，构成事物的要素（指标）与事物的结果是什么关系？哪些是主要指标？哪些是次要指标？指标和指标之间存在什么关系？PCA通过一组样本集的计算分析，就可以精确回答这些问题。

第三篇：18大经典数据挖掘算法小结

18大经典数据挖掘算法小结

2015-03-05 CSDN大数据 CSDN大数据

csdnbigdataCSDN分享Hadoop、Spark、NoSQL/NewSQL、HBase、Impala、内存计算、流计算、机器学习和智能算法等相关大数据观点，提供云计算和大数据技术、平台、实践和产业信息等服务。本文所有涉及到的数据挖掘代码的都放在了github上了。

地址链接: https://github.com/linyiqun/DataMiningAlgorithm 大概花了将近2个月的时间，自己把18大数据挖掘的经典算法进行了学习并且进行了代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的小小入门了吧。下面就做个小小的总结，后面都是我自己相应算法的博文链接，希望能够帮助大家学习。

1.C4.5算法。C4.5算法与ID3算法一样，都是数学分类算法，C4.5算法是ID3算法的一个改进。ID3算法采用信息增益进行决策判断，而C4.5采用的是增益率。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42395865 2.CART算法。CART算法的全称是分类回归树算法，他是一个二元分类，采用的是类似于熵的基尼指数作为分类决策，形成决策树后之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法，详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42558235 3.KNN(K最近邻)算法。给定一些已经训练好的数据，输入一个新的测试数据点，计算包含于此测试数据点的最近的点的分类情况，哪个分类的类型占多数，则此测试点的分类与此相同，所以在这里,有的时候可以复制不同的分类点不同的权重。近的点的权重大点，远的点自然就小点。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42613011 4.Naive Bayes(朴素贝叶斯)算法。朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法，用到了一个比较重要的贝叶斯定理，用一句简单的话概括就是条件概率的相互转换推导。详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42680161 5.SVM(支持向量机)算法。支持向量机算法是一种对线性和非线性数据进行分类的方法，非线性数据进行分类的时候可以通过核函数转为线性的情况再处理。其中的一个关键的步骤是搜索最大边缘超平面。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42780439 6.EM(期望最大化)算法。期望最大化算法，可以拆分为2个算法，1个E-Step期望化步骤,和1个M-Step最大化步骤。他是一种算法框架，在每次计算结果之后，逼近统计模型参数的最大似然或最大后验估计。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42921789 7.Apriori算法。Apriori算法是关联规则挖掘算法，通过连接和剪枝运算挖掘出频繁项集，然后根据频繁项集得到关联规则，关联规则的导出需要满足最小置信度的要求。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43059211 8.FP-Tree(频繁模式树)算法。这个算法也有被称为FP-growth算法，这个算法克服了Apriori算法的产生过多侯选集的缺点，通过递归的产生频度模式树，然后对树进行挖掘，后面的过程与Apriori算法一致。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43234309 9.PageRank(网页重要性/排名)算法。PageRank算法最早产生于Google,核心思想是通过网页的入链数作为一个网页好快的判定标准，如果1个网页内部包含了多个指向外部的链接，则PR值将会被均分，PageRank算法也会遭到Link Span攻击。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43311943 10.HITS算法。HITS算法是另外一个链接算法，部分原理与PageRank算法是比较相似的，HITS算法引入了权威值和中心值的概念，HITS算法是受用户查询条件影响的，他一般用于小规模的数据链接分析，也更容易遭受到攻击。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43311943 11.K-Means(K均值)算法。K-Means算法是聚类算法，k在在这里指的是分类的类型数，所以在开始设定的时候非常关键，算法的原理是首先假定k个分类点，然后根据欧式距离计算分类，然后去同分类的均值作为新的聚簇中心，循环操作直到收敛。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43373159 12.BIRCH算法。BIRCH算法利用构建CF聚类特征树作为算法的核心，通过树的形式，BIRCH算法扫描数据库，在内存中建立一棵初始的CF-树，可以看做数据的多层压缩。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43532111 13.AdaBoost算法。AdaBoost算法是一种提升算法，通过对数据的多次训练得到多个互补的分类器，然后组合多个分类器，构成一个更加准确的分类器。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43635115 14.GSP算法。GSP算法是序列模式挖掘算法。GSP算法也是Apriori类算法，在算法的过程中也会进行连接和剪枝操作，不过在剪枝判断的时候还加上了一些时间上的约束等条件。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43699083 15.PreFixSpan算法。PreFixSpan算法是另一个序列模式挖掘算法，在算法的过程中不会产生候选集，给定初始前缀模式，不断的通过后缀模式中的元素转到前缀模式中，而不断的递归挖掘下去。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43766253 16.CBA(基于关联规则分类)算法。CBA算法是一种集成挖掘算法，因为他是建立在关联规则挖掘算法之上的，在已有的关联规则理论前提下，做分类判断，只是在算法的开始时对数据做处理，变成类似于事务的形式。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43818787 17.RoughSets(粗糙集)算法。粗糙集理论是一个比较新颖的数据挖掘思想。这里使用的是用粗糙集进行属性约简的算法，通过上下近似集的判断删除无效的属性，进行规制的输出。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43876001 18.gSpan算法。gSpan算法属于图挖掘算法领域。，主要用于频繁子图的挖掘，相较于其他的图算法，子图挖掘算法是他们的一个前提或基础算法。gSpan算法用到了DFS编码，和Edge五元组，最右路径子图扩展等概念，算法比较的抽象和复杂。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43924273

第四篇：算法总结

算法分析与设计总结报告

71110415 钱玉明

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。

下面我将谈谈我对这门课程的心得与体会。

一、数学是算法的基础

经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。

①主定理

本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。

②随机算法中的许多定理的运用

在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。

这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。

二、算法的核心是思想

我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。

①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。

动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。

贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。

周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。

回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。

分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。

②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。

这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。

三、算法与应用紧密相关

我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。

这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。

四、对计算模型和NP问题的理解

由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。

首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。

NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。

最后谈谈对这门课程的建议

①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。

②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。

③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。

第五篇：算法总结

算法分块总结

为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。

图论模型的应用

分层图思想的应用：

用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。

这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：

最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：

容量有上下界的最大流的应用：

欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：

求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：

抽象成数学模型就是：

设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k

首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。

假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树；

2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。

加边和去边过程，利用动态规划优化特别值得注意。

次小生成树：

加边和去边很值得注意。

每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法：

首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

最短路径的应用：

Dijkstra 算法应用： Folyed 算法应用：

Bellman-Ford 算法的应用：

差分约束系统的应用：

搜索算法

搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用：

IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索：

可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。

动态规划

动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。

状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP：

状态划分比较困难的题目： 树形DP：

四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2)

高档数据结构的应用

并查集的应用：

巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用：

总结用线段树解题的方法

根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等

树的每个节点根据题目所需，设置变量记录要求的值

用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。

在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。

Trie的应用：；

Trie图的应用探索： 后缀数组的应用研究：

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。

树状数组的应用探索：；

计算几何

掌握基本算法的实现。凸包的应用：；

半平面交算法的应用：；

几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：；

转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：；

经典算法：找平面上的最近点对。

贪心

矩形切割

二分思想应用

活用经典算法

利用归并排序算法思想求数列的逆序对数：

利用快速排序算法思想，查询N个数中的第K小数：

博弈问题

博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。

第一类：推结论。典型题目： 第二类：递推。典型题目：

比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质：

1． 所有的结束位置都是P位置。

2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。

这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。

与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为：

1． 将所有的结束位置标为P位置。

2． 将所有能一步到达P位置的点标为N位置。

3． 找出所有只能到达N位置的点，将它们标为P位置。

4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。

关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为

g(x)min{n0,ng(y)对于所有yF(x)}

1． 对于所有的结束位置x，g(x)= 0。

2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。

3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。

定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四类：极大极小法。

典型题目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩阵妙用

矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目：

数学模型举例

向量思想的应用：

UVA 10089：注意降维和向量的规范化 ；

利用复数思想进行向量旋转。

UVA 10253：

递推

数代集合

数代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。

组合数学

Polya定理则是解决同构染色计数问题的有力工具。

补集转化思想

ZOJ 单色三角形：

字符串相关

扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀；

填充问题

高精度运算

三维空间问题专题

无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。

其它问题的心得

解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广