#алгоритм
Допустим, есть два текстовых документа, векторами которых будут два массива, состоящие
из их слов: D1 = {word1, word2, word3} и D2 = {word1, word5, word8}.
Как найти косинусное сходство двух этих векторов? Как вообще перемножить (или провести
другие математические операции) со строками в рамках какого-то языка программирования?
И как быть если векторы будут разных размеров? (Например, в одном документе будет
больше слов, чем в другом).
Ответы
Ответ 1
В процессе написания обнаружилось, что тема крайне велика, чтобы ее можно было так просто кратко и понятно расписать в ответе. Я бы рекомендовал обратиться к классическим учебникам - из них вы узнаете гораздо больше. Например, IR-Book. Тем не менее: Вы не можете проводить математические операции над строками. Можете с векторами. Процесс перехода к векторам называется векторизацией. Векторизация естественных языков языков тема относительно хорошо изученная - самый известный мне пример - это word2vec - можете вместо своих велосипедов сразу начать с него (или с какого-нибудь побратима doc2vec). Одна с ним проблема - детальный разбор механизма разбора требует довольно высокой квалификации. Но никто не запрещает пользовать этот инструмент как черный ящик. Теперь о велосипедах. Можно взять простую реализацию TF-IDF - с помощью нее можно получить вектора и оперировать с векторами. Писать я буду на Python без использования специфических конструкций (предпочитаемый язык у вас не указан). Порядок моих действий такой: Из корпуса составить словарь слов, где ключом будет слово, а значением - индекс в векторе (каждое слово - отдельное измерение в получающихся векторах) Для каждого документа в корпусе посчитать TF-IDF для всех слов из документа. После этого для каждого слова в документе можно будет сопоставить вектор размерностью n, где n - количество уникальных слов в корпусе (см. 1). В результате получаем матрицу вхождения отдельных слов в документы. Такой подход называется Bag of Words (порядок слов в документе нарушается и представляется как мешок перемешанных слов) и TF-IDF вы можете заменить какой угодно мерой, что вам приглянется. Можно просто посчитать, сколько отдельное слово встречается в документе. В дальнейшем вы можете сравнивать уже получившиеся вектора между собой или с новыми векторами. Корпус такой: str1 = "Я люблю тортики больше, чем яблоки" str2 = "Я уважаю апельсины больше, чем торты" str3 = "Яблочные сады раскинулись над дорогой" str4 = "Ехал Грека через реку" Как видно количество слов различно - так же проявляется еще одна проблема - одинаковые слова употребляются в разных формах/падежах (тортики-тортиков). Эта проблема решается разными путями - стеммингом (stemming), нормализацией - слова приводятся к единственному числу, именительному падежу (тортики - торт, тортиков - торт) - но это отдельная большая тема. Еще туда же - фильтрация знаков препинания - больше, и больше - разные слова (токены). from collections import Counter import operator import math def tokenize(doc): words = [word.replace(',', '').lower() for word in doc.split()] return words def build_terms(corpus): terms = {} current_index = 0 for doc in corpus: for word in tokenize(doc): if word not in terms: terms[word] = current_index current_index += 1 return terms def tf(document, terms): words = tokenize(document) total_words = len(words) doc_counter = Counter(words) for word in doc_counter: # Можно и не делить, а оставить как есть, с частотой doc_counter[word] /= total_words tfs = [0 for _ in range(len(terms))] for term, index in terms.items(): tfs[index] = doc_counter[term] return tfs def _count_docs_with_word(word, docs): counter = 1 for doc in docs: if word in doc: counter += 1 return counter # documents - это корпус def idf(documents, terms): idfs = [0 for _ in range(len(terms))] total_docs = len(documents) for word, index in terms.items(): docs_with_word = _count_docs_with_word(word, documents) # Основание логарифма не важно # Боюсь отрицательныз значений, только положительные idf = 1 + math.log10(total_docs / docs_with_word) idfs[index] = idf return idfs def _merge_td_idf(tf, idf, terms): return [tf[i] * idf[i] for i in range(len(terms))] def build_tfidf(corpus, document, terms): doc_tf = tf(document, terms) doc_idf = idf(corpus, terms) return _merge_td_idf(doc_tf, doc_idf, terms) def cosine_similarity(vec1, vec2): # Целиком отсюда: http://stackoverflow.com/questions/18424228/cosine-similarity-between-2-number-lists def dot_product2(v1, v2): return sum(map(operator.mul, v1, v2)) def vector_cos5(v1, v2): prod = dot_product2(v1, v2) len1 = math.sqrt(dot_product2(v1, v1)) len2 = math.sqrt(dot_product2(v2, v2)) return prod / (len1 * len2) return vector_cos5(vec1, vec2) str1 = "Я люблю тортики больше, чем яблоки" str2 = "Я уважаю апельсины больше, чем торты" str3 = "Яблочные сады раскинулись над дорогой" str4 = "Ехал Грека через реку" # Проверочные документы check_str1 = "Тортики делают из муки, апельсины и воды" check_str2 = "Торты исчезли там, где появился я" check_str3 = "Ехал тортик через реку" # --------------------- Основной код -------------------- tf_idf_total = [] corpus = (str1, str2, str3, str4) terms = build_terms(corpus) for document in corpus: tf_idf_total.append(build_tfidf(corpus, document, terms)) print(terms.keys()) for doc_rating in tf_idf_total: print(doc_rating) queries = (check_str1, check_str2, check_str3) for query in queries: print("QUERY:", query) query_tfidf = build_tfidf(corpus, query, terms) for index, document in enumerate(tf_idf_total): print("Similarity with DOC", index, "=", cosine_similarity(query_tfidf, document)) Я хотел покороче, но не вышло. Результаты такие: dict_keys(['я', 'люблю', 'тортики', 'больше', 'чем', 'яблоки', 'уважаю', 'апельсины', 'торты', 'яблочные', 'сады', 'раскинулись', 'над', 'дорогой', 'ехал', 'грека', 'через', 'реку']) [0.21683833261066354, 0.21683833261066354, 0.21683833261066354, 0.18748978943471664, 0.18748978943471664, 0.21683833261066354, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] [0.21683833261066354, 0.0, 0.0, 0.18748978943471664, 0.18748978943471664, 0.0, 0.21683833261066354, 0.21683833261066354, 0.21683833261066354, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.3204119982655925, 0.26020599913279624, 0.26020599913279624, 0.26020599913279624, 0.26020599913279624, 0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.4005149978319906, 0.4005149978319906, 0.3252574989159953, 0.3252574989159953] QUERY: Тортики делают из муки, апельсины и воды Similarity with DOC 0 = 0.3016416923422043 Similarity with DOC 1 = 0.3016416923422043 Similarity with DOC 2 = 0.0 Similarity with DOC 3 = 0.0 QUERY: Торты исчезли там, где появился я Similarity with DOC 0 = 0.3016416923422042 Similarity with DOC 1 = 0.6032833846844085 Similarity with DOC 2 = 0.0 Similarity with DOC 3 = 0.0 QUERY: Ехал тортик через реку Similarity with DOC 0 = 0.0 Similarity with DOC 1 = 0.0 Similarity with DOC 2 = 0.0 Similarity with DOC 3 = 0.8358857904935546
Комментариев нет:
Отправить комментарий