Word2VEC中distance函数的优化

[siegfang]

Word2VEC.distrance函数的作用是查找与某最相近的若干词，通过遍历词表中的所有词，并不断查找和替换相似度最小的词，最后使用TreeSet进行排序，我的方法是直接使用TreeSet进行排序，每次同样去除相似度最小的词，性能上要快1毫秒，具体如下：

public Set<WordEntry> similar(String queryWord){

    float[] center = wordMap.get(queryWord);
    if (center == null){
        return Collections.emptySet();
    }

    int resultSize = wordMap.size() < topNSize ? wordMap.size() : topNSize;
    TreeSet<WordEntry> result = new TreeSet<WordEntry>();
    for (int i = 0; i < resultSize + 1; i++){
        result.add(new WordEntry("^_^", -Float.MAX_VALUE));
    }

    for (Map.Entry<String, float[]> entry : wordMap.entrySet()){
        float[] vector = entry.getValue();
        float dist = 0;
        for (int i = 0; i < vector.length; i++){
            dist += center[i] * vector[i];
        }
        result.add(new WordEntry(entry.getKey(), dist));
        result.pollLast();
    }
    result.pollFirst();

    return result;
}

最相似的词肯定是查询词queryWord自己，所以最后使用pollFirst去掉。

[ansjsun]

这么做。会导致 。。你的 result存储了所有的key。。。如果key很大。内存太 高。。。

还有

for (int i = 0; i < resultSize + 1; i++){ result.add(new WordEntry("^_^", -Float.MAX_VALUE)); }

这一段彻底没看懂。。。你觉得打个笑脸 jvm就会对你温柔点么？

于 2013年12月27日 14:47, siegfang 写道:

Word2VEC.distrance函数的作用是查找与某最相近的若干词，通过遍历词表中的 所有词，并不断查找和替换相似度最小的 词，最后使用TreeSet进行排序，我的 方法是直接使用TreeSet进行排序，每次同样去除相似度最小的词，性能上要快1 毫秒，具体 如下：

public Set similar(String queryWord){

 float[]  center  =  wordMap.get(queryWord);
 if  (center  ==  null){
     return  Collections.emptySet();
 }

 int  resultSize  =  wordMap.size()  <  topNSize  ?  wordMap.size()  :  topNSize;
 TreeSet<WordEntry>  result  =  new  TreeSet<WordEntry>();
 for  (int  i  =  0;  i  <  resultSize  +  1;  i++){
     result.add(new  WordEntry("^_^",  -Float.MAX_VALUE));
 }

 for  (Map.Entry<String,  float[]>  entry  :  wordMap.entrySet()){
     float[]  vector  =  entry.getValue();
     float  dist  =  0;
     for  (int  i  =  0;  i  <  vector.length;  i++){
         dist  +=  center[i]  *  vector[i];
     }
     result.add(new  WordEntry(entry.getKey(),  dist));
     result.pollLast();
 }
 result.pollFirst();

 return  result;

}

最相似的词肯定是查询_queryWord_自己，所以最后使用_pollFirst_去 掉。

— Reply to this email directly or view it on GitHub https://github.com/ansjsun/Word2VEC_java/issues/3.

[siegfang]

我调试查看了result最后的大小，每次都只有topNSize+1个，并没有存储所有的key。

for (int i = 0; i < resultSize + 1; i++){
    result.add(new WordEntry("^_^", -Float.MAX_VALUE));
}

这一句是预先向result存储元素，在之后都会被相似度更大的词所替换，这样result就已经有topNSize个元素了，之后不必判断的result的大小，有插入就直接去除相似度的最小值即可。

[ansjsun]

哦我看错了有个 result.pollLast();

[siegfang]

for (int i = 0; i < resultSize + 1; i++){
    result.add(new WordEntry("^_^", -Float.MAX_VALUE));
}

是做预先赋值的，否则result就是空集，之后就需要在遍历词表的每次循环中判断result的大小是否达到topNSize+1。加个笑脸^_^是觉得挺好玩的。嘿嘿~

[ansjsun]

是的。。开成许没注意 。。这个办法是不错的。。有一点不好的是resultSize>mapsize 的时候。最后几条数据是脏数据。。不过这个发生的概率不是很高

[siegfang]

resultSize会取topNSize和wordMap.size中较小的那个，也就是这段代码：

int resultSize = wordMap.size() < topNSize ? wordMap.size() : topNSize;

这样result中总是会将初始化的数据去除。

[ansjsun]

好吧。。:-)看来我错的不是一星半点。。最近不知道怎么了。。应该还有一个地方可以优化。我试试

[siegfang]

嗯嗯，analogy函数也是可以依照相同的方法进行优化的。

[ansjsun]

vec.distance(str) ; 调用100次 3428毫秒 vec.similar(str) ; 调用100次 3167毫秒 vec.newSimilar(str); 调用100次 2633毫秒

public Set newSimilar(String queryWord) {

    float[] center = wordMap.get(queryWord);
    if (center == null) {
        return Collections.emptySet();
    }

    int resultSize = wordMap.size() < topNSize ? wordMap.size() : topNSize;
    TreeSet<WordEntry> result = new TreeSet<WordEntry>();
    for (int i = 0; i < resultSize + 1; i++) {
        result.add(new WordEntry("^_^", -Float.MAX_VALUE));
    }

    double min = Float.MIN_VALUE ;
    for (Map.Entry<String, float[]> entry : wordMap.entrySet()) {
        float[] vector = entry.getValue();
        float dist = 0;
        for (int i = 0; i < vector.length; i++) {
            dist += center[i] * vector[i];
        }

        if(dist>min){
            result.add(new WordEntry(entry.getKey(), dist));
            result.pollLast();
            min = result.last().score ;
        }
    }
    result.pollFirst();

    return result;
}

[ansjsun]

但是最耗时的是 for (int i = 0; i < vector.length; i++) { dist += center[i] * vector[i]; }

这个 。。。

[ansjsun]

我tmd又错了。。。。貌似不是 相乘最耗时

[siegfang]

汗~时间测量本身会影响程序运行时间的。向量的点积几乎就是无法绕开的，或许可以用Hash做吧~

[ansjsun]

算了不带弄了。。最近不知道怎么了总出错。。要过年了心情无法平静。。。:-) 谢谢你的提议。