Ich wollte URLs kategorisieren und versuchte, b-Bit Min Hash zu verwenden. Insbesondere dient es dazu, Folgendes zu tun. Bei der Berechnung der CV-Wahrscheinlichkeit des Benutzers unter Verwendung der aus dem Cookie extrahierten Website-Browsing-Informationen als Identität wird der Identitätsvektor ziemlich spärlich. Daher wollte ich die URL in Kategorien unterteilen und die Dichte des Identitätsvektors in gewissem Maße erhöhen. Aus diesem Grund experimentiere ich mit dem Titel.
Eine Übersicht über die Methode finden Sie im SmartNews-Entwicklungsblog. Ich möchte, dass Sie sich auf PFIs Mr. Okanoharas Material beziehen, das im Text erscheint. Es ist viel einfacher zu verstehen, als ich die Erklärung schreibe.
Daher werde ich hier kurz die Vorgehensweise zum Schreiben von Code beschreiben.
Unten ist der Code, den ich erstellt habe. Ich habe es geschafft, indem ich verschiedene Dinge ausgeschnitten und eingefügt habe, damit die Namensregeln durcheinander geraten. .. Wie üblich wird es von einem Nicht-Ingenieur geschrieben, daher ist der Code ziemlich unansehnlich, aber es wäre sehr hilfreich, wenn Sie ihn mit einem breiten Verstand lesen könnten. ..
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 der zu ignorierenden Wörter
ignorewords = set(['the', 'of', 'to', 'and', 'a', 'in', 'is', 'it', '-', '/', '#', "'", '_', ',', '(', ')', '[', ']', '〜', '!', '|', '♪', '...', '>', '<', ':', '!!', '&', '/', '+', '*'])
#Liste der Tags, die als Blöcke erkannt werden sollen
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:
#Initialisieren Sie den Crawler mit dem Namen der Datenbank
def __init__(self, dbname):
self.dbname = dbname
self.con=sqlite.connect(dbname)
self.con.text_factory = str # utf-Geben Sie str an, um 8 zu verwenden
def __del__(self):
self.con.close()
def dbcommit(self):
self.con.commit()
#Indizieren Sie einzelne Seiten
def addtoindex(self,url,category,wordlist):
if self.isindexed(url): return
print 'Indexing' + url
#Speichern Sie die Wortliste für jede URL in der Datenbank
self.con.execute( "insert into wordvector values(?,?,?,?)" , \
(url, category, pickle.dumps(wordlist), '') )
self.dbcommit()
def getNavigableStrings(self,soup):
#Stellen Sie fest, ob Suppe ein Typ ist, der Inhalt enthält
if isinstance(soup, NavigableString): #
if type(soup) not in (Comment, Declaration):
yield soup
#Text abrufen, wenn er Inhalt enthält und kein Programmcode ist
elif soup.name not in ('script', 'style'):
is_block = soup.name in block_tags #Bestätigen Sie das Vorhandensein des Block-Tags
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'
#Gibt ture zurück, wenn die URL bereits indiziert ist
def isindexed(self,url):
u=self.con.execute \
("select words from wordvector where url='%s'" % url).fetchone()
if u!=None:
return True
return False
#Empfängt eine Liste von Seiten und führt eine Breitensuche in einer bestimmten Tiefe durch
#Indizieren Sie die Seite
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), #Konvertieren Sie den Zeichencode entsprechend der Site
convertEntities = BeautifulStoneSoup.HTML_ENTITIES) #Zeichenkonvertierung von HTML-Sonderzeichen
text = u''.join( self.getNavigableStrings(soup) )
text = normalizeText(text) #String-Normalisierung
words = spw.separateWords(text) #Holen Sie sich das Wort gesetzt
self.addtoindex(page,category,words) # url, category,Wortsatz in DB speichern
#Rufen Sie die URL des a-Tags ab, um tiefer als 2 zu suchen
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] #Fragmentkennung entfernen
if url[0:4]=='http' and not self.isindexed(url):
newpages.add(url)
pages=newpages
#Erstellen Sie eine Datenbanktabelle
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):
"""Entfernt unnötige Leerzeichen und gibt nicht leere Zeilen zurück"""
for line in text.splitlines():
line = u' '.join(line.split())
if line:
yield line
def normalizeText(text):
"""Entfernen Sie nach der Normalisierung unnötige Leerzeichen und Zeilenumbrüche"""
Text = unicodedata. normalize ('NFKC', text) #Konvertieren Sie die japanische Halbbreite in die volle Breite+Alphabet,Das Symbol ist halb breit
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)
Der Teil, der Wörter aus dem Text extrahiert (spw.separateWords (Text)), hat den folgenden Code.
python
# coding: utf-8
import MeCab
#Liste der zu ignorierenden Wörter
ignorewords = set(['the', 'of', 'to', 'and', 'a', 'in', 'is', 'it', 'von'])
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] == "Substantiv" \
and (feat[1] == "Allgemeines"
or feat[1] == "Proprietäre Nomenklatur" or feat[1] == "Adjektiv Verbstamm"):
#word = node.surface.decode(en)
word = node.surface
if word not in ignorewords:
word_set.add( word )
node = node.next
return word_set
Erstellen Sie als Nächstes eine Mindest-Hash-Liste für Lehrer aus dem erfassten Wortsatz und beschreiben Sie den Teil, in dem die Datenbank aktualisiert werden soll.
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-Geben Sie str an, um 8 zu verwenden
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) #Rufen Sie die Datenbank auf, in der der Wortvektor gespeichert ist
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()
Die minimale Hash-Liste wird wie folgt erstellt.
python
# coding: utf-8
import numpy as np
import mmh3
from multiprocessing import *
class Hashing(object):
'''
Hashing wird auf den Wortsatz angewendet, der bei jeder URL erhalten wird, um den Mindestwert zu erhalten.
Holen Sie sich einen k-dimensionalen Vektor für jede URL
Beurteilung der Ähnlichkeit durch Vergleich dieses k-dimensionalen Vektors
'''
def __init__(self,bbit=1,k=128):
self.bbit = bbit
self.hash_cnt = k
def get_min_vector(self,feat_names):
'''Diese Funktion wird per URL aktiviert'''
hash_vec = []
#Holen Sie sich nur den minimalen Hash eines k-mal eingestellten Wortes
for seed in xrange(self.hash_cnt): # self.hash_Samen für cnt generieren
pool = Pool(processes=8)
hash_val = pool.map( get_hash_value, ((feat_name, seed) for feat_name in feat_names) ) #Generieren Sie k Hash-Funktionen mit k Seeds
pool.close()
pool.join()
min_val = int( str( min(hash_val) )[-self.bbit] )
hash_vec.append(min_val) #Holen Sie sich nur die erste Ziffer des Mindestwerts
return hash_vec
def get_hash_value((feat_name,seed)):
return mmh3.hash(feat_name,seed)
Zu diesem Zeitpunkt sind die Lehrerdaten bereit. Holen Sie sich auf ähnliche Weise das Wort für den Lernenden und speichern Sie es in der Datenbank.
Im Folgenden wird MinHash unter Verwendung des erfassten Wortsatzes des Lernenden und der erstellten Lehrer-Hash-Liste ausgeführt. Fügen Sie dann der URL des Lernenden eine Kategorie hinzu, aktualisieren Sie die Datenbank und beenden Sie den Vorgang. Der Code wird unten beschrieben.
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 ) ) #Berechnung der Ähnlichkeit
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):
"""Aktualisieren Sie die ursprüngliche Datenbank, während Sie einen Hash-Vektor erstellen"""
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), ) ) #Mit Gurke speichern
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) #Berechnung der Ähnlichkeit
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) #Eine einfache Kombination von zwei Wortmengen wird als ganze Wortmenge betrachtet.
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()
Wie Sie beim Lesen des Papiers sehen können, ist es eine Voraussetzung, dass D (die Größe des Wortsatzes) und k (die Art der Hash-Funktion) groß genug sind. Wenn dies nicht der Fall ist, gilt die Annäherung nicht und Sie erhalten möglicherweise seltsame Werte. Seien Sie also bitte vorsichtig. Im obigen Code ist D eine Kombination aus zwei Wortsätzen, aber ich habe es nur zum Experimentieren gemacht. Wenn es tatsächlich verwendet wird, setzen Sie das gesamte Wort auf D.
Ich habe in den Kategorien Finanzen, Wirtschaft und Sport (Baseball, Golf) experimentiert. Die im Sport verwendeten Wörter unterscheiden sich so stark zwischen Baseball und Golf, dass sie in Bezug auf Sport nicht gut kategorisiert wurden. Wenn es in der Praxis verwendet wird, denke ich, ist es notwendig, die Kategorie selbst zu entwickeln. Übrigens habe ich beim Erstellen der Kategorie auf Open Directory Project (ODP) verwiesen.
Wenn es um die Berechnungszeit geht, ist das Erstellen einer Liste mit minimalen Hashwerten am zeitaufwändigsten. Derzeit versuche ich, eine Parallelverarbeitung durchzuführen, habe aber immer noch den Eindruck, dass eine beträchtliche Wartezeit auftreten wird. (Da ich es mir nicht leisten konnte, die durchschnittliche Zeit zu messen, gebe ich Ihnen nur einen Eindruck.
Obwohl im obigen Code 32-Bit-Hash verwendet wird, wird empfohlen, 64-Bit-Hash zu verwenden. 64bit kollidieren weniger wahrscheinlich.
Interessant ist zunächst die in MinHash verwendete Approximationsmethode. Dieselbe Approximationsmethode wird in Lightweight Data Clustering Tool Bayon verwendet, das in Mixis Blog eingeführt wurde, sodass eine große Datenmenge verarbeitet wird. Wenn ja, denke ich, dass eine effiziente Berechnung schwierig ist, ohne eine solche Näherungsmethode zu kennen (wenn ich es nicht schaffen kann). ..
B-Bit MinHash als Werkzeug macht eine ziemlich genaue Beurteilung, obwohl es einfach zu erstellen ist. Wie in dem Papier erwähnt, gibt es meines Erachtens viele Situationen, in denen es in der Praxis angewendet werden kann.
Es tut mir leid, Sie zu belästigen, aber ich würde mich freuen, wenn Sie auf Fehler hinweisen könnten.