关于VSM性能优化的思考🤔

作者: gunjianpan | 来源:发表于2018-11-15 00:29 被阅读20次

blog可能排版更好点

Github

Update 一下

跟室友讨论了一下才发现有一些我以为很理所应当的点才是优化的关键 ~~（当然你们看我的code应该也能看出来只是没点明白）~~

Optimize Point

不要试图去开大数据量的二维数组

一旦你初始化一个3k✖️3k的数据你就会发现即使你只是读一下这个数组就会死慢死慢还要频繁写入效率可想而知
正确的姿势应该是开一个一维的数组然后每次存入一个3k数组的Index
这么做是有道理的
- 首先实际数组相对于动态开起来的
- 然后我们存在一维数组里的实际上是Index值这个会快很多
- 而且存进去的数组是Immutable-不(可)更改的不需要update 这个又会快很多
- 于是乎这就是第一个bonus Ponit

要用Numpy的矩阵乘法 🙅不要手写

虽然我不知道它的内部实现机理但真的很快
快到瞠目结舌 3k✖️6w的矩阵相乘 10s不到
这我3k✖️3k遍历一遍就要1min

可以考虑动态对齐词矩阵降低词向量维数

目前我们是按所有文章中词向量维数为所有词向量的长度大约6w维
如果按每个article为粒度用动态对齐的方式可以省很多空间
我之所以没这么干
- 因为我tf做了smooth操作所有零项不能简单的补零复杂度较高
- 然后动态补零就不能用numpy的矩阵乘法就很伤

另外就是通过开线程实现加速操作

剩下的看代码应该就会懂得 ~~（这样应该干货多了吧）~~

然后吕同学提的预处理的问题挺好的词性确实很重要

做了个小统计发现整个词袋里面有5477个词有多重词性的高等词还有8个词性 so 呢

VSM很简单但hand write起来还是会有一些问题的

Preproccess

额我们拿到的文本虽然已经分词好了但并不是很能用

所以我们需要预处理

对于这种文本的预处理 shell是最好的选择 ~~(不是php 手动滑稽)~~

shell 或者说bash脚本性能对于这种文本处理基本上是秒级的

image

可以看出好像前面15位的代表ArticleId 属于同一个文章

然后虽然分词过了但有很多分隔符什么/ n, / c, / vn

本来我是想枚举的但发现好像26个字母都有真的恐怖

然后不只有这些还有中文标点什么《》, （）的也得去掉

然后整理一下就变成了

image

性能方面虽然没打时间但基本上秒级

附上code

# @Author: gunjianpan
# @Date:   2018-11-11 19:11:19
# @Last Modified by:   gunjianpan
# @Last Modified time: 2018-11-11 20:26:47

cp data.txt test
# Set Tag Where File End
echo '1' >> test

# According article to jonit string
# @1: Remove blank lines
# @2: split by ‘/x’ or ‘/xx’
#     then, jonit string until into another article(recognition by $1)
# @return: Plain text which one plain one artile
sed - n '/./p' test | awk '{split($0,a,"/. |/.. ");b="";for(i=3;i<length(a);i++){b=b" "a[i];}if(!last||last==substr($1,0,15)){total=total""b;}else{print substr(total,2);total=b;}last=substr($1,0,15)}' >> test2

# Remove Chinese punctuation
# @1: replace punctuation Chinese or English to blank
# @2: replace mutil-blank to one-blank
sed 's/[；：，。（）？！《》【】{}“”、——;:,.()?!_]/ /g' test2 | sed 's/[ ][ ]*/ /g' >> test3

VSM

VSM分三步

词长度对齐
TF - IDF（考虑平滑, similarity 方式）
one by one calaulate

思路很简单

我一开始觉得 TF - IDF计算需要针对每个(article1, article2)进行计算

因为需要对齐而且最关键要平滑

如果有个词article1没有，article2也没有如何计算tf的时候因为进行平滑处理就会占一定比例这对于那些高词频的 word就不太友好

于是我第一版就一个个遍历过去 3100✖️3100 （见VSM.vsmCalculate()）

看起来没啥乘起来就是500w

初始化数组就要1min

于是开了两级多线程

每行为一个线程
每行里面每组similarity计算为一个线程

但效果很差因为那么多个线程争夺写一个3100✖️3100的numpy.Array 出现了写阻塞现象

通过Activity Monitor观察实际上线程数只有5.6左右

把numpy.Array换成list 发现效率高了一点还是不行

于是想能不能不同时争夺写一个list 直接每一行维护一个list 直接写文件

发现效率提高很多基本上1s能处理500个数据

那500w需要3h+

于是牺牲一下精确度先按词袋里所有词对齐词向量（见VSM.vsmTest()）

如何先生成3100篇文章的词向量组（tf - idf之后）

再做一次 A.dot(A.T)就可以得到结果

实际效果总耗时215s 约3min 效果较好

然后一次误输出发现内存中的中间状态数组已经到了4.3G

~~额内存小的同学可能就比较尴尬了~~

image

关于隐语义等考完试再来弄

之前写过一篇关于时序分析相关内容RNN家族的blog

# -*- coding: utf-8 -*-
# @Author: gunjianpan
# @Date:   2018-11-11 20:27:41
# @Last Modified by:   gunjianpan
# @Last Modified time: 2018-11-13 01:07:16

import math
import numpy as np
import pandas as pd
import threading
import time


