SAT布尔可满足性算法步骤

⑴ 数据挖掘十大算法-

整理里一晚上的数据挖掘算法，其中主要引自wiki和一些论坛。发布到上作为知识共享，但是发现Latex的公式转码到网页的时候出现了丢失，暂时没找到解决方法，有空再回来填坑了。

——编者按

一、 C4.5

C4.5算法是由Ross Quinlan开发的用于产生决策树的算法[1]，该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法主要应用于统计分类中，主要是通过分析数据的信息熵建立和修剪决策树。

1.1 决策树的建立规则

在树的每个节点处，C4.5选择最有效地方式对样本集进行分裂，分裂规则是分析所有属性的归一化的信息增益率，选择其中增益率最高的属性作为分裂依据，然后在各个分裂出的子集上进行递归操作。

依据属性A对数据集D进行分类的信息熵可以定义如下：

划分前后的信息增益可以表示为：

那么，归一化的信息增益率可以表示为：

1.2 决策树的修剪方法

C4.5采用的剪枝方法是悲观剪枝法(Pessimistic Error Pruning，PEP)，根据样本集计算子树与叶子的经验错误率，在满足替换标准时，使用叶子节点替换子树。

不妨用K表示训练数据集D中分类到某一个叶子节点的样本数，其中其中错误分类的个数为J，由于用估计该节点的样本错误率存在一定的样本误差，因此用表示修正后的样本错误率。那么，对于决策树的一个子树S而言，设其叶子数目为L(S)，则子树S的错误分类数为：

设数据集的样本总数为Num，则标准错误可以表示为：

那么，用表示新叶子的错误分类数，则选择使用新叶子节点替换子树S的判据可以表示为：

二、KNN

最近邻域算法(k-nearest neighbor classification, KNN)[2]是一种用于分类和回归的非参数统计方法。KNN算法采用向量空间模型来分类，主要思路是相同类别的案例彼此之间的相似度高，从而可以借由计算未知样本与已知类别案例之间的相似度，来实现分类目标。KNN是一种基于局部近似和的实例的学习方法，是目前最简单的机器学习算法之一。

在分类问题中，KNN的输出是一个分类族群，它的对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。在回归问题中，KNN的输出是其周围k个邻居的平均值。无论是分类还是回归，衡量邻居的权重都非常重要，目标是要使较近邻居的权重比较远邻居的权重大，例如，一种常见的加权方案是给每个邻居权重赋值为1/d，其中d是到邻居的距离。这也就自然地导致了KNN算法对于数据的局部结构过于敏感。

三、Naive Bayes

在机器学习的众多分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive Bayesian Model，NBC)[3]。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。

在假设各个属性相互独立的条件下，NBC模型的分类公式可以简单地表示为：

但是实际上问题模型的属性之间往往是非独立的，这给NBC模型的分类准确度带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型；而在属性相关性较小时，NBC模型的性能最为良好。

四、CART

CART算法(Classification And Regression Tree)[4]是一种二分递归的决策树，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤：将样本递归划分进行建树过程；用验证数据进行剪枝。

五、K-means

k-平均算法(k-means clustering)[5]是源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-means的聚类目标是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类。

5.1 k-means的初始化方法

通常使用的初始化方法有Forgy和随机划分(Random Partition)方法。Forgy方法随机地从数据集中选择k个观测作为初始的均值点；而随机划分方法则随机地为每一观测指定聚类，然后执行“更新”步骤,即计算随机分配的各聚类的图心，作为初始的均值点。Forgy方法易于使得初始均值点散开，随机划分方法则把均值点都放到靠近数据集中心的地方；随机划分方法一般更适用于k-调和均值和模糊k-均值算法。对于期望-最大化(EM)算法和标准k-means算法，Forgy方法作为初始化方法的表现会更好一些。

5.2 k-means的标准算法

k-means的标准算法主要包括分配(Assignment)和更新(Update)，在初始化得出k个均值点后，算法将会在这两个步骤中交替执行。

分配(Assignment)：将每个观测分配到聚类中，使得组内平方和达到最小。

更新(Update)：对于上一步得到的每一个聚类，以聚类中观测值的图心，作为新的均值点。

六、Apriori

Apriori算法[6]是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。Apriori采用自底向上的处理方法，每次只扩展一个对象加入候选集，并且使用数据集对候选集进行检验，当不再产生匹配条件的扩展对象时，算法终止。

