基于协同过滤的推荐方法

协同过滤(Collaborative Filtering, CF)是推荐系统广泛使用的一种技术,它主要通过考虑用户(User)与用户之间、物品(Item)与物品之间的相似度(Similarity),来向用户推荐物品,常被用在电商网站中。其中,在推荐系统中最常使用的协同过滤方法,有如下4种: 基于用户的协同过滤推荐 基于物品的协同过滤推荐 基于模型的协同过滤推荐 混合协同过滤推荐 上面4种方法中,基于用户的协同过滤推荐、基于物品的协同过滤推荐都是基于内存的协同过滤推荐,一般在数据量较小的应用场景下,可以直接在线使用的实时推荐方法;基于模型的协同过滤推荐一般用于离线计算,它采用机器学习的方法,一般首相将用户偏好行为数据分成2个数据集(有时可能会将数据集分成k个子集,采用交叉验证的方式来提高模型精度),一个为训练集,一个为测试集,使用训练集数据来训练出推荐模型,然后使用测试集数据来评估模型的精度,当满足特定精度时,可以将得到的推荐模型应用于实

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的方法处理,每次交换一个中心点和非中心点,然后执行

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值的一个簇,二分这个簇以后得到的

k-means聚类算法原理及其实现

k-means(k-均值)算法是一种基于距离的聚类算法,它用质心(Centroid)到属于该质心的点距离这个度量来实现聚类,通常可以用于N维空间中对象。下面,我们以二维空间为例,概要地总结一下k-means聚类算法的一些要点: 除了随机选择的初始质心,后续迭代质心是根据给定的待聚类的集合S中点计算均值得到的,所以质心一般不是S中的点,但是标识的是一簇点的中心。 基本k-means算法,开始需要随机选择指定的k个质心,因为初始k个质心是随机选择的,所以每次执行k-means聚类的结果可能都不相同。如果初始随机选择的质心位置不好,可能造成k-means聚类的结果非常不理想。 计算质心:假设k-means聚类过程中,得到某一个簇的集合Ci={p(x1,y1), p(x2,y2), …,p(xn,yn)},则簇Ci的质心,质心x坐标为(x1+x2+ …+xn)/n,质心y坐标为(y1+y2+ …+yn)/n。 k-means算法的终止条件:质心在每一轮迭代中会发生变化,然后需要重新将非质心点指派给最近的质心而形

