在许多的现实生活中的很多场景中，我们常常只能接触到隐性的反馈（例如游览，点击，购买，喜欢，分享等等）在 MLlib 中所用到的处理这种数据的方法来源于文献： Collaborative Filtering for Implicit Feedback Datasets。 本质上，这个方法将数据作为二元偏好值和偏好强度的一个结合，而不是对评分矩阵直接进行建模。因此，评价就不是与用户对商品的显性评分而是和所观察到的用户偏好强度关联了起来。然后，这个模型将尝试找到隐语义因子来预估一个用户对一个商品的偏好。

package org.apache.spark.examples.mllib;

// $example on$

import scala.Tuple2;

import org.apache.spark.api.java.*;

import org.apache.spark.api.java.function.Function;

import org.apache.spark.mllib.recommendation.ALS;

import org.apache.spark.mllib.recommendation.MatrixFactorizationModel;

import org.apache.spark.mllib.recommendation.Rating;

import org.apache.spark.SparkConf;

// $example off$

public class JavaRecommendationExample {

  public static void main(String args[]) {

    // $example on$

    SparkConf conf = new SparkConf().setAppName("Java Collaborative Filtering Example");

    JavaSparkContext jsc = new JavaSparkContext(conf);

    // Load and parse the data

    String path = "../data/mllib/als/test.data";

    JavaRDD<String> data = jsc.textFile(path);

    JavaRDD<Rating> ratings = data.map(

      new Function<String, Rating>() {

        public Rating call(String s) {

          String[] sarray = s.split(",");

          return new Rating(Integer.parseInt(sarray[0]), Integer.parseInt(sarray[1]),

            Double.parseDouble(sarray[2]));

        }

      }

    );

    // Build the recommendation model using ALS

    int rank = 10;

    int numIterations = 10;

//使用具体评分数进行训练

    MatrixFactorizationModel model = ALS.train(JavaRDD.toRDD(ratings), rank, numIterations, 0.01);

//忽略评分数据进行模型训练

//MatrixFactorizationModel model = ALS.trainImplicit(JavaRDD.toRDD(ratings), rank, numIterations, 0.01, 0.01);

    // Evaluate the model on rating data

    JavaRDD<Tuple2<Object, Object>> userProducts = ratings.map(

      new Function<Rating, Tuple2<Object, Object>>() {

        public Tuple2<Object, Object> call(Rating r) {

          return new Tuple2<Object, Object>(r.user(), r.product());

        }

      }

    );

    JavaPairRDD<Tuple2<Integer, Integer>, Double> predictions = JavaPairRDD.fromJavaRDD(

      model.predict(JavaRDD.toRDD(userProducts)).toJavaRDD().map(

        new Function<Rating, Tuple2<Tuple2<Integer, Integer>, Double>>() {

          public Tuple2<Tuple2<Integer, Integer>, Double> call(Rating r){

            return new Tuple2<Tuple2<Integer, Integer>, Double>(

              new Tuple2<Integer, Integer>(r.user(), r.product()), r.rating());

          }

        }

      ));

    JavaRDD<Tuple2<Double, Double>> ratesAndPreds =

      JavaPairRDD.fromJavaRDD(ratings.map(

        new Function<Rating, Tuple2<Tuple2<Integer, Integer>, Double>>() {

          public Tuple2<Tuple2<Integer, Integer>, Double> call(Rating r){

            return new Tuple2<Tuple2<Integer, Integer>, Double>(

              new Tuple2<Integer, Integer>(r.user(), r.product()), r.rating());

          }

        }

      )).join(predictions).values();

    double MSE = JavaDoubleRDD.fromRDD(ratesAndPreds.map(

      new Function<Tuple2<Double, Double>, Object>() {

        public Object call(Tuple2<Double, Double> pair) {

          Double err = pair._1() - pair._2();

          return err * err;

        }

      }

    ).rdd()).mean();

    System.out.println("Mean Squared Error = " + MSE);

    // Save and load model

    model.save(jsc.sc(), "target/tmp/myCollaborativeFilter");

    MatrixFactorizationModel sameModel = MatrixFactorizationModel.load(jsc.sc(),

      "target/tmp/myCollaborativeFilter");

//使用模型为用户推荐内容

    Rating[] recommendations =sameModel.recommendProducts(1, 3);

    for(int i=0;i<recommendations.length;i++){

    System.out.println("推荐的产品:"+recommendations[i].product());

    }

    // $example off$

  }

}

