Je voulais catégoriser les URL et j'ai essayé d'utiliser b-Bit Min Hash. Plus précisément, c'est pour faire ce qui suit. Lors du calcul de la probabilité CV de l'utilisateur en utilisant les informations de navigation sur le site extraites du cookie comme identité, le vecteur d'identité devient assez rare. Par conséquent, je voulais diviser l'URL en catégories et augmenter dans une certaine mesure la densité du vecteur d'identité. Pour cette raison, j'expérimente le titre.
Pour un aperçu de la méthode, voir blog de développement de SmartNews Je voudrais que vous vous référiez au [matériel de M. Okanohara] de PFI (http://research.preferred.jp/2011/02/minhash/) qui apparaît dans le texte. C'est beaucoup plus facile à comprendre que j'écris l'explication.
Donc, ici, je vais décrire brièvement la procédure d'écriture de code.
Voici le code que j'ai créé. Je l'ai fait en coupant et collant diverses choses, donc les règles de dénomination sont faussées. .. Comme d'habitude, il est écrit par une personne qui n'est pas un ingénieur, donc le code est assez disgracieux, mais il serait très utile que vous puissiez le lire avec un esprit large. ..
python
# coding: utf-8
import urllib2
from BeautifulSoup import BeautifulSoup, NavigableString, \
Declaration, Comment, BeautifulStoneSoup
import unicodedata
import chardet
from urlparse import urljoin
import sqlite3 as sqlite
import pickle
import SeparateWords as spw
#Liste de mots à ignorer
ignorewords = set(['the', 'of', 'to', 'and', 'a', 'in', 'is', 'it', '-', '/', '#', "'", '_', ',', '(', ')', '[', ']', '〜', '!', '|', '♪', '...', '>', '<', ':', '!!', '&', '/', '+', '*'])
#Liste des balises à reconnaître comme blocs
block_tags = frozenset(['p', 'div', 'table', 'dl', 'ul', 'ol', 'form', 'address',
'blockquote', 'h1', 'h2', 'h3', 'h4', 'h5', 'h6', 'fieldset',
'hr', 'pre' 'article', 'aside', 'dialog', 'figure',
'footer', 'header', 'legend', 'nav', 'section'])
class crawler:
#Initialisez le robot avec le nom de la base de données
def __init__(self, dbname):
self.dbname = dbname
self.con=sqlite.connect(dbname)
self.con.text_factory = str # utf-Spécifiez str pour utiliser 8
def __del__(self):
self.con.close()
def dbcommit(self):
self.con.commit()
#Indexer des pages individuelles
def addtoindex(self,url,category,wordlist):
if self.isindexed(url): return
print 'Indexing' + url
#Enregistrer la liste de mots dans la base de données pour chaque URL
self.con.execute( "insert into wordvector values(?,?,?,?)" , \
(url, category, pickle.dumps(wordlist), '') )
self.dbcommit()
def getNavigableStrings(self,soup):
#Déterminer si la soupe est un type qui contient du contenu
if isinstance(soup, NavigableString): #L'objet NavigableString a toutes les variables membres sauf le contenu et la chaîne
if type(soup) not in (Comment, Declaration):
yield soup
#Obtenir du texte s'il contient du contenu et n'est pas un code de programme
elif soup.name not in ('script', 'style'):
is_block = soup.name in block_tags #Confirmer l'existence de la balise de bloc
if is_block:
yield u'\n'
for c in soup.contents:
for g in self.getNavigableStrings(c):
yield replace_str(g)
if is_block:
yield u'\n'
#Renvoie ture si l'URL est déjà indexée
def isindexed(self,url):
u=self.con.execute \
("select words from wordvector where url='%s'" % url).fetchone()
if u!=None:
return True
return False
#Reçoit une liste de pages et effectue une recherche de largeur en premier à une profondeur donnée
#Indexer la page
def crawl(self,pages,category,depth=2):
for _ in xrange(depth):
newpages=set()
for page in pages:
try:
response=urllib2.urlopen(page).read()
except:
print "Could not open %s" % page
continue
en = chardet.detect(response)['encoding']
soup=BeautifulSoup(response.decode(en), #Convertir le code de caractère en fonction du site
convertEntities = BeautifulStoneSoup.HTML_ENTITIES) #Conversion de caractères des caractères spéciaux HTML
text = u''.join( self.getNavigableStrings(soup) )
text = normalizeText(text) #Normalisation des chaînes
words = spw.separateWords(text) #Obtenir un jeu de mots
self.addtoindex(page,category,words) # url, category,Enregistrer le jeu de mots dans DB
#Obtenez l'URL de la balise a pour une recherche plus profonde que 2
links=soup('a')
for link in links:
if ('href' in dict(link.attrs)):
url=urljoin(page,link['href'])
if url.find("'")!=-1: continue
url=url.split('#')[0] #Supprimer l'identifiant du fragment
if url[0:4]=='http' and not self.isindexed(url):
newpages.add(url)
pages=newpages
#Créer une table de base de données
def createindextables(self):
name = 'wordvector'
sql="SELECT name FROM sqlite_master WHERE type='table' AND name='MYTABLE';" \
.replace('MYTABLE', name)
res = self.con.execute(sql).fetchone()
if res is None:
self.con.execute('create table wordvector(url, category, words, hash_vector)')
self.con.execute('create index urlidx on wordvector(url)')
self.dbcommit()
else:
self.con.execute('drop table wordvector')
self.con.execute('create table wordvector(url, category, words, hash_vector)')
self.con.execute('create index urlidx on wordvector(url)')
self.dbcommit()
def nonEmptyLines(text):
"""Supprime les blancs inutiles et renvoie les lignes non vides"""
for line in text.splitlines():
line = u' '.join(line.split())
if line:
yield line
def normalizeText(text):
"""Supprimez les blancs et les sauts de ligne inutiles après la normalisation"""
Text = unicodedata. normalize ('NFKC', text) #Convertir la demi-largeur japonaise en pleine largeur+Alphabet,Le symbole est demi-largeur
return u'\n'.join(nonEmptyLines(text))
def replace_str(line):
return line.replace('&','&')
if __name__=='__main__':
fname = 'teacherURL.txt'
crawler=crawler('teacher.db')
crawler.createindextables()
with open(fname, 'r') as f:
for line in f:
s = line.strip().split('\t')
print s[0]
category = s[0]
pagelist = [s[1]]
crawler.crawl(pagelist, category, depth=1)
La partie qui extrait les mots du texte (spw.separateWords (text)) contient le code suivant.
python
# coding: utf-8
import MeCab
#Liste de mots à ignorer
ignorewords = set(['the', 'of', 'to', 'and', 'a', 'in', 'is', 'it', 'de'])
igonoresymbols = set(['-', '/', '#', "'", '_', ',', '(', ')', '[', ']',
'~', '!', '|', '♪', '...', '>', '<', ':', '!',
'&', '/', '+', '*', '【', '】', '（', '）', '！', '：', '-',
'＿', '？','%', '「', '」','～','.', '{', '}','"',
'＜', '＞', '／'])
def separateWords(text):
tagger = MeCab.Tagger('-Ochasen')
node = tagger.parseToNode(text.encode('utf-8'))
word_set = set([])
while node:
feat = node.feature.split(",")
if feat[0] == "nom" \
and (feat[1] == "Général"
or feat[1] == "Nomenclature propriétaire" or feat[1] == "Racine du verbe adjectif"):
#word = node.surface.decode(en)
word = node.surface
if word not in ignorewords:
word_set.add( word )
node = node.next
return word_set
Ensuite, créez une liste de hachage minimale pour les enseignants à partir de l'ensemble de mots acquis et décrivez la partie pour mettre à jour la base de données.
python
# coding: utf-8
import sqlite3 as sqlite
import pickle
import hashing
class CreateDB(object):
def __init__(self,dbname):
self.db = sqlite.connect(dbname)
self.db.text_factory = str # utf-Spécifiez str pour utiliser 8
self.hashing = hashing.Hashing()
def __del__(self):
self.db.close()
def db_commit(self):
self.db.commit()
def create_hashtable(self, url, wordlist):
hash_v = self.hashing.get_min_vector(wordlist)
self.update_vector(url, pickle.dumps(hash_v))
self.db_commit()
def update_vector(self,url,vector):
self.db.execute("update wordvector set hash_vector=? where url=?" , \
(vector, url))
if __name__=='__main__':
dbname = 'teachre.db'
c_db = CreateDB(dbname)
con = sqlite.connect(dbname) #Appelez la base de données dans laquelle le vecteur de mot est stocké
itr = 1
while True:
sql = "select * from wordvector where rowid=='%d'"
res = con.execute(sql % itr).fetchone()
print res
if res is None:break
url = res[0]; category = res[1]; wordlist = res[2]
c_db.create_hashtable(url, wordlist)
itr += 1
con.close()
La liste de hachage minimum est créée comme suit.
python
# coding: utf-8
import numpy as np
import mmh3
from multiprocessing import *
class Hashing(object):
'''
Le hachage est appliqué à l'ensemble de mots obtenu à chaque URL pour obtenir la valeur minimale.
Obtenez un vecteur k-dimensionnel pour chaque URL
Jugement de similitude en comparant ce vecteur k-dimensionnel
'''
def __init__(self,bbit=1,k=128):
self.bbit = bbit
self.hash_cnt = k
def get_min_vector(self,feat_names):
'''Cette fonction sera activée par URL'''
hash_vec = []
#Obtenez seulement le hachage minimum d'un ensemble de mots k fois
for seed in xrange(self.hash_cnt): # self.hash_Générer des semences pour cnt
pool = Pool(processes=8)
hash_val = pool.map( get_hash_value, ((feat_name, seed) for feat_name in feat_names) ) #Générer k fonctions de hachage en utilisant k graines
pool.close()
pool.join()
min_val = int( str( min(hash_val) )[-self.bbit] )
hash_vec.append(min_val) #Obtenez uniquement le premier chiffre de la valeur minimale
return hash_vec
def get_hash_value((feat_name,seed)):
return mmh3.hash(feat_name,seed)
À ce stade, les données de l'enseignant sont prêtes. De même, récupérez le mot défini pour l'apprenant et stockez-le dans la base de données.
Dans ce qui suit, MinHash est exécuté à l'aide de l'ensemble de mots acquis de l'apprenant et de la liste de hachage de l'enseignant créée. Ensuite, ajoutez une catégorie à l'URL de l'apprenant, mettez à jour la base de données et terminez. Le code est décrit ci-dessous.
python
# coding: utf-8
import numpy as np
import sqlite3 as sqlite
import hashing
import pickle
from multiprocessing import *
class MinHash(object):
def __init__(self,train_dbname,teacher_dbname):
self.train_db = sqlite.connect(train_dbname)
self.teacher_db = sqlite.connect(teacher_dbname)
self.hashing = hashing.Hashing() # default values are bbit=1, k=128
def __del__(self):
self.train_db.close()
self.teacher_db.close()
def db_commit(self):
self.train_db.commit()
def get_category(self):
learner_urls = self.get_urls(self.train_db)
teacher_urls = self.get_urls(self.teacher_db)
for lrnr_url in learner_urls:
print "computing hash vector:", lrnr_url[0]
learner_hash = self.calculate_hashvecotr( lrnr_url[0] )
print "calculating similarity:", lrnr_url[0]
learner_words = self.get_wordslist( self.train_db,lrnr_url[0] )
pool = Pool(processes=8)
sim = pool.map( similarity_value,
( (learner_words, self.get_wordslist( self.teacher_db,tchr_url[0] ),
learner_hash, self.get_hash_vector(tchr_url[0]))
for tchr_url in teacher_urls ) ) #Calcul de la similitude
pool.close()
pool.join()
sim = np.array(sim)
print "sim: ",sim
idx = np.where(sim==max(sim))[0][0]
sim_url = teacher_urls[idx][0]
category = self.get_similer_category( sim_url )
print "similar category of this URL is: ", category
self.update_category(category, sim_url)
def calculate_hashvecotr(self, url):
"""Mettre à jour la base de données d'origine lors de la création d'un vecteur de hachage"""
hash_vector = self.hashing.get_min_vector(
self.get_wordslist(self.train_db, url) )
self.train_db.execute( "update wordvector set hash_vector=? where url=?" ,
(url, pickle.dumps(hash_vector), ) ) #Économisez avec cornichon
self.db_commit()
return hash_vector
def update_category(self,category,url):
self.train_db.execute( "update wordvector set category=? where url=?" ,(category, url, ) )
self.db_commit()
def get_wordslist(self,db,url):
wordlist = db.execute( "select words from wordvector where url=?" , (url,) ).fetchone()[0]
return pickle.loads(wordlist)
def get_urls(self,db):
return db.execute("select url from wordvector").fetchall()
def get_similer_category(self,url):
return self.teacher_db.execute( "select category from wordvector where url=?" ,(url, ) ).fetchone()[0]
def get_hash_vector(self,url):
hash_v = self.teacher_db.execute( "select hash_vector from wordvector where url=?" , (url, ) ).fetchone()[0]
return pickle.loads(hash_v)
def similarity_value( (lrnr_words, teacher_words, lrnr_hash, teacher_hash) ):
try:
feat_dim = 1 << len(lrnr_hash)
C1, C2 = calculate_distribusion(lrnr_words, teacher_words, feat_dim)
jaccard = float( sum( np.array(lrnr_hash)==np.array(teacher_hash) ) ) \
/len(lrnr_hash) #Calcul de la similitude
return (jaccard-C1)/(1-C2)
except Exception, e:
import sys
import traceback
sys.stderr.write(traceback.format_exc())
def calculate_distribusion(lrnr_words, teacher_words, feat_dim):
all_words = lrnr_words | teacher_words
D = len(all_words); f1 = len(lrnr_words); f2 = len(teacher_words) #Une simple combinaison de deux ensembles de mots est considérée comme un ensemble de mots complet.
r1 = float(f1)/D; r2 = float(f2)/D; sum_r = r1 + r2
A1 = calc_A(r1, feat_dim); A2 = calc_A(r2,feat_dim)
C1 = A1*r2/sum_r + A2*r1/sum_r
C2 = A1*r1/sum_r + A2*r2/sum_r
return C1, C2
def calc_A(r, feat_dim):
A_num = r*(1-r)**(feat_dim-1)
A_denom = 1-(1-r)**feat_dim
return A_num/A_denom
if __name__=='__main__':
traindbname = 'learner.db'
teacherdbname = 'teacher.db'
minhash = MinHash(traindbname,teacherdbname)
minhash.get_category()
Comme vous pouvez le voir en lisant l'article, il est indispensable que D (taille de l'ensemble de mots) et k (type de fonction de hachage) soient suffisamment grands. Si ce n'est pas le cas, l'approximation ne tiendra pas et vous pourriez obtenir des valeurs étranges, alors soyez prudent. Dans le code ci-dessus, D est une combinaison de deux ensembles de mots, mais je l'ai fait simplement pour l'expérimentation. Lorsqu'il est réellement utilisé, définissez l'ensemble de mots sur D.
J'ai expérimenté dans les catégories de la finance, de l'économie et des sports (baseball, golf). Les mots utilisés dans les sports sont si différents entre baseball et golf qu'ils n'étaient pas bien catégorisés en termes de sports. S'il est utilisé dans la pratique, je pense qu'il est nécessaire de concevoir la catégorie elle-même. En passant, j'ai fait référence à projet de répertoire ouvert (ODP) lors de la création de la catégorie.
En ce qui concerne le temps de calcul, la création d'une liste de valeurs de hachage minimales est la plus longue. Pour le moment, j'essaye d'effectuer des traitements parallèles, mais j'ai toujours l'impression qu'un temps d'attente considérable va se produire. (Comme je ne pouvais pas me permettre de mesurer le temps moyen, je vais juste vous donner une impression.
De plus, bien que le hachage 32 bits soit utilisé dans le code ci-dessus, il est recommandé d'utiliser le hachage 64 bits. 64 bits est moins susceptible d'entrer en collision.
La méthode d'approximation utilisée dans MinHash est d'abord intéressante. La même méthode d'approximation est utilisée dans Lightweight data clustering tool bayon introduit dans le blog de mixi, donc il gère une grande quantité de données. Si tel est le cas, j'ai estimé qu'un calcul efficace serait difficile sans connaître (ou faire) une telle méthode d'approximation. ..
B-Bit MinHash en tant qu'outil rend un jugement assez précis même s'il est facile à créer. De plus, comme mentionné dans l'article, j'estime qu'il existe de nombreuses situations où cela peut être appliqué dans la pratique.
Désolé de vous déranger, mais j'apprécierais que vous signaliez des erreurs.