從源代碼剖析Mahout推薦引擎

jopen 11年前發布 | 76K 次閱讀 Mahout 推薦引擎

前言

Mahout框架中cf.taste包實現了推薦算法引擎，它提供了一套完整的推薦算法工具集，同時規范了數據結構，并標準化了程序開發過程。應用推薦算法時，代碼也就7-8行，簡單地有點像R了。為了使用簡單的目標，Mahout推薦引擎必然要做到精巧的程序設計。

本文將介紹Mahout推薦引擎的程序設計。

Mahout推薦引擎概況
標準化的程序開發過程
數據模型
相似度算法工具集
近鄰算法工具集
推薦算法工具集
創建自己的推薦引擎構造器

1. Mahout推薦引擎概況

Mahout的推薦引擎，要從org.apache.mahout.cf.taste包說起。

從源代碼剖析Mahout推薦引擎

packages的說明：

common: 公共類包括，異常，數據刷新接口，權重常量
eval: 定義構造器接口，類似于工廠模式
model: 定義數據模型接口
neighborhood: 定義近鄰算法的接口
recommender: 定義推薦算法的接口
similarity: 定義相似度算法的接口
transforms: 定義數據轉換的接口
hadoop: 基于hadoop的分步式算法的實現類
impl: 單機內存算法實現類

從上面的package情況，我可以粗略地看出推薦引擎分為5個主要部分組成：數據模型，相似度算法，近鄰算法，推薦算法，算法評分器。

從數據處理能力上，算法可以分為：單機內存算法，基于hadoop的分步式算法。

下面我們將基于單機內存算法，研究Mahout的推薦引擎的結構。

2. 標準化的程序開發過程

以UserCF的推薦算法為例，官方建議我們的開發過程：

從源代碼剖析Mahout推薦引擎

圖片摘自Mahout in Action

從上圖中我們可以看到，算法是被模塊化的，通過1,2,3,4的過程進行方法調用。

程序代碼：

 public class UserCF {

    final static int NEIGHBORHOOD_NUM = 2;
    final static int RECOMMENDER_NUM = 3;

    public static void main(String[] args) throws IOException, TasteException {
        String file = "datafile/item.csv";
        DataModel model = new FileDataModel(new File(file));
        UserSimilarity user = new EuclideanDistanceSimilarity(model);
        NearestNUserNeighborhood neighbor = new NearestNUserNeighborhood(NEIGHBORHOOD_NUM, user, model);
        Recommender r = new GenericUserBasedRecommender(model, neighbor, user);
        LongPrimitiveIterator iter = model.getUserIDs();

        while (iter.hasNext()) {
            long uid = iter.nextLong();
            List list = r.recommend(uid, RECOMMENDER_NUM);
            System.out.printf("uid:%s", uid);
            for (RecommendedItem ritem : list) {
                System.out.printf("(%s,%f)", ritem.getItemID(), ritem.getValue());
            }
            System.out.println();
        }
    }
}

我們調用算法的程序，要用到4個對象：DataModel, UserSimilarity, NearestNUserNeighborhood, Recommender。

3. 數據模型

Mahout的推薦引擎的數據模型，以DataModel接口為父類。

通過“策略模式”匹配不同的數據源，支持File, JDBC(MySQL, PostgreSQL), NoSQL(Cassandra, HBase, MongoDB)。

注：NoSQL的實現在mahout-integration-0.8.jar中。

數據格式支持2種：

GenericDataModel: 用戶ID，物品ID，用戶對物品的打分(UserID,ItemID,PreferenceValue)
GenericBooleanPrefDataModel: 用戶ID，物品ID (UserID,ItemID)，這種方式表達用戶是否瀏覽過該物品，但并未對物品進行打分。

從源代碼剖析Mahout推薦引擎

4. 相似度算法工具集

相似度算法分為2種

基于用戶(UserCF)的相似度算法
基于物品(ItemCF)的相似度算法

1). 基于用戶(UserCF)的相似度算法

從源代碼剖析Mahout推薦引擎

