Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Латентно-семантический обзор и поиск на python

Anna | 16.06.2014 | нет комментариев

Незадолго 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 — библиотека для нормализации слов

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB