Недавно Google объявил, что он переходит от поиска по ключевым словам к полностью семантическому поиску. Не знаю, насколько круты алгоритмы поиска у мировых гигантов, но поиск в маленькой песочнице получается довольно семантическим. Конечно, с поиском по более менее крупным объёмам данных уже не всё так радужно, готовить слова надо очень тщательно, но тем не менее.
Сразу оговорюсь: кому интересна только голая теория, то отсылаю к очень хорошей статье на хабре, кому не особо интересно знать как все работает, а интересует только продакшн, то он может попробовать неплохую библиотеку для семантического поиска на питоне.
Итак, у нас есть список с десятком документов, по которым мы и будем искать:
titles =[
"Британская полиция знает о местонахождении основателя WikiLeaks",
"В суде США начинается процесс против россиянина, рассылавшего спам",
"Церемонию вручения Нобелевской премии мира бойкотируют 19 стран",
"В Великобритании арестован основатель сайта Wikileaks Джулиан Ассандж",
"Украина игнорирует церемонию вручения Нобелевской премии",
"Шведский суд отказался рассматривать апелляцию основателя Wikileaks",
"НАТО и США разработали планы обороны стран Балтии против России",
"Полиция Великобритании нашла основателя WikiLeaks, но, не арестовала",
"В Стокгольме и Осло сегодня состоится вручение Нобелевских премий"
]
Собственно это входные данные. Теперь нам нужно сделать три подготовительные операции:
1) Удалить разные запятые, точки, двоеточия, если есть html и прочий мусор из текста.
2) Привести все в нижний регистр и удалить все предлоги в, на, за, и тд.
3) Привести слова в нормальную форму, то есть поскольку для поиска слова типа Премия премий и прочее будет разными словами, надо это исправить.
4) Если мы просто хотим найти похожие документы, то можно удалить встречающиеся всего лишь один раз слова — для анализа сходства они бесполезны и будучи удалёнными позволят существенно сэкономить память.
Теперь сам алгоритм, благодаря математическим библиотекам питона тут все довольно просто.
5) Мы составляем матрицу нолей и единиц, соответственно представляющих отсутствие или наличие слова в документе.
6) Выполняем сингулярное разложение этой матрицы, в результате чего получаем три другие матрицы, в которых получим координаты документов и слов в пространстве.
На последнем этапе в упрощённом виде нам остается просто сравнить между собой координаты документов и/или слов: те, которые находятся ближе всего друг к другу и есть нужный результат, те которые подальше соответственно менее релевантны.
Все манипуляции с матрицами мы будем осуществлять с помощью numpy и scipy приводить слова к изначальной форме будем с помощью nltk. Устанавливаем…
pip install numpy
pip install nltk
pip install scipy
Если при попытке установить scipy возникнут какие то проблемы (будет требовать установить BLASS) то возможно поможет.
apt-get install gfortran libopenblas-dev liblapack-dev
Инициализация класса.
class LSI(object):
def __init__(self, stopwords, ignorechars, docs):
# все слова которые встречаются в документах, и содержит номера документов в которых встречается каждое слово
self.wdict = {}
# dictionary - Ключевые слова в матрице слева содержит коды слов
self.dictionary = []
# слова которые исключаем из анализа типа и, в, на
self.stopwords = stopwords
if type(ignorechars) == unicode: ignorechars = ignorechars.encode('utf-8')
self.ignorechars = ignorechars
# инициализируем сами документы
for doc in docs: self.add_doc(doc)
Подготовка слов, пополняем словарь, если слово есть в словаре возвращаем его номер, предварительно очищаем от лишних символов и приводим в начальную форму
def dic(self, word, add = False):
if type(word) == unicode: word = word.encode('utf-8')
# чистим от лишних символом
word = word.lower().translate(None, self.ignorechars)
word = word.decode('utf-8')
# приводим к начальной форме
word = stemmer.stem(word)
# если слово есть в словаре возвращаем его номер
if word in self.dictionary: return self.dictionary.index(word)
else:
# если нет и стоит флаг автоматически добавлять то пополняем словари возвращвем код слова
if add:
#self.ready = False
self.dictionary.append(word)
return len(self.dictionary) - 1
else: return None
Построение исходной матрицы
def build(self):
# убираем одиночные слова
self.keys = [k for k in self.wdict.keys() if len(self.wdict[k]) > 0]
self.keys.sort()
# создаём пустую матрицу
self.A = zeros([len(self.keys), len(self.docs)])
# наполняем эту матрицу
for i, k in enumerate(self.keys):
for d in self.wdict[k]:
self.A[i,d] += 1
Построение остальных матриц
def calc(self):
""" Вычисление U, S Vt - матриц """
self.U, self.S, self.Vt = svd(self.A)
Нормализация веса или важности слов в матрице. Вычисляем важность термина в зависимости от его встречаемости. Например, слово «и» встречается достаточно часто, поэтому это слово будет иметь низкую значимость, а, скажем, слово «США» встречается значительно режем и, соответственно, будет иметь большую значимость. Стандартные обороты речи отсеиваются, а редкие термины остаются.
def TFIDF(self):
# всего кол-во слов на документ
wordsPerDoc = sum(self.A, axis=0)
# сколько документов приходится на слово
docsPerWord = sum(asarray(self.A > 0, 'i'), axis=1)
rows, cols = self.A.shape
for i in range(rows):
for j in range(cols):
self.A[i,j] = (self.A[i,j] / wordsPerDoc[j]) * log(float(cols) / docsPerWord[i])
Сравнение документов на оси координат и поиск по ним.
def find(self, word):
self.prepare()
idx = self.dic(word)
if not idx:
print 'слово невстерчается'
return []
if not idx in self.keys:
print 'слово отброшено как не имеющее значения которое через stopwords'
return []
idx = self.keys.index(idx)
print 'word --- ', word, '=', self.dictionary[self.keys[idx]], '.n'
# получаем координаты слова
wx, wy = (-1 * self.U[:, 1:3])[idx]
print 'word {}t{:0.2f}t{:0.2f}t{}n'.format(idx, wx, wy, word)
arts = []
xx, yy = -1 * self.Vt[1:3, :]
for k, v in enumerate(self.docs):
# получаем координаты документа
ax, ay = xx[k], yy[k]
#вычисляем расстояние между словом и документом
dx, dy = float(wx - ax), float(wy - ay)
arts.append((k, v, ax, ay, sqrt(dx * dx + dy * dy)))
# возвращаем отсортированный по расстоянию список
return sorted(arts, key = lambda a: a[4])
class LSI(object):
def __init__(self, stopwords, ignorechars, docs):
self.wdict = {}
self.dictionary = []
self.stopwords = stopwords
if type(ignorechars) == unicode: ignorechars = ignorechars.encode('utf-8')
self.ignorechars = ignorechars
for doc in docs: self.add_doc(doc)
def prepare(self):
self.build()
self.calc()
def dic(self, word, add = False):
if type(word) == unicode: word = word.encode('utf-8')
word = word.lower().translate(None, self.ignorechars)
word = word.decode('utf-8')
word = stemmer.stem(word)
if word in self.dictionary: return self.dictionary.index(word)
else:
if add:
self.dictionary.append(word)
return len(self.dictionary) - 1
else: return None
def add_doc(self, doc):
words = [self.dic(word, True) for word in doc.lower().split()]
self.docs.append(words)
for word in words:
if word in self.stopwords: continue
elif word in self.wdict: self.wdict[word].append(len(self.docs) - 1)
else: self.wdict[word] = [len(self.docs) - 1]
def build(self):
self.keys = [k for k in self.wdict.keys() if len(self.wdict[k]) > 0]
self.keys.sort()
self.A = zeros([len(self.keys), len(self.docs)])
for i, k in enumerate(self.keys):
for d in self.wdict[k]:
self.A[i,d] += 1
def calc(self):
self.U, self.S, self.Vt = svd(self.A)
def TFIDF(self):
wordsPerDoc = sum(self.A, axis=0)
docsPerWord = sum(asarray(self.A > 0, 'i'), axis=1)
rows, cols = self.A.shape
for i in range(rows):
for j in range(cols):
self.A[i,j] = (self.A[i,j] / wordsPerDoc[j]) * log(float(cols) / docsPerWord[i])
def dump_src(self):
self.prepare()
print 'Здесь представлен расчет матрицы '
for i, row in enumerate(self.A):
print self.dictionary[i], row
def print_svd(self):
self.prepare()
print 'Здесь сингулярные значения'
print self.S
print 'Здесь первые 3 колонки U матрица '
for i, row in enumerate(self.U):
print self.dictionary[self.keys[i]], row[0:3]
print 'Здесь первые 3 строчки Vt матрица'
print -1*self.Vt[0:3, :]
def find(self, word):
self.prepare()
idx = self.dic(word)
if not idx:
print 'слово невстерчается'
return []
if not idx in self.keys:
print 'слово отброшено как не имеющее значения которое через stopwords'
return []
idx = self.keys.index(idx)
print 'word --- ', word, '=', self.dictionary[self.keys[idx]], '.n'
# получаем координаты слова
wx, wy = (-1 * self.U[:, 1:3])[idx]
print 'word {}t{:0.2f}t{:0.2f}t{}n'.format(idx, wx, wy, word)
arts = []
xx, yy = -1 * self.Vt[1:3, :]
for k, v in enumerate(self.docs):
ax, ay = xx[k], yy[k]
dx, dy = float(wx - ax), float(wy - ay)
arts.append((k, v, ax, ay, sqrt(dx * dx + dy * dy)))
return sorted(arts, key = lambda a: a[4])
Осталось вызвать приведенный выше код.
docs =[
"Британская полиция знает о местонахождении основателя WikiLeaks",
"В суде США США начинается процесс против россиянина, рассылавшего спам",
"Церемонию вручения Нобелевской премии мира бойкотируют 19 стран",
"В Великобритании арестован основатель сайта Wikileaks Джулиан Ассандж",
"Украина игнорирует церемонию вручения Нобелевской премии",
"Шведский суд отказался рассматривать апелляцию основателя Wikileaks",
"НАТО и США разработали планы обороны стран Балтии против России",
"Полиция Великобритании нашла основателя WikiLeaks, но, не арестовала",
"В Стокгольме и Осло сегодня состоится вручение Нобелевских премий"
]
ignorechars = ''',:'!'''
word = "США"
lsa = LSI([], ignorechars, docs)
lsa.build()
lsa.dump_src()
lsa.calc()
lsa.print_svd()
for res in lsa.find(word):
print res[0], res[4], res[1], docs[res[0]]
lsa.dump_src() британск [ 1. 0. 0. 0. 0. 0. 0. 0. 0.] полиц [ 1. 0. 0. 0. 0. 0. 0. 1. 0.] знает [ 1. 0. 0. 0. 0. 0. 0. 0. 0.] ...
В столбцах документы, в строчках термины.
lsa.print_svd() здесь первые 3 колонки U матрица британск [-0.06333698 -0.08969849 0.03023127] полиц [-0.14969793 -0.20853416 0.07106177] знает [-0.06333698 -0.08969849 0.03023127] ... Здесь первые 3 строчки Vt матрица [[ 0.25550481 0.47069418 0.27633104 0.39579252 0.21466192 0.26635401 0.32757769 0.3483847 0.3666749 ] [ 0.34469126 -0.18334417 -0.36995197 0.37444485 -0.29101203 0.27916372 -0.26791709 0.45665895 -0.35715836] [-0.10950444 0.64280654 -0.39672464 -0.1011325 -0.36012511 -0.01213328 0.38644373 -0.14789727 -0.32579232]]
for res in lsa.find(word): print res[0], res[4], res[1], docs[res[0]] word 9 (код слова в словаре) -0.17(первая координата слова) 0.46(вторая координата) США (само слово) номер документа в списке | растояние | документ разложеный на коды | сам документ 6 0.127328977215 [35, 36, 9, 37, 38, 39, 23, 40, 12, 41] НАТО и США разработали планы обороны стран Балтии против России 1 0.182108022464 [7, 8, 9, 9, 10, 11, 12, 13, 14, 15] В суде США начинается процесс против россиянина, рассылавшего спам 5 0.649492914495 [31, 8, 32, 33, 34, 5, 6] Шведский суд отказался рассматривать апелляцию основателя Wikileaks 0 0.765573367056 [0, 1, 2, 3, 4, 5, 6] Британская полиция знает о местонахождении основателя WikiLeaks 3 0.779637110377 [7, 24, 25, 5, 26, 6, 27, 28] В Великобритании арестован основатель сайта Wikileaks Джулиан Ассандж 8 0.810477163078 [7, 45, 36, 46, 47, 48, 17, 18, 19] В Стокгольме и Осло сегодня состоится вручение Нобелевских премий 4 0.831319718049 [29, 30, 16, 17, 18, 19] Украина игнорирует церемонию вручения Нобелевской премии 7 0.870710388156 [1, 24, 42, 5, 6, 43, 44, 25] Полиция Великобритании нашла основателя WikiLeaks, но, не арестовала 2 0.88243190531 [16, 17, 18, 19, 20, 21, 22, 23] Церемонию вручения Нобелевской премии мира бойкотируют 19 стран
На этом все, тема довольно обширная, старался как можно лаконичней.
Полезные ссылки
— Краткая теория латентно-семантического поиска (рус.)
— gensim — библиотека для ЛСА python
— nltk — библиотека для нормализации слов
Автор: Alex10