Apriori的缺点在于生成候选集的过程中，算法总是尝试扫描整个数据集并尽可能多地添加扩展对象，导致计算效率较低；其本质上采用的是宽度优先的遍历方式，理论上需要遍历次才可以确定任意的最大子集S。

七、SVM

支持向量机(Support Vector Machine, SVM)[7]是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

除了进行线性分类之外，SVM还可以使用所谓的核技巧有效地进行非线性分类，将其输入隐式映射到高维特征空间中，即支持向量机在高维或无限维空间中构造超平面或超平面集合，用于分类、回归或其他任务。直观来说，分类边界距离最近的训练数据点越远越好，因为这样可以缩小分类器的泛化误差。

八、EM

最大期望算法(Expectation–Maximization Algorithm, EM)[7]是从概率模型中寻找参数最大似然估计的一种算法。其中概率模型依赖于无法观测的隐性变量。最大期望算法经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望(E)，利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化(M)，最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

九、PageRank

PageRank算法设计初衷是根据网站的外部链接和内部链接的数量和质量对网站的价值进行衡量。PageRank将每个到网页的链接作为对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。

算法假设上网者将会不断点网页上的链接，当遇到了一个没有任何链接出页面的网页，这时候上网者会随机转到另外的网页开始浏览。设置在任意时刻，用户到达某页面后并继续向后浏览的概率，该数值是根据上网者使用浏览器书签的平均频率估算而得。PageRank值可以表示为：

其中，是被研究的页面集合，N表示页面总数，是链接入页面的集合，是从页面链接处的集合。

PageRank算法的主要缺点是的主要缺点是旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多外链，除非它是某个站点的子站点。

十、AdaBoost

