通过 采集系统 我们采集了大量文本数据，但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复，如何选择和设计文本的去重算法？常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用，如果我们的爬虫每天采集的数据以千万计算，我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单，我们来做个测试，就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下：

String s1 = "你妈妈喊你回家吃饭哦，回家罗回家罗" ;  
String s2 = "你妈妈叫你回家吃饭啦，回家罗回家罗" ;  

long t1 = System.currentTimeMillis();  

for (int i = 0; i < 1000000; i++) {  
    int dis = StringUtils .getLevenshteinDistance(s1, s2);  
}  

long t2 =System.currentTimeMillis();  

System.out.println(" 耗费时间： " + (t2 - t1) + "  ms ");

耗费时间： 4266 ms

大跌眼镜，居然计算耗费4秒。假设我们一天需要比较100w次，光是比较100w次的数据是否重复就需要4s，就算4s一个文档，单线程一分钟才处理15个文档，一个小时才900个，一天也才21600个文档，这个数字和一天100w相差甚远，需要多少机器和资源才能解决。

K-Means介绍

K-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据他们的属性分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。其聚类过程可以用下图表示：

如图所示，数据样本用圆点表示，每个簇的中心点用叉叉表示。(a)刚开始时是原始数据，杂乱无章，没有label，看起来都一样，都是绿色的。(b)假设数据集可以分为两类，令K=2，随机在坐标上选两个点，作为两个类的中心点。(c-f)演示了聚类的两种迭代。先划分，把每个数据样本划分到最近的中心点那一簇；划分完后，更新每个簇的中心，即把该簇的所有数据点的坐标加起来去平均值。这样不断进行”划分—更新—划分—更新”，直到每个簇的中心不在移动为止。

聚类和分类

机器学习中，有聚类和分类两种问题，前面的两篇相关博文介绍了最简单的分类算法KNN算法，今天我们来谈谈最简单的聚类算法K-means算法。

什么是分类

就像前面介绍KNN时那样，分类是在一群已经知道类别标号的样本中，训练一种分类器，让其能够对某种未知的样本进行分类。这属于监督学习（supervised learning）。

什么是聚类

区别于分类，聚类是在一群未知类别标号的样本上，用某种算法将它们分成若干类别。这是一种非监督学习（unsupervisedlearning）。考虑到，第一次接触聚类，所以也选取最简单的聚类算法k-means算法来介绍。

两者的区别

最大的区别莫过于，分类的目标事先标明，而聚类则没有标明。

1 聚类方法概述

聚类方法是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程被成为聚类。由聚类所组成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此类似，与其他簇中的对象相异。在许多应用中，可以将一些簇中的数据对象作为一个整体来对待。

聚类是研究数据间逻辑上或物理上的相互关系的技术，其分析结果不仅可以揭示数据间的内在联系与区别，还可以为进一步的数据分析与知识发现提供重要依据。它是数据挖掘技术中的重要组成部分。作为统计学的重要研究内容之一，聚类分析具有坚实的理论基础，并形成了系统的方法学体系。

数据挖掘中聚类算法的应用很广泛。在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用不同的购买模式来刻画不同的消费群体的特征。在生物学上，聚类能用于帮助推导植物和动物的种类，基因和蛋白质的分类，获得对种群中固定结构的认识。聚类在地球观测数据中相似地区的确定，根据房屋的类型、价值和位置对一个城市中房屋的分类发挥作用。聚类也能用来对web上的文档进行分类，以发现有用的信息。聚类分析能作为一种独立的工具来获得数据分布的情况，观察每个簇的特点，并对某些特定的节点进一步分析。此外，聚类还可以作为其他方法的预处理步骤。

数据聚类正在蓬勃的发展，有贡献的领域包括数据挖掘，统计学，机器学习，空间数据库技术，生物学以及市场营销。现在数据聚类分析已经成为一个非常活跃的研究课题。

作为统计学的一个分支，聚类分析已经被广泛地研究若干年，主要集中在基于距离的聚类分析。基于k-means（k-平均值）、k-medoids（k-中心点）和其他一些的聚类分析工具已经被加入到许多统计分析的软件中，例如S-Plus、SPSS和SAS。

在机器学习领域，聚类分析是无指导学习的例子。与分类不同，聚类不需要依赖事先定义的类和带符号的训练实践。所以聚类分析是观察式学习，而不是示例式学习。

在数据挖掘领域，研究工作已经集中在为大型数据库的有效和实际的聚类分析寻找适当的方法。活跃的研究课题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大型数据库中混合数值和分类数据的聚类方法。

“We are leaving the age of information and entering the age of recommendation” — Chris Anderson in The Long Tail。

我们正在远离信息，而进入推荐时代。——克里斯·安德森

在介绍微博推荐算法之前，我们先聊一聊推荐系统和推荐算法。有这样一些问题：推荐系统适用哪些场景？用来解决什么问题、具有怎样的价值？效果如何衡量？

推荐系统诞生很早，但真正被大家所重视，缘起于以”facebook”为代表的社会化网络的兴起和以“淘宝“为代表的电商的繁荣，”选择“的时代已经来临，信息和物品的极大丰富，让用户如浩瀚宇宙中的小点，无所适从。推荐系统迎来爆发的机会，变得离用户更近：

• 快速更新的信息，使用户需要借助群体的智慧，了解当前热点。
• 信息极度膨胀，带来了高昂的个性化信息获取成本，过滤获取有用信息的效率低下。
• 很多情况下，用户的个性化需求很难明确表达，比如“今天晚上需要在附近找一个性价比高、又符合我口味的餐馆“。

推荐系统的适用场景还有很多，不再一一列举；其主要解决的问题是为用户找到合适的item（连接和排序），并找到一个合理的理由来解释推荐结果。而问题的解决，就是系统的价值，即建立关联、促进流动和传播、加速优胜劣汰。

推荐算法是实现推荐系统目标的方法和手段。算法与产品相结合，搭载在高效稳定的架构上，才能发挥它的最大功效。

接下来我们说一下微博推荐，微博本身的产品设计，使得即使没有推荐系统，仍然会形成一个大的用户关系网络，实现信息快速传播；而衡量一个事物的价值，一个简单的方法是对比看看保留它和去掉它时的差别。微博需要健康的用户关系网络，保障用户feed流的质量，且需要优质信息快速流动，通过传播淘汰低质信息。微博推荐的作用在于加速这一过程，并在特定的情况下控制信息的流向，所以微博推荐的角色是一个加速器和控制器。

最后回到微博推荐算法中来，上面扯了那么多，只是为了让大家能对微博推荐算法有更好的理解。我们的工作，是将微博推荐的目标和需要解决的问题，抽样为一系列的数学问题，然后运用多种数据工具进行求解。