計算用戶的相似矩陣，可以通過上圖中幾種算法。

2). 基于物品(ItemCF)的相似度算法

計算物品的相似矩陣，可以通過上圖中幾種算法。

關于相似度距離的說明：

EuclideanDistanceSimilarity: 歐氏距離相似度

原理：利用歐式距離d定義的相似度s，s=1 / (1+d)。

范圍：[0,1]，值越大，說明d越小，也就是距離越近，則相似度越大。

說明：同皮爾森相似度一樣，該相似度也沒有考慮重疊數對結果的影響，同樣地，Mahout通過增加一個枚舉類型（Weighting）的參數來使得重疊數也成為計算相似度的影響因子。
PearsonCorrelationSimilarity: 皮爾森相似度

原理：用來反映兩個變量線性相關程度的統計量

范圍：[-1,1]，絕對值越大，說明相關性越強，負相關對于推薦的意義小。

說明：1、不考慮重疊的數量；2、如果只有一項重疊，無法計算相似性（計算過程被除數有n-1）；3、如果重疊的值都相等，也無法計算相似性（標準差為0，做除數）。

該相似度并不是最好的選擇，也不是最壞的選擇，只是因為其容易理解，在早期研究中經常被提起。使用Pearson線性相關系數必須假設數據是成對地從正態分布中取得的，并且數據至少在邏輯范疇內必須是等間距的數據。Mahout中，為皮爾森相關計算提供了一個擴展，通過增加一個枚舉類型（Weighting）的參數來使得重疊數也成為計算相似度的影響因子。
UncenteredCosineSimilarity: 余弦相似度

原理：多維空間兩點與所設定的點形成夾角的余弦值。

范圍：[-1,1]，值越大，說明夾角越大，兩點相距就越遠，相似度就越小。

說明：在數學表達中，如果對兩個項的屬性進行了數據中心化，計算出來的余弦相似度和皮爾森相似度是一樣的，在mahout中，實現了數據中心化的過程，所以皮爾森相似度值也是數據中心化后的余弦相似度。另外在新版本中，Mahout提供了UncenteredCosineSimilarity類作為計算非中心化數據的余弦相似度。
SpearmanCorrelationSimilarity: Spearman秩相關系數相似度
原理：Spearman秩相關系數通常被認為是排列后的變量之間的Pearson線性相關系數。

范圍：{-1.0,1.0}，當一致時為1.0，不一致時為-1.0。

說明：計算非常慢，有大量排序。針對推薦系統中的數據集來講，用Spearman秩相關系數作為相似度量是不合適的。
CityBlockSimilarity: 曼哈頓距離相似度
原理：曼哈頓距離的實現，同歐式距離相似，都是用于多維數據空間距離的測度

范圍：[0,1]，同歐式距離一致，值越小，說明距離值越大，相似度越大。

說明：比歐式距離計算量少，性能相對高。
LogLikelihoodSimilarity: 對數似然相似度
原理：重疊的個數，不重疊的個數，都沒有的個數

范圍：具體可去百度文庫中查找論文《Accurate Methods for the Statistics of Surprise and Coincidence》

說明：處理無打分的偏好數據，比Tanimoto系數的計算方法更為智能。
TanimotoCoefficientSimilarity: Tanimoto系數相似度

原理：又名廣義Jaccard系數，是對Jaccard系數的擴展，等式為

范圍：[0,1]，完全重疊時為1，無重疊項時為0，越接近1說明越相似。

說明：處理無打分的偏好數據。

相似度算法介紹，摘自：http://www.cnblogs.com/dlts26/archive/2012/06/20/2555772.html

5. 近鄰算法工具集

近鄰算法只對于UserCF適用，通過近鄰算法給相似的用戶進行排序，選出前N個最相似的，作為最終推薦的參考的用戶。

從源代碼剖析Mahout推薦引擎

近鄰算法分為2種：

NearestNUserNeighborhood:指定N的個數，比如，選出前10最相似的用戶。
ThresholdUserNeighborhood:指定比例，比如，選擇前10%最相似的用戶。