AdaBoost方法[10]是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器Ck[，并且如此迭代地进行下去。

AdaBoost方法的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，AdaBoost方法相对于大多数其它学习算法而言，不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。

引用

[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.

[2] Altman, N. S. An introction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879

[3] Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6

[4] decisiontrees.net Interactive Tutorial

[5] Hamerly, G. and Elkan, C. Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 2002

[6] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

[7] Cortes, C.; Vapnik, V. Support-vector networks. Machine Learning. 1995, 20 (3): 273–297. doi:10.1007/BF00994018

[8] Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39 (1):1–38, 1977

[9] Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]

[10] Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855

⑵ 计算复杂性理论的理论与实践

计算复杂性的初衷是理解不同算法问题的难度，特别的是一些重要算法问题的困难性。为了确切的描述一个问题的困难性，计算复杂性的第一步抽象是认为多项式时间是有效的，非多项式时间是困难的。这基于指数函数增长速度的“违反直觉”的特性：如果一个算法的时间复杂性为2，取输入的规模是100，在运算速度是10每秒（关于CPU速度，参见Instructions per second，其中报告截止2009年，主流个人电脑的运算速度可以看作是每秒
）
的情况下，该程序将会运行年，几乎是宇宙年龄。这为多项式时间被看作是有效时间提供了直观上的证据。
然而多项式的指数很大的时候，算法在实践中也不能看作是有效的。如n的多项式算法，取问题规模大小为1000，那么几乎就是2的大小。另一方面，即便一个问题没有多项式算法，它可能会有近似比很好的近似算法（参见近似算法），或有很好的启发式算法（heuristics）。启发式算法的特点是在理论上没有精确的行为的分析，或者可以表明存在很坏的输入，在这些输入上运行很慢。然而在大多数时候，它都能快速解决问题。计算复杂性中对应的理论分析是平均复杂性理论（average-case complexity theory）和光滑分析（smooth analysis）。实际中的例子包括en:Presburger arithmetic、布尔可满足性问题（参见SAT solver）和背包问题。

⑶ 算法基础

谨以此文，感谢我在这个学校最喜欢的两个老师之一——肖my老师。本文基本为老师上课说讲授内容加上一部分自己的感悟拼凑而来，写作文本的目的是为自己的算法课程留下一点点东西，站在老师肩膀上形成粗糙的框架，方便以后的复习以及深入。文笔有限，其中包含的错误还请多多包容，不吝赐教。

to do list：

时间复杂度中递归树法；动规，分治新的感悟；

点覆盖：一组点的集合，使得图中所有边都至少与该集合中一个点相连。

支配集：一组点的集合，使得图中所有的点要么属于该集合，要么与该集合相连。

最大团：在一个无向图中找出点数最多的完全图。

独立集：一组点的集合，集合中的顶点两两不相邻。（团转过来）

SAT问题：也称布尔可满足性问题。给一组变

其中Ci被称为句子。

点覆盖<->独立集<->最大团

最小割：割是一组边集。如s-t割就是如果去掉这些边，将把原图划分为两个点集，其中一个点集包含s，一个点集包含t。（两个是指不相连，而不是代表不存在边相连，如反向边）

decision problem: 是否存在。

search problem:找到一个解。

（这个还能扩展，比如decision problem在多项式时间内解决，所以他是P问题吗）

渐进符号：

注意以上三种都是紧的，对应的两个小写的符号是不紧的，即如下图所示：

概念：算法的时间复杂度是一个函数，用于定性描述算法的运行时间。注意，这个一个代表算法输入字符串长度的函数。

[注]输入字符串长度是一个比较关键的理解，比如在背包问题中，其时间复杂度为O(nW)，因为W不定，所以只能是一个伪多项式时间。

比较：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n

大致：常数<对数<幂函数<指数函数<阶乘

对于指数是n相关的进行比较，优先比较指数，再比较底数。

记住一个特例：n ^(logn)<n!<n n

计算：

一般来说，计算采用主方法和递归树法，其中递归树技巧性比较强，主方法其实也是递归树推导归纳而来，且主方法能得到一个比较紧的结果。

主方法：

f(n) = af(n-b)+g(n) =>O( a^(n/b) *g(n) )

P：decision problems有一个多项式算法。

NP（nondeterministic polynomial-time）：decision problems能够在多项式时间内验证。

NPC：NP完全问题，首先这个问题是NP的，其次，其他所有问题都可以多项式时间内归约到它。

NPH：如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。

因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。

一些NP问题能在多项式时间内解决，因为 P∈NP

NP难类型问题的证明：

先选好一个已知NP难的问题，然后将已知NP难问题多项式归约到要证明的问题上。先给出这个归约，然后再证明这个归约的正确性。

NPC类型问题的证明：

证明一个问题Y是NPC问题，先说明Y是NP的，然后找到一个NPC问题X，将这个问题X归约到问题Y上，即证明完成。

常见的NPC问题（重要，规约的时候有用！）：

packing problems: set-packing，独立集

覆盖问题：集合覆盖问题，顶点覆盖问题

严格满足问题(constraint satisfaction problems)：SAT，3SAT

序列问题：哈密尔顿回路，旅行商问题

划分问题：3D-matching, 3着色问题

数字问题：子集合问题（子集元素之和为t），背包问题

其他：分团问题（是否存在一个规模为k的团）

规约的概念与理解

规约：意味着对问题进行转换，例如将一个未知的问题转换成我们能够解决的问题，转换的过程可能涉及到对问题的输入输出的转换。

自归约：search problem <=p decision problem

归约：A归约到B，也就是说，我们对A套一个函数f，在f函数的作用下形成一个新的问题，对这个问题运用B的黑盒解法，能够解决问题A。

(B <=p A)一般说来，B问题如果可以归约到A问题，也就是说，一个解决A问题的算法可以被用做子函数（子程序）来解决B问题，也就是说，求解B问题不会比求解A问题更困难。因此，如果B问题是困难的，那么A问题也就是困难的，因为不存在求解A问题的高效算法。(最后一句不懂)

我简单说一下我理解的规约，以X规约到Y为准，大概分成两个方面：

注：在 三 的一些实例中细品。

概念：在对问题求解时，总是做出在当前看来是最好的选择。

贪心的证明：先假设贪心算法得到的解不是最优解，假设S1是贪心算法得到的解，而S2是所有最优解中和S1具有最多相同元素的解，然后比较S1和S2，观察S1和S2中第一个（最前面一个）不一样的元素，然后在贪心解S2中将不一样的元素换成S1中的那个元素得到另一个最优解S3，这样S3和S1比S2和S1有更多相同元素，和假设S2是与S1有最多相同元素的最优解矛盾，这样来推导S1是最优解。

我的理解：假设这个不是最优的，但是一定存在一个最优的解在某一个位置之前和我当前解结构是一样的，那么在这个位置，选最优解也可以选当前解，不影响最终答案。

[注]概念很简单，但是实际操作的时候，贪心的角度很重要，同样的贪心，方向对了，算法就是对的。

例子：

给你一系列活动，每个活动有一个起始时间和一个结束时间，要求在活动不冲突的情况下找到一种有最多活动的安排。

对于这个问题，我们有一下几种贪心的角度：

①将任务按照 开始时间 升序排列。

②将任务按照 结束时间 升序排列。

③将任务按照 任务时长 升序排列。

④对于每一个任务，都记录与其他任务冲突的数量，按照 冲突数量 的升序排列。

其中1，3，4都是不可以的。

任务结束时间的贪心证明（反证法）：

假设贪心不是最最优的，那我们在最优解中找一个与当前解有最相似的解。

由图可以知道，贪心贪的就是最早结束，所以如果不是最优，那么最优的结束时间一定晚于贪心的结束时间。

由上图就可以证明。

最大流通常与最小割相联系。

f 为任意一个流，cap为容量，对于任意的s-t割出来的点集（A，B），v( f ) <= cap(A, B)。

当流增加到与割的容量相等时候，就不可能再有增长空间了，称为最大流。

对于割的容量来说，不同的割法会有不同流量，有些割法永远不会有流达到，比如部分A = {s}, B = {V - s}，这种把源点割出来的割法。

综上，通过这种感性的认识，如果能找到一个最小的割，那么这个割就一定是最大能跑到的流（如果流能更高的话在这个割上就会超过容量，反证。）

上图为一条增广路，一条增广路即为一条s-t的路径，在路径上仍有流可以跑，其曾广的流就是该条路径上最小的剩余容量。（相当于每找一条增广路，就至少有一条边达到满流。）

直到在图中找不到增广路，此时已经达到了最大流。

找ST集合：把满流的边去掉，从S出发走到能到的点，遍历的点就是S集合；剩下的点就属于T集合。注意，如果找到了在找S集合的时候找到了T点，说明还可以继续找增广路。

[补]有一个很有趣的延伸，如多源点多终点问题。问：如果我有两个源点s1，s2，两个终点t1，t2，我想求一组流，使得s1-t1，s2-t2的流达到最大，是否可以加一个源点S，S与s1，s2相连，边流无限大；加一个终点T，T与t1，t2相连，边流无限大，然后这组ST的最大流即可。——答案是No，无法保证是s1-t1，s2-t2，有可能交错。

例子讲的感觉不是特别好，对理解感觉起不到很大作用，希望以后有新的想法后进行补充。

规约是一个重要的概念和思想。

一个图的 最大独立集 与 最小点覆盖 是不相交的两个点集，它们的并就是整个点集。

个人理解：独立集和点覆盖都是从点的角度进行划分的，如果我们从边的角度来看，①一个最小的点覆盖即为我集合中的每一个点都尽可能与更多的边相连，②同时，一条边的两个端点中，只能有一个端点在最小点覆盖中[下注]

[注]我们假设有一条边两个端点（u，v）都在点覆盖之中，首先显然u，v都不是端点，因为假设u是端点的话只需要选择v即可；

给一个集合S和一堆S的子集S1，S2，...，Sm，问是否存在存在k个子集，使它们的并集为S。

构造：

集合为点，集合中的元素为边，有相同元素的边相连。（注意如果某一元素只在一个子集中出现，应该怎么处理呢！）

规约：在构造的图中找最小的点覆盖，选中的点能覆盖所有的边即为对应集合的并集能包含所有的元素。所以就完成了集合覆盖到点覆盖的规约。

构造：每个句子构造一个三角形，把对应变量但是相反取值的点相连。

规约：3SAT的有一个特点就是，每一个句子中至少有一个为真即可，每个句子都必须是真。将相同变量相反取值相连的目的就是，在最大独立集中，比如选择x为真，则剩下所有句子中x-ba一定不会被选中，同时由独立集和构造出来三角形的性质可以知道，每一个句子，有且仅有一个会被选中（为真）。如上图，x1-ba为真，x2-ba和x3任选一个为真即可满足。

search problem <=p decision version

比如：如果能在多项式时间内找到一个哈密尔顿圈，那么就能在多项式时间内找到一个哈密尔顿圈（删边）

在此再谈P和NP：

我们知道有些问题是可以从搜索问题规约到判断问题的，也就是所该问题如果能在多项式内判断，那么久能在多项式中搜索到，那么我们只需要说，这个判断问题能在多项式时间内求解，就叫做P问题，也就是上图红字的意思；那NP问题呢，必须要给出一个解的实例，判断的是这个实例是否满足求解问题，这个才是上图中的红字。比如，我如果能在多项式时间内判断哈密尔顿圈是否（Yes/No）存在，那这个就是ploy-time algorithm，如果我给出了一系列点，能过多项式时间内判断这些点能否构成哈密尔顿圈，那这个就是poly-time certifier。

构造：把一个点拆分成三个点。

构造：（下面两个图要连在一起看）

从行的角度看，一行代表一个变量；从列的角度来看，每三列代表一个句子。两边中一边是两个点，一边是一个点，所以有k个句子的话，每一行有3k+3个节点。从哈密尔顿圈的答案转到3SAT的答案看这个圈在每一行是从左到右还是从右到左。

子集和问题：给一个集合S，问是否能在集合中选取元素，使得总和为W。

构造：如下图，按照前六行和前三列进行分割，可以分成4部分，其中1,3,4部分是固定的，即在第一部分，变量v列和 变量为v（包括变量及取反）的行对应的格子为0，其余为0；第三部分全为0；第四部分按照12依次写下来。第二部分，如果Ci句子中有变量v，则记为1，因为一个句子只有三个变量，可以简单通过第二部分每一列和为3进行判定。此时集合已经构造出来，W为111444，与上面的规约相似，可以通过3SAT的简单性质进行感性的认知。

近似的想法很简单，要解决一个问题，我们希望能够做到①求解结果是最优的 ②在多项式时间内解决 ③对于任意的实例都能够通过该算法解决。现在对于部分问题，无法完全满足以上要求，所以就牺牲了①，但是我们希望结果不是盲目的，所以就引入了近似的概念。

近似算法。比如2-近似，认为W为近似解，W 为最优解，在求最小值的情况下W<=2W ；在求最大值的情况下，W>=1/2W*

给m个机器和n个任务，每个任务有一个ti的执行时间，我们认为完成最后一个任务所需的时间为负载时间，希望能够让这个负载时间最短。

第一种：将任务依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

证明：

引理1.最短时间安排是大于等于任务中时间最长的任务，L* >= max tj

我们在考虑放入最后一个任务前，根据我们放置的规则，该机器是耗时最短，也就是说，该机器此时的用时是低于除掉最后一个任务后的平均时长，更低于所有任务的平均时长（引理2）；再根据引理1，最后一个任务应该是小于最优解的。

补充：

在这里，我还想讨论一下这个近似算法的中等于符号，先上结论：等号不一定能够找到一个实例，但是可以构造出一种结构，通过取极限求得，我们认为这样 也算是紧的。

构造实例：有m个机器，其中m(m-1)个任务的用时为1，1个任务的用时为m。肯定有一种任务集合，可以按照以下方式进行安排，此时的贪心解为19。

此时最佳的解为10，如下图：

通过推广可以知道此时的比为（2m-1）/m，当m取极限，能够达到2倍。

第二种：将任务从大到小排序，然后依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

引理3：如果有大于m个任务，那么L*>=2t(m-1)。证明：t(m+1)是目前最短的任务，且目前所有机器上都有任务了，所以该任务加入时最优的情况不过是加入设备的原有任务刚好和t(m+1)相等，即等号。

（2近似）在n个点中，选取k个中心点，使得这些中心点能够以半径R的圆包含所有的点，让其中最大的半径最小，如下图所示：

基础：距离需要满足的三个定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)

