Переполнение стека — очевидное спасение жизни для многих разработчиков, использующих его в повседневной жизни (говорю это, поскольку я сам разработчик :) ). Это сайт вопросов и ответов для профессиональных программистов и программистов-энтузиастов. В нем представлены вопросы и ответы по широкому кругу тем компьютерного программирования, и теперь он не ограничивается только программированием, а отвечает на вопросы по широкому спектру вопросов.
Это краткое введение в stackoverflow перед тем, как углубиться в проект
О проекте
Веб-сайт переполнения стека также имеет этот конкретный раздел на странице всех вопросов и ответов.
В нем перечислены все вопросы, связанные с текущими вопросами, которые могут помочь пользователю перемещаться по самой текущей странице, чтобы найти подходящую страницу вопросов, если текущая страница не отвечает их потребностям. Проект направлен на прогнозирование связанных сообщений для заданного сообщения с запросом, как на изображении для вопроса: загрузите txt данных из pandas, он предсказывает похожие сообщения, как показано на рисунке выше.
Поскольку мы создаем это как поисковую систему в дополнение к семантической релевантности прогнозируемых сообщений по отношению к сообщению с запросом, необходимо выполнить дополнительные ограничения.
- Низкая задержка — время предсказания должно быть меньше
- Масштабируемость — должна работать, даже когда объем данных, которые мы ищем, значительно увеличивается.
Вся проблема заключается в том, чтобы построить поисковую систему на основе вопросов StackOverflow, результаты поиска должны включать семантическое значение, с масштабируемой архитектурой, которая возвращает результаты за очень короткое время.
Подход
1. Сбор данных
Ссылка на данные: https://meta.stackexchange.com/questions/138356/how-do-i-download-stack-overflows-data
Приведенная выше ссылка содержит все данные о переполнении стека в различных темах, среди которых загружаются только файлы этих сообщений.
cs.meta.stackexchange.com.7z cs.stackexchange.com.7z datascience.meta.stackexchange.com.7z datascience.stackexchange.com.7z ai.meta.stackexchange.com.7z ai.stackexchange.com.7z computergraphics.meta.stackexchange.com.7z computergraphics.stackexchange.com.7z
Загруженные zip-файлы содержат вопросы и ответы по четырем основным темам — информатике, науке о данных, искусственному интеллекту и компьютерной графике. Приведенные выше файлы в несжатом виде дают множество файлов, среди которых получаются только файлы posts.xml в каждом несжатом каталоге, поскольку только этот конкретный файл содержит текст сообщения.
Каждый файл post.xml назван в соответствии с его темой и хранится в каталоге файлов XML.
XML Files -> DataScienceMeta_Posts.xml -> ComputerGraphicsMeta_Posts.xml -> AI_Posts.xml -> CSMeta_Posts.xml -> AIMeta_Posts.xml -> CS_Posts.xml -> ComputerGraphics_Posts.xml -> DataScience_Posts.xml
2. Предварительная обработка данных
Полученные 9 xml-файлов содержат гораздо больше данных, таких как postId, комментарии, отзывы и т. д., в дополнение к текстовым данным в формате xml. Следовательно, необходимо проанализировать файл xml и получить только текстовый атрибут каждого элемента xml, присутствующего в файлах.
# specifying the fields for csv file
fields = ['Id', 'Text', 'Topic']
def parseXML(xmlfile, start_count):
#create element tree object
print("File", xmlfile)
tree = ET.parse(xmlfile)
topic = xmlfile.split("/")[1].split("_")[0]
# get root element
root = tree.getroot()
# create empty list for news items
newsitems = []
count = start_count
# iterate news items
for each_row in root.iter("row"):
news = {}
news["Id"] = count
news["Text"] = each_row.attrib["Body"]
news["Topic"] = topic
count=count+1
newsitems.append(news)
# return news items list
print("len", len(newsitems))
return newsitems
Каждый файл xml анализируется для получения текста и соответствующей темы сообщения, которое является именем файла файла xml и сохраняется вместе с сгенерированным полем идентификатора.
def savetoCSV(newsitems, filename):
# writing to csv file
with open(filename, 'w') as csvfile:
# creating a csv dict writer object
writer = csv.DictWriter(csvfile, fieldnames = fields)
# writing headers (field names)
writer.writeheader()
# writing data rows
writer.writerows(newsitems)
Полученный результат сохраняется под тем же именем, что и файл CSV, в каталоге с именем CSV Files.
# specifying the fields for csv file
fields = ['Id', 'Text', 'Topic']
start_count = 0
for each_file in postfiles:
print(each_file)
# parse xml file
newsitems = parseXML("XML Files/"+each_file, start_count)
csv_filename = each_file.split('.')[0] + ".csv"
print("csv_filename", csv_filename)
# store news items in a csv file
savetoCSV(newsitems, "CSV Files/" + csv_filename)
start_count = len(newsitems) + start_count
Каталог файлов CSV выглядит так
CSV Files -> DataScienceMeta_Posts.csv -> ComputerGraphicsMeta_Posts.csv -> AI_Posts.csv -> CSMeta_Posts.csv -> AIMeta_Posts.csv -> CS_Posts.csv -> ComputerGraphics_Posts.csv -> DataScience_Posts.csv
Затем все файлы в файлах CSV анализируются в кадры данных, которые затем объединяются и сохраняются в файле рассола, который является окончательным файлом данных, который мы будем использовать для дальнейшей обработки. Структура нашего окончательного файла рассола
3. Очистка данных
Поскольку текст получен с веб-сайта, он, как правило, имеет много html-объектов и, следовательно, должен подвергаться обширному этапу предварительной обработки данных.
Выполнена различная предварительная обработка данных:
- Удаление тегов HTML
- Удаление URL
- Удаление знаков препинания (#,&,*), стоп-слов и т. д.
Еще один ключевой и другой шаг предварительной обработки данных:
4) Удаление программного кода
for(i=0;i‹n;i++) { печать(i) }
Поскольку это в основном портал вопросов и ответов по программированию в области компьютерных наук, большинство сообщений с вопросами и ответами, как правило, содержат программный код, который имеет много пунктуации и уникальную структуру, которая потеряет смысл после предварительной обработки данных.
Следовательно, программный код должен быть удален, а затем разработан отдельно для получения хорошего прогноза.
3. Разработка функций
Разработка признаков — один из самых важных и решающих шагов в решении любой проблемы науки о данных. Хорошо выполненная разработка признаков может сильно помочь модели в прогнозировании. Здесь я придумал три новые функции.
- тема
- программный код
- Ссылается на ту же ссылку
3а) тема
Тема каждого из сообщений используется как одна из функций, поскольку сообщения с похожей темой имеют тенденцию быть более похожими, чем другие. Функция темы является одной горячей кодировкой, поскольку она является категориальной функцией.
3b) Программный код
Хотя программный код в каждом из сообщений удален, он предоставляет очень важную информацию, которую нельзя потерять. Следовательно, программный код разработан отдельно, чтобы мы могли извлечь для него больше информации. Это делается путем удаления части кода отдельно из каждой записи, ее векторизации и кластеризации кодовых векторов с помощью кластеров k-средних. Таким образом, мы могли бы получить прекрасное представление о программном коде, как показано на изображениях ниже.
Как мы могли видеть, код сгруппирован по соответствующему типу. Всего получается 24 кластера, а пост без кода помещается в отдельный 25-й кластер. Таким образом, кластер кода теперь является категориальной функцией для аналогичного пост-прогнозирования, которое также является горячим кодированием.
3c) Имеет ли_сайт_тот же_адрес
Подобно программному коду, URL-адрес также является одной из таких функций, требующих специальной настройки. Поскольку URL тоже имеет особую структуру, при обычной обработке данных он потеряет свое значение. URL-адреса могут быть спроектированы отдельно, определяя, ссылаются ли два сообщения на один и тот же URL-адрес или нет, если да, то оба могут ссылаться на одно и то же.
При анализе мы обнаружили, что почти 31% цитируемых URL-адресов являются повторяющимися. Следовательно, существует вероятность того, что цитаты будут повторяться, и это можно использовать для поиска похожих сообщений.
3d) Вложения документов
Для векторизации предварительно обработанных текстовых данных поста используется пять типов вложений.
- Вложение векторов перчаток
- Встраивание векторов взвешенных перчаток TF-IDF
Наряду с этим используется новая техника под названием «Еще один экстрактор ключевых слов» для извлечения ключевых слов из текста сообщений и последующей его векторизации.
YAKE — Yet Another Keyword Extractor — один из хороших подходов к извлечению ключевых слов из текста. Было доказано, что он превосходит ряд неконтролируемых методов и контролируемый метод для ряда коллекций разных размеров, языков или доменов.
Чтобы узнать больше о YAKE, загляните на эту страницу: https://github.com/LIAAD/yake.
Следовательно, он используется для извлечения ключевых слов в тексте каждого сообщения, а затем для применения к нему вложений.
3) Извлечение ключевых слов на основе YAKE + встраивание векторов перчаток
4) Извлечение ключевых слов на основе YAKE + встраивание векторов взвешенных перчаток TF-IDF
def tokenization(keywords_text):
tokenizer = RegexpTokenizer(r'\w+')
return tokenizer.tokenize(keywords_text)
#Converting each posts text into corresponding keyword sets
simple_kwextractor = yake.KeywordExtractor()
questions_keywords_text = []
for i in range(preprocessed_text.shape[0]):
if i%10 == 0:
print(i,"vectors finished")
keyword_simple = simple_kwextractor.extract_keywords(preprocessed_text[i])
keyword_text = ""
for each_kw in keyword_simple:
keyword_text += each_kw[0] + " "
questions_keywords_text.append(set(tokenization(keyword_text)))
questions_keywords_sets = np.array(questions_keywords_text)
5) Встраивание BERT
Модель BERT, которая означает двунаправленные представления кодировщика от преобразователя, опубликованные Google, в настоящее время является современной моделью для выполнения задач, связанных с НЛП. BERT, который является моделью LSTM, работает на основе концепции внимания, пытающегося предсказать следующий токен на основе серии предыдущих токенов, с которыми он столкнулся. Встраивание на основе BERT может оказаться полезным для этого проекта, чтобы извлечь более значимую информацию из текста сообщения.
def avg_of_token_embedding(result):
document_embeddings = np.zeros(768)
count = 0
for i in range(len(result)):
for j in range(len(result[i][1])):
document_embeddings = document_embeddings + result[i][1][j]
count = count + 1
return (document_embeddings/count)
from bert_embedding import BertEmbedding
bert_document_embeddings = []
for i in range(preprocesses_text.shape[0]):
sentences = bert_abstract.split(' ')
bert_embedding = BertEmbedding()
token_embedding = bert_embedding(preprocesses_text[i],'sum')
bert_embedding_vector = avg_of_token_embedding(token_embedding)
bert_document_embeddings.append(bert_embedding_vector)
bert_document_embeddings = np.array(bert_document_embeddings)
4. Создание простой поисковой системы
Это наиболее важная часть решения, так как поисковая система должна быть масштабируемой и иметь меньшую задержку. Сходство между текстами двух сообщений рассчитывается следующим образом:
Post Similarity(i,j) = cosine_similarity(post_vector(i),post_vector(j)) + similarity(topic_vector(i), topic_vectorr(j)) + similarity(code_cluster(i), code_cluster(j)) + number of common urls
На основе приведенной выше формулы вычисляется сходство между двумя сообщениями. Косинусное сходство используется для текста сообщения, поскольку евклидово расстояние подвержено проблеме проклятия размерности для больших размеров. Для тематического вектора и кодового кластерного вектора сходство вычисляется как обратное евклидову расстоянию.
similarity = 1/ euclidean distance
Для создания поисковой системы реализовано эффективное решение сокращение карты, в котором 8 процессов создаются для независимого выполнения.
Для заданного поста запроса каждый процесс обрабатывает 1/8 часть данных об общем количестве постов, возвращает список из 10 длин, который представляет собой 10 постов с самым высоким сходством из общего количества постов, которые он вычислил. Затем все 10 длин списка, возвращенные всеми процессами, объединяются вместе и сортируются, чтобы получить общее сходство 10 лучших. Простая технология уменьшения карты позволила задержке быть в пределах 20 секунд.
Код для поисковой системы:
import multiprocessing
alpha = 0.001
//returns topic wise similarity of two posts
def get_topic_similarity(ind1, ind2):
dist = euclidean_distances(topics[ind1], topics[ind2])[0][0]
if dist == 0:
return 1/(dist+alpha)
else:
return dist
//returns code wise similarity of two posts
def get_code_similarity(ind1, ind2):
dist = euclidean_distances(code_cluster_list[ind1].reshape(-1,1),
code_cluster_list[ind2].reshape(-1, 1))[0][0]
if dist == 0:
return 1/(dist+alpha)
return dist
def insert_into_top_k_similar_docs(top_k_similar_docs,
vec_similarity, doc_id):
doc_dict = dict()
doc_dict["doc_id"] = doc_id
doc_dict["similarity"] = vec_similarity
should_insert = False
for i in range(11):
if i == 10:
return
if vec_similarity > top_k_similar_docs[i]['similarity']:
should_insert = True
break
if should_insert:
docs_place = i
temp_list = []
for i in range(docs_place, k-1):
#print("it 2", i)
temp_list.append(top_k_similar_docs[i])
ind = 0
for i in range(docs_place+1 , k):
top_k_similar_docs[i] = temp_list[ind]
ind = ind + 1
top_k_similar_docs[docs_place] = doc_dict
// Finds the top 10 similar posts for a given query post from the
// posts in the start and end range
def find_vector_similarity(preprocessed_text_vector, test_query_point, start, end, topic_weight=1, code_weight=1,
cites_weight=1):
top_k_similar_docs = []
for i in range(10):
doc_dict = dict()
doc_dict['doc_id'] = 0
doc_dict['similarity'] = -1
top_k_similar_docs.append(doc_dict)
for i in range(start, end):
if i >= preprocessed_text_vector.shape[0]:
return
vec_similarity = cosine_similarity(preprocessed_text_vector[i].reshape(1,-1),
preprocessed_text_vector[test_query_point].reshape(1,-1))[0][0]
topicwise_similarity = get_topic_similarity(i, test_query_point)* topic_weight
codewise_similarity = get_code_similarity(i, test_query_point) * code_weight
cites_similarity = get_cites_similarity(i, test_query_point)
if cites_similarity:
cites_similarity = cites_similarity * cites_weight
vec_similarity = vec_similarity + topicwise_similarity + codewise_similarity + cites_similarity
else:
vec_similarity = vec_similarity + topicwise_similarity + codewise_similarity
vec_sim_list.append(vec_similarity)
insert_into_top_k_similar_docs(top_k_similar_docs, vec_similarity, i)
return top_k_similar_docs
def simple_search_engine(preprocessed_text_vector, test_sample, topic_weight=1, code_weight=1, cites_weight=1):
count = 0
posts_text = pd.read_pickle('Preprocessed_questions_text.pkl')['Text'].values
for each_test_point in test_sample:
list_of_top_k_docs = []
start_time = datetime.now()
#print(each_test_point)
#print("top_k_similar_docs", top_k_similar_docs)
vec_sim_list = []
test_query_point = preprocessed_text_vector[each_test_point]
print("Query posts",each_test_point, ":" , posts_text[each_test_point])
print("#"*100)
start = 0
step = preprocessed_text_vector.shape[0]/8
input_list = []
while start < preprocessed_text_vector.shape[0]:
input_list.append([preprocessed_text_vector, each_test_point, start, start+step,
topic_weight, code_weight, cites_weight ])
start = start+step
pool = multiprocessing.Pool(processes=4)
tasks=[]
for each in input_list:
tasks.append(pool.apply_async(find_vector_similarity,each))
pool.close()
pool.join()
for each in tasks:
each.wait()
result = each.get()
list_of_top_k_docs.extend(result)
quickSort(list_of_top_k_docs, 0, len(list_of_top_k_docs))
list_of_top_k_docs = list_of_top_k_docs[0:10]
total_time = (datetime.now() - start_time).total_seconds()
print("Total time taken:", humanize_seconds(total_time))
print("The Most similar ",k,"posts are:")
for each in list_of_top_k_docs:
print(posts_text[each['doc_id']])
print("#"*100)
print("*"*200)
5. Сравнение производительности пяти методов встраивания
У нас нет явной метрики производительности для оценки качества сделанных нами прогнозов, мы должны оценить прогнозы, сделанные путем ручного чтения 10 постов, предсказанных моделью. Исходя из этого, производительность пяти вложений, которые мы использовали, составляет:
- В аналогичных прогнозах сообщений с использованием векторов перчаток и взвешенных векторов перчаток TF-IDF первые сообщения посвящены полной задаче NP, называемой гамильтоновым циклом. Мы могли наблюдать за использованием перчаток и взвешенных векторов перчаток TF-IDF, они предсказывают сообщения, связанные с теорией вычислений, временной сложностью и некоторыми сообщениями о полноте NP и т. д.
Пример прогнозирования с помощью простых векторов перчаток:
Query Posts:
Hint: Hamiltonian Cycle is $NP$-Complete.
Sample predicted posts:
1) <p>Hint: This is just the well-known NP-complete problem PARTITION.</p>
2) <p>Is there a notion of a context-free complete language (in the analogous sense to a <span class="math-container">$NP$</span>-complete language)?</p>
3) <p>For example;</p>
<p>Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?</p>
4) <p>How Decision procedure and Decidable problem are different from each other?
Both are having solutions in yes and no form. Is any else solution for both? </p>
Примеры прогнозов по взвешенным векторам перчаток TF-IDF:
Query Posts: Hint: Hamiltonian Cycle is $NP$-Complete. Sample predicted posts: 1) <p>Hint: This is just the well-known NP-complete problem PARTITION.</p> 2) <p>Is there a notion of a context-free complete language (in the analogous sense to a <span class="math-container">$NP$</span>-complete language)?</p> 3) <p>Can an ambiguous context-free grammar be converted into Chomsky normal form? I think the answer is yes.</p> 4) <p>Time complexity, like any other nontrivial property of programs, is undecidable: there can be no algorithm to compute it, in Python or anything else.</p>
2) Прогнозы, основанные на извлеченных ключевых словах. Векторы перчаток кажутся немного более точными, чем прогнозы, сделанные с использованием векторов перчаток.
Примеры прогнозов по извлеченным ключевым словам перчаточным векторам:
Query Posts:
Hint: Hamiltonian Cycle is $NP$-Complete.
Sample predicted posts:
1) <p>Is there a notion of a context-free complete language (in the analogous sense to a <span class="math-container">$NP$</span>-complete language)?</p>
2) <p>Does it exist an algorithm to find a median of table with a complexity nlog(n) Thank</p>
3) <p>2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1
since 2^n may or not be element of O(3^n)
I need a hint to figure the problem</p>
4) <p>Yes and yes. Look at this graph:</p>
<ul>
<li>$V=\{1,2,3,4\}$</li>
<li>$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$</li>
</ul>
<p>There is neither articulation point nor bridge. But if you delete any node/edge...</p>
Примеры прогнозов по извлеченным ключевым словам векторам перчаток TF-IDF:
Query Posts:
Hint: Hamiltonian Cycle is $NP$-Complete.
Sample predicted posts:
1) <p>Is there a notion of a context-free complete language (in the analogous sense to a <span class="math-container">$NP$</span>-complete language)?</p>
2) <p>Does it exist an algorithm to find a median of table with a complexity nlog(n)
Thank</p>
3) <p>2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1
since 2^n may or not be element of O(3^n)
I need a hint to figure the problem</p>
4) <p>Yes and yes. Look at this graph:</p>
<ul>
<li>$V=\{1,2,3,4\}$</li>
<li>$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$</li>
</ul>
<p>There is neither articulation point nor bridge. But if you delete any node/edge...</p>
3) Прогнозы, основанные на встраивании BERT, кажутся намного более точными, чем перчатка с извлечением ключевого слова и взвешенные векторы перчаток tf-idf с извлечением ключевого слова, поскольку сообщение посвящено NP-полной проблеме, прогнозируется больше сообщений о NP-полных проблемах, чем любой разное. Также для вторых сообщений SVM прогнозируется больше сообщений в SVM, чем в любых других темах.
Пример предсказания BERT Embeddings:
Query Posts:
Hint: Hamiltonian Cycle is $NP$-Complete.
Sample predicted posts:
1) <p>Yes, this is decidable, because you can do an exhaustive search of all possible paths. There is no need to look at any paths that repeat a vertex, since the "detour" could be skipped. But the length of any non-repetitive path is bounded by the size of the graph, which is finite, and so there are only finitely many such paths, which can be checked one by one.</p>
<p>What is not decidable is the following: given an infinite graph $G$ and two vertices $a$ and $b$, decide whether there is a path from $a$ to $b$. This is not decidable if the graph is given as an oracle and is also not decidable if the graph is given via a program that computes it. </p>
2) <blockquote>
<p>What is the time complexity of finding the diameter of a graph
$G=(V,E)$?</p>
<ul>
<li>${O}(|V|^2)$</li>
<li>${O}(|V|^2+|V| \cdot |E|)$</li>
<li>${O}(|V|^2\cdot |E|)$</li>
<li>${O}(|V|\cdot |E|^2)$</li>
</ul>
</blockquote>
<p>The diameter of a graph $G$ is the maximum of the set of shortest path distances between all pairs of vertices in a graph.</p>
<p>I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.</p>
3) <p>When searching graphs, there are two easy algorithms: <strong>breadth-first</strong> and <strong>depth-first</strong> (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).</p>
<p>Now, are there any advantages of one over another?</p>
<p>The ones I could think of:</p>
<ul>
<li>If you expect your data to be pretty far down inside the graph, <em>depth-first</em> might find it earlier, as you are going down into the deeper parts of the graph very fast.</li>
<li>Conversely, if you expect your data to be pretty far up in the graph, <em>breadth-first</em> might give the result earlier.</li>
</ul>
<p>Is there anything I have missed or does it mostly come down to personal preference?</p>
4) <p>Breadth-first and depth-first certainly have the same worst-case behaviour (the desired node is the last one found). I suspect this is also true for averave-case if you don't have information about your graphs.</p>
<p>One nice bonus of breadth-first search is that it finds shortest paths (in the sense of fewest edges) which may or may not be of interest.</p>
<p>If your average node rank (number of neighbours) is high relative to the number of nodes (i.e. the graph is dense), breadth-first will have huge queues while depth-first will have small stacks. In sparse graphs, the situation is reversed. Therefore, if memory is a limiting factor the shape of the graph at hand may have to inform your choice of search strategy.</p>
4) Таким образом, прогнозы, основанные на вложениях BERT, кажутся более точными, чем прогнозы, основанные на вложениях текста с извлечением ключевых слов, которые, в свою очередь, работают лучше, чем обычные вложения векторов перчаток. Мы также могли наблюдать, как взвешенные векторы перчаток TF-IDF выполняют почти ту же работу с точки зрения прогнозирования. Следовательно, значения TF-IDF не оказывают никакого влияния на улучшение производительности прогнозирования.
5. Ссылка
- YAKE — Еще один экстрактор ключевых слов https://github.com/LIAAD/yake
- Вложения Берта — https://github.com/imgarylai/bert-embedding
Чтобы просмотреть всю работу, перейдите по ссылке на мой git hub: https://github.com/gayathriabhi/StackOverflow-Search-Engine
Мой профиль в LinkedIn: https://www.linkedin.com/in/gayathri-s-a90322126/