发表评论

IT瘾于2016年4月11日 上午05时52分00秒发布 #

##4.2 简化距离计算公式方法
1）基本思路
我们的业务场景仅仅是在一个城市范围内进行距离计算，也就是说两个点之间的距离一般不会超过200多千米。由于范围小，可以认为经线和纬线是垂直的，如图所示，要求A（116.8，39,78）和B（116.9，39.68）两点的距离，我们可以先求出南北方向距离AM，然后求出东西方向距离BM，最后求矩形对角线距离，即sqrt(AMAM + BMBM)。

南北方向AM = R纬度差Math.PI/180.0；
东西方向BM = R经度差Cos<当地纬度数* Math.PI/180.0>
这种方式仅仅需要计算一次cos函数。

public static double distanceSimplify(double lat1, double lng1, double lat2, double lng2, double[] a) {      double dx = lng1 - lng2; // 经度差值      double dy = lat1 - lat2; // 纬度差值      double b = (lat1 + lat2) / 2.0; // 平均纬度      double Lx = toRadians(dx) * 6367000.0* Math.cos(toRadians(b)); // 东西距离      double Ly = 6367000.0 * toRadians(dy); // 南北距离      return Math.sqrt(Lx * Lx + Ly * Ly);  // 用平面的矩形对角距离公式计算总距离     } } 

我们对这个方法的有效性和性能进行验证。
1.1）有效性验证
我们首先检验这种简化是否能满足我们应用的精度，如果精度较差将不能用于实际生产环境。

我们的方法叫distanceSimplify，lucene的方法叫distHaversineRAD。下表是在不同尺度下两个方法的相差情况。

可以看到两者在百米、千米尺度上几乎没有差别，在万米尺度上也仅有分米的差别，此外由于我们的业务是在一个城市范围内进行筛选排序，所以我们选择了北京左下角和右上角两点进行比较，两点相距有260多千米，两个方法差别17m。从精度上看该优化方法能满足我们应用需求。

1.2）性能验证

2）进一步优化
我们看到这里计算了一次cos这一三角函数，如果我们能消除此三角函数，那么将进一步提高计算效率。
如何消除cos三角函数呢？

采用多项式来拟合cos三角函数，这样不就可以将三角函数转换为加减乘除了嘛！

首先决定多项式的最高次数，次数为1和2显然都无法很好拟合cos函数，那么我们选择3先尝试吧，注：最高次数不是越多越好，次数越高会产生过拟合问题。

使用org.apache.commons.math3这一数学工具包来进行拟合。中国的纬度范围在10~60之间，即我们将此区间离散成Length份作为我们的训练集。

public static double[] trainPolyFit(int degree, int Length){     PolynomialCurveFitter polynomialCurveFitter = PolynomialCurveFitter.create(degree);     double minLat = 10.0; //中国最低纬度     double maxLat = 60.0; //中国最高纬度     double interv = (maxLat - minLat) / (double)Length;     List<WeightedObservedPoint> weightedObservedPoints = new ArrayList<WeightedObservedPoint>();     for(int i = 0; i < Length; i++) {         WeightedObservedPoint weightedObservedPoint = new WeightedObservedPoint(1,  minLat + (double)i*interv, Math.cos(toRadians(x[i])));         weightedObservedPoints.add(weightedObservedPoint);      }     return polynomialCurveFitter.fit(weightedObservedPoints); }   public static double distanceSimplifyMore(double lat1, double lng1, double lat2, double lng2, double[] a) {      //1) 计算三个参数      double dx = lng1 - lng2; // 经度差值      double dy = lat1 - lat2; // 纬度差值      double b = (lat1 + lat2) / 2.0; // 平均纬度      //2) 计算东西方向距离和南北方向距离(单位：米)，东西距离采用三阶多项式      double Lx = (a[3] * b*b*b  + a[2]* b*b  +a[1] * b + a[0] ) * toRadians(dx) * 6367000.0; // 东西距离      double Ly = 6367000.0 * toRadians(dy); // 南北距离      //3) 用平面的矩形对角距离公式计算总距离      return Math.sqrt(Lx * Lx + Ly * Ly); } 

我们对此优化方法进行有效性和性能验证。
2.1）有效性验证
我们的优化方法叫distanceSimplifyMore，lucene的方法叫distHaversineRAD，下表是在不同尺度下两个方法的相差情况。

可以看到在百米尺度上两者几乎未有差别，在千米尺度上仅有分米的区别，在更高尺度上如72千米仅有5.6m米别，在264千米也仅有8.1米区别，因此该优化方法的精度能满足我们的应用需求。

2.2）性能验证

#5 实际应用
坐标转换方法和简化距离公式方法性能都非常高，相比lucene使用的Haversine算法大大提高了计算效率，然而坐标转换方法存在一些缺点：
a）坐标转换后的数据不能被直接用于空间索引。lucene可以直接对经纬度进行geohash空间索引，而通过空间转换变成三维数据后不能直接使用。我们的应用有附近范围筛选功能（例如附近5km的团购单子），通过geohash空间索引可以提高范围筛选的效率；
b）坐标转换方法增大内存开销。我们会将坐标写入倒排索引中，之前坐标是2列（经度和纬度），现在变成3列（x,y,z），在使用中我们往往会将这数据放入到cache中，因此会增大内存开销；
c）坐标转换方法增大建索引开销。此方法本质上是将计算从查询阶段放至到索引阶段，因此提高了建索引的开销。

基于上述原因我们在实际应用中采用简化距离公式方法（通过三次多项式来拟合cos三角函数），此方法在团购筛选和商家筛选的距离排序、智能排序中已经开始使用，与之前相比，筛选团购时北京全城美食品类距离排序响应时间从40ms下降为20ms。

阅读全文……

发表评论

IT瘾于2016年3月27日 上午03时34分00秒发布 #

首先，由人工标注训练数据。也就是说，对于某个查询Q,人工标出哪些文档是和这个査询相关的，同时标出相关程度，相关程度有时候可以用数值序列来表示，比如从1分 到5分为3个档次，1代表微弱相关，5代表最相关，其他数值代表相关性在两者之间。对于某个查询，可能相关文档众多，同时用户査询也五花八门，所以全部靠人工标注有时候 不太可能。此时，可以利用用户点击记录来模拟这种人工打分机制。
      对于机器学习来说，输入是用户查询和一系列标注好的文档，机器学习系统需要学习打分函数，然后按照打分函数输出搜索结果，但是在其内部，每个文档由若干特征构成的，即每个文档进入机器学习系统之前，首先需要将其转换我饿滴特征向量，比较常用的特征包括：

• 查询词在文档中的词频信息
• 查询词的IDF信息
• 文档长度： 
• 网页的入链数量： 
• 网页的出链数量：
• 网页的pageRank值； 
• 网页的URL松度： 
• 査询词的Proximity值：即在文档中多大的窗口内可以出现所有査询词。

        以上所列只是影响排序的一部分特征，实际上还有很多类似的特征可以作为特征向量中的一维加入。在确定了特征数量后，即可将文档转換为特征向量X,前面说过每个文档会人工标出其相关性得分y.这样每个文档会转換为<X,Y>的形式，即特征向量及其对应的相关性得分，这样就形成了一个具体的训练实例。

       通过多个调练实例，就可以采用机器学习技术来对系统进行训练，训练的结果往在是 ―个分类函数或者回归函数，在之后的用户搜索中，就可以用这个分类函数对文档进行打分，形成搜索结果 

    从目前的研究方法来说，可以将机器学习揉序方法分为以下3种：单文档方法、文档对方法和文档列表方法。

3. 单文档方法（PointWise Approach》

        单文档方法的处理对象是单独的一篇文档，将文档转换为特征向量后，机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分，打分结果即是搜索结果。下面我们用一个简单的例子说明这种方法。 
        图2是人工标注的训练集合，在这个例子中，我们对于每个文档采用了3个特征： 査询与文档的Cosme相似性分值、査询词的Proximity值及页面的PageRank数值，而相关性判断是二元的，即要么相关要么不相关，当然，这里的相关性判断完全可以按照相关程度扩展为多元的，本例为了方便说明做了简化。

                                          图2 训练数据
        

      例子中提供了5个训练实例，每个训练实例分别标出来其对应的查询，3个特征的得分情况及相关性判断。对于机器学习系统来说，根据训练数据，需要如下的线性打分函数：
  
       Score(Q, D)=a x CS+ b x PM+cx PR+ d 
        这个公式中，cs代表Cosine相似度变徽，PM代表Proximity值变量，PR代表pageRank， 而a、 b、 c、 d则是变量对应的参数。

        如果得分大于一设定阀值，则叫以认为是相关的， 如果小于设定闽值则可以认为不相关。通过训练实例，可以获得最优的a、 b,、c、d参数组合，当这些参数确定后，机器学习系统就算学习完毕，之后即可利用这个打分函数进行相关性判断。对于某个新的查询Q和文档D，系统首先获得其文档D对应的3个特 I特征值，之后利用学习到的参数组合计算两者得分，当得分大于设定的闽值，即可判断文档是相关文档，否则判断为不相关文档。

4. 文档对方法（PairWise Approach)

        对于搜索系统来说，系统接收到用户査询后，返回相关文档列表，所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算，没有考虑文档之间的顺序关系。文档对方法则将重点转向量对文档顺序关系是否合理进行判断。

        之所以被称为文档对方法，是因为这种机器学习方法的训练过程和训练目标，是判断任意两个文档组成的文档对<D0C1，D0C2>是否满足顺序关系，即判断是否D0C1应该排在DOC2的前面。图3展示了一个训练实例：査询Q1对应的搜索结果列表如何转换为文档对的形式，因为从人工标注的相关性得分可以看出，D0C2得分最高，D0C3次之，D0C1得分最低，于是我们可以按照得分大小顺序关系得到3个如图3所示的文档对，将每个文档对的文档转换为特征向量后，就形成了一个具体的训练实例。

                                            图3  文档对的方法训练实例

       根据转换后的训练实例，就可以利用机器学习方法进行分类函数的学习，具体的学习方法有很多，比如SVM. Boosts、神经网络等都可以作为具体的学习方法，但是不论具体方法是什么，其学习目标都是一致的，即输入- 个査询和文档对<Docl，DOC2>, 机器学习排序能够判断这种顺序关系是否成立，如果成立，那么在搜索结果中D0C1应该排在D0C2 前面，否则Doe2应该摔在Docl前面，通过这种方式，就完成搜索结果的排序任务。
        尽管文档对方法相对单文档方法做出了改进，但是这种方法也存在两个明显的问题：

       一个问题是：文档对方法只考虑了两个文档对的相对先后顺序，却没有考虑文档出现在搜索列表中的位置，排在搜索站果前列的文档更为重要，如果前列文档出现判断错误，代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素，即每个文档对根据其在列表中的顺序具有不同的权重，越是排在前列的权重越大，即在搜索列表前列如 果排错顺序的话其付出的代价更高•
        另外一个问题是：不同的査询，其相关文档数量差异很大，所以转换为文档对之后， 有的查询对能有几百个对应的文档对，而有的查询只有十几个对应的文档对，这对机器学习系统的效果评价造成困难 •我们设想有两个查询，査询Q1对应500个文文档对，查询Q2 对应10个文档对，假设学习系统对于査询Ql的文档对能够判断正确480个，对于査询 Q2的义格对能够判新正确2个，如果从总的文档对数量来看，这个学习系统的准确率是 (480+2)/（500+10）=0.95.即95%的准确率，但是从査询的角度，两个査询对应的准确率 分别为：96%和20%,两者平均为58%,与纯粹从文档对判断的准确率相差甚远，这对如何继续调优机器学习系统会带来困扰。

4. 文档列表方法（ListWise Approach)

          单文档方法将训练集里每一个文档当做一个训练实例，文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例，文档列表方法与上述两种表示方式不同，是将每一个查询对应的所有搜索结果列表整体作为一个训练实例，这也是为何称之为文档列表方法的原因。
        文档列表方法根据K个训练实例（一个査询及其对应的所有搜索结果评分作为一个实 例）训练得到最优评分函数F， 对于一个新的用户査询，函数F 对每一个文档打分，之后按照得分顺序由高到低排序，就是对应的搜索结果。 所以关键问题是：拿到训练数据，如何才能训练得到最优的打分函数？

        这里介绍一种训练方法，它是基于搜索结果排列组合的概率分布情况来训练的，图4是这种方式训练过程的图解示意。

                                       图4 不同评分函数的KL距离

       首先解释下什么是搜索结果排列组合的概率分布，我们知道，对于搜索 引擎来说，用户输入査询Q， 搜索引擎返回搜索结果，我们假设搜索结果集合包含A. B 和C 3个文档，搜索引擎要对搜索结果排序，而这3个文档的顺序共有6种排列组合方式:

      ABC, ACB, BAG, BCA, CAB和CBA,

        而每种排列组合都是一种可能的搜索结果排序方法。

        对于某个评分函数F来说，对3个搜索结果文档的相关性打分，得到3个不同的相关度得分F(A)、 F(B)和F(C)， 根据这3个得分就可以计算6种排列组合情况各自的概率值。 不同的评分函数，其6种搜索结果排列组合的概率分布是不一样的。
      了解了什么是搜索结果排列组合的概率分布，我们介绍如何根据训练实例找到最优的 评分函数。图4展示了一个具体的训练实例，即査询Q1及其对应的3个文档的得分情况，这个得分是由人工打上去的，所以可以看做是标准答案。可以设想存在一个最优的评分函数g，对查询Q1来说，其打分结果是：A文档得6分，B文档得4分，C文档得3分， 因为得分是人工打的，所以具体这个函数g是怎样的我们不清楚，我们的任务就是找到一 个函数，使得函数对Ql的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分 (虚拟的函数g) 已知，那么我们可以计算函数g对应的搜索结果排列组合概率分布，其具体分布情况如图4中间的概率分布所示。假设存在两个其他函数h和f，它们的计算方法已知，对应的对3个搜索结果的打分在图上可以看到，由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布，那么h与f哪个与虚拟的最优评分函数g更接近呢？一般可以用两个分布概率之间的距离远近来度量相似性，KL距离就是一种衡量概率分布差异大小的计算工具，通过分别计算h与g的差异大小及f与g的差异大小，可以看出f比h更接近的最优函数g，那么在这个函数中，我们应该优先选f作为将来搜索可用的评分函数，训练过程就是在可能的函数中寻找最接近虚拟最优函数g的那个函数作为训练结果，将来作为在搜索时的评分函数。

       上述例子只是描述了对于单个训练实例如何通过训练找到最优函数，事实上我们有K 个训练实例，虽然如此，其训练过程与上述说明是类似的，可以认为存在一个虚拟的最优 评分函数g (实际上是人工打分），训练过程就是在所有训练实例基础上，探寻所有可能的 候选函数，从中选择那个KL距离最接近于函数g的，以此作为实际使用的评分函数。 经验结果表明，基于文档列表方法

的机器学习排序效果要好于前述两种方法。

阅读全文……

发表评论

IT瘾于2016年3月24日 下午05时34分00秒发布 #