r(C)为C集合中所有点的最大覆盖半径。（需要求min r(C)）

算法：在点集中任选一个作为中心点，然后重复以下步骤k-1次:选取距离已选点集中最远的点，加入点集。

证明：先假设r(C )< 1/2 * r(C)以选好的点画半径为1/2 * r(C)的圆，显然可知[注]，这个圆里有且仅有一个r(C )中的点。那么根据在下图中，根据三角不等式可以得出：

[注]在每个点上r(c )一定会包含到c点，而r(C )<1/2 * r(C)，相当于大圆套小圆，所以c*一定在c的圆中。

（2近似）问题还是很好理解的，在点上加权值，要找一个点覆盖，使得权值最小。如下图左边就是一个带权的最小点覆盖。

算法： 任选一条边(i, j)加上代价，这个代价从零开始，且这个代价的最大值低于i和j节点的权值。显然，这个边权值的最大值取决于两个端点权值的最小值，我们认为当边权值与点权值相等时，对应的那个点是紧的。把所有紧的点找出来即为点覆盖。

流程：

证明：

引理：边权之和小于等于点覆盖的点权之和。这主要是由于涉及到一条边上两个点都被选（紧的）的情况，感性认知可以看上图，缩放证明如下：

w(S)是等于所选的节点的权值之和的，等于所选节点节点所对应的边权之和，可以把它放大到所有节点对应边权之和，这样因为一条边(u, v)在u上算过一次后还要在v上算一次，所以等于边权和的两倍。再由上面引理可得。

