分类/聚类/文本分析算法介绍
分类算法
Decision tree, Random forest decision tree, linear regression, logistic regression, Naive bayesian, SVM
决策树是用于分类和预测的主要技术之一，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则。构造决策树的目的是找出属性和类别间的关系，用它来预测将来未知类别的记录的类别。它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性值判断从该节点向下的分支，在决策树的叶节点得到结论。
主要的决策树算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻，能否处理大数据集等方面都有各自的不同之处。1决策树（Decision Trees）的优缺点
决策树的优点：
一、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。
二、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。
三、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。
四、决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
五、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
六、 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
七、 可以对有许多属性的数据集构造决策树。
八、 决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小
决策树的缺点：
一、对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。
二、决策树处理缺失数据时的困难。
三、 过度拟合问题的出现。
四、忽略数据集中属性之间的相关性。
改进措施
1、对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法。
2、使用基于决策树的combination算法，如bagging算法，randomforest算法，可以解决过拟合的问题
应用领域
• 企业管理实践，企业投资决策，由于决策树很好的分析能力，在决策过程应用较多。
贝叶斯（Bayes）
贝叶斯（Bayes）算法是一类利用概率统计知识进行分类的算法，如朴素贝叶斯（Naive Bayes）算法。这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提，而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降。为此就出现了许多降低独立性假设的贝叶斯分类算法，如TAN（Tree Augmented Na?ve Bayes)算法，它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。
朴素贝叶斯的主要优点有：
1）朴素贝叶斯模型发源于古典数学理论，有稳定的分类效率。
2）对小规模的数据表现很好，能个处理多分类任务，适合增量式训练，尤其是数据量超出内存时，我们可以一批批的去增量训练。
3）对缺失数据不太敏感，算法也比较简单，常用于文本分类。
朴素贝叶斯的主要缺点有：
1） 理论上，朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为朴素贝叶斯模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好。而在属性相关性较小时，朴素贝叶斯性能最为良好。对于这一点，有半朴素贝叶斯之类的算法通过考虑部分关联性适度改进。
2）需要知道先验概率，且先验概率很多时候取决于假设，假设的模型可以有很多种，因此在某些时候会由于假设的先验模型的原因导致预测效果不佳。
3）由于我们是通过先验和数据来决定后验的概率从而决定分类，所以分类决策存在一定的错误率。
4）对输入数据的表达形式很敏感。
现在贝叶斯已经广泛应用了，海难搜救、生物医药、疾病诊断、邮件过滤、文本分类、侦破案件、工业生产等很多方面。
支持向量机（SVM，Support Vector Machine）是Vapnik根据统计学习理论提出的一种新的学习方法[43] ，它的最大特点是根据结构风险最小化准则，以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力，较好地解决了非线性、高维数、局部极小点等问题。对于分类问题，支持向量机算法根据区域中的样本计算该区域的决策曲面，由此确定该区域中未知样本的类别。
支持向量机（SVM）的优缺点
SVM的优点：
一、可以解决小样本情况下的机器学习问题。
二、可以提高泛化性能。
三、可以解决高维问题。
四、可以解决非线性问题。
五、可以避免神经网络结构选择和局部极小点问题。
SVM的缺点：
一、对缺失数据敏感。
二、对非线性问题没有通用解决方案，必须谨慎选择Kernelfunction来处理。
SVM应用领域
文本分类、图像识别、主要二分类领域
聚类算法
K-means， Hierarchical clustering, Gaussian mixture model,
聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同数据尽量分离。
何时使用？
当你事先知道你将找到多少个分组的时候。（这个就比较尴尬了，因为很多情况下，我们并不知道要聚多少个类）
工作方式
该算法可以随机将每个观察（observation）分配到 k 类中的一类，然后计算每个类的平均。接下来，它重新将每个观察分配到与其最接近的均值的类别，然后再重新计算其均值。这一步不断重复，直到不再需要新的分配为止。（机器学习里面最简单的算法之一了，过程很简单）
经典K-means算法流程：
1. 随机地选择k个对象，每个对象初始地代表了一个簇的中心；
2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；
3. 重新计算每个簇的平均值，更新为新的簇中心；
4. 不断重复2、3，直到准则函数收敛。
算法优缺点
优点：对于大型数据集也是简单高效、时间复杂度、空间复杂度低。
缺点：最重要是数据集大时结果容易局部最优；需要预先设定K值，对最先的K个点选取很敏感；对噪声和离群值非常敏感；只用于numerical类型数据；不能解决非凸（non-convex）数据。
常见的算法及改进
k-means对初始值的设置很敏感，所以有了k-means++、intelligent k-means、genetic k-means。
k-means对噪声和离群值非常敏感，所以有了k-medoids和k-medians。
k-means只用于numerical类型数据，不适用于categorical类型数据，所以k-modes。
k-means不能解决非凸（non-convex）数据，所以有了kernel k-means。
层次聚类（Hierarchical clustering）
何时使用？
当我们希望进一步挖掘观测数据的潜在关系，可以使用层次聚类算法。
工作方式
首先我们会计算距离矩阵（distance matrix），其中矩阵的元素（i，j）代表观测值 i 和 j 之间的距离度量。然后将最接近的两个观察值组为一对，并计算它们的平均值。通过将成对观察值合并成一个对象，我们生成一个新的距离矩阵。具体合并的过程即计算每一对最近观察值的均值，并填入新距离矩阵，直到所有观测值都已合并。
有效案例：
以下是关于鲸鱼或海豚物种分类的超简单数据集。作为受过专业教育的生物学家，我可以保证通常我们会使用更加详尽的数据集构建系统。现在我们可以看看这六个物种的典型体长。本案例中我们将使用 2 次重复步骤。
高斯混合 [Gaussian mixture model]
高斯混合模型 表达的是一种混合分布，所有点都来自于k个高斯子分布中的一个，每个点都对应一个相应的概率。在MLlib的实现中 ，对于给定的样本集，使用最大期望算法(EM)来引导最大似然模型。
混合高斯模型的应用场景包括：
• 数据集分类，如会员分类；
• 图像分割以及以及特征抽取，例如在视频中跟踪人物以及区分动作，识别汽车、建筑物等；
• 语音分割以及特征特征抽取，例如从一堆杂乱的声音中提取某个人的声音，从音乐中提取背景音乐，从大自然中提取地震的声音等。
深度学习
FeedForward Classification, FeedForward Regression, LSTM RNN, CNN, Deep Belief,
RBM
文本分析
LDA，TFIDF，Word2vector, Word segmentation, Sentiment analysis
隐含狄利克雷分布(Latent Dirichlet Allocation，以下简称LDA)
LDA是基于贝叶斯模型的，涉及到贝叶斯模型离不开“先验分布”，“数据（似然）”和"后验分布"三块。在朴素贝叶斯算法原理小结中我们也已经讲到了这套贝叶斯理论。在贝叶斯学派这里：
先验分布 + 数据（似然）= 后验分布
这点其实很好理解，因为这符合我们人的思维方式，比如你对好人和坏人的认知，先验分布为：100个好人和100个的坏人，即你认为好人坏人各占一半，现在你被2个好人（数据）帮助了和1个坏人骗了，于是你得到了新的后验分布为：102个好人和101个的坏人。现在你的后验分布里面认为好人比坏人多了。这个后验分布接着又变成你的新的先验分布，当你被1个好人（数据）帮助了和3个坏人（数据）骗了后，你又更新了你的后验分布为：103个好人和104个的坏人。依次继续更新下去。
LDA（Latent Dirichlet Allocation）是一种文档主题生成模型，包含词、主题和文档三层结构。通常认为一篇文章的每个词都是通过一定概率选择了某个主题，并从这个主题中以一定概率选择某个词语，从文档—主题—词语，
应用：针对给定输入文本与文本库，计算得出文本库中与输入文本最相似的文本
TFIDF
TF-IDF是Term Frequency - Inverse Document Frequency的缩写，即“词频-逆文本频率”。它由两部分组成，TF和IDF。
TF-IDF是非常常用的文本挖掘预处理基本步骤，但是如果预处理中使用了Hash Trick，则一般就无法使用TF-IDF了，因为Hash Trick后我们已经无法得到哈希后的各特征的IDF的值。使用了IF-IDF并标准化以后，我们就可以使用各个文本的词特征向量作为文本的特征，进行分类或者聚类分析。Word2vector
word2vec 是Google在2013年年中开源的一款将词表征为实数值向量的高效工具，采用的模型有 CBOW（Continuous Bag-Of-Words，即连续的词袋模型）和Skip-Gram 两种。word2vec 通过训练， 可以把对文本内容的处理简化为 K 维向量空间中的向量运算， 而向量空间上的相似度可以用来表示文本语义上的相似度。 因此， word2vec输出的词向量可以被用来做很多 NLP 相关的工作，比如聚类、找同义词、词性分析等等。
情感分析(SentimentAnalysis)即分析发贴人对某个对象的态度是正面还是负面。这个过程当然不是仅仅查找"好"，"坏"这些关键字那 么简单，有时候相似度很高的句子，却反映了截然不同的态度，譬如下面这两句话
"这瓶洗发水，适合头发很干的人用"
"用了这瓶洗发水，头发变得很干"
两个句子中的主要成分都差不多，"洗发水"，"头发"，"很干"，但是第一句是褒义，第二句则很可能是贬义。对于后一句的处理还算简单，告诉计算机 程序头发"很干"不好，因此让头发"变得""很干"的洗发水，也就不是好的洗发水。而前一句呢，我们能够理解"适合头发很干的人用"是指使用该洗发水后， 能让头发变得不那么干燥点。但是假设我们告诉计算机，"某某产品适合XXX的人用"就是指用了某某产品后，XXX的人就会变得不那么XXX，那么当计算机 处理"这件衣服，适合漂亮女生穿"，你猜它会怎么理解？(漂亮的女生穿了就会变得不那么漂亮)
还有一类问题是讽刺(反话)和幽默，国外的一个自然语言处理专家也在他的blog上感叹道，"Humor is hard"。在国内，很多褒义词受到论坛文化的影响，往贬义词发展的趋势，例如"我太崇拜你了"，"你太有才了"。
说到底，这些都是自然语言处理面对的一个挑战，即如何将生活经验、文化传统等表达为一种可以被计算机
推荐算法
Factorization Based, Neighborhood based, popularity based, CF, slope one
Matrix Factorization即矩阵分解（MF），广泛地应用于各种数据分析、机器学习的场景，推荐领域也不例外。MF矩阵分解算法用于推荐方法时，它的好处很明显，易于编程实现，复杂度也比较低，预测效果也还不错，同时具有较好的拓展性；当然，矩阵分解的解释性会稍微弱些。
目前应用于推荐领域的矩阵分解模型，除了有基于SVD的各种矩阵分解算法如FunkSVD、BiasSVD、SVD++等，最基础的矩阵分解模型（Basic MF）也可以应用于推荐系统，增加一些正则化项（Regularized MF）或偏置项后（Bias MF）的矩阵分解算法也都可以很好地作为推荐算法使用。
在实际应用中，矩阵分解也受到了推荐系统较多的青睐，尤其是小的推荐系统很多都会使用矩阵分解，而很大型的推荐系统，则会用深度学习的一些模型。
矩阵分解MF的主要思想是，1)通过分解得到用户潜在因子矩阵U和商品潜在因子矩阵V，2）然后两者通过外积便可得到一个用户-商品评分矩阵的估计。
基于流行度的算法(popularity based)
基于流行度的算法非常简单粗暴，类似于各大新闻、微博热榜等，根据PV、UV、日均PV或分享率等数据来按某种热度排序来推荐给用户。
这种算法的优点是简单，适用于刚注册的新用户。缺点也很明显，它无法针对用户提供个性化的推荐。基于这种算法也可做一些优化，比如加入用户分群的流行度排序，例如把热榜上的体育内容优先推荐给体育迷，把政要热文推给热爱谈论政治的用户。
协同过滤算法(Collaborative Filtering, CF)
CF是很常用的一种算法，在很多电商网站上都有用到。CF算法包括基于用户的CF(User-based CF)和基于物品的CF(Item-based CF)。
基于用户的CF原理如下：
• 分析各个用户对item的评价（通过浏览记录、购买记录等）；
• 依据用户对item的评价计算得出所有用户之间的相似度；
• 选出与当前用户最相似的N个用户；
• 将这N个用户评价最高并且当前用户又没有浏览过的item推荐给当前用户。
基于物品的CF原理大同小异，只是主体在于物品：
• 分析各个用户对item的浏览记录。
• 依据浏览记录分析得出所有item之间的相似度；
• 对于当前用户评价高的item，找出与之相似度最高的N个item；
• 将这N个item推荐给用户。
•
• 我们可以看到，CF算法确实简单，而且很多时候推荐也是很准确的。然而它也存在一些问题：
• 依赖于准确的用户评分；
• 在计算的过程中，那些大热的物品会有更大的几率被推荐给用户；
• 冷启动问题。当有一名新用户或者新物品进入系统时，推荐将无从依据；
• 在一些item生存周期短（如新闻、广告）的系统中，由于更新速度快，大量item不会有用户评分，造成评分矩阵稀疏，不利于这些内容的推荐。
Slope One
算法是由 Daniel Lemire 教授在 2005 年提出的一个Item-Based 的协同过滤推荐算法。和其它类似算法相比, 它的最大优点在于算法很简单, 易于实现, 执行效率高, 同时推荐的准确性相对较高。
Slope One算法是基于不同物品之间的评分差的线性算法，预测用户对物品评分的个性化算法。主要两步：
Step1:计算物品之间的评分差的均值，记为物品间的评分偏差(两物品同时被评分)；
Step2:根据物品间的评分偏差和用户的历史评分，预测用户对未评分的物品的评分。
Step3:将预测评分排序，取topN对应的物品推荐给用户。
slopeOne使用场景
该算法适用于物品更新不频繁，数量相对较稳定并且物品数目明显小于用户数的场景。依赖用户的用户行为日志和物品偏好的相关内容。
优点：
1.算法简单，易于实现，执行效率高；
2.可以发现用户潜在的兴趣爱好；
缺点：
依赖用户行为，存在冷启动问题和稀疏性问题。