Mahout协同过滤框架Taste的源码分析(1)
问题导读：
1.Mahout如何优化内存开销？
2.Taste如何实现基于用户的推荐？
static/image/hrline/4.gif
Taste相关简介及使用参见协同过滤原理与Mahout实现
包结构
[*]Taste实现
org.apache.mahout.cf.taste
[*]common
公有类, 包括: 异常、数据刷新接口、权重常量
[*]eval
定义构造器接口, 类似于工厂模式
[*]model
定义数据模型接口
[*]transforms
定义数据转换的接口
[*]similarity
定义相似度算法的接口
[*]neighborhood
定义近邻算法的接口
[*]recommender
定义推荐算法的接口
[*]impl
基于单机内存的推荐流程实现
[*]hadoop
基于集群的分布式推荐流程实现
偏好
基本接口
偏好信息由用户ID、物品ID、偏好分值组成
public interface Preference {
long getUserID();
long getItemID();
float getValue();
void setValue(float value);
}
偏好数组// 对于偏好信息的存储
// 为了节省内存, Mahout没有直接采用数组
public interface PreferenceArray extends Cloneable, Serializable, Iterable<Preference> {
void setUserID(int i, long userID);
void setItemID(int i, long itemID);
void setValue(int i, float value);
}
具体实现-用户偏好信息public final class GenericUserPreferenceArray implements PreferenceArray {
private long id;
// 为节省内存, 使用数组存储
private final long[] ids;
private final float[] values;
@Override
public long getUserID(int i) {
return id;
}
@Override
public long getItemID(int i) {
return ids;
}
@Override
public void setItemID(int i, long itemID) {
ids = itemID;
}
}
具体实现-物品偏好信息// 与用户偏好信息数组的实现相同
public final class GenericItemPreferenceArray implements PreferenceArray {
private final long[] ids;
private long id;
private final float[] values;
@Override
public long getItemID(int i) {
return id;
}
@Override
public long getUserID(int i) {
return ids;
}
@Override
public void setUserID(int i, long userID) {
ids = userID;
}
}
内存问题
在 Java 中，一个对象占用的字节数 = 基本的8字节 + 基本数据类型所占的字节 + 对象引用所占的字节。
基本的8字节在 JVM 中，每个对象（数组除外）都有一个头，这个头有两个字，第一个字存储对象的一些标志位信息，如：锁标志位、经历了几次 gc 等信息；第二个字节是一个引用，指向这个类的信息。JVM 为这两个字留了8个字节的空间。这样一来的话，new Object() 就占用了8个字节，那怕它是个空对象。
基本数据类型byte/boolean 1bytes
char/short 2bytes
int/float 4bytes
double/long 8bytes
对象引用reference 4bytes
内存占用对比一个GenericPreference对象需要28字节, 其中userID用8字节, itemID用8字节, value用4字节, 还有基本的8字节。
Array of Preferences方式
基本8字节 + 一个Preference对象的28字节 + 4个空引用的12字节 = 48字节
PreferenceArray方式
基本8字节 + userID的8字节 + itemID的8字节 + value的4字节 = 28字节
数据基本接口// 用户偏好信息的压缩表示, 为各类推荐算法提供了对数据的高效访问
public interface DataModel extends Refreshable, Serializable {
// 用于计算的一些常用方法
LongPrimitiveIterator getUserIDs() throws TasteException;
PreferenceArray getPreferencesFromUser(long userID) throws TasteException;
FastIDSet getItemIDsFromUser(long userID) throws TasteException;
Float getPreferenceValue(long userID, long itemID) throws TasteException;
}
具体实现–基于内存public final class GenericDataModel extends AbstractDataModel {
// 存储用户标示, 物品标示, 偏好信息
private final long[] userIDs;
private final long[] itemIDs;
private final FastByIDMap<PreferenceArray> preferenceFromUsers;
public GenericDataModel(FastByIDMap<PreferenceArray> userData) {
......
}
}
具体实现–基于文件public class FileDataModel extends AbstractDataModel {
// 分隔符
private static final char[] DELIMIETERS = { ',', '\t' };
// 数据文件
private final File dataFile;
// 用于存储用户, 物品, 偏好信息
private DataModel delegate;
// 查找相同目录下的增量文件进行处理
// 增量文件格式要求第一个'.'符号前的名字相同
// 比如: /foo/data.txt.gz
// /foo/data.1.txt.gz, /foo/data.2.txt.gz
protected DataModel buildModel() throws IOException {
processFile()
}
// 逐行处理文件
// 将内容转换为PreferenceArray以便于构建GenericDataModel对象
// 要求文件格式为: userID,itemID[,preference[,timestamp]]
protected void processLine(String line, FastByIDMap<?> data,
FastByIDMap<FastByIDMap<Long>> timestamps, boolean fromPriorData) {
...
}
}
内存问题
Java自带的HashMap和HashSet占用内存较大, 因此Mahout对这两个常用的数据结构也做了为减少内存开销的精简实现。
FastIDSet的每个元素平均占14字节, 而HashSet而需要84字节；FastByIDMap的每个Entry占28字节, 而HashMap则需要84字节。改进如此显著的原因在于:
* 和HashMap一样, FastByIDMap也是基于hash的。不过FastByIDMap使用的是线性探测来解决hash冲突, 而不是分割链；* FastByIDMap的key和值都是long类型, 而不是Object, 这是基于节省内存开销和改善性能所作的改良；* FastByIDMap类似于一个缓存区, 它有一个maximum size的概念, 当我们添加一个新元素的时候, 如果超过了这个size, 那些使用不频繁的元素就会被移除。
相似度基本接口推测用户对某个物品的偏好public interface PreferenceInferrer extends Refreshable {
float inferPreference(long userID, long itemID) throws TasteException;
}
用户相似度public interface UserSimilarity extends Refreshable {
// 返回值范围 -1.0 ~ 1.0, Double.NaN表示相似度未知
double userSimilarity(long userID1, long userID2) throws TasteException;
// 设置PreferenceInferrer接口的实现类, 以用于推测偏好
void setPreferenceInferrer(PreferenceInferrer inferrer);
}
物品相似度public interface ItemSimilarity extends Refreshable {
// 返回值范围 -1.0 ~ 1.0, Double.NaN表示相似度未知
double itemSimilarity(long itemID1, long itemID2) throws TasteException;
double[] itemSimilarities(long itemID1, long[] itemID2s) throws TasteException;
long[] allSimilarItemIDs(long itemID) throws TasteException;
}
抽象类实现物品相似度的抽象类public abstract class AbstractItemSimilarity implements ItemSimilarity {
private final DataModel dataModel;
@Override
public long[] allSimilarItemIDs(long itemID) throws TasteException {
// 从dataModel中获取所有的物品
// 将相似度不为NaN的物品ID添加到返回数组中
FastIDSet allSimilarItemIDs = new FastIDSet();
LongPrimitiveIterator allItemIDs = dataModel.getItemIDs();
while (allItemIDs.hasNext()) {
long possiblySimilarItemID = allItemIDs.nextLong();
if (!Double.isNaN(itemSimilarity(itemID, possiblySimilarItemID))) {
allSimilarItemIDs.add(possiblySimilarItemID);
}
}
return allSimilarItemIDs.toArray();
}
}
实现用户、物品相似度的抽象类// 继承AbstractItemSimilarity使得该类可以计算物品相似度
// 实现UserSimilarity接口使得该类可以计算用户相似度
abstract class AbstractSimilarity extends AbstractItemSimilarity implements UserSimilarity {
// 是否考虑重叠部分对结果的影响
private final boolean weighted;
// 是否取标准差
private final boolean centerData;
@Override
public double userSimilarity(long userID1, long userID2) throws TasteException {
// 计算 count, sumXY, sumX2, sumY2, sumXYdiff2
// 然后调用computeResult获取相似度
......
}
@Override
public final double itemSimilarity(long itemID1, long itemID2) throws TasteException {
// 计算 count, sumXY, sumX2, sumY2, sumXYdiff2
// 然后调用computeResult获取相似度
......
}
// 具体在各个子类中实现
abstract double computeResult(int n, double sumXY, double sumX2, double sumY2, double sumXYdiff2);
}
具体实现欧几里得距离public final class EuclideanDistanceSimilarity extends AbstractSimilarity {
@Override
double computeResult(int n, double sumXY, double sumX2, double sumY2, double sumXYdiff2) {
// 这里对普通的欧式距离进行了修正
return 1.0 / (1.0 + Math.sqrt(sumXYdiff2) / Math.sqrt(n));
}
}
皮尔逊距离public final class PearsonCorrelationSimilarity extends AbstractSimilarity {
public PearsonCorrelationSimilarity(DataModel dataModel, Weighting weighting) throws TasteException {
// 取均值
super(dataModel, weighting, true);
}
@Override
double computeResult(int n, double sumXY, double sumX2, double sumY2, double sumXYdiff2) {
// 皮尔逊距离用于度量两个维度之间的线性相关性
// 统计学的意义为两个序列协方差与两者方差乘积的比值
if (n == 0) {
return Double.NaN;
}
double denominator = Math.sqrt(sumX2) * Math.sqrt(sumY2);
if (denominator == 0.0) {
return Double.NaN;
}
return sumXY / denominator;
}
}
邻居
基本接口// 用户邻居接口
public interface UserNeighborhood extends Refreshable {
// 需要根据用户ID给出其邻居用户的ID列表
long[] getUserNeighborhood(long userID) throws TasteException;
}
抽象类// 规定使用指定的相似度实现类从指定的数据模型中查找邻居用户
// getUserNeighborhood方法在继承者中实现
abstract class AbstractUserNeighborhood implements UserNeighborhood {
private final UserSimilarity userSimilarity;
private final DataModel dataModel;
}
具体实现基于个数public final class NearestNUserNeighborhood extends AbstractUserNeighborhood {
// 邻居个数
private final int n;
// 最小距离
private final double minSimilarity;
@Override
public long[] getUserNeighborhood(long userID) throws TasteException {
// 计算相似度, 返回TopN
......
}
}
基于距离public final class ThresholdUserNeighborhood extends AbstractUserNeighborhood {
// 距离门槛
private final double threshold;
@Override
public long[] getUserNeighborhood(long userID) throws TasteException {
// 遍历用户, 计算相似度, 返回大于门槛值的用户
......
}
}
基于内存public final class CachingUserNeighborhood implements UserNeighborhood {
// 使用一种计算邻居的实现
private final UserNeighborhood neighborhood;
// 存储用户的邻居
private final Cache<Long, long[]> neighborhoodCache;
public CachingUserNeighborhood(UserNeighborhood neighborhood, DataModel dataModel) throws TasteException {
this.neighborhood = neighborhood;
int maxCacheSize = dataModel.getNumUsers();
// 使用内部类实现邻居用户的计算
this.neighborhoodCache = new Cache<Long, long[]>(new NeighborhoodRetriever(neighborhood), maxCacheSize);
}
@Override
public long[] getUserNeighborhood(long userID) throws TasteException {
return neighborhoodCache.get(userID);
}
// 内部类
// 使用计算邻居的具体实现来实例化
private static final class NeighborhoodRetriever implements Retriever<Long, long[]> {
private final UserNeighborhood neighborhood;
private NeighborhoodRetriever(UserNeighborhood neighborhood) {
this.neighborhood = neighborhood;
}
@Override
public long[] get(Long key) throws TasteException {
return neighborhood.getUserNeighborhood(key);
}
}
}
推荐
基本接口推荐项// 定义了推荐项的基本属性
public interface RecommendedItem {
long getItemID();
float getValue();
}
推荐器// 定义了推荐器应提供的基本方法
public interface Recommender extends Refreshable {
List<RecommendedItem> recommend(long userID, int howMany) throws TasteException;
}
基于用户推荐// 基于用户推荐的接口
public interface UserBasedRecommender extends Recommender {
// 需要实现根据用户ID, 指定推荐数目来给用户提供推荐
long[] mostSimilarUserIDs(long userID, int howMany) throws TasteException;
}
基于物品推荐// 基于物品的推荐
public interface ItemBasedRecommender extends Recommender {
// 需要实现根据物品ID和指定推荐数量来给出推荐的物品
List<RecommendedItem> mostSimilarItems(long itemID, int howMany) throws TasteException;
}
抽象类public abstract class AbstractRecommender implements Recommender {
// 用于存储用户偏好信息的属性
private final DataModel dataModel;
}
具体实现基于用户
public class GenericUserBasedRecommender extends AbstractRecommender implements UserBasedRecommender {
// 用于计算相似度的属性
private final UserSimilarity similarity;
// 用于计算邻居用户的属性
private final UserNeighborhood neighborhood;
@Override
public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer) throws TasteException{
// 获取邻居用户
long[] theNeighborhood = neighborhood.getUserNeighborhood(userID);
// 从邻居用户中查找当前用户没有偏好信息的物品ID
FastIDSet allItemIDs = getAllOtherItems(theNeighborhood, userID);
// 定义一个对未评论物品计算估值的实现类
TopItems.Estimator<Long> estimator = new Estimator(userID, theNeighborhood);
// 对物品估值后返回TopN
List<RecommendedItem> topItems = TopItems.getTopItems(howMany, allItemIDs.iterator(), rescorer, estimator);
return topItems;
}
// 使用内部类计算估值
private final class Estimator implements TopItems.Estimator<Long> {
private final long theUserID;
private final long[] theNeighborhood;
Estimator(long theUserID, long[] theNeighborhood) {
this.theUserID = theUserID;
this.theNeighborhood = theNeighborhood;
}
@Override
public double estimate(Long itemID) throws TasteException {
return doEstimatePreference(theUserID, theNeighborhood, itemID);
}
}
// 计算估值的实现方法
protected float doEstimatePreference(long theUserID, long[] theNeighborhood, long itemID) throws TasteException {
DataModel dataModel = getDataModel();
double preference = 0.0;
double totalSimilarity = 0.0;
int count = 0;
// 遍历所有邻居用户
for (long userID : theNeighborhood) {
if (userID != theUserID) {
Float pref = dataModel.getPreferenceValue(userID, itemID);
if (pref != null) {
// 计算邻居用户与当前用户的相似度
double theSimilarity = similarity.userSimilarity(theUserID, userID);
if (!Double.isNaN(theSimilarity)) {
// 加权过程实现
preference += theSimilarity * pref;
totalSimilarity += theSimilarity;
count++;
}
}
}
}
if (count <= 1) {
return Float.NaN;
}
// 加权过程实现
float estimate = (float) (preference / totalSimilarity);
if (capper != null) {
estimate = capper.capEstimate(estimate);
}
return estimate;
}
}
引用：http://matrix-lisp.github.io/blo ... out-taste-source-1/
页:
[1]