主要为了线性规划和整数规划。

（2近似）没啥好说的，只需要把方程构造出来就行了。

由于求解出来结果不一定是整数，所以我们认为某一点的值大于1/2，就选入点集。

证明：

因为xi+xj >=1,且都是正数，那必至少一个点是大于1/2的（反证，两个都小于1/2则和小于1）。

给你n个物品和一个背包，每个物品有一个价值v和一个大小w，背包的容量是W，要求让背包装下尽可能大价值。

背包的时间复杂度：O(nW)

注意其中n表示物品的个数，无论是1个还是999个，他都是多项式的，这个很好理解。但是W就不一样了，这是一个数字。我理解的是这个数字会很奇特，比如1.00001，比如99999，这些有可能看起来不大但是实际在处理的时候很难处理的数字，统一的来说，如果我们把这些数字放在电脑上，都会以二进制的方式存储起来，有些数字用十进制表示很小，但是放在二进制上面就会很大，由W导致不能在多项式时间内解决（找不到一个范围/上界来框它）。

算法： 为了处理这个问题，我们改动了dp的状态转移方程，要让这个转移方程和W无关[注]。

此时还不是多项式的，然后我们再对value进行约。[注]

[注]这两步中，我们把w改成v，并对v进行近似处理。OPT的含义变成了，在面对是否选择第i个物品时，要想让价值达到当前值，最少的weight。理由是更改后的误差是可以忍受的：对v进行近似，结果只会出现最大价值的上下误差，如果对w进行近似，则有可能出现该物品不能放入背包中，导致整个物品直接放弃的情况。

