问题导读:
1.Mahout如何优化内存开销?
2.Taste如何实现基于用户的推荐?
Taste
包结构- Taste实现
org.apache.mahout.cf.taste
- common
公有类, 包括: 异常、数据刷新接口、权重常量
偏好
基本接口
偏好信息由用户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[i];
- }
-
- @Override
- public void setItemID(int i, long itemID) {
- ids[i] = 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[i];
- }
-
- @Override
- public void setUserID(int i, long userID) {
- ids[i] = userID;
- }
- }
复制代码
内存问题
在 Java 中,一个对象占用的字节数 = 基本的8字节 + 基本数据类型所占的字节 + 对象引用所占的字节。
基本的8字节在 JVM 中,每个对象(数组除外)都有一个头,这个头有两个字,第一个字存储对象的一些标志位信息,如:锁标志位、经历了几次 gc 等信息;第二个字节是一个引用,指向这个类的信息。JVM 为这两个字留了8个字节的空间。这样一来的话,new Object() 就占用了8个字节,那怕它是个空对象。
基本数据类型- byte/boolean 1bytes
- char/short 2bytes
- int/float 4bytes
- double/long 8bytes
复制代码
对象引用复制代码
内存占用对比一个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/
|