`
wangzjie
  • 浏览: 74563 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

MapReduce在相似度计算中的应用及优化

阅读更多

需求:计算用户的相似度,有用户列表U和特征列表F以及用户和特征的关系<U,F>。 根据<U1,Fn> ∩ <U2, Fm>的交集数来判断U1和U2的相似度。

解决方法:

一、用户维度的Join

最暴力低效的方法,因为用户量一般很大,所以join效率极低。一般不考虑。

二、特征维度

将用户对特征的矩阵转成特征对用户的矩阵。

1、转成特征对用户的矩阵:F1->U1...Un  

map: context.write(F, U)

reduce: context.write(F,List<U>)

2、计算相似度

各种解决方案如下:

(1)直接输出UxUy pair(IO密集型)

map:  将user list拆成各user pair对并输出,具体如下所示范例(代码只是伪码):

String data[] = value.toSting().split("\t");
String users[] = data[1].split(",");//user间以,分隔
for(int i = 0; i < users.length; i ++){
    for(int j = i + 1; j < users.length; j ++){
        //判断users[i]与users[j]的大小
        context.write(users[i]+"_"+users[j], 1);//这里要加上users[i]与users[j]大小的判断,小放前,大放后,便于后面的操作
    }
}

 

reduce: 对每个user pair的value list进行求和,即是这两个用户的相似度

缺点:map端输出的user pair很多(O(N*N)),使reducer的shuffle成为瓶颈

(2)按各user进行聚合(计算密集型)

<u1,u3,u5,u2>,按(1)的输出是<u1_u3-->1>,  <u1_u5-->1>,  <u1_u2-->1>, <u3_u5-->1>, <u3_u2-->1>,<u5_u2-->1>。  (1是次数)

按user聚合的结果是:<u1-->u2,u3,u5> ,<u2-->u3,u5>,<u3-->u5>,输出数为N(U)-1。

该方案需要对user list进行排序,便于后面reduce进行按userid聚合,如一个user list输出的是<u1-->u2,u3,u5>,另一个是<u1-->u3,u5>,这样reduce时就是u1->u2,u3,u5,u3,u5。

而如果不排序的话就需要再弄一个job进行操作:如<u1-->u2,u3,u5>, <u2-->u1,u3,u5> 。 这样会得到<u1_u2>与<u2_u1>,还需要job进行一次合并求和处理。

mapper:

StringBuilder uuidListStr = new StringBuilder();
String data[] = value.toString().split("\t");
String uuidArr[] = data[1].split(",");
Arrays.sort(uuidArr);
for(int i = 0; i < uuidArr.length; i ++){
    for(int j = i + 1; j < uuidArr.length; j ++){
        uuidListStr.append(uuidArr[j]).append(",");
    }
    if(uuidListStr.length() > 0){
        uuidListStr.deleteCharAt(uuidListStr.length() - 1);
        context.write(new Text(uuidArr[i]), new Text(uuidListStr.toString()));
        uuidListStr = new StringBuilder();
    }
}

 

reduce: 会得到u1->u2,u3,u5,u3,u5,  计算values中各用户出现的个数<ux,count>, 然后输出count>即可

//利用hashMap来管理各user的次数
Map<String, Integer> countMap = new HashMap<String, Integer>();
for (Text v : values) { //每个v都是u1,u2,u3这样的形式
    uuids = v.toString().split(",");
    for (int i = 0; i < uuids.length; i++) {
        uuid = uuids[i];
        tmp = countMap.get(uuid);
        if (null == tmp) {
            countMap.put(uuid, new Integer(1));
        } else {
            countMap.put(uuid, tmp + 1);
        }
    }
}
for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
    context.write(new Text(key.toString() + "_" + entry.getKey()), new IntWritable(entry.getValue()));
}

 

该方案有个瓶颈是map中自己实现的排序,可能某个F下用户数特别大,会造成数据倾斜,有的user list特别大,排序花费时间长,导致整个任务变慢(计算密集型)。一种思路是将splitSize变小,如从默认的64M变成8M,这样InputSplit数将变多,即Mapper变多,各个Mapper处理的数据量变小,充分发挥并行的优势。

具体设置splitSize的代码:

//splitSize = max(minSize, min(maxSize, blockSize))
conf.set("mapred.min.split.size", 8 * 1024 * 1024 + "");
conf.set("mapred.max.split.size", 8 * 1024 * 1024 + "");

 

(3)排序放到Reducer端

在转置特征对用户的矩阵的job中reduce已经得到了各F的user list,则可以直接对user list进行排序并输出按user聚合的结果。

a、reduce方法中对user list进行排序

会遇到和(2)方案中一样的数据倾斜问题,且无法像(2)那样减少splitSize来减少各Mapper的处理数据量,增大Mapper数。 该方案一般会作死,数据量大时不用考虑。

b、利用Reducer的Sort功能

需要覆盖的类:

需要覆盖的类:

MapOutputKey:其中的compareTo用于map/reduce各阶段进行排序的依据

Partitioner: 用于partition分到哪个区

GroupingComparator:用于reduce的sort-->reduce中 key迭代时的分组。

 

Reducer的各阶段为:Shuffle/Merge,  Sort, Reduce, Output。其中Sort与Reduce是并行的。Sort迭代遍历得到的记录会进行grouping,从而得到reduce方法中的values。

Sort会将各文件按Key(MapOutputKey)的大小建最小堆,每取一个最小Key的记录, 都会到GroupingComparator进行判断(具体源码没研究,不过这里面的实现应该是会保存上一个记录的Key, 如果当前记录与上一Key 通过GroupingComparator方法得到的结果是一样的话,则把当前记录加到group的记录列表中,该列表元素顺序是按插入顺序的;如果不一样的话,就将Key以前列表的数据传到reduce方法,并清空group的记录列表)

我们可以创建自己的MapOutputKey

public class GeoMapOutputKey implements Writable,WritableComparable<GeoMapOutputKey> {
    private Text geohash = new Text();//相当于Feature
    private Text uuid = new Text();  //相当于user
    public GeoMapOutputKey(){}
    public GeoMapOutputKey(String geohash, String uuid){
        this.geohash.set(geohash);
        this.uuid.set(uuid);
    }
    public Text getGeohash() {
        return geohash;
    }
    public void setGeohash(Text geohash) {
        this.geohash = geohash;
    }
    public Text getUuid() {
        return uuid;
    }
    public void setUuid(Text uuid) {
        this.uuid = uuid;
    }
    @Override
    public void write(DataOutput dataOutput) throws IOException {
        geohash.write(dataOutput);
        uuid.write(dataOutput);
    }
    @Override
    public void readFields(DataInput dataInput) throws IOException {
        geohash.readFields(dataInput);
        uuid.readFields(dataInput);
    }
    @Override
    //重点是这个compareTo方法,会先根据geohash进行排序,再根据uuid进行排序
    public int compareTo(GeoMapOutputKey o) {
        int compareValue = this.geohash.compareTo(o.geohash);
        if(compareValue == 0){
            compareValue = this.uuid.compareTo(o.uuid);
        }
        return compareValue;
    }
    @Override
    public int hashCode() {
        return geohash.hashCode() * 163 + uuid.hashCode() * 163;
    }
    @Override
    public boolean equals(Object o) {
        if (o instanceof GeoMapOutputKey) {
            GeoMapOutputKey ok = (GeoMapOutputKey) o;
            return geohash.equals(ok.getGeohash()) && uuid.equals(ok.getUuid());
        }
        return false;
    }
    @Override
    public String toString() {
        return geohash + "\t" + uuid;
    }
}

 

通过这个GeoMapOutputKey,就可以保存先按Feature进行排序,再按user进行排序。(map输出有N行记录,Reducer默认情况下也要对这N行记录进行compare,所以性能没有什么影响)。

Mapper的map阶段的输出会调用Partitioner方法进行决定分区,默认情况下会按feature+user进行分区,我们需要按Feature进行分区,所以要覆盖:

public class GeoPartitioner extends Partitioner<GeoMapOutputKey, Text> {
    @Override
    public int getPartition(GeoMapOutputKey geoMapOutputKey, Text text, int numPartitions) {
   //这里的geohash就是feature
        return Math.abs(geoMapOutputKey.getGeohash().hashCode()) % numPartitions;
    }
}

 

默认情况下Reducer的GroupingComparator会按Key进行grouping聚合操作,这样reduce方法中的key就是feature_u1这样的,没多大帮助,所以我们要自定义GroupingComparator,让相同feature的聚合在一起,即reduce方法中的key是feature。

public class GeoGroupingComparator extends WritableComparator {
    protected GeoGroupingComparator() {
        super(GeoMapOutputKey.class, true);
    }
    @Override
    public int compare(WritableComparable a, WritableComparable b) {
        GeoMapOutputKey ok1 = (GeoMapOutputKey) a;
        GeoMapOutputKey ok2 = (GeoMapOutputKey) b;
        //这里只对feature进行比较,即会按feature进行grouping聚合
        return ok1.getGeohash().compareTo(ok2.getGeohash());
    }
}

 

设置这两个类的代码:

job.setMapOutputKeyClass(GeoMapOutputKey.class);
job.setGroupingComparatorClass(GeoGroupingComparator.class);

 

通过这样的设置,就可以实现Sort最小堆是按先feature再user进行排序,而聚合时又是按feature进行聚合。

reduce中的key是<F,u1>,<F,u2>,<F,u5>中的某一个(第一个?),value是<u1,u2,u5>

这个job的输出是U1–>u2,u3,u5这样的形式。下一个job的mapper只要context("u1","u2,u3,u5"),而reducer和(2)中的reducer操作一样。

 

第(3)种方案是最优的,处理速度比前面的高效很多。

分享到:
评论

相关推荐

    Hadoop在相似度计算中的优化_林述民

    ### Hadoop在相似度计算中的优化 #### 一、引言 随着大数据时代的到来,海量数据的处理成为了各个领域面临的重大挑战。Hadoop作为一种分布式计算框架,在处理大规模数据集方面表现出色。本文将探讨Hadoop如何应用于...

    基于MapReduce实现的TFIDF计算

    这种方法对于搜索引擎的排名、文本相似度计算以及信息检索等应用非常有用。在实际项目中,可能会使用Hadoop或者其他支持MapReduce的框架来实现这个过程。 总结来说,基于MapReduce的TF-IDF计算是一个将分布式计算与...

    云计算-旅游数据关联化及语义相似度计算并行化研究与实现.pdf

    "云计算-旅游数据关联化及语义相似度计算并行化研究与实现"这篇论文关注的是如何利用云计算技术解决旅游行业中的数据孤岛问题,提高数据的复用和共享效率。 首先,论文强调了旅游数据的关联化。旅游信息系统的多样...

    python hadoop mapreduce 相似用户|mapreduce.rar

    由于数据量可能很大,因此在实际操作中可能需要优化算法,比如使用近似算法或采样方法来降低计算复杂性。 为了提高代码的效率和可读性,可以使用Python的pyspark库,它是Apache Spark的Python接口,支持分布式计算...

    大数据技术分享 Hadoop技术分享 Hadoop在反作弊中的应用 案例分享:应用MR计算用户相似度 共31页.pdf

    此外,通过MR(MapReduce)计算用户相似度的案例分享,揭示了大数据分析在个性化推荐或广告投放优化中的实践。 Hadoop是Apache软件基金会开发的一个开源分布式计算框架,它允许在廉价硬件上存储和处理海量数据。在...

    Pairwise Document Similarity in Large Collections with MapReduce

    文档相似度计算在许多实际应用中都非常重要,如文献检索、信息检索系统、文本挖掘、推荐系统等。例如,在PubMed搜索引擎中,“更多类似此”的浏览功能就是通过预先计算文档之间的相似度得分来实现的。这种功能可以...

    KNN分类算法的MapReduce并行化实现1

    在KNN算法的MapReduce实现中,Map函数承担了计算任务的主要部分。对于每一个测试样本,Map函数会遍历所有的训练样本,计算它们之间的相似度(如欧氏距离、曼哈顿距离等)。由于计算量巨大,Map函数的并行化处理显著...

    基于MapReduce的商品推荐算法.zip

    本文将深入探讨MapReduce的原理以及其在商品推荐系统中的应用。 MapReduce是Google提出的一种分布式计算模型,它简化了大规模数据处理的过程,特别适合处理和生成大规模数据集。Map阶段将原始数据分片,并将分片...

    基于物品的协同过滤算法 (mapreduce)

    每对物品的相似度计算可以看作一个键值对,键是物品对,值是相似度分数。 3. **分发和并行计算**:由于MapReduce的并行特性,这个计算过程可以在多台机器上同时进行,大大提高了效率。Map任务将处理一部分数据,...

    基于MapReduce实现物品协同过滤算法(ItemCF).zip

    为了实现高效的ItemCF,还需要考虑如数据稀疏性、相似度计算的优化、内存管理和延迟问题等挑战。通过MapReduce,我们可以并行地处理这些问题,使得算法在大数据场景下仍能保持高效运行。 总之,“基于MapReduce实现...

    基于哈希技术和MapReduce的大数据集K-近邻算法实现代码

    在这个项目中,我们结合了哈希技术和MapReduce,以处理海量数据集上的KNN计算。首先,通过哈希函数对数据进行预处理,降低数据的维度,使得在Map阶段能更快地计算距离。接着,Map任务并行处理各个数据块,计算每个...

    MapReduce实现基于物品的协同过滤算法,即电影推荐系统.zip

    在实际应用中,还需要考虑性能优化,例如通过增加数据分区、调整缓存大小等方式提高处理效率。 总之,这个项目展示了如何利用Hadoop MapReduce的分布式计算能力,实现基于物品的协同过滤算法,从而构建一个电影推荐...

    用mapreduce计算框架实现了4个小demo wordcount、基于物品的推荐算法和基于用户的推荐算法

    6. **MapReduce在人工智能中的应用** 在AI领域,MapReduce常用于大规模机器学习任务,如训练深度学习模型、执行图像分类或自然语言处理。通过并行化计算,MapReduce大大加快了这些任务的处理速度,使其能够在有限...

    基于MapReduce实现物品协同过滤算法(ItemCF)

    5. **相似度计算**:在Reduce阶段,我们计算每对物品的相似度,这一步可能涉及到一些优化技巧,如采样或者Top-K策略,以减少计算量。 6. **推荐生成**:最后,对于每个用户,我们找出其已评分物品的相似物品,并...

    基于Java MapReduce实现物品协同过滤算法【100012582】

    在这个Java MapReduce实现中,我们关注的是基于物品的协同过滤,即不是寻找相似的用户,而是寻找相似的物品。具体步骤如下: 1. **数据预处理**:首先,我们需要收集用户对物品的评分数据。这通常是一个稀疏矩阵,...

    MapReduce基于物品的协同过滤算法实现电影推荐系统

    在实际应用中,为了提高推荐的准确性和效率,我们可能需要引入其他优化策略,如使用近似算法计算物品相似度,或者采用缓存机制减少重复计算。同时,推荐系统还需要考虑新鲜度、多样性等因素,以提供更全面的用户体验...

    用MapReduce实现KMeans算法

    在实际应用中,可能还需要考虑以下几点: - **迭代管理**:KMeans是一个迭代算法,需要多次运行MapReduce作业以达到收敛。这可以通过保存每次迭代的结果,然后在下一次迭代中作为输入来实现。 - **并行性和效率**:...

    基于Hadoop的MapReduce架构编写的KNN算法.zip

    针对这些问题,可以采取优化策略,如使用稀疏向量表示数据、采用更高效的相似度计算方法,以及通过采样或分层抽样减少计算量。 总结来说,基于Hadoop的MapReduce架构实现KNN算法,能够有效解决大数据环境下KNN计算...

Global site tag (gtag.js) - Google Analytics