Mahout中数据的存储方式

用意： 希望了解Mahout中数据的存储方式， 它如何避免java object带来的冗余开销。学完知识，要进行些实战
去分析数据。

花了些时间看了看Mahout的源码和官方资料，记录下自己的一些收获。文字写了很多， 有点啰嗦了， 但是这些东西都是我这段时间学习推荐系统的一些感悟，希望感兴趣的朋友可以耐心看看，指点指点。
一、Mahout内容补充
     1. Mahout本质上是一个开源的机器学习框架. http://mloss.org/software/ 有大量的机器学习开源框架, mahout也在其中.
     2. Hadoop是大象的意思, Mahout是骑象人的意思。 Mahout是Hadoop生态圈中的机器学习算法库. 它的所有算法都基于斯坦福大学的一篇论文"基于多核的Map-Reduce机器学习算法"(Map-Reduce for Machine Learning on Multicore) http://pan.baidu.com/s/1cMXzG。论文摘要提到，只要满足他们的统计查询模型(Statistic Query Model)的算法都可以写成多核Map-Reduce形式。

     3. Mahout由一系列jar包组成,包括推荐、分类以及聚类库, 数学操作库(例如线性代数，统计学)以及自定义的Java数据结构类(为了优化内存的使用)。
     如上篇博客所示, 挑取taste推荐系统库以及部分数学操作库和Java数据结构类既可以作为普通的jar包一样引入你的工程进行开发, 完全无需hadoop. 当然由于很多算法空间和时间都是平方级别以上的复杂度, 一台PC无法满足秒级别的业务需求, 但是它这个jar包特性方便我们在单机上进行小数据实验,而不用先纠结在hadoop的问题上.

二、主要内容
1. 充分地掌握推荐系统算法和数据结构内部实现.
2. 熟练地分析所有算法的空间和时间消耗并跑程序进行测试.
3. 选择合适的算法和数据结构, 进行10K级别的movielens数据实战, 并进行调参
4. 最终进行服务器性能测试, 测试内存消耗. 

     真实的数据是GB\TB甚至PB级别的, 例如Google Picasa中的照片级别是数十亿的, 每天都有上百万的新照片加入, 对它们进行聚类操作工作量巨大. 我们由于计算能力有限和考虑到学习曲线问题, 使用10K级别数据, 之后慢慢向上提升数据量。

三、知识准备
    在使用Mahout推荐系统之前, 首先应该熟悉user-based和item-based协同过滤, 基于内容的推荐以及SVD的基本思想. 可以参考https://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy2/的相关介绍.
     协同过滤的基本思路：以用户为中心的话, 每个人都是由一个物品集表示, 相同爱好越多的人将被分为一个圈子，这个圈子里面和你都比较亲近，当然也有亲近的差异。通过为每个用户推荐圈子里面最受欢迎的物品(通过亲近程度加权而来)。
     SVD的基本思路： 以音乐为例, 音乐有作曲家、专辑等大量属性, 但是更有价值的是作曲风格, 乐器等潜在的特征。通过挖掘这些潜在特征与音乐属性以及潜在特征与用户之间的关系, 最终获得最好的推荐。此外，SVD还能实现降维作用.
    基于内容的推荐：如果我们喜欢的是文章, 也可以通过文章的词语, 标题等来进行推荐.

四、Mahout库初探
【参考Mahout0.9 API, 预计2013年11月10日左右发布】https://builds.apache.org/job/Mahout-Quality/javadoc/ 
4.1 Mahout中和推荐系统相关内容有四个部分:
    Preference类: 表示每个用户或者物品的属性, 如{1: {2: 1.0, 3: 2.0}} 表示用户2和3分别对1进行了评价, 评分分别为1.0和2.0
    DataModel类: 表示所有的数据集合, 即Preference的聚合. DataModel可以是代码输入或者HTTP参数获取, 也可以从文件或者数据库中读取.
    Similarity类: 表示所有Preference两者之间的相似度, 所有的用户或者物品都通过Similarty建立起了联系, 所以这个是非常重要的, Similarity的选择和数据的类型有很大关系. Neighberhood记录每个用户或者物品相似的物品集, 方便后期调用.
    Recommender类: 表示推荐算法, 整个系统的核心。 如何使用前面的Preference, DataModel, Similarity以及Neigherhood都将结合在Recommender来来使用。 

一个优秀的推荐系统由以下五个部分构成:
    1. 高质量和高数量的数据. Garbage in, Garbage out.
    2. 高效存储的数据结构以及高效的数学运算库
    3. 优秀的算法架构和调参技术
    4. 优秀的架构设计, 防止数据的多次拷贝, 并且利于数据的更新和一致性.
    5. 优秀的用户体验和人机交互设计