從源代碼剖析Mahout推薦引擎

6. 推薦算法工具集

推薦算法是以Recommender作為基礎的父類，關于推薦算法的詳細介紹，請參考文章：Mahout推薦算法API詳解

7. 創建自己的推薦引擎構造器

有了上面的知識，我就清楚地知道了Mahout推薦引擎的原理和使用，我們就可以寫一個自己的構造器，通過“策略模式”實現，算法的組合。

新建文件：org.conan.mymahout.recommendation.job.RecommendFactory.java

 public final class RecommendFactory {
...
}

1). 構造數據模型

     public static DataModel buildDataModel(String file) throws TasteException, IOException {
        return new FileDataModel(new File(file));
    }

    public static DataModel buildDataModelNoPref(String file) throws TasteException, IOException {
        return new GenericBooleanPrefDataModel(GenericBooleanPrefDataModel.toDataMap(new FileDataModel(new File(file))));
    }

    public static DataModelBuilder buildDataModelNoPrefBuilder() {
        return new DataModelBuilder() {
            @Override
            public DataModel buildDataModel(FastByIDMap trainingData) {
                return new GenericBooleanPrefDataModel(GenericBooleanPrefDataModel.toDataMap(trainingData));
            }
        };
    }

2). 構造相似度算法模型

 public enum SIMILARITY {
        PEARSON, EUCLIDEAN, COSINE, TANIMOTO, LOGLIKELIHOOD, FARTHEST_NEIGHBOR_CLUSTER, NEAREST_NEIGHBOR_CLUSTER
    }

    public static UserSimilarity userSimilarity(SIMILARITY type, DataModel m) throws TasteException {
        switch (type) {
        case PEARSON:
            return new PearsonCorrelationSimilarity(m);
        case COSINE:
            return new UncenteredCosineSimilarity(m);
        case TANIMOTO:
            return new TanimotoCoefficientSimilarity(m);
        case LOGLIKELIHOOD:
            return new LogLikelihoodSimilarity(m);
        case EUCLIDEAN:
        default:
            return new EuclideanDistanceSimilarity(m);
        }
    }

    public static ItemSimilarity itemSimilarity(SIMILARITY type, DataModel m) throws TasteException {
        switch (type) {
        case LOGLIKELIHOOD:
            return new LogLikelihoodSimilarity(m);
        case TANIMOTO:
        default:
            return new TanimotoCoefficientSimilarity(m);
        }
    }

    public static ClusterSimilarity clusterSimilarity(SIMILARITY type, UserSimilarity us) throws TasteException {
        switch (type) {
        case NEAREST_NEIGHBOR_CLUSTER:
            return new NearestNeighborClusterSimilarity(us);
        case FARTHEST_NEIGHBOR_CLUSTER:
        default:
            return new FarthestNeighborClusterSimilarity(us);
        }
    }

3). 構造近鄰算法模型

   public enum NEIGHBORHOOD {
        NEAREST, THRESHOLD
    }

    public static UserNeighborhood userNeighborhood(NEIGHBORHOOD type, UserSimilarity s, DataModel m, double num) throws TasteException {
        switch (type) {
        case NEAREST:
            return new NearestNUserNeighborhood((int) num, s, m);
        case THRESHOLD:
        default:
            return new ThresholdUserNeighborhood(num, s, m);
        }
    }