class VSM():
  """
  handle write vsm 🙉
  """

  def __init__(self):
    self.articleMaps = []
    self.articleNum = 0
    self.process = 0
    self.resultArray = []
    self.wordMaps = {}
    self.preData()

  def preData(self):
    """
    data prepare
    """
    begin_time()
    file_d = open('test3', 'r')
    articles = file_d.readlines()
    threadings = []
    self.articleNum = len(articles)
    self.articleMaps = [None for i in range(self.articleNum)]
    self.resultArray = [None for i in range(self.articleNum)]
    for index in range(self.articleNum):
      work = threading.Thread(target=self.preDataBasic, args=(
          articles[index].strip('\n').rstrip(), index,))
      threadings.append(work)
    for work in threadings:
      work.start()
    for work in threadings:
      work.join()
    end_time()

  def preDataBasic(self, article, articleId):
    """
    prepare data basic in Threading
    @param article: article string
    @param articleId: article id
    """
    words = article.split(' ')
    wordMap = {}
    for word in words:
      if word in wordMap:
        wordMap[word] = wordMap[word] + 1
      else:
        wordMap[word] = 1
    for word in wordMap:
      if word in self.wordMaps:
        self.wordMaps[word] = self.wordMaps[word] + 1
      else:
        self.wordMaps[word] = 1
    self.articleMaps[articleId] = wordMap

  def tfidfTest(self, wordMap):
    """
    calculate tdidf value
    td use Augmented Frequency 0.5 + 0.5 * fre/maxFre
    """

    wordlist = [wordMap[i] for i in [*wordMap]]
    maxFrequency = max(wordlist)
    tf = np.array([0.5 + 0.5 * index / maxFrequency for index in wordlist])
    idf = np.array([math.log(self.articleNum / self.wordMaps[word])
                    for word in [*wordMap]])
    tfidf = tf * idf
    return tfidf

  def tfidf(self, wordMap):
    """
    calculate tdidf value
    td use Augmented Frequency 0.5 + 0.5 * fre/maxFre
    """

    wordlist = [wordMap[i] for i in [*wordMap]]
    maxFrequency = max(wordlist)
    tf = np.array([0.5 + 0.5 * index / maxFrequency for index in wordlist])
    idf = np.array([math.log(self.articleNum / (1 + self.wordMaps[word]))
                    for word in [*wordMap]])
    tfidf = tf * idf
    return tfidf / np.linalg.norm(tfidf, ord=2)

  def preSimilarity(self, wordMap, index):
    """
    align map and then calculate one tfidf
    """
    tempMap = {
        index: wordMap[index] if index in wordMap else 0 for index in self.wordMaps}
    preMap = {**wordMap, **tempMap}
    self.resultArray[index] = self.tfidf(preMap)
    self.process += 1
    if not self.process % 100:
      print(self.process)

  def vsmTest(self):
    """
    once to calaulate vsm
    """
    begin_time()
    threadings = []
    for index in range(self.articleNum):
      work = threading.Thread(target=self.preSimilarity, args=(
          self.articleMaps[index], index,))
      threadings.append(work)
    for work in threadings:
      work.start()
    for work in threadings:
      work.join()
    tempMatrix = np.array(self.resultArray)
    result = tempMatrix.dot(tempMatrix.T)
    df = pd.DataFrame(result)
    df.to_csv("vsm1.csv", header=False)
    end_time()

  def preSimilarityTest(self, wordMap1, wordMap2):
    """
    align map and then calculate one tfidf
    """
    tempMap1 = {
        index: wordMap1[index] if index in wordMap1 else 0 for index in wordMap2}
    preMap1 = {**wordMap1, **tempMap1}
    return self.tfidfTest(preMap1)

  def similarity(self, wordMap1, wordMap2, types):
    """
    calculate similarity by cos distance
    @Param types: distance calculate type
                =0 Cos Distance
                =1 Chebyshev Distance
                =2 Manhattan Distance
                =3 Euclidean Distance
    """
    tfidf1 = self.preSimilarityTest(wordMap1, wordMap2)
    tfidf2 = self.preSimilarityTest(wordMap2, wordMap1)
    if not types:
      return np.dot(tfidf1, tfidf2) / (np.linalg.norm(tfidf1, ord=2) * np.linalg.norm(tfidf2, ord=2))
    elif types == 1:
      return np.abs(tfidf1 - tfidf2).max()
    elif types == 2:
      return np.sum(np.abs(tfidf1 - tfidf2))
    elif types == 3:
      return np.linalg.norm(tfidf1 - tfidf2)
    else:
      return np.shape(np.nonzero(tfidf1 - tfidf2)[0])[0]

  def vsmCalculate(self):
    """
    calculate vsm
    """
    #: todo write block
    begin_time()
    threadings = []
    for index1 in range(self.articleNum):
      work = threading.Thread(target=self.vsmThread, args=(index1,))
      threadings.append(work)
    for work in threadings:
      work.start()
    for work in threadings:
      work.join()
    end_time()

  def vsmThread(self, index1):
    """
    vsm threading
    """
    nowarticle = self.articleMaps[index1]
    tempResult = []
    for index2 in range(index1, self.articleNum):
      tempResult.append(self.vsmPre(
          nowarticle, self.articleMaps[index2]))

    df = pd.DataFrame({index1: tempResult})
    df.to_csv('vsm.csv', mode='a', header=False)

  def vsmPre(self, wordMap1, wordMap2):
    """
    load data to result
    prevent read block
    """

    self.process += 1
    if not self.process % 100:
      print(self.process)
    return self.similarity(wordMap1, wordMap2, 0)


start = 0


def begin_time():
  global start
  start = time.time()


def end_time():
  print(time.time() - start)

祝大家考试顺利🙏

关于VSM性能优化的思考🤔

Optimize Point

Preproccess

VSM

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读