协同过滤（Collaborative Filtering， CF）是推荐系统广泛使用的一种技术，它主要通过考虑用户（User）与用户之间、物品（Item）与物品之间的相似度（Similarity），来向用户推荐物品，常被用在电商网站中。其中，在推荐系统中最常使用的协同过滤方法，有如下 4 种： 基于用户的协同过滤推荐 基于物品的协同过滤推荐 基于模型的协同过滤推荐 混合协同过滤推荐 上面 4 种方法中，基于用户的协同过滤推荐、基于物品的协同过滤推荐都是基于内存的协同过滤推荐，一般在数据量较小的应用场景下，可以直接在线使用的实时推荐方法；基于模型的协同过滤推荐一般用于离线计算，它采用机器学习的方法，一般首相将用户偏好行为数据分成 2 个数据集（有时可能会将数据集分成 k 个子集，采用交叉验证的方式来提高模型精度），一个为训练集，一个为测试集，使用训练集数据来训练出推荐模型，然后使用测试集数据来评估模型的精度，当满足特定精度时，可以将得到的推荐模型应用于实际线上环境；混合协同过滤推荐，是综合基于内存的协同过滤（基于用户的协同过滤推荐、基于物品的协
按月份浏览文章: 十二月 2015
MapReduce V1：TaskTracker端启动Task流程分析
我们基于Hadoop 1.2.1源码分析MapReduce V1的处理流程。 TaskTracker周期性地向JobTracker发送心跳报告，在RPC调用返回结果后，解析结果得到JobTracker下发的运行Task的指令，即LaunchTaskAction，就会在TaskTracker节点上准备运行这个Task。Task的运行是在一个与TaskTracker进程隔离的JVM实例中执行，该JVM实例是通过org.apache.hadoop.mapred.Child来创建的，所以在创建Child VM实例之前，需要做大量的准备工作来启动Task运行。一个Task的启动过程，如下序列图所示： 通过上图，结合源码，我们将一个Task启动的过程，分为下面3个主要的步骤： 初始化跟踪Task运行的相关数据结构 准备Task运行所共享的Job资源 启动Task 下面，我们详细分析上面3个步骤的流程： 初始化跟踪Task运行的相关数据结构 如果是LaunchTaskAction，则TaskTracker会将该指令加入到一个启动Task的队列中，进行一步加载处理，如下所示： private void addToTaskQueue(LaunchTaskAction action) { if (action.getTask().isMapTask()) { mapLauncher.addToTaskQueue(action);
MapReduce V1：TaskTracker设计要点概要分析
我们基于Hadoop 1.2.1源码分析MapReduce V1的处理流程。 本文不打算深入地详细分析TaskTracker某个具体的处理流程，而是概要地分析TaskTracker在MapReduce框架中的主要负责处理那些事情，是我们能够在宏观上了解TaskTracker端都做了哪些工作。我尽量将TaskTracker端的全部要点内容提出来，但是涉及到详细的分析，只是点到为止，后续会对相应模块的处理流程结合代码进行分析。 TaskTracker主要负责MapReduce计算集群中Task运行的管理，所以TaskTracker要管理的事情比较多。一个MapReduce Job由很多的Task组成，而一个Job的所有Task被分成几个相斥的子集，每个子集被分配到某一个TaskTracker上去运行，所以一个TaskTracker管理运行了一个Job的所有Task的一个子集，也就是说TaskTracker不仅要维护每个Job对应的一个Task的子集，还要维护这些Task所属的Job的运行状态，对于Job/Task的状态的管理都是与JobTracker通过RPC通信保持状态的同步。 下面是TaskTracker端的主要组件，如下图所示： 为了了解TaskTracker中各个组件都负责处理哪些工作，我们通过下表来简要地说明各
k-medoids聚类算法实现
k-medoids聚类算法，即k-中心聚类算法，它是基于k-means聚类算法的改进。我们知道，k-means算法执行过程，首先需要随机选择初始质心，只有第一次随机选择的初始质心才是实际待聚类点集中的点，而后续将非质心点指派到对应的质心点后，重新计算得到的质心并非是待聚类点集中的点，而且如果某些非质心点是离群点的话，导致重新计算得到的质心可能偏离整个簇，为了解决这个问题，提出了改进的k-medoids聚类算法。 k-medoids聚类算法也是通过划分的方式来计算得到聚类结果，它使用绝对差值和（Sum of Absolute Differences，SAD）的度量来衡量聚类结果的优劣，在n维欧几里德空间中，计算SAD的公式如下所示： 围绕中心点划分（Partitioning Around Medoids，PAM）的方法是比较常用的，使用PAM方法进行处理，可以指定一个最大迭代次数的参数，在迭代过程中基于贪心策略来选择使得聚类的质量最高的划分。使用PAM的方法处理，每次交换一个中心点和非中心点，然后执行将非中心点指派到最近的中心点，计算得到的SAD值越小，则聚类质量越好，如此不断地迭代，直到找到一个最好
Bisecting k-means聚类算法实现
Bisecting k-means聚类算法，即二分k均值算法，它是k-means聚类算法的一个变体，主要是为了改进k-means算法随机选择初始质心的随机性造成聚类结果不确定性的问题，而Bisecting k-means算法受随机选择初始质心的影响比较小。 首先，我们考虑在欧几里德空间中，衡量簇的质量通常使用如下度量：误差平方和（Sum of the Squared Error，简称SSE），也就是要计算执行聚类分析后，对每个点都要计算一个误差值，即非质心点到最近的质心的距离。那么，既然每个非质心点都已经属于某个簇，也就是要计算每个非质心点到其所在簇的质心的距离，最后将这些距离值相加求和，作为SSE去评估一个聚类的质量如何。我们的最终目标是，使得最终的SSE能够最小，也就是一个最小化目标SSE的问题。在n维欧几里德空间，SSE形式化地定义，计算公式如下： Bisecting k-means聚类算法的基本思想是，通过引入局部二分试验，每次试验都通过二分具有最大SSE值的一个簇，二分这个簇以后得到的2个子簇，选择2个子簇的总SSE最小的划分方法，这样能够保证每次二分得到的2个簇是比较优的（也可能是最优的