DBSCAN聚类算法原理及其实现

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚类算法,它是一种基于高密度连通区域的、基于密度的聚类算法,能够将具有足够高密度的区域划分为簇,并在具有噪声的数据中发现任意形状的簇。我们总结一下DBSCAN聚类算法原理的基本要点: DBSCAN算法需要选择一种距离度量,对于待聚类的数据集中,任意两个点之间的距离,反映了点之间的密度,说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难,所以对于二维空间中的点,可以使用欧几里德距离来进行度量。 DBSCAN算法需要用户输入2个参数:一个参数是半径(Eps),表示以给定点P为中心的圆形邻域的范围;另一个参数是以点P为中心的邻域内最少点的数量(MinPts)。如果满足:以点P为中心、半径为Eps的邻域内的点的个数不少于MinPts,则称点P为核心点。 DBSCAN聚类使用到一个k-距离的概念,k-距离是指:给定数据集P={p(i); i=0,1,…n},对于任意点P(i

使用libsvm实现文本分类

文本分类,首先它是分类问题,应该对应着分类过程的两个重要的步骤,一个是使用训练数据集训练分类器,另一个就是使用测试数据集来评价分类器的分类精度。然而,作为文本分类,它还具有文本这样的约束,所以对于文本来说,需要额外的处理过程,我们结合使用libsvm从宏观上总结一下,基于libsvm实现文本分类实现的基本过程,如下所示: 选择文本训练数据集和测试数据集:训练集和测试集都是类标签已知的; 训练集文本预处理:这里主要包括分词、去停用词、建立词袋模型(倒排表); 选择文本分类使用的特征向量(词向量):最终的目标是使得最终选出的特征向量在多个类别之间具有一定的类别区分度,可以使用相关有效的技术去实现特征向量的选择,由于分词后得到大量的词,通过选择降维技术能很好地减少计算量,还能维持分类的精度; 输出libsvm支持的量化的训练样本集文件:类别名称、特征向量中每个词元素分别到数字编号的映射转换,以及基于类别和特征向量

聚类算法:K-means

K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。 对于聚类问题,我们事先并不知道给定的一个训练数据集到底具有哪些类别(即没有指定类标签),而是根据需要设置指定个数类标签的数量(但不知道具体的类标签是什么),然后通过K-means算法将具有相同特征,或者基于一定规则认为某一些对象相似,与其它一些组明显的不同的数据聚集到一起,自然形成分组。之后,我们可以根据每一组的数据的特点,给定一个合适的类标签(当然,可能给出类标签对实际应用没有实际意义,例如可能我们就想看一下聚类得到的各个数据集的相似性)。 首先说明一个概念:质心(Centroid)。质心可以认为就是一个样本点,或者可以认为是数据集中的一个数据点P,它是具有相似性的一组数据的中心,即该组中每个数据点到P的距离都比到其

分类算法:决策树(C4.5)

C4.5是机器学习算法中的另一个分类决策树算法,它是基于ID3算法进行改进后的一种重要算法,相比于ID3算法,改进有如下几个要点: 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy, 熵是一种不纯度度量准则),也就是熵的变化值,而C4.5用的是信息增益率。 在决策树构造过程中进行剪枝,因为某些具有很少元素的结点可能会使构造的决策树过适应(Overfitting),如果不考虑这些结点可能会更好。 对非离散数据也能处理。 能够对不完整数据进行处理。 首先,说明一下如何计算信息增益率。 熟悉了ID3算法后,已经知道如何计算信息增益,计算公式如下所示(来自Wikipedia): 或者,用另一个更加直观容易理解的公式计算: 按照类标签对训练数据集D的属性集A进行划分,得到信息熵: 按照属性集A中每个属性进行划分,得到一组信息熵: 计算信息增益 然后计算信息增益,即前者对后者做差

分类算法:决策树(ID3)

决策树是以实例为基础的归纳学习算法。 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则,整个决策树就对应着一组析取表达式规则。 一棵决策树由以下3类结点构成: 根结点 内部结点(决策结点) 叶结点 其中,根结点和内部结点都对应着我们要进行分类的属性集中的一个属性,而叶结点是分类中的类标签的集合。如果一棵决策树构建起来,其分类精度满足我们的实际需要,我们就可以使用它来进行分类新的数据集。 这棵决策树就是我们根据已有的训练数据集训练出来的分类模型,可以通过使用测试数据集来对分类模型进行验证,经过调整模型直到达到我们所期望的分类精度,然后就可以使用该模型来预测实际应用中的新数据,对新的数据进行分类。 通过上面描述,我们已经能

使用libsvm进行分类预测

使用libsvm,首先需要将实际待分类的内容或数据(训练数据,或预测数据)进行量化,然后通过libsvm提供的功能实现分类和预测。下面介绍使用libsvm的基本步骤。 准备训练数据 数据格式: <label1> <index1>:<value11> <index2>:<value12>... <label2> <index1>:<value21> <index2>:<value22>... <label3> <index1>:<value31> <index2>:<value32>... ... 每一行,表示以已定义的类别标签,以及属于该标签的各个属性值,每个属性值以“属性索引编号:属性值”的格式。一行内容表示一个类别属性以及与该类别相关的各个属性的值。属性的值,一般可以表示为“该属性隶属于该类别的程度”,越大,表示该属性更能决定属性该类别。 上面的数据必须使用数字类型,例如类别,可以通过不同的整数来表示不同的类别。 准备的原始训练样本数据存放在文件raw_data.txt中,