⑷ 关联规则挖掘算法的介绍

学号：17020110019    姓名：高少魁

【嵌牛导读】关联规则挖掘算法是数据挖掘中的一种常用算法，用于发现隐藏在大型数据集中令人感兴趣的频繁出现的模式、关联和相关性。这里将对该算法进行简单的介绍，之后通过Apriori算法作为实例演示算法执行结果。

【嵌牛鼻子】数据挖掘    关联规则挖掘    python

【嵌牛正文】

一、算法原理

1、基本概念

关联规则用于发现隐藏在大型数据集中令人感兴趣的频繁出现的模式、关联和相关性。 而 Apriori算法则是经典的挖掘频繁项集的关联规则算法，它通过层层迭代来寻找频繁项集，最后输出关联规则：首先扫描数据集，得到 1-频繁项集，记为 L1，通过合并 L1得到 2-频繁项集 L2，再通过 L2找到 L3，如此层层迭代，直到找不到频繁项集为止。

在Apriori算法中，定义了如下几个概念：

⚫ 项与项集 ：设 I={i1,i2,…,im}是由 m个不同项构成的集合，其中的每个 ik(k=1,2,…,m)被称为一个项 (Item)，项的集合 I被称为项集和，即项集。在实验中，每一条购物记录可以被看做 一个项集，用户购买的某个商品即为一个项。

⚫ 事务与事务集：神乎事务 T是项集 I的一个子集，而事务的全体被称为事务集。

⚫ 关联规则：形如 A=>B的表达式，其中， A和 B都属于项集 I，且 A与 B不相交。

⚫ 支持度：定义如下 support(A=>B) = P(A B)，即 A和 B所含的项在事务集中同时出现的概率。

⚫ 置信度：定义如下 confidence(A⇒B)=support(A⇒B)/support(A)=P(A B)/P(A)=P(B|A)，即如果事务包含 A，则事务中同时出现 B的概率。

⚫ 频繁项集：如果项集 I的支持度满足事先定义好的最小支持度阈慧液值（即 I的出现频度大于相应的最小出现频度阈值），则 I是频繁项集。