4). 構造推薦算法模型

  public enum RECOMMENDER {
        USER, ITEM
    }

    public static RecommenderBuilder userRecommender(final UserSimilarity us, final UserNeighborhood un, boolean pref) throws TasteException {
        return pref ? new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel model) throws TasteException {
                return new GenericUserBasedRecommender(model, un, us);
            }
        } : new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel model) throws TasteException {
                return new GenericBooleanPrefUserBasedRecommender(model, un, us);
            }
        };
    }

    public static RecommenderBuilder itemRecommender(final ItemSimilarity is, boolean pref) throws TasteException {
        return pref ? new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel model) throws TasteException {
                return new GenericItemBasedRecommender(model, is);
            }
        } : new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel model) throws TasteException {
                return new GenericBooleanPrefItemBasedRecommender(model, is);
            }
        };
    }

    public static RecommenderBuilder slopeOneRecommender() throws TasteException {
        return new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel dataModel) throws TasteException {
                return new SlopeOneRecommender(dataModel);
            }

        };
    }

    public static RecommenderBuilder itemKNNRecommender(final ItemSimilarity is, final Optimizer op, final int n) throws TasteException {
        return new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel dataModel) throws TasteException {
                return new KnnItemBasedRecommender(dataModel, is, op, n);
            }
        };
    }

    public static RecommenderBuilder svdRecommender(final Factorizer factorizer) throws TasteException {
        return new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel dataModel) throws TasteException {
                return new SVDRecommender(dataModel, factorizer);
            }
        };
    }

    public static RecommenderBuilder treeClusterRecommender(final ClusterSimilarity cs, final int n) throws TasteException {
        return new RecommenderBuilder() {
            @Override
            public Recommender buildRecommender(DataModel dataModel) throws TasteException {
                return new TreeClusteringRecommender(dataModel, cs, n);
            }
        };
    }

5). 構造算法評估模型

  public enum EVALUATOR {
        AVERAGE_ABSOLUTE_DIFFERENCE, RMS
    }

    public static RecommenderEvaluator buildEvaluator(EVALUATOR type) {
        switch (type) {
        case RMS:
            return new RMSRecommenderEvaluator();
        case AVERAGE_ABSOLUTE_DIFFERENCE:
        default:
            return new AverageAbsoluteDifferenceRecommenderEvaluator();
        }
    }

    public static void evaluate(EVALUATOR type, RecommenderBuilder rb, DataModelBuilder mb, DataModel dm, double trainPt) throws TasteException {
        System.out.printf("%s Evaluater Score:%s\n", type.toString(), buildEvaluator(type).evaluate(rb, mb, dm, trainPt, 1.0));
    }

    public static void evaluate(RecommenderEvaluator re, RecommenderBuilder rb, DataModelBuilder mb, DataModel dm, double trainPt) throws TasteException {
        System.out.printf("Evaluater Score:%s\n", re.evaluate(rb, mb, dm, trainPt, 1.0));
    }

    /**
     * statsEvaluator
     */
    public static void statsEvaluator(RecommenderBuilder rb, DataModelBuilder mb, DataModel m, int topn) throws TasteException {
        RecommenderIRStatsEvaluator evaluator = new GenericRecommenderIRStatsEvaluator();
        IRStatistics stats = evaluator.evaluate(rb, mb, m, null, topn, GenericRecommenderIRStatsEvaluator.CHOOSE_THRESHOLD, 1.0);
        // System.out.printf("Recommender IR Evaluator: %s\n", stats);
        System.out.printf("Recommender IR Evaluator: [Precision:%s,Recall:%s]\n", stats.getPrecision(), stats.getRecall());
    }

6). 推薦結果輸出

     public static void showItems(long uid, List recommendations, boolean skip) {
        if (!skip || recommendations.size() > 0) {
            System.out.printf("uid:%s,", uid);
            for (RecommendedItem recommendation : recommendations) {
                System.out.printf("(%s,%f)", recommendation.getItemID(), recommendation.getValue());
            }
            System.out.println();
        }
    }

7). 完整源代碼文件及使用樣例：
https://github.com/bsspirit/maven_mahout_template/tree/mahout-0.8/src/main/java/org/conan/mymahout/recommendation/job

轉載請注明出處：
http://blog.fens.me/mahout-recommend-engine/

本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1403343883293.html

Mahout 推薦引擎

從源代碼剖析Mahout推薦引擎

1. Mahout推薦引擎概況

2. 標準化的程序開發過程

3. 數據模型

4. 相似度算法工具集

5. 近鄰算法工具集

6. 推薦算法工具集

7. 創建自己的推薦引擎構造器

相關經驗

相關資訊

相關文檔

目錄