我主要想了解一下Mahout中数据结构的设计方法以及算法设计. 
4.2 数据格式和相关函数API:
要玩数据的前提是, 先把数据搞到手, 常见的数据格式有两种, 非结构化数据和结构化数据. 结构化数据如文章, 图片, 未清晰的数据等, 这类数据的可用性不佳. 我们现在主要讲的是结构化数据, 如博客1所示, 按规范格式存在文件里面的数据以及代码生成的数据. 对于标准化的数据, 计算机将其加载到内存中成为In-memory数据, 往往将数据封装成为一个数据结构对象, 从而实现复用并提升可用性； 此外, 由于In-memory数据不持久, 文件表示方法单一, 往往使用数据库来保存数据, 方便动态访问以及更高级的结构化存储.
     下面介绍一下Mahout中提供给用户存储结构化数据的类：

     Class FileDataModel: 读取一个有分隔符的数据文件，分隔符仅支持tab和逗号(comma)。 
     数据格式： userID,itemID[,preference[,timestamp]]
     【要求：数据必须是2列或者4列；所有数据格式必须一致, 即分隔符数量一致；超过4列的数据, 空行以及以'#'开头的数据都会被忽略。】
     示例：如123,456或者123,456,3,129050099059 或者123,456,,129050099059。

     如果一个人只是看过某部电影, 则没有preference项, timestamp表示时间戳.  
     格式：preference自动解析为double类型; userID和itemID解析为longs类型, timestamp自动解析为longs, 但是可以通过重写readTimestampFromString(String)方法来自己解析.
     自定义读取方法: 重写processLine和 processLineWithoutID(String, FastByIDMap, FastByIDMap)
     文件格式：FileDataModel可以读取.zip和.gz格式的压缩包数据。

     Class MysqlJDBCModel: 读取数据库中的数据, 为了提升数据查询效率. userID和itemID不能为空, 两者均需要建立索引, 主键primary key为userID和itemID的composition. 在Mysql中, 需要使用BIGINT和FLOAT类型, 调整buffer和查询cache的大小, Mysql的Connector/J driver中的cachePreparedStatements需要设置为true.

     Class FileIDMigrator: 专门用于读取一系列的字符串并生成相应的MD5标识码在一个FastByIDMap(类似于Java SE中的HashMap中, 用途暂时不明确. 例如数据是一个电影名列表, 文件每行只有一个电影名, 那么FileIDMigrator将生成对应的MD5码。

【源码中的数据存储均由GenericDataModel和GenericBooleanPrefDataModel来存储. 】

它们提供一下的比较重要的方法:
getUserIDs: 获取所有用户的ID
getPreferencesFromUser: 获取某个用户对所有物品的评分.
getItemIDsFromUser: 获取某个用户评论过的所有物品.
getItemIDs: 获取所有物品的ID.
getPreferencesForItem: 获取某个物品的所有评分.
getPreferenceValue: 获取某个用户对某个物品的评分.
getPreferenceTime: 获取某个用户对某个物品的评分时间.
getNumItems: 获取所有的物品总数
getNumUsers: 获取所有的用户综述.
getNumUsersWithPreferenceFor 1 item 获取对某个item评论过的用户数目.
getNumUsersWithPreferenceFor 2 items 获取对两个items同时评论过的用户数目.
hasPreferenceValues: 判断是否有评分, 用于区分BooleanDataModel.
getMaxPreference: 最大评分
getMinPreference: 最小评分
setPreference 改变某个用户对某个物品的评分, 并不改变数据源的数据.
removePreference 去除某个用户对某个物品的评分, 并不改变数据源的数据. 

真实的数据存储在GenericDataModel的下面几个成员变量中, 下面介绍一下这些数据结构

private final long[] userIDs;

private final FastByIDMap preferenceFromUsers;

private final long[] itemIDs;

private final FastByIDMap preferenceForItems;

4.3  数据高效存储高效的数据结构
     下面介绍下Mahout节省内存的机制, 并介绍一些基本的内存消耗参数.
     Preference [找时间把右边这个java内存消耗图重画一下, 来源[3]http://algs4.cs.princeton.edu/14analysis/ 这本算法书网站做的是极好的, 各种java算法动态图]



     Preference不允许修改userID以及itemID, 如要删除部分数据, 只能通过修改value或者通过DataModel的removePreference方法来删除.
     存储Preference最理想的内存开销是20bytes(long为8bytes, float为4bytes, 8*2 + 4 = 20bytes), 由于object overhead(包括一个reference指针8bytes(64位为16bytes), 以及16bytes的其它开销), 由于20+24=44bytes, 不为8的倍数, 还需要4bytes的padding开销. 所以为了存储20bytes的数据使用了多大48bytes的内存, 140%的冗余. 
    如果是100M的数据, 将额外消耗2.8GBytes的内存, 这是巨大的浪费. 为此系统引入PreferenceItemArray和PreferenceUserArray来存储与某个物品或者用户有关的所有数据. 最终每个Preference仅需12*2 = 24bytes(由于一个数据需要存储两次). 比理想的20bytes只多了4bytes, 冗余度为20%. 

以PreferenceUserArray为例, 结构如下


    此外FastIDSets和FastMap使用线性查找而不是链式查找, 可以节约空间且避免使用Entry Object. 同时FastIDSet避免使用Map. 待深入了解. 
    总结: FastIDSet平均为每个成员消耗14bytes, FastByIDMap为每个entry消耗28bytes. GenericDataModel为每个Preference消耗28bytes. [后面会使用System.gc(), Runtime.totalMemory()和Runtime.freeMemory()方法来进行内存消耗的测试]
此外: 系统需要保存一个相似矩阵, 相似矩阵或者Slope-One相似矩阵的空间复杂度上限为O(itemsNum**2) 或者O(usersNum**2).
4.4 更新数据
如何更新和删除数据?
如果标准数据为foo.txt.gz, 数据为1, 102, 4.0形式. 那么可以在foo.*.txt.gz中加入如下所示的数据
1, 108, 3.0 
1, 103, 
并使用recommender.refresh(null)来更新数据. [1, 108]数据项的value讲更新为3.0, 而[1, 103]数据项将会被删除.
此外, 为避免数据被频繁的更新, DataModel中有一个加载间隔时间参数delta.

 

http://blog.sina.com.cn/s/blog_86dad8bb0101pzfy.html