⚫ 强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。

根据以上概念，要实现关联规则的挖掘，首先要找到所有的频繁项集，之后找出强关联规则（即通过多次扫描数据集，找出频繁集，然后产生关联规则）。

2、挖掘频繁项集

在该步骤中有两个较为重要的部分 ：连接和修剪。连接步骤即使用k-1频繁项集，通过连接得到 k-候选项集，并且只有相差一个项的项集才能进行连接，如 {A,B}和 {B,C}连接成为 {A,B,C}。修剪步骤基于一个性质：一个 k-项集，如果它的一个 k-1项集（子集）不是频繁的，那么它本身也不可能是频繁的。 因此可以基于这个性质，通过判断先验性质来对候选集进行修剪。

3、产生关联规则

经过连接和修剪之后，即找到了所有的频繁项集，此时可以在此基础上产生关联规则，步骤如下

（1）对于每个频繁项集 l，产生 l的所有非空子集（这些非空子集一定是频繁项集）；

（2）对于 l的每一个非空子集 x，计算 confidence(x => (l-x))，如果 confidence(x => (l-x)) confmin，那么规则 x => (l-x)”成立。

二、算法设计

1、数据集

通过语句 import xlrd导入相关的库来进行数据的读取 。数据内容为十条购物记录 ，每条购物记录有若干个商品，表示某个顾客的购买记录 ，如图

对于数据加载部分 使用了 xlrd库中的函数 open_workbook来 打开一个表格文件，使用sheet_by_index函数得到一个工作表， row_values函数即可读取表格中的内容。由于每个购物记录的商品数不一定相同，导致读取的内容含有空格 (’ ’)，因此对数据进行删减以得到紧凑的数据 ，最终读取数据的结果以列表的游碧悉形式返回。

2、连接

对于连接部分，主要目标是根据已有的k-1频繁项集生成 k-候选频繁项集。算法步骤为：首先将项集中的项按照字典顺序排序，之后将 k-1项集中两个项作比较，如果两个项集中前 k-2个项是相同的，则可以通过或运算（|）将它们连接起来。

3、修剪

修剪操作主要使用一个判断函数，通过传入连接操作后的项集和之前的k-1频繁项集，对新的项集中的每一个项的补集进行判断，如果该补集不是 k-1频繁项集的子集，则证明新的项集不满足先验性质，即一个频繁项集的所有非空子集一定是频繁的 ，否则就满足先验形式。返回布尔类型的参数来供调用它的函数作判断。

经过连接和修剪步骤之后，项基要成为频繁项集还必须满足最小支持度的条件，笔者设计了generateFrequentItems函数来对连接、修剪后产生的 k-候选项集进行判断，通过遍历数据集，计算其支持度，满足最小支持度的项集即是 一个频繁项集，可将其返回。

以上，经过不断的遍历、连接、修剪、删除，可将得到的所有结果以列表形式返回。笔者还设计了字典类型的变量 support_data，以得到某个频繁项集及其支持度 。

4、挖掘关联规则

generateRules函数用来挖掘关联规则，通过传入 最小置信度、 频繁项集及其 支持度来生成规则 。根据定理：对于频繁项集 l的每一个非空子集 x，计算 confidence(x => (l-x))，如果 confidence(x => (l-x)) confmin，那么规则 x => (l-x)”成立，因此，该函数重点在扫描频繁项集，得到每一个子集，并计算置信度，当置信度满足条件（即大于等于最小置信度）时，生成一条规则。在函数中，使用了元组来表示一条规则，元组中包含 x、 l-x以及其置信度 ，最后返回生成的所有规则的列表。

三、算法执行结果

设置最大频繁项集数k为 3，最小支持度为 0.2，最小置信度为 0.8 使用 pycharm运行程序 ，得到以下结果：

由图中结果可以看出，对于频繁 1-项集，有五个满足的项集，频繁 2-项集有 6个，频繁 3-项集有 2个，它们都满足支持度大于或等于最小支持度 0.2。根据频繁项集，程序得到的关联规则有三条，即 {面包 }=>{牛奶 }，，{鸡蛋 }=>{牛奶 }，，{面包，苹果 }=>{牛奶 其中，这些规则的置信度都是 1.0，满足大于或等于最小置信度 0.8的条件 。

四、程序源码