edit_CookingLDA_PA


Programming Assignment:

Готовим LDA по рецептам

Как вы уже знаете, в тематическом моделировании делается предположение о том, что для определения тематики порядок слов в документе не важен; об этом гласит гипотеза «мешка слов». Сегодня мы будем работать с несколько нестандартной для тематического моделирования коллекцией, которую можно назвать «мешком ингредиентов», потому что на состоит из рецептов блюд разных кухонь. Тематические модели ищут слова, которые часто вместе встречаются в документах, и составляют из них темы. Мы попробуем применить эту идею к рецептам и найти кулинарные «темы». Эта коллекция хороша тем, что не требует предобработки. Кроме того, эта задача достаточно наглядно иллюстрирует принцип работы тематических моделей.

Для выполнения заданий, помимо часто используемых в курсе библиотек, потребуются модули json и gensim. Первый входит в дистрибутив Anaconda, второй можно поставить командой

pip install gensim

Построение модели занимает некоторое время. На ноутбуке с процессором Intel Core i7 и тактовой частотой 2400 МГц на построение одной модели уходит менее 10 минут.

Загрузка данных

Коллекция дана в json-формате: для каждого рецепта известны его id, кухня (cuisine) и список ингредиентов, в него входящих. Загрузить данные можно с помощью модуля json (он входит в дистрибутив Anaconda):


In [1]:
import json

In [2]:
with open("recipes.json") as f:
    recipes = json.load(f)

In [3]:
print(recipes[0])


{'id': 10259, 'cuisine': 'greek', 'ingredients': ['romaine lettuce', 'black olives', 'grape tomatoes', 'garlic', 'pepper', 'purple onion', 'seasoning', 'garbanzo beans', 'feta cheese crumbles']}

Составление корпуса


In [4]:
from gensim import corpora, models
import numpy as np


/usr/lib/python3.5/site-packages/gensim/utils.py:1015: UserWarning: Pattern library is not installed, lemmatization won't be available.
  warnings.warn("Pattern library is not installed, lemmatization won't be available.")

Наша коллекция небольшая, и целиком помещается в оперативную память. Gensim может работать с такими данными и не требует их сохранения на диск в специальном формате. Для этого коллекция должна быть представлена в виде списка списков, каждый внутренний список соответствует отдельному документу и состоит из его слов. Пример коллекции из двух документов:

[["hello", "world"], ["programming", "in", "python"]]

Преобразуем наши данные в такой формат, а затем создадим объекты corpus и dictionary, с которыми будет работать модель.


In [5]:
texts = [recipe["ingredients"] for recipe in recipes]
dictionary = corpora.Dictionary(texts)   # составляем словарь
corpus = [dictionary.doc2bow(text) for text in texts]  # составляем корпус документов

In [6]:
print(texts[2])
print(corpus[2])


['eggs', 'pepper', 'salt', 'mayonaise', 'cooking oil', 'green chilies', 'grilled chicken breasts', 'garlic powder', 'yellow onion', 'soy sauce', 'butter', 'chicken livers']
[(0, 1), (10, 1), (17, 1), (20, 1), (21, 1), (22, 1), (23, 1), (24, 1), (25, 1), (26, 1), (27, 1), (28, 1)]

У объекта dictionary есть полезная переменная dictionary.token2id, позволяющая находить соответствие между ингредиентами и их индексами.

Обучение модели

Вам может понадобиться документация LDA в gensim.

Задание 1. Обучите модель LDA с 40 темами, установив количество проходов по коллекции 5 и оставив остальные параметры по умолчанию.

Затем вызовите метод модели show_topics, указав количество тем 40 и количество токенов 10, и сохраните результат (топы ингредиентов в темах) в отдельную переменную. Если при вызове метода show_topics указать параметр formatted=True, то топы ингредиентов будет удобно выводить на печать, если formatted=False, будет удобно работать со списком программно. Выведите топы на печать, рассмотрите темы, а затем ответьте на вопрос:

Сколько раз ингредиенты "salt", "sugar", "water", "mushrooms", "chicken", "eggs" встретились среди топов-10 всех 40 тем? При ответе не нужно учитывать составные ингредиенты, например, "hot water".

Передайте 6 чисел в функцию save_answers1 и загрузите сгенерированный файл в форму.

У gensim нет возможности фиксировать случайное приближение через параметры метода, но библиотека использует numpy для инициализации матриц. Поэтому, по утверждению автора библиотеки, фиксировать случайное приближение нужно командой, которая написана в следующей ячейке. Перед строкой кода с построением модели обязательно вставляйте указанную строку фиксации random.seed.


In [7]:
from gensim.models import LdaModel

In [8]:
np.random.seed(76543)
# здесь код для построения модели:
lda = LdaModel(corpus, num_topics=40, passes=5)

In [9]:
lda.show_topics(num_topics=40, num_words=10)


Out[9]:
[(0,
  '0.110*"712" + 0.098*"557" + 0.064*"551" + 0.058*"501" + 0.050*"189" + 0.049*"970" + 0.032*"89" + 0.032*"86" + 0.031*"708" + 0.028*"908"'),
 (1,
  '0.111*"17" + 0.106*"34" + 0.103*"212" + 0.071*"33" + 0.059*"30" + 0.048*"0" + 0.048*"200" + 0.044*"180" + 0.030*"1185" + 0.022*"1286"'),
 (2,
  '0.045*"500" + 0.037*"1337" + 0.036*"17" + 0.032*"122" + 0.032*"30" + 0.031*"770" + 0.030*"278" + 0.029*"23" + 0.028*"533" + 0.028*"344"'),
 (3,
  '0.067*"233" + 0.061*"210" + 0.053*"209" + 0.051*"447" + 0.040*"315" + 0.034*"237" + 0.031*"1073" + 0.031*"743" + 0.030*"18" + 0.029*"235"'),
 (4,
  '0.059*"17" + 0.054*"195" + 0.053*"27" + 0.053*"33" + 0.045*"186" + 0.042*"40" + 0.036*"348" + 0.032*"6" + 0.028*"206" + 0.025*"32"'),
 (5,
  '0.080*"57" + 0.070*"252" + 0.068*"305" + 0.058*"54" + 0.048*"107" + 0.038*"76" + 0.038*"33" + 0.033*"36" + 0.033*"17" + 0.031*"385"'),
 (6,
  '0.060*"199" + 0.058*"1638" + 0.045*"339" + 0.038*"483" + 0.030*"944" + 0.029*"1735" + 0.026*"2481" + 0.026*"931" + 0.024*"1024" + 0.020*"723"'),
 (7,
  '0.094*"207" + 0.076*"916" + 0.039*"373" + 0.039*"173" + 0.034*"490" + 0.032*"1080" + 0.032*"223" + 0.025*"152" + 0.024*"691" + 0.022*"982"'),
 (8,
  '0.167*"143" + 0.114*"71" + 0.059*"219" + 0.046*"15" + 0.032*"204" + 0.024*"502" + 0.021*"519" + 0.020*"560" + 0.019*"514" + 0.019*"1068"'),
 (9,
  '0.154*"535" + 0.070*"876" + 0.064*"245" + 0.064*"437" + 0.052*"1070" + 0.048*"874" + 0.039*"320" + 0.031*"804" + 0.029*"609" + 0.028*"1518"'),
 (10,
  '0.109*"12" + 0.103*"17" + 0.098*"10" + 0.091*"122" + 0.074*"23" + 0.066*"50" + 0.055*"65" + 0.049*"53" + 0.041*"311" + 0.041*"289"'),
 (11,
  '0.079*"59" + 0.068*"74" + 0.068*"17" + 0.054*"111" + 0.052*"55" + 0.052*"6" + 0.048*"840" + 0.046*"465" + 0.044*"112" + 0.033*"5"'),
 (12,
  '0.099*"731" + 0.079*"82" + 0.058*"352" + 0.055*"334" + 0.052*"446" + 0.042*"798" + 0.040*"938" + 0.030*"286" + 0.026*"33" + 0.025*"1744"'),
 (13,
  '0.076*"107" + 0.076*"116" + 0.071*"17" + 0.069*"278" + 0.045*"57" + 0.036*"119" + 0.031*"309" + 0.031*"30" + 0.031*"213" + 0.028*"32"'),
 (14,
  '0.077*"228" + 0.045*"200" + 0.042*"362" + 0.037*"22" + 0.032*"162" + 0.028*"6" + 0.027*"53" + 0.027*"16" + 0.024*"96" + 0.022*"95"'),
 (15,
  '0.146*"193" + 0.145*"312" + 0.062*"77" + 0.051*"699" + 0.037*"106" + 0.034*"253" + 0.031*"18" + 0.027*"243" + 0.026*"333" + 0.021*"1051"'),
 (16,
  '0.138*"250" + 0.086*"330" + 0.056*"949" + 0.054*"772" + 0.045*"276" + 0.029*"312" + 0.029*"76" + 0.026*"77" + 0.026*"868" + 0.026*"795"'),
 (17,
  '0.049*"17" + 0.043*"274" + 0.041*"351" + 0.038*"33" + 0.037*"124" + 0.037*"358" + 0.036*"28" + 0.034*"560" + 0.033*"38" + 0.032*"11"'),
 (18,
  '0.080*"215" + 0.064*"17" + 0.058*"33" + 0.041*"30" + 0.041*"458" + 0.035*"0" + 0.035*"267" + 0.035*"656" + 0.032*"388" + 0.028*"735"'),
 (19,
  '0.076*"31" + 0.048*"17" + 0.047*"113" + 0.040*"277" + 0.030*"346" + 0.029*"33" + 0.028*"16" + 0.026*"123" + 0.025*"43" + 0.024*"90"'),
 (20,
  '0.052*"1276" + 0.049*"598" + 0.043*"118" + 0.038*"2028" + 0.037*"336" + 0.036*"103" + 0.036*"495" + 0.031*"932" + 0.031*"895" + 0.030*"1099"'),
 (21,
  '0.142*"62" + 0.095*"622" + 0.049*"146" + 0.039*"484" + 0.034*"1546" + 0.032*"1168" + 0.031*"1035" + 0.030*"139" + 0.030*"1065" + 0.028*"589"'),
 (22,
  '0.081*"51" + 0.068*"438" + 0.057*"53" + 0.049*"23" + 0.047*"597" + 0.040*"48" + 0.030*"17" + 0.029*"131" + 0.028*"244" + 0.028*"581"'),
 (23,
  '0.068*"75" + 0.066*"31" + 0.047*"84" + 0.041*"1044" + 0.039*"16" + 0.038*"38" + 0.038*"17" + 0.037*"695" + 0.031*"729" + 0.030*"107"'),
 (24,
  '0.079*"53" + 0.073*"1083" + 0.064*"525" + 0.041*"30" + 0.038*"702" + 0.034*"1043" + 0.021*"337" + 0.020*"148" + 0.020*"111" + 0.019*"350"'),
 (25,
  '0.134*"202" + 0.102*"122" + 0.093*"17" + 0.076*"53" + 0.058*"312" + 0.038*"460" + 0.035*"396" + 0.034*"364" + 0.031*"302" + 0.029*"532"'),
 (26,
  '0.100*"230" + 0.070*"52" + 0.064*"373" + 0.055*"370" + 0.042*"17" + 0.039*"23" + 0.035*"496" + 0.034*"899" + 0.032*"10" + 0.031*"128"'),
 (27,
  '0.094*"190" + 0.053*"57" + 0.052*"17" + 0.035*"227" + 0.033*"6" + 0.032*"0" + 0.031*"477" + 0.030*"84" + 0.029*"261" + 0.027*"394"'),
 (28,
  '0.090*"57" + 0.090*"6" + 0.078*"33" + 0.061*"17" + 0.043*"552" + 0.038*"0" + 0.033*"145" + 0.029*"357" + 0.029*"354" + 0.023*"657"'),
 (29,
  '0.071*"188" + 0.065*"451" + 0.064*"1124" + 0.064*"1106" + 0.064*"406" + 0.058*"172" + 0.053*"485" + 0.039*"781" + 0.037*"2029" + 0.029*"1210"'),
 (30,
  '0.071*"268" + 0.046*"38" + 0.045*"521" + 0.044*"577" + 0.044*"203" + 0.038*"247" + 0.034*"31" + 0.030*"33" + 0.027*"228" + 0.022*"11"'),
 (31,
  '0.116*"153" + 0.077*"91" + 0.070*"205" + 0.066*"957" + 0.049*"174" + 0.034*"844" + 0.033*"182" + 0.033*"606" + 0.027*"222" + 0.024*"30"'),
 (32,
  '0.068*"300" + 0.049*"22" + 0.042*"295" + 0.041*"53" + 0.035*"826" + 0.033*"125" + 0.032*"299" + 0.032*"30" + 0.031*"47" + 0.027*"793"'),
 (33,
  '0.083*"25" + 0.061*"108" + 0.060*"517" + 0.054*"165" + 0.054*"160" + 0.030*"1259" + 0.030*"760" + 0.029*"197" + 0.027*"993" + 0.025*"505"'),
 (34,
  '0.100*"76" + 0.071*"107" + 0.062*"57" + 0.055*"17" + 0.051*"18" + 0.044*"5" + 0.037*"109" + 0.037*"102" + 0.035*"79" + 0.029*"11"'),
 (35,
  '0.093*"22" + 0.052*"95" + 0.050*"98" + 0.046*"97" + 0.045*"53" + 0.045*"6" + 0.033*"351" + 0.032*"30" + 0.029*"17" + 0.025*"16"'),
 (36,
  '0.078*"248" + 0.070*"26" + 0.052*"77" + 0.041*"6" + 0.039*"57" + 0.037*"732" + 0.034*"553" + 0.030*"989" + 0.030*"527" + 0.029*"18"'),
 (37,
  '0.071*"187" + 0.062*"590" + 0.058*"980" + 0.056*"2" + 0.050*"1378" + 0.050*"1296" + 0.045*"1413" + 0.040*"822" + 0.032*"1391" + 0.031*"685"'),
 (38,
  '0.064*"623" + 0.062*"254" + 0.060*"30" + 0.060*"433" + 0.058*"33" + 0.057*"431" + 0.047*"645" + 0.042*"183" + 0.038*"35" + 0.036*"107"'),
 (39,
  '0.096*"24" + 0.088*"488" + 0.078*"46" + 0.060*"375" + 0.052*"17" + 0.044*"211" + 0.043*"170" + 0.040*"57" + 0.026*"121" + 0.023*"18"')]

In [10]:
top_words = lda.show_topics(num_topics=40, num_words=10, formatted=False)
top_words = [tup[1] for tup in top_words]
print(top_words)
ingrids = ["salt", "sugar", "water", "mushrooms", "chicken", "eggs"]
ids = [dictionary.token2id[x] for x in ingrids]
counts = {"salt": 0, "sugar": 0, "water": 0, "mushrooms": 0, "chicken": 0, "eggs": 0}
for ingrid_list in top_words:
    for x in ingrid_list:
        for i in range(len(ids)):
            if ids[i] == int(x[0]):
                counts[ingrids[i]] += 1


[[('712', 0.11031740481837812), ('557', 0.098193181698149709), ('551', 0.063549768269111781), ('501', 0.057512832024643593), ('189', 0.049778735762024212), ('970', 0.048737415497588532), ('89', 0.031943297110414479), ('86', 0.031716896320199209), ('708', 0.031294694814618183), ('908', 0.027818586106326756)], [('17', 0.11073841821130752), ('34', 0.10583958132715006), ('212', 0.10295859991958865), ('33', 0.071340056185906039), ('30', 0.059081795220026899), ('0', 0.048246586828244405), ('200', 0.047503916970522232), ('180', 0.043636812760221695), ('1185', 0.030418956700502417), ('1286', 0.021815875968393957)], [('500', 0.045074518229531874), ('1337', 0.036551414746393236), ('17', 0.036467646976469849), ('122', 0.032442875519816013), ('30', 0.032222596543938352), ('770', 0.030531984415805593), ('278', 0.02985497923078239), ('23', 0.028851247563552861), ('533', 0.028339029539539567), ('344', 0.028329314894459036)], [('233', 0.067254800399685261), ('210', 0.061377467247493558), ('209', 0.053425792904435603), ('447', 0.050821185556799431), ('315', 0.040210418660281695), ('237', 0.033700608768516674), ('1073', 0.03123395963863063), ('743', 0.030525529668608529), ('18', 0.029523661722000633), ('235', 0.02886173323841331)], [('17', 0.059320536822449331), ('195', 0.054224808034073882), ('27', 0.0533866727267285), ('33', 0.052757583701288031), ('186', 0.044554194938916124), ('40', 0.042071363337108335), ('348', 0.03555400567793441), ('6', 0.031558398296023825), ('206', 0.027915328472925726), ('32', 0.025373300407842806)], [('57', 0.079852464331273201), ('252', 0.069939052288326461), ('305', 0.068160503621738297), ('54', 0.058319941840173549), ('107', 0.047870110762918215), ('76', 0.03782650526770661), ('33', 0.03780052551386872), ('36', 0.033186247743527499), ('17', 0.032517655703001032), ('385', 0.031462566957437661)], [('199', 0.060234069693142517), ('1638', 0.058349917829353316), ('339', 0.0452308073844696), ('483', 0.037564675311015136), ('944', 0.029729687275530495), ('1735', 0.028920649916506967), ('2481', 0.026092574889520943), ('931', 0.025893102510467669), ('1024', 0.02376007072419661), ('723', 0.020283928742927729)], [('207', 0.094104761526915742), ('916', 0.075580333317662243), ('373', 0.038972556302062165), ('173', 0.038857800016602696), ('490', 0.033679591953835797), ('1080', 0.032367013306989344), ('223', 0.03205419543533454), ('152', 0.024527068504773299), ('691', 0.024001425416295036), ('982', 0.022386139603383069)], [('143', 0.16748937793740232), ('71', 0.11396093219514668), ('219', 0.059397573371305641), ('15', 0.045576782342901113), ('204', 0.032449580759370288), ('502', 0.024047817702988365), ('519', 0.020649978221485579), ('560', 0.01996165030559157), ('514', 0.019479428050762197), ('1068', 0.018614509974930585)], [('535', 0.15398177303987884), ('876', 0.070264623818883279), ('245', 0.064080985735085846), ('437', 0.063685801623154722), ('1070', 0.051876692412845433), ('874', 0.048014617072455128), ('320', 0.038535771638636286), ('804', 0.030816941050488482), ('609', 0.028656921329072757), ('1518', 0.028228646475154245)], [('12', 0.10916850214478813), ('17', 0.10330407667707098), ('10', 0.097861386088721677), ('122', 0.091441298538657775), ('23', 0.073634788192786793), ('50', 0.06631824626914902), ('65', 0.055130812590191473), ('53', 0.048776846218307267), ('311', 0.041136922671192531), ('289', 0.040817005273811345)], [('59', 0.079276281648342967), ('74', 0.068215683509304778), ('17', 0.067899262974302863), ('111', 0.053708296749761894), ('55', 0.052231478425913344), ('6', 0.051595662181120362), ('840', 0.047966521922836423), ('465', 0.046034900945882036), ('112', 0.043955650700653055), ('5', 0.033455806908704776)], [('731', 0.099321146208647959), ('82', 0.079009172927578461), ('352', 0.058489135903042493), ('334', 0.055072778120090995), ('446', 0.052110457875305757), ('798', 0.041785812403924122), ('938', 0.039770863458143471), ('286', 0.03047655884381608), ('33', 0.025511416272929872), ('1744', 0.024505434875950308)], [('107', 0.076153334241783013), ('116', 0.075693676159786477), ('17', 0.071052056136298197), ('278', 0.068844893972015875), ('57', 0.045187369280209097), ('119', 0.036300512577867726), ('309', 0.030837246953198477), ('30', 0.03059772020406502), ('213', 0.030573772412076049), ('32', 0.028353661296773882)], [('228', 0.077029635951001083), ('200', 0.044883428393283631), ('362', 0.042425257192061527), ('22', 0.036745788135712748), ('162', 0.032411935465174499), ('6', 0.027889090186329239), ('53', 0.027461372284407662), ('16', 0.027150017822779388), ('96', 0.023514675288020672), ('95', 0.021816438785205474)], [('193', 0.14593216375808044), ('312', 0.14520143254738885), ('77', 0.06169325149006815), ('699', 0.05058743157528639), ('106', 0.037367594259907981), ('253', 0.034208058068761676), ('18', 0.030643492047096384), ('243', 0.027487877351335711), ('333', 0.025829129538369203), ('1051', 0.021138059359712243)], [('250', 0.13766122465508093), ('330', 0.086170706211659912), ('949', 0.055748050649396121), ('772', 0.05355957962690884), ('276', 0.045197285873743671), ('312', 0.028891468862695613), ('76', 0.028540155540682111), ('77', 0.026244317974660127), ('868', 0.025696318944993069), ('795', 0.025651755670563211)], [('17', 0.049293344740257622), ('274', 0.04304747040119053), ('351', 0.040878936458253426), ('33', 0.038170837282037635), ('124', 0.037050651227055642), ('358', 0.036617094956315807), ('28', 0.035604316612760055), ('560', 0.034021413324606883), ('38', 0.032518114768076069), ('11', 0.032097034357012146)], [('215', 0.080213046872792321), ('17', 0.064301405163097139), ('33', 0.057561988823765668), ('30', 0.041055293414583346), ('458', 0.040805910927123885), ('0', 0.035457004215095837), ('267', 0.03478249927379095), ('656', 0.034502834021356413), ('388', 0.031534308152203948), ('735', 0.028335514878835177)], [('31', 0.075768496082628839), ('17', 0.04774365470111358), ('113', 0.047408655926203566), ('277', 0.0395238878463883), ('346', 0.029521086651328656), ('33', 0.029167491603855882), ('16', 0.027770417921579076), ('123', 0.025662186172984519), ('43', 0.025406706788283343), ('90', 0.024098869898488483)], [('1276', 0.051792625158022326), ('598', 0.048840147026277529), ('118', 0.043363109583184643), ('2028', 0.038367693314633036), ('336', 0.036903265958810799), ('103', 0.036434564648813075), ('495', 0.036039475857797092), ('932', 0.031423774079323188), ('895', 0.030965856756100623), ('1099', 0.03028071003528186)], [('62', 0.14197309778091763), ('622', 0.094787929196020443), ('146', 0.049492134719345514), ('484', 0.038933361182664591), ('1546', 0.033963401033095704), ('1168', 0.032369576341951811), ('1035', 0.030584018376797174), ('139', 0.030185084974304367), ('1065', 0.02999233941450314), ('589', 0.028021560948687838)], [('51', 0.081012113831658128), ('438', 0.067894582663356295), ('53', 0.0573384908761101), ('23', 0.049372682677593087), ('597', 0.046875584451679178), ('48', 0.039509823226766549), ('17', 0.029701153583017635), ('131', 0.029413460660494301), ('244', 0.028286395069721821), ('581', 0.027693930921596908)], [('75', 0.068127455128870404), ('31', 0.065842144162111843), ('84', 0.046969884537141383), ('1044', 0.041121352514615954), ('16', 0.039175188920116871), ('38', 0.038243881168596637), ('17', 0.038154921396462392), ('695', 0.037358895491386747), ('729', 0.030992996800724745), ('107', 0.030291725482058968)], [('53', 0.078855733132913775), ('1083', 0.073481991220539833), ('525', 0.063564552771998101), ('30', 0.040547920443899078), ('702', 0.038349883055970813), ('1043', 0.034485558016859846), ('337', 0.021466131792527297), ('148', 0.020101420848300352), ('111', 0.019741219297539581), ('350', 0.019426317865499972)], [('202', 0.13437685332572161), ('122', 0.10158245691389667), ('17', 0.093010471030096825), ('53', 0.075924603474159413), ('312', 0.058263788575322002), ('460', 0.038277201504787708), ('396', 0.035375369915315098), ('364', 0.034128616418202321), ('302', 0.030756461926521497), ('532', 0.029445546999593553)], [('230', 0.10017817492419163), ('52', 0.069562438240563101), ('373', 0.06412479932653628), ('370', 0.05478401435607614), ('17', 0.042386408615201814), ('23', 0.03861634509873061), ('496', 0.034858123424690378), ('899', 0.034350991181369826), ('10', 0.032217125682040999), ('128', 0.030993159545632032)], [('190', 0.093597116924427959), ('57', 0.052501583538487967), ('17', 0.05243687781786828), ('227', 0.034971419367096614), ('6', 0.033490783881027109), ('0', 0.03179029763753119), ('477', 0.031202673698816671), ('84', 0.030040649274892046), ('261', 0.029312444994978794), ('394', 0.02707707825402831)], [('57', 0.090074916630196289), ('6', 0.089774528616299518), ('33', 0.077806640675628147), ('17', 0.061230046326876543), ('552', 0.0426414098323986), ('0', 0.03755024740789123), ('145', 0.03319938522102537), ('357', 0.029448762226671144), ('354', 0.028610417283435559), ('657', 0.022754400719705335)], [('188', 0.071464790437822195), ('451', 0.064793179324297651), ('1124', 0.064388630280295761), ('1106', 0.063949489449031116), ('406', 0.063766059706165459), ('172', 0.058312498725896077), ('485', 0.052888962813850283), ('781', 0.039217986135024599), ('2029', 0.037441831393949104), ('1210', 0.029110724002620863)], [('268', 0.070611194697888249), ('38', 0.045931222149349409), ('521', 0.045396651788099693), ('577', 0.044098645421050832), ('203', 0.043533964231587494), ('247', 0.038471723025966763), ('31', 0.03409026464610615), ('33', 0.030155165463030816), ('228', 0.0269320184653612), ('11', 0.022383459697389092)], [('153', 0.1156522356668228), ('91', 0.076770996382038936), ('205', 0.070399000132738546), ('957', 0.066440041070095934), ('174', 0.049322972427510187), ('844', 0.033580035131554713), ('182', 0.0332541890598992), ('606', 0.032523891716690796), ('222', 0.027006829193221598), ('30', 0.024039418270893769)], [('300', 0.068154549276348966), ('22', 0.049426366328389613), ('295', 0.04198439851503713), ('53', 0.040547267563622834), ('826', 0.035291552651297887), ('125', 0.03338773384713737), ('299', 0.032294544018030509), ('30', 0.031876879066903979), ('47', 0.03056863201377627), ('793', 0.02652606923998229)], [('25', 0.082566132932977154), ('108', 0.060918312290853455), ('517', 0.060489653563005348), ('165', 0.054492642485868936), ('160', 0.054271291038884423), ('1259', 0.030213179228007897), ('760', 0.02972693696607067), ('197', 0.029466243384103464), ('993', 0.027064023179212478), ('505', 0.025495854358799558)], [('76', 0.10012195345527423), ('107', 0.070876724365020419), ('57', 0.061522516018911427), ('17', 0.055402996323434352), ('18', 0.050945734972775707), ('5', 0.043516638785107281), ('109', 0.037307690662662644), ('102', 0.036577153232141967), ('79', 0.034917859473177104), ('11', 0.02856835680620335)], [('22', 0.092681931270940487), ('95', 0.051907477498082298), ('98', 0.050112784924124888), ('97', 0.045780525767373716), ('53', 0.044814566263902192), ('6', 0.044800504986864456), ('351', 0.033097504193278275), ('30', 0.031760665344231956), ('17', 0.028507812246634248), ('16', 0.025469340911313604)], [('248', 0.077568733985662539), ('26', 0.070011011362731176), ('77', 0.051834995919736691), ('6', 0.041319554811478997), ('57', 0.039368599423571515), ('732', 0.037311254387466929), ('553', 0.034291798951201692), ('989', 0.030446724852364812), ('527', 0.030143698821303827), ('18', 0.029343290586638201)], [('187', 0.071118892813440859), ('590', 0.061764678470958533), ('980', 0.057547075562669789), ('2', 0.056314390521240883), ('1378', 0.050262010068037863), ('1296', 0.050258624629407743), ('1413', 0.0451466847252339), ('822', 0.0399682383040098), ('1391', 0.032231265434303699), ('685', 0.030886963302067492)], [('623', 0.063639565741272081), ('254', 0.062136983465440603), ('30', 0.060017271506337004), ('433', 0.059790501473295614), ('33', 0.057957425099329184), ('431', 0.056827825782738407), ('645', 0.047421106514967275), ('183', 0.042161216558993318), ('35', 0.038391767902530995), ('107', 0.036127872683778886)], [('24', 0.096033115677320188), ('488', 0.088262868357828247), ('46', 0.078041691569743582), ('375', 0.059728665922038349), ('17', 0.051892049781362588), ('211', 0.044403597528076662), ('170', 0.042963702334527509), ('57', 0.03991006501439133), ('121', 0.026403680692333321), ('18', 0.023278278605623495)]]

In [11]:
def save_answers1(c_salt, c_sugar, c_water, c_mushrooms, c_chicken, c_eggs):
    with open("cooking_LDA_pa_task1.txt", "w") as fout:
        fout.write(" ".join([str(el) for el in [c_salt, c_sugar, c_water, c_mushrooms, c_chicken, c_eggs]]))

In [12]:
save_answers1(counts["salt"], counts["sugar"], counts["water"], counts["mushrooms"], counts["chicken"], counts["eggs"])

Фильтрация словаря

В топах тем гораздо чаще встречаются первые три рассмотренных ингредиента, чем последние три. При этом наличие в рецепте курицы, яиц и грибов яснее дает понять, что мы будем готовить, чем наличие соли, сахара и воды. Таким образом, даже в рецептах есть слова, часто встречающиеся в текстах и не несущие смысловой нагрузки, и поэтому их не желательно видеть в темах. Наиболее простой прием борьбы с такими фоновыми элементами — фильтрация словаря по частоте. Обычно словарь фильтруют с двух сторон: убирают очень редкие слова (в целях экономии памяти) и очень частые слова (в целях повышения интерпретируемости тем). Мы уберем только частые слова.


In [13]:
import copy
dictionary2 = copy.deepcopy(dictionary)

In [14]:
print(dictionary2.dfs)


{0: 4438, 1: 137, 2: 228, 3: 270, 4: 358, 5: 1896, 6: 7380, 7: 229, 8: 148, 9: 154, 10: 3388, 11: 3058, 12: 2263, 13: 361, 14: 341, 15: 385, 16: 4385, 17: 18048, 18: 4784, 19: 108, 20: 5, 21: 65, 22: 3296, 23: 4847, 24: 781, 25: 483, 26: 1184, 27: 1442, 28: 768, 29: 26, 30: 7457, 31: 2747, 32: 2627, 33: 7972, 34: 1970, 35: 839, 36: 1477, 37: 103, 38: 2036, 39: 282, 40: 1523, 41: 24, 42: 40, 43: 925, 44: 18, 45: 343, 46: 1394, 47: 338, 48: 501, 49: 678, 50: 1738, 51: 1298, 52: 1231, 53: 6434, 54: 1094, 55: 796, 56: 73, 57: 7971, 58: 103, 59: 1730, 60: 940, 61: 461, 62: 554, 63: 1, 64: 22, 65: 1348, 66: 173, 67: 51, 68: 119, 69: 424, 70: 164, 71: 1698, 72: 300, 73: 56, 74: 1439, 75: 965, 76: 2747, 77: 3113, 78: 298, 79: 1137, 80: 1223, 81: 154, 82: 578, 83: 62, 84: 1706, 85: 185, 86: 164, 87: 55, 88: 134, 89: 168, 90: 1503, 91: 341, 92: 439, 93: 152, 94: 505, 95: 1773, 96: 425, 97: 1757, 98: 1891, 99: 264, 100: 125, 101: 114, 102: 1679, 103: 171, 104: 13, 105: 150, 106: 285, 107: 6236, 108: 258, 109: 858, 110: 841, 111: 1072, 112: 1228, 113: 768, 114: 134, 115: 99, 116: 1490, 117: 286, 118: 212, 119: 473, 120: 41, 121: 227, 122: 4632, 123: 738, 124: 644, 125: 366, 126: 110, 127: 192, 128: 455, 129: 37, 130: 233, 131: 395, 132: 5, 133: 81, 134: 395, 135: 8, 136: 17, 137: 158, 138: 19, 139: 130, 140: 472, 141: 1939, 142: 793, 143: 1368, 144: 116, 145: 1554, 146: 387, 147: 22, 148: 111, 149: 429, 150: 178, 151: 317, 152: 156, 153: 509, 154: 263, 155: 71, 156: 454, 157: 227, 158: 22, 159: 20, 160: 206, 161: 122, 162: 676, 163: 459, 164: 14, 165: 220, 166: 137, 167: 51, 168: 93, 169: 248, 170: 541, 171: 155, 172: 249, 173: 229, 174: 206, 175: 406, 176: 347, 177: 28, 178: 455, 179: 312, 180: 416, 181: 9, 182: 148, 183: 340, 184: 87, 185: 90, 186: 1287, 187: 268, 188: 295, 189: 244, 190: 1885, 191: 79, 192: 342, 193: 1146, 194: 13, 195: 1180, 196: 111, 197: 106, 198: 57, 199: 473, 200: 2814, 201: 30, 202: 2948, 203: 865, 204: 447, 205: 350, 206: 837, 207: 610, 208: 376, 209: 674, 210: 912, 211: 1604, 212: 1018, 213: 538, 214: 267, 215: 620, 216: 528, 217: 84, 218: 113, 219: 482, 220: 37, 221: 5, 222: 122, 223: 1247, 224: 207, 225: 120, 226: 26, 227: 585, 228: 3078, 229: 1623, 230: 1093, 231: 107, 232: 2, 233: 688, 234: 1, 235: 276, 236: 345, 237: 306, 238: 114, 239: 50, 240: 50, 241: 253, 242: 259, 243: 336, 244: 562, 245: 302, 246: 196, 247: 769, 248: 1039, 249: 167, 250: 949, 251: 42, 252: 873, 253: 422, 254: 1036, 255: 59, 256: 44, 257: 16, 258: 54, 259: 3, 260: 11, 261: 467, 262: 52, 263: 50, 264: 130, 265: 45, 266: 15, 267: 373, 268: 1538, 269: 175, 270: 79, 271: 56, 272: 295, 273: 458, 274: 935, 275: 159, 276: 299, 277: 694, 278: 1250, 279: 189, 280: 152, 281: 16, 282: 31, 283: 61, 284: 19, 285: 1, 286: 205, 287: 15, 288: 85, 289: 863, 290: 66, 291: 118, 292: 98, 293: 17, 294: 226, 295: 345, 296: 121, 297: 24, 298: 39, 299: 331, 300: 503, 301: 51, 302: 619, 303: 86, 304: 234, 305: 1218, 306: 282, 307: 175, 308: 825, 309: 457, 310: 1299, 311: 942, 312: 2782, 313: 367, 314: 118, 315: 1218, 316: 129, 317: 877, 318: 68, 319: 345, 320: 306, 321: 26, 322: 4, 323: 506, 324: 276, 325: 128, 326: 11, 327: 36, 328: 68, 329: 248, 330: 578, 331: 227, 332: 44, 333: 218, 334: 435, 335: 62, 336: 193, 337: 191, 338: 83, 339: 256, 340: 20, 341: 14, 342: 90, 343: 364, 344: 1158, 345: 117, 346: 949, 347: 307, 348: 873, 349: 30, 350: 121, 351: 1755, 352: 408, 353: 442, 354: 453, 355: 11, 356: 62, 357: 501, 358: 854, 359: 1, 360: 142, 361: 152, 362: 1204, 363: 27, 364: 575, 365: 311, 366: 19, 367: 25, 368: 15, 369: 19, 370: 605, 371: 110, 372: 4, 373: 1503, 374: 1, 375: 513, 376: 10, 377: 28, 378: 60, 379: 5, 380: 51, 381: 4, 382: 62, 383: 298, 384: 96, 385: 402, 386: 144, 387: 15, 388: 237, 389: 371, 390: 118, 391: 574, 392: 178, 393: 108, 394: 474, 395: 238, 396: 577, 397: 206, 398: 189, 399: 92, 400: 42, 401: 63, 402: 78, 403: 204, 404: 470, 405: 111, 406: 271, 407: 16, 408: 43, 409: 67, 410: 144, 411: 27, 412: 104, 413: 37, 414: 54, 415: 32, 416: 49, 417: 193, 418: 130, 419: 160, 420: 12, 421: 33, 422: 4, 423: 5, 424: 3, 425: 11, 426: 458, 427: 112, 428: 87, 429: 20, 430: 59, 431: 453, 432: 154, 433: 646, 434: 395, 435: 85, 436: 18, 437: 336, 438: 849, 439: 53, 440: 149, 441: 7, 442: 77, 443: 164, 444: 31, 445: 1, 446: 345, 447: 414, 448: 103, 449: 8, 450: 74, 451: 234, 452: 5, 453: 5, 454: 64, 455: 138, 456: 84, 457: 3, 458: 316, 459: 21, 460: 764, 461: 61, 462: 216, 463: 322, 464: 43, 465: 684, 466: 21, 467: 282, 468: 77, 469: 440, 470: 109, 471: 326, 472: 953, 473: 221, 474: 12, 475: 352, 476: 385, 477: 865, 478: 156, 479: 3, 480: 268, 481: 260, 482: 92, 483: 131, 484: 130, 485: 209, 486: 208, 487: 73, 488: 752, 489: 35, 490: 1583, 491: 201, 492: 45, 493: 57, 494: 31, 495: 167, 496: 460, 497: 8, 498: 1, 499: 7, 500: 426, 501: 287, 502: 189, 503: 52, 504: 36, 505: 95, 506: 319, 507: 220, 508: 342, 509: 27, 510: 240, 511: 3, 512: 3, 513: 81, 514: 205, 515: 31, 516: 86, 517: 225, 518: 131, 519: 175, 520: 116, 521: 896, 522: 409, 523: 291, 524: 49, 525: 355, 526: 18, 527: 268, 528: 31, 529: 136, 530: 44, 531: 71, 532: 485, 533: 353, 534: 25, 535: 768, 536: 17, 537: 19, 538: 42, 539: 4, 540: 364, 541: 22, 542: 2, 543: 393, 544: 21, 545: 15, 546: 39, 547: 3, 548: 108, 549: 6, 550: 292, 551: 348, 552: 892, 553: 383, 554: 9, 555: 72, 556: 62, 557: 502, 558: 10, 559: 193, 560: 1160, 561: 68, 562: 9, 563: 137, 564: 55, 565: 181, 566: 62, 567: 387, 568: 70, 569: 173, 570: 1, 571: 116, 572: 82, 573: 30, 574: 7, 575: 150, 576: 60, 577: 963, 578: 11, 579: 50, 580: 33, 581: 453, 582: 106, 583: 109, 584: 57, 585: 68, 586: 27, 587: 3, 588: 50, 589: 158, 590: 267, 591: 17, 592: 21, 593: 6, 594: 9, 595: 250, 596: 60, 597: 542, 598: 230, 599: 57, 600: 436, 601: 22, 602: 55, 603: 119, 604: 18, 605: 157, 606: 157, 607: 15, 608: 9, 609: 137, 610: 106, 611: 72, 612: 11, 613: 4, 614: 19, 615: 5, 616: 69, 617: 14, 618: 37, 619: 1, 620: 10, 621: 196, 622: 352, 623: 567, 624: 222, 625: 28, 626: 10, 627: 23, 628: 50, 629: 50, 630: 124, 631: 62, 632: 355, 633: 136, 634: 22, 635: 34, 636: 60, 637: 18, 638: 140, 639: 5, 640: 266, 641: 13, 642: 70, 643: 81, 644: 9, 645: 600, 646: 49, 647: 15, 648: 11, 649: 62, 650: 10, 651: 157, 652: 159, 653: 66, 654: 7, 655: 22, 656: 240, 657: 669, 658: 26, 659: 122, 660: 44, 661: 103, 662: 34, 663: 21, 664: 321, 665: 11, 666: 19, 667: 158, 668: 582, 669: 61, 670: 50, 671: 6, 672: 49, 673: 189, 674: 11, 675: 375, 676: 221, 677: 40, 678: 17, 679: 618, 680: 94, 681: 212, 682: 183, 683: 60, 684: 104, 685: 135, 686: 17, 687: 17, 688: 246, 689: 21, 690: 61, 691: 163, 692: 29, 693: 48, 694: 44, 695: 314, 696: 127, 697: 27, 698: 48, 699: 353, 700: 29, 701: 144, 702: 223, 703: 83, 704: 339, 705: 71, 706: 20, 707: 266, 708: 206, 709: 20, 710: 47, 711: 125, 712: 591, 713: 77, 714: 159, 715: 10, 716: 4, 717: 63, 718: 135, 719: 28, 720: 185, 721: 222, 722: 10, 723: 64, 724: 194, 725: 5, 726: 133, 727: 78, 728: 73, 729: 302, 730: 42, 731: 982, 732: 321, 733: 94, 734: 7, 735: 202, 736: 5, 737: 71, 738: 5, 739: 147, 740: 128, 741: 73, 742: 57, 743: 243, 744: 247, 745: 19, 746: 9, 747: 2, 748: 14, 749: 268, 750: 33, 751: 21, 752: 55, 753: 59, 754: 53, 755: 77, 756: 179, 757: 159, 758: 352, 759: 32, 760: 100, 761: 9, 762: 7, 763: 21, 764: 18, 765: 16, 766: 46, 767: 29, 768: 39, 769: 5, 770: 309, 771: 19, 772: 356, 773: 100, 774: 138, 775: 52, 776: 9, 777: 72, 778: 65, 779: 48, 780: 28, 781: 174, 782: 165, 783: 106, 784: 18, 785: 74, 786: 285, 787: 77, 788: 16, 789: 97, 790: 6, 791: 29, 792: 145, 793: 197, 794: 8, 795: 157, 796: 1111, 797: 387, 798: 271, 799: 3, 800: 93, 801: 4, 802: 20, 803: 215, 804: 161, 805: 58, 806: 4, 807: 173, 808: 1, 809: 21, 810: 43, 811: 10, 812: 59, 813: 59, 814: 192, 815: 79, 816: 68, 817: 20, 818: 34, 819: 364, 820: 229, 821: 62, 822: 157, 823: 13, 824: 30, 825: 6, 826: 230, 827: 277, 828: 3, 829: 203, 830: 229, 831: 1, 832: 51, 833: 97, 834: 10, 835: 21, 836: 2, 837: 37, 838: 268, 839: 61, 840: 1142, 841: 27, 842: 55, 843: 142, 844: 159, 845: 33, 846: 35, 847: 32, 848: 63, 849: 76, 850: 32, 851: 47, 852: 5, 853: 47, 854: 133, 855: 184, 856: 28, 857: 102, 858: 63, 859: 73, 860: 30, 861: 91, 862: 416, 863: 7, 864: 377, 865: 3, 866: 94, 867: 22, 868: 169, 869: 47, 870: 9, 871: 46, 872: 119, 873: 9, 874: 258, 875: 23, 876: 345, 877: 76, 878: 4, 879: 217, 880: 16, 881: 80, 882: 39, 883: 7, 884: 141, 885: 41, 886: 22, 887: 27, 888: 24, 889: 122, 890: 69, 891: 22, 892: 2, 893: 119, 894: 218, 895: 146, 896: 69, 897: 19, 898: 32, 899: 696, 900: 51, 901: 1, 902: 24, 903: 280, 904: 16, 905: 26, 906: 8, 907: 55, 908: 133, 909: 85, 910: 137, 911: 46, 912: 329, 913: 68, 914: 14, 915: 199, 916: 432, 917: 23, 918: 60, 919: 36, 920: 31, 921: 27, 922: 106, 923: 36, 924: 13, 925: 27, 926: 2, 927: 407, 928: 23, 929: 195, 930: 86, 931: 88, 932: 167, 933: 10, 934: 3, 935: 73, 936: 3, 937: 99, 938: 257, 939: 40, 940: 171, 941: 11, 942: 79, 943: 26, 944: 115, 945: 13, 946: 44, 947: 29, 948: 44, 949: 348, 950: 16, 951: 5, 952: 3, 953: 170, 954: 3, 955: 11, 956: 43, 957: 273, 958: 4, 959: 14, 960: 190, 961: 79, 962: 7, 963: 1, 964: 21, 965: 31, 966: 6, 967: 4, 968: 54, 969: 106, 970: 284, 971: 79, 972: 92, 973: 53, 974: 17, 975: 34, 976: 67, 977: 41, 978: 1, 979: 18, 980: 219, 981: 6, 982: 135, 983: 60, 984: 92, 985: 3, 986: 84, 987: 1, 988: 24, 989: 266, 990: 33, 991: 337, 992: 39, 993: 96, 994: 3, 995: 294, 996: 27, 997: 10, 998: 108, 999: 189, 1000: 100, 1001: 1, 1002: 78, 1003: 4, 1004: 228, 1005: 41, 1006: 33, 1007: 126, 1008: 19, 1009: 28, 1010: 98, 1011: 36, 1012: 4, 1013: 11, 1014: 40, 1015: 46, 1016: 86, 1017: 1, 1018: 39, 1019: 18, 1020: 2, 1021: 62, 1022: 142, 1023: 89, 1024: 95, 1025: 272, 1026: 9, 1027: 50, 1028: 100, 1029: 105, 1030: 183, 1031: 118, 1032: 85, 1033: 18, 1034: 15, 1035: 178, 1036: 40, 1037: 92, 1038: 282, 1039: 5, 1040: 33, 1041: 112, 1042: 38, 1043: 187, 1044: 348, 1045: 61, 1046: 63, 1047: 7, 1048: 333, 1049: 1, 1050: 26, 1051: 148, 1052: 75, 1053: 112, 1054: 1, 1055: 64, 1056: 25, 1057: 10, 1058: 114, 1059: 36, 1060: 36, 1061: 51, 1062: 58, 1063: 119, 1064: 41, 1065: 103, 1066: 47, 1067: 4, 1068: 152, 1069: 77, 1070: 270, 1071: 36, 1072: 33, 1073: 368, 1074: 108, 1075: 187, 1076: 181, 1077: 33, 1078: 149, 1079: 95, 1080: 198, 1081: 14, 1082: 18, 1083: 338, 1084: 100, 1085: 145, 1086: 21, 1087: 6, 1088: 50, 1089: 7, 1090: 263, 1091: 177, 1092: 27, 1093: 26, 1094: 41, 1095: 87, 1096: 6, 1097: 19, 1098: 17, 1099: 143, 1100: 37, 1101: 23, 1102: 38, 1103: 85, 1104: 9, 1105: 34, 1106: 280, 1107: 18, 1108: 23, 1109: 52, 1110: 15, 1111: 105, 1112: 68, 1113: 62, 1114: 15, 1115: 37, 1116: 9, 1117: 60, 1118: 40, 1119: 12, 1120: 2, 1121: 70, 1122: 30, 1123: 18, 1124: 242, 1125: 35, 1126: 16, 1127: 19, 1128: 77, 1129: 7, 1130: 43, 1131: 30, 1132: 3, 1133: 36, 1134: 18, 1135: 45, 1136: 58, 1137: 8, 1138: 134, 1139: 108, 1140: 54, 1141: 51, 1142: 25, 1143: 19, 1144: 5, 1145: 6, 1146: 3, 1147: 1, 1148: 29, 1149: 7, 1150: 67, 1151: 96, 1152: 9, 1153: 11, 1154: 5, 1155: 19, 1156: 32, 1157: 8, 1158: 42, 1159: 17, 1160: 71, 1161: 1, 1162: 63, 1163: 28, 1164: 38, 1165: 1, 1166: 4, 1167: 1, 1168: 126, 1169: 2, 1170: 24, 1171: 31, 1172: 68, 1173: 113, 1174: 237, 1175: 75, 1176: 164, 1177: 6, 1178: 96, 1179: 1, 1180: 10, 1181: 102, 1182: 25, 1183: 46, 1184: 22, 1185: 313, 1186: 6, 1187: 1, 1188: 1, 1189: 66, 1190: 11, 1191: 15, 1192: 4, 1193: 6, 1194: 28, 1195: 19, 1196: 45, 1197: 19, 1198: 4, 1199: 161, 1200: 10, 1201: 37, 1202: 60, 1203: 57, 1204: 5, 1205: 31, 1206: 68, 1207: 22, 1208: 30, 1209: 37, 1210: 123, 1211: 155, 1212: 10, 1213: 9, 1214: 16, 1215: 11, 1216: 130, 1217: 58, 1218: 193, 1219: 29, 1220: 42, 1221: 2, 1222: 10, 1223: 221, 1224: 49, 1225: 6, 1226: 18, 1227: 6, 1228: 25, 1229: 133, 1230: 23, 1231: 6, 1232: 17, 1233: 29, 1234: 4, 1235: 4, 1236: 15, 1237: 8, 1238: 12, 1239: 5, 1240: 19, 1241: 20, 1242: 183, 1243: 14, 1244: 17, 1245: 1, 1246: 19, 1247: 17, 1248: 55, 1249: 11, 1250: 17, 1251: 117, 1252: 70, 1253: 36, 1254: 20, 1255: 134, 1256: 37, 1257: 78, 1258: 8, 1259: 179, 1260: 51, 1261: 31, 1262: 91, 1263: 6, 1264: 143, 1265: 64, 1266: 25, 1267: 10, 1268: 2, 1269: 11, 1270: 39, 1271: 12, 1272: 20, 1273: 52, 1274: 184, 1275: 6, 1276: 277, 1277: 77, 1278: 220, 1279: 88, 1280: 10, 1281: 32, 1282: 23, 1283: 10, 1284: 10, 1285: 57, 1286: 219, 1287: 3, 1288: 105, 1289: 43, 1290: 175, 1291: 2, 1292: 71, 1293: 18, 1294: 263, 1295: 30, 1296: 209, 1297: 44, 1298: 51, 1299: 44, 1300: 6, 1301: 3, 1302: 139, 1303: 28, 1304: 52, 1305: 1, 1306: 1, 1307: 7, 1308: 15, 1309: 4, 1310: 50, 1311: 113, 1312: 2, 1313: 1, 1314: 33, 1315: 163, 1316: 37, 1317: 40, 1318: 62, 1319: 15, 1320: 64, 1321: 5, 1322: 7, 1323: 124, 1324: 35, 1325: 16, 1326: 4, 1327: 15, 1328: 16, 1329: 37, 1330: 70, 1331: 42, 1332: 50, 1333: 21, 1334: 3, 1335: 49, 1336: 16, 1337: 381, 1338: 26, 1339: 107, 1340: 48, 1341: 12, 1342: 202, 1343: 43, 1344: 2, 1345: 20, 1346: 2, 1347: 4, 1348: 224, 1349: 74, 1350: 13, 1351: 13, 1352: 133, 1353: 85, 1354: 1, 1355: 37, 1356: 38, 1357: 36, 1358: 67, 1359: 51, 1360: 53, 1361: 42, 1362: 1, 1363: 7, 1364: 10, 1365: 9, 1366: 131, 1367: 62, 1368: 18, 1369: 29, 1370: 10, 1371: 58, 1372: 17, 1373: 67, 1374: 19, 1375: 2, 1376: 30, 1377: 10, 1378: 193, 1379: 8, 1380: 14, 1381: 29, 1382: 29, 1383: 139, 1384: 34, 1385: 24, 1386: 27, 1387: 1, 1388: 8, 1389: 4, 1390: 7, 1391: 140, 1392: 6, 1393: 6, 1394: 179, 1395: 175, 1396: 8, 1397: 2, 1398: 26, 1399: 159, 1400: 169, 1401: 47, 1402: 14, 1403: 33, 1404: 11, 1405: 127, 1406: 8, 1407: 1, 1408: 1, 1409: 10, 1410: 91, 1411: 44, 1412: 65, 1413: 177, 1414: 65, 1415: 4, 1416: 2, 1417: 48, 1418: 10, 1419: 44, 1420: 4, 1421: 2, 1422: 5, 1423: 30, 1424: 15, 1425: 72, 1426: 63, 1427: 61, 1428: 37, 1429: 7, 1430: 10, 1431: 117, 1432: 34, 1433: 18, 1434: 14, 1435: 1, 1436: 21, 1437: 55, 1438: 60, 1439: 5, 1440: 22, 1441: 55, 1442: 31, 1443: 45, 1444: 60, 1445: 103, 1446: 36, 1447: 15, 1448: 16, 1449: 31, 1450: 93, 1451: 45, 1452: 4, 1453: 8, 1454: 171, 1455: 13, 1456: 3, 1457: 25, 1458: 46, 1459: 20, 1460: 19, 1461: 36, 1462: 21, 1463: 92, 1464: 53, 1465: 8, 1466: 51, 1467: 19, 1468: 124, 1469: 3, 1470: 3, 1471: 10, 1472: 28, 1473: 39, 1474: 1, 1475: 5, 1476: 23, 1477: 26, 1478: 1, 1479: 90, 1480: 48, 1481: 34, 1482: 17, 1483: 37, 1484: 6, 1485: 9, 1486: 16, 1487: 57, 1488: 2, 1489: 65, 1490: 7, 1491: 81, 1492: 7, 1493: 17, 1494: 4, 1495: 208, 1496: 27, 1497: 1, 1498: 93, 1499: 11, 1500: 3, 1501: 50, 1502: 126, 1503: 9, 1504: 14, 1505: 7, 1506: 3, 1507: 21, 1508: 48, 1509: 32, 1510: 42, 1511: 25, 1512: 7, 1513: 14, 1514: 7, 1515: 9, 1516: 12, 1517: 46, 1518: 139, 1519: 22, 1520: 8, 1521: 68, 1522: 106, 1523: 25, 1524: 6, 1525: 66, 1526: 38, 1527: 58, 1528: 190, 1529: 27, 1530: 4, 1531: 38, 1532: 15, 1533: 18, 1534: 14, 1535: 61, 1536: 12, 1537: 25, 1538: 18, 1539: 24, 1540: 7, 1541: 51, 1542: 1, 1543: 69, 1544: 56, 1545: 79, 1546: 130, 1547: 38, 1548: 6, 1549: 9, 1550: 16, 1551: 54, 1552: 3, 1553: 20, 1554: 2, 1555: 47, 1556: 8, 1557: 2, 1558: 1, 1559: 85, 1560: 16, 1561: 51, 1562: 90, 1563: 12, 1564: 40, 1565: 6, 1566: 24, 1567: 8, 1568: 13, 1569: 46, 1570: 156, 1571: 9, 1572: 104, 1573: 137, 1574: 26, 1575: 47, 1576: 12, 1577: 39, 1578: 36, 1579: 4, 1580: 12, 1581: 21, 1582: 5, 1583: 58, 1584: 54, 1585: 9, 1586: 40, 1587: 7, 1588: 30, 1589: 94, 1590: 6, 1591: 8, 1592: 3, 1593: 5, 1594: 3, 1595: 3, 1596: 1, 1597: 1, 1598: 9, 1599: 27, 1600: 10, 1601: 4, 1602: 10, 1603: 4, 1604: 100, 1605: 100, 1606: 3, 1607: 177, 1608: 8, 1609: 3, 1610: 14, 1611: 17, 1612: 38, 1613: 1, 1614: 15, 1615: 69, 1616: 23, 1617: 15, 1618: 35, 1619: 36, 1620: 106, 1621: 7, 1622: 26, 1623: 27, 1624: 9, 1625: 32, 1626: 42, 1627: 4, 1628: 10, 1629: 11, 1630: 22, 1631: 46, 1632: 29, 1633: 33, 1634: 9, 1635: 3, 1636: 62, 1637: 4, 1638: 215, 1639: 3, 1640: 73, 1641: 12, 1642: 78, 1643: 33, 1644: 56, 1645: 1, 1646: 12, 1647: 26, 1648: 48, 1649: 1, 1650: 6, 1651: 62, 1652: 33, 1653: 53, 1654: 9, 1655: 22, 1656: 21, 1657: 9, 1658: 13, 1659: 2, 1660: 103, 1661: 1, 1662: 50, 1663: 5, 1664: 61, 1665: 39, 1666: 3, 1667: 1, 1668: 6, 1669: 1, 1670: 120, 1671: 64, 1672: 38, 1673: 29, 1674: 6, 1675: 18, 1676: 49, 1677: 5, 1678: 30, 1679: 11, 1680: 81, 1681: 21, 1682: 33, 1683: 45, 1684: 110, 1685: 2, 1686: 28, 1687: 21, 1688: 4, 1689: 37, 1690: 13, 1691: 22, 1692: 13, 1693: 79, 1694: 26, 1695: 16, 1696: 72, 1697: 2, 1698: 47, 1699: 11, 1700: 29, 1701: 21, 1702: 2, 1703: 70, 1704: 93, 1705: 32, 1706: 20, 1707: 5, 1708: 44, 1709: 7, 1710: 109, 1711: 1, 1712: 4, 1713: 4, 1714: 5, 1715: 5, 1716: 21, 1717: 8, 1718: 123, 1719: 63, 1720: 49, 1721: 7, 1722: 22, 1723: 63, 1724: 22, 1725: 14, 1726: 9, 1727: 4, 1728: 59, 1729: 28, 1730: 7, 1731: 8, 1732: 10, 1733: 7, 1734: 27, 1735: 107, 1736: 2, 1737: 27, 1738: 66, 1739: 23, 1740: 66, 1741: 7, 1742: 26, 1743: 6, 1744: 225, 1745: 48, 1746: 4, 1747: 1, 1748: 35, 1749: 2, 1750: 22, 1751: 78, 1752: 5, 1753: 26, 1754: 9, 1755: 7, 1756: 27, 1757: 1, 1758: 42, 1759: 7, 1760: 34, 1761: 50, 1762: 15, 1763: 15, 1764: 31, 1765: 42, 1766: 3, 1767: 2, 1768: 41, 1769: 6, 1770: 8, 1771: 18, 1772: 22, 1773: 50, 1774: 103, 1775: 43, 1776: 17, 1777: 82, 1778: 37, 1779: 25, 1780: 7, 1781: 33, 1782: 2, 1783: 4, 1784: 8, 1785: 11, 1786: 1, 1787: 25, 1788: 25, 1789: 37, 1790: 26, 1791: 11, 1792: 82, 1793: 23, 1794: 31, 1795: 15, 1796: 11, 1797: 6, 1798: 4, 1799: 8, 1800: 10, 1801: 7, 1802: 2, 1803: 20, 1804: 4, 1805: 1, 1806: 30, 1807: 5, 1808: 18, 1809: 18, 1810: 29, 1811: 35, 1812: 9, 1813: 2, 1814: 7, 1815: 21, 1816: 57, 1817: 35, 1818: 3, 1819: 44, 1820: 20, 1821: 21, 1822: 8, 1823: 54, 1824: 37, 1825: 13, 1826: 7, 1827: 1, 1828: 81, 1829: 91, 1830: 25, 1831: 76, 1832: 71, 1833: 3, 1834: 40, 1835: 21, 1836: 53, 1837: 31, 1838: 105, 1839: 4, 1840: 8, 1841: 7, 1842: 12, 1843: 18, 1844: 16, 1845: 84, 1846: 35, 1847: 32, 1848: 27, 1849: 22, 1850: 37, 1851: 104, 1852: 121, 1853: 3, 1854: 7, 1855: 11, 1856: 169, 1857: 21, 1858: 59, 1859: 1, 1860: 3, 1861: 10, 1862: 43, 1863: 92, 1864: 38, 1865: 15, 1866: 3, 1867: 1, 1868: 22, 1869: 24, 1870: 65, 1871: 84, 1872: 24, 1873: 86, 1874: 14, 1875: 209, 1876: 24, 1877: 9, 1878: 12, 1879: 66, 1880: 45, 1881: 2, 1882: 79, 1883: 3, 1884: 50, 1885: 18, 1886: 60, 1887: 5, 1888: 2, 1889: 5, 1890: 10, 1891: 2, 1892: 10, 1893: 81, 1894: 15, 1895: 14, 1896: 15, 1897: 56, 1898: 33, 1899: 10, 1900: 30, 1901: 97, 1902: 11, 1903: 13, 1904: 30, 1905: 21, 1906: 5, 1907: 9, 1908: 7, 1909: 4, 1910: 19, 1911: 47, 1912: 60, 1913: 33, 1914: 49, 1915: 6, 1916: 23, 1917: 17, 1918: 10, 1919: 9, 1920: 14, 1921: 75, 1922: 38, 1923: 25, 1924: 1, 1925: 21, 1926: 61, 1927: 15, 1928: 11, 1929: 11, 1930: 3, 1931: 3, 1932: 10, 1933: 27, 1934: 32, 1935: 18, 1936: 18, 1937: 5, 1938: 19, 1939: 74, 1940: 2, 1941: 44, 1942: 13, 1943: 46, 1944: 46, 1945: 46, 1946: 2, 1947: 5, 1948: 42, 1949: 21, 1950: 11, 1951: 3, 1952: 2, 1953: 3, 1954: 5, 1955: 28, 1956: 4, 1957: 21, 1958: 74, 1959: 69, 1960: 10, 1961: 7, 1962: 4, 1963: 6, 1964: 5, 1965: 38, 1966: 1, 1967: 17, 1968: 5, 1969: 36, 1970: 12, 1971: 6, 1972: 17, 1973: 23, 1974: 43, 1975: 4, 1976: 35, 1977: 30, 1978: 14, 1979: 11, 1980: 42, 1981: 4, 1982: 34, 1983: 45, 1984: 2, 1985: 5, 1986: 4, 1987: 67, 1988: 2, 1989: 2, 1990: 9, 1991: 35, 1992: 40, 1993: 71, 1994: 2, 1995: 12, 1996: 93, 1997: 17, 1998: 40, 1999: 5, 2000: 19, 2001: 31, 2002: 20, 2003: 37, 2004: 34, 2005: 25, 2006: 17, 2007: 62, 2008: 10, 2009: 18, 2010: 4, 2011: 18, 2012: 35, 2013: 4, 2014: 8, 2015: 14, 2016: 7, 2017: 18, 2018: 1, 2019: 5, 2020: 97, 2021: 9, 2022: 30, 2023: 27, 2024: 36, 2025: 31, 2026: 32, 2027: 16, 2028: 169, 2029: 167, 2030: 5, 2031: 37, 2032: 6, 2033: 55, 2034: 42, 2035: 15, 2036: 14, 2037: 30, 2038: 9, 2039: 49, 2040: 4, 2041: 2, 2042: 6, 2043: 7, 2044: 12, 2045: 7, 2046: 50, 2047: 49, 2048: 24, 2049: 25, 2050: 26, 2051: 5, 2052: 38, 2053: 10, 2054: 1, 2055: 14, 2056: 14, 2057: 2, 2058: 14, 2059: 13, 2060: 93, 2061: 9, 2062: 11, 2063: 9, 2064: 12, 2065: 9, 2066: 6, 2067: 1, 2068: 16, 2069: 22, 2070: 5, 2071: 18, 2072: 35, 2073: 12, 2074: 5, 2075: 17, 2076: 18, 2077: 4, 2078: 2, 2079: 8, 2080: 6, 2081: 11, 2082: 5, 2083: 24, 2084: 73, 2085: 9, 2086: 2, 2087: 76, 2088: 14, 2089: 9, 2090: 13, 2091: 10, 2092: 2, 2093: 15, 2094: 15, 2095: 34, 2096: 1, 2097: 65, 2098: 14, 2099: 27, 2100: 6, 2101: 38, 2102: 2, 2103: 7, 2104: 8, 2105: 31, 2106: 12, 2107: 6, 2108: 16, 2109: 3, 2110: 9, 2111: 22, 2112: 31, 2113: 10, 2114: 12, 2115: 15, 2116: 51, 2117: 29, 2118: 9, 2119: 41, 2120: 13, 2121: 38, 2122: 21, 2123: 14, 2124: 83, 2125: 2, 2126: 37, 2127: 46, 2128: 22, 2129: 2, 2130: 6, 2131: 4, 2132: 5, 2133: 7, 2134: 1, 2135: 12, 2136: 31, 2137: 51, 2138: 33, 2139: 37, 2140: 5, 2141: 3, 2142: 1, 2143: 3, 2144: 13, 2145: 19, 2146: 10, 2147: 23, 2148: 21, 2149: 2, 2150: 41, 2151: 16, 2152: 8, 2153: 38, 2154: 15, 2155: 2, 2156: 52, 2157: 51, 2158: 5, 2159: 41, 2160: 12, 2161: 2, 2162: 26, 2163: 25, 2164: 6, 2165: 2, 2166: 36, 2167: 21, 2168: 6, 2169: 117, 2170: 6, 2171: 5, 2172: 8, 2173: 6, 2174: 1, 2175: 18, 2176: 4, 2177: 4, 2178: 5, 2179: 14, 2180: 29, 2181: 39, 2182: 4, 2183: 7, 2184: 17, 2185: 30, 2186: 2, 2187: 25, 2188: 1, 2189: 10, 2190: 10, 2191: 4, 2192: 4, 2193: 1, 2194: 30, 2195: 35, 2196: 7, 2197: 6, 2198: 23, 2199: 10, 2200: 4, 2201: 83, 2202: 8, 2203: 111, 2204: 1, 2205: 11, 2206: 51, 2207: 38, 2208: 24, 2209: 9, 2210: 7, 2211: 67, 2212: 22, 2213: 3, 2214: 2, 2215: 21, 2216: 15, 2217: 12, 2218: 21, 2219: 18, 2220: 5, 2221: 27, 2222: 10, 2223: 115, 2224: 8, 2225: 14, 2226: 22, 2227: 1, 2228: 14, 2229: 17, 2230: 17, 2231: 6, 2232: 10, 2233: 12, 2234: 11, 2235: 19, 2236: 4, 2237: 13, 2238: 6, 2239: 21, 2240: 19, 2241: 2, 2242: 11, 2243: 16, 2244: 2, 2245: 2, 2246: 6, 2247: 7, 2248: 5, 2249: 8, 2250: 12, 2251: 47, 2252: 1, 2253: 4, 2254: 11, 2255: 69, 2256: 45, 2257: 69, 2258: 4, 2259: 36, 2260: 14, 2261: 9, 2262: 4, 2263: 34, 2264: 3, 2265: 5, 2266: 8, 2267: 10, 2268: 10, 2269: 1, 2270: 15, 2271: 7, 2272: 18, 2273: 12, 2274: 15, 2275: 5, 2276: 23, 2277: 17, 2278: 12, 2279: 18, 2280: 1, 2281: 21, 2282: 2, 2283: 2, 2284: 6, 2285: 4, 2286: 25, 2287: 40, 2288: 4, 2289: 9, 2290: 5, 2291: 1, 2292: 23, 2293: 13, 2294: 3, 2295: 5, 2296: 30, 2297: 12, 2298: 9, 2299: 7, 2300: 33, 2301: 61, 2302: 14, 2303: 43, 2304: 20, 2305: 1, 2306: 41, 2307: 8, 2308: 10, 2309: 2, 2310: 6, 2311: 3, 2312: 45, 2313: 80, 2314: 4, 2315: 27, 2316: 12, 2317: 5, 2318: 5, 2319: 9, 2320: 11, 2321: 15, 2322: 5, 2323: 10, 2324: 8, 2325: 9, 2326: 9, 2327: 9, 2328: 18, 2329: 2, 2330: 5, 2331: 3, 2332: 49, 2333: 15, 2334: 3, 2335: 7, 2336: 60, 2337: 2, 2338: 10, 2339: 2, 2340: 2, 2341: 11, 2342: 24, 2343: 6, 2344: 92, 2345: 25, 2346: 7, 2347: 8, 2348: 28, 2349: 7, 2350: 38, 2351: 3, 2352: 23, 2353: 16, 2354: 2, 2355: 17, 2356: 31, 2357: 22, 2358: 32, 2359: 17, 2360: 3, 2361: 2, 2362: 4, 2363: 9, 2364: 6, 2365: 7, 2366: 11, 2367: 4, 2368: 7, 2369: 55, 2370: 3, 2371: 15, 2372: 21, 2373: 17, 2374: 1, 2375: 11, 2376: 7, 2377: 4, 2378: 17, 2379: 27, 2380: 36, 2381: 10, 2382: 5, 2383: 12, 2384: 4, 2385: 6, 2386: 8, 2387: 8, 2388: 16, 2389: 30, 2390: 4, 2391: 5, 2392: 7, 2393: 46, 2394: 1, 2395: 5, 2396: 39, 2397: 9, 2398: 5, 2399: 16, 2400: 5, 2401: 1, 2402: 7, 2403: 18, 2404: 25, 2405: 4, 2406: 132, 2407: 6, 2408: 49, 2409: 24, 2410: 1, 2411: 5, 2412: 29, 2413: 43, 2414: 4, 2415: 20, 2416: 1, 2417: 1, 2418: 14, 2419: 5, 2420: 5, 2421: 4, 2422: 3, 2423: 10, 2424: 10, 2425: 21, 2426: 22, 2427: 51, 2428: 5, 2429: 49, 2430: 7, 2431: 14, 2432: 52, 2433: 8, 2434: 31, 2435: 5, 2436: 6, 2437: 39, 2438: 7, 2439: 10, 2440: 6, 2441: 12, 2442: 74, 2443: 9, 2444: 6, 2445: 1, 2446: 3, 2447: 31, 2448: 6, 2449: 18, 2450: 20, 2451: 11, 2452: 30, 2453: 1, 2454: 4, 2455: 10, 2456: 1, 2457: 31, 2458: 4, 2459: 17, 2460: 9, 2461: 13, 2462: 15, 2463: 1, 2464: 5, 2465: 3, 2466: 1, 2467: 5, 2468: 47, 2469: 19, 2470: 18, 2471: 16, 2472: 31, 2473: 3, 2474: 44, 2475: 1, 2476: 16, 2477: 1, 2478: 4, 2479: 61, 2480: 8, 2481: 83, 2482: 1, 2483: 37, 2484: 5, 2485: 21, 2486: 6, 2487: 38, 2488: 3, 2489: 1, 2490: 4, 2491: 11, 2492: 35, 2493: 39, 2494: 1, 2495: 10, 2496: 2, 2497: 4, 2498: 7, 2499: 8, 2500: 3, 2501: 10, 2502: 15, 2503: 22, 2504: 1, 2505: 2, 2506: 2, 2507: 3, 2508: 3, 2509: 6, 2510: 24, 2511: 4, 2512: 21, 2513: 18, 2514: 1, 2515: 4, 2516: 11, 2517: 2, 2518: 7, 2519: 12, 2520: 26, 2521: 4, 2522: 1, 2523: 20, 2524: 43, 2525: 4, 2526: 1, 2527: 47, 2528: 40, 2529: 5, 2530: 1, 2531: 4, 2532: 15, 2533: 42, 2534: 18, 2535: 5, 2536: 17, 2537: 15, 2538: 96, 2539: 31, 2540: 11, 2541: 6, 2542: 5, 2543: 13, 2544: 1, 2545: 1, 2546: 14, 2547: 11, 2548: 7, 2549: 7, 2550: 22, 2551: 23, 2552: 13, 2553: 14, 2554: 1, 2555: 13, 2556: 31, 2557: 7, 2558: 17, 2559: 61, 2560: 1, 2561: 100, 2562: 47, 2563: 27, 2564: 7, 2565: 4, 2566: 5, 2567: 14, 2568: 12, 2569: 5, 2570: 30, 2571: 1, 2572: 1, 2573: 5, 2574: 44, 2575: 2, 2576: 3, 2577: 3, 2578: 2, 2579: 1, 2580: 15, 2581: 3, 2582: 22, 2583: 1, 2584: 1, 2585: 36, 2586: 22, 2587: 2, 2588: 59, 2589: 1, 2590: 19, 2591: 3, 2592: 5, 2593: 1, 2594: 1, 2595: 48, 2596: 4, 2597: 34, 2598: 10, 2599: 11, 2600: 3, 2601: 5, 2602: 1, 2603: 5, 2604: 8, 2605: 12, 2606: 6, 2607: 32, 2608: 20, 2609: 10, 2610: 4, 2611: 35, 2612: 12, 2613: 16, 2614: 11, 2615: 3, 2616: 10, 2617: 16, 2618: 17, 2619: 14, 2620: 10, 2621: 7, 2622: 15, 2623: 20, 2624: 6, 2625: 7, 2626: 10, 2627: 1, 2628: 24, 2629: 1, 2630: 21, 2631: 25, 2632: 11, 2633: 26, 2634: 2, 2635: 11, 2636: 7, 2637: 3, 2638: 10, 2639: 1, 2640: 30, 2641: 38, 2642: 2, 2643: 47, 2644: 9, 2645: 8, 2646: 3, 2647: 21, 2648: 26, 2649: 9, 2650: 1, 2651: 5, 2652: 10, 2653: 7, 2654: 2, 2655: 1, 2656: 29, 2657: 6, 2658: 3, 2659: 5, 2660: 5, 2661: 1, 2662: 74, 2663: 1, 2664: 2, 2665: 2, 2666: 24, 2667: 7, 2668: 4, 2669: 2, 2670: 4, 2671: 8, 2672: 2, 2673: 44, 2674: 21, 2675: 6, 2676: 4, 2677: 21, 2678: 6, 2679: 1, 2680: 8, 2681: 5, 2682: 12, 2683: 1, 2684: 1, 2685: 3, 2686: 3, 2687: 11, 2688: 11, 2689: 3, 2690: 7, 2691: 6, 2692: 8, 2693: 3, 2694: 2, 2695: 24, 2696: 4, 2697: 7, 2698: 12, 2699: 21, 2700: 1, 2701: 1, 2702: 4, 2703: 2, 2704: 15, 2705: 17, 2706: 3, 2707: 6, 2708: 2, 2709: 5, 2710: 26, 2711: 47, 2712: 1, 2713: 32, 2714: 16, 2715: 4, 2716: 8, 2717: 9, 2718: 1, 2719: 21, 2720: 1, 2721: 20, 2722: 15, 2723: 1, 2724: 11, 2725: 2, 2726: 2, 2727: 3, 2728: 16, 2729: 5, 2730: 12, 2731: 17, 2732: 17, 2733: 7, 2734: 1, 2735: 3, 2736: 2, 2737: 3, 2738: 2, 2739: 14, 2740: 6, 2741: 14, 2742: 9, 2743: 4, 2744: 28, 2745: 1, 2746: 2, 2747: 16, 2748: 14, 2749: 38, 2750: 14, 2751: 8, 2752: 6, 2753: 18, 2754: 2, 2755: 11, 2756: 14, 2757: 12, 2758: 7, 2759: 8, 2760: 19, 2761: 6, 2762: 10, 2763: 4, 2764: 6, 2765: 15, 2766: 14, 2767: 12, 2768: 3, 2769: 20, 2770: 9, 2771: 1, 2772: 1, 2773: 4, 2774: 8, 2775: 53, 2776: 14, 2777: 1, 2778: 22, 2779: 1, 2780: 6, 2781: 5, 2782: 19, 2783: 2, 2784: 4, 2785: 4, 2786: 1, 2787: 9, 2788: 21, 2789: 10, 2790: 12, 2791: 10, 2792: 4, 2793: 20, 2794: 34, 2795: 13, 2796: 29, 2797: 37, 2798: 18, 2799: 10, 2800: 19, 2801: 16, 2802: 1, 2803: 1, 2804: 32, 2805: 1, 2806: 14, 2807: 8, 2808: 9, 2809: 4, 2810: 5, 2811: 34, 2812: 29, 2813: 9, 2814: 1, 2815: 1, 2816: 7, 2817: 42, 2818: 15, 2819: 17, 2820: 2, 2821: 15, 2822: 31, 2823: 4, 2824: 6, 2825: 11, 2826: 17, 2827: 5, 2828: 11, 2829: 4, 2830: 12, 2831: 6, 2832: 20, 2833: 6, 2834: 20, 2835: 3, 2836: 6, 2837: 28, 2838: 13, 2839: 1, 2840: 1, 2841: 6, 2842: 26, 2843: 36, 2844: 15, 2845: 12, 2846: 3, 2847: 8, 2848: 41, 2849: 2, 2850: 45, 2851: 31, 2852: 6, 2853: 32, 2854: 6, 2855: 17, 2856: 4, 2857: 19, 2858: 2, 2859: 1, 2860: 5, 2861: 12, 2862: 5, 2863: 5, 2864: 1, 2865: 1, 2866: 1, 2867: 27, 2868: 2, 2869: 3, 2870: 5, 2871: 5, 2872: 20, 2873: 6, 2874: 2, 2875: 1, 2876: 10, 2877: 4, 2878: 2, 2879: 13, 2880: 9, 2881: 1, 2882: 9, 2883: 1, 2884: 13, 2885: 13, 2886: 3, 2887: 18, 2888: 8, 2889: 4, 2890: 1, 2891: 20, 2892: 9, 2893: 20, 2894: 1, 2895: 26, 2896: 6, 2897: 29, 2898: 3, 2899: 2, 2900: 21, 2901: 3, 2902: 2, 2903: 20, 2904: 3, 2905: 24, 2906: 1, 2907: 1, 2908: 1, 2909: 10, 2910: 3, 2911: 15, 2912: 21, 2913: 1, 2914: 10, 2915: 3, 2916: 6, 2917: 11, 2918: 1, 2919: 11, 2920: 22, 2921: 5, 2922: 1, 2923: 5, 2924: 1, 2925: 6, 2926: 1, 2927: 10, 2928: 3, 2929: 8, 2930: 6, 2931: 1, 2932: 26, 2933: 5, 2934: 12, 2935: 5, 2936: 31, 2937: 11, 2938: 1, 2939: 9, 2940: 10, 2941: 1, 2942: 18, 2943: 11, 2944: 5, 2945: 18, 2946: 11, 2947: 18, 2948: 17, 2949: 21, 2950: 25, 2951: 6, 2952: 4, 2953: 4, 2954: 6, 2955: 12, 2956: 2, 2957: 7, 2958: 6, 2959: 3, 2960: 18, 2961: 8, 2962: 2, 2963: 1, 2964: 2, 2965: 16, 2966: 34, 2967: 13, 2968: 6, 2969: 1, 2970: 11, 2971: 5, 2972: 5, 2973: 3, 2974: 23, 2975: 20, 2976: 10, 2977: 9, 2978: 5, 2979: 1, 2980: 10, 2981: 36, 2982: 55, 2983: 12, 2984: 6, 2985: 54, 2986: 4, 2987: 7, 2988: 16, 2989: 14, 2990: 3, 2991: 6, 2992: 13, 2993: 11, 2994: 3, 2995: 10, 2996: 3, 2997: 1, 2998: 2, 2999: 2, 3000: 8, 3001: 21, 3002: 4, 3003: 3, 3004: 3, 3005: 4, 3006: 3, 3007: 1, 3008: 1, 3009: 2, 3010: 6, 3011: 2, 3012: 13, 3013: 2, 3014: 13, 3015: 28, 3016: 20, 3017: 5, 3018: 32, 3019: 3, 3020: 30, 3021: 23, 3022: 20, 3023: 5, 3024: 2, 3025: 9, 3026: 36, 3027: 4, 3028: 2, 3029: 21, 3030: 7, 3031: 6, 3032: 1, 3033: 10, 3034: 5, 3035: 1, 3036: 1, 3037: 1, 3038: 7, 3039: 17, 3040: 15, 3041: 15, 3042: 12, 3043: 11, 3044: 1, 3045: 2, 3046: 13, 3047: 1, 3048: 23, 3049: 19, 3050: 1, 3051: 13, 3052: 3, 3053: 3, 3054: 8, 3055: 50, 3056: 12, 3057: 31, 3058: 41, 3059: 16, 3060: 21, 3061: 3, 3062: 1, 3063: 8, 3064: 5, 3065: 16, 3066: 3, 3067: 22, 3068: 12, 3069: 11, 3070: 18, 3071: 6, 3072: 4, 3073: 9, 3074: 4, 3075: 9, 3076: 13, 3077: 21, 3078: 1, 3079: 4, 3080: 3, 3081: 3, 3082: 7, 3083: 3, 3084: 7, 3085: 23, 3086: 3, 3087: 1, 3088: 11, 3089: 26, 3090: 2, 3091: 14, 3092: 2, 3093: 6, 3094: 2, 3095: 8, 3096: 2, 3097: 2, 3098: 1, 3099: 23, 3100: 14, 3101: 13, 3102: 1, 3103: 16, 3104: 4, 3105: 2, 3106: 20, 3107: 9, 3108: 11, 3109: 7, 3110: 5, 3111: 2, 3112: 46, 3113: 14, 3114: 8, 3115: 7, 3116: 2, 3117: 1, 3118: 22, 3119: 7, 3120: 2, 3121: 1, 3122: 2, 3123: 5, 3124: 9, 3125: 3, 3126: 1, 3127: 19, 3128: 4, 3129: 2, 3130: 3, 3131: 2, 3132: 4, 3133: 11, 3134: 10, 3135: 1, 3136: 7, 3137: 2, 3138: 58, 3139: 2, 3140: 19, 3141: 11, 3142: 21, 3143: 14, 3144: 4, 3145: 7, 3146: 2, 3147: 9, 3148: 2, 3149: 16, 3150: 20, 3151: 3, 3152: 26, 3153: 12, 3154: 2, 3155: 9, 3156: 3, 3157: 4, 3158: 4, 3159: 21, 3160: 4, 3161: 20, 3162: 7, 3163: 1, 3164: 9, 3165: 4, 3166: 7, 3167: 12, 3168: 2, 3169: 1, 3170: 2, 3171: 24, 3172: 18, 3173: 14, 3174: 6, 3175: 10, 3176: 30, 3177: 14, 3178: 10, 3179: 20, 3180: 2, 3181: 4, 3182: 2, 3183: 4, 3184: 5, 3185: 27, 3186: 14, 3187: 3, 3188: 1, 3189: 2, 3190: 5, 3191: 2, 3192: 17, 3193: 19, 3194: 4, 3195: 9, 3196: 1, 3197: 2, 3198: 8, 3199: 10, 3200: 2, 3201: 1, 3202: 1, 3203: 6, 3204: 1, 3205: 12, 3206: 7, 3207: 3, 3208: 10, 3209: 5, 3210: 1, 3211: 4, 3212: 11, 3213: 16, 3214: 3, 3215: 4, 3216: 2, 3217: 1, 3218: 1, 3219: 5, 3220: 9, 3221: 3, 3222: 5, 3223: 10, 3224: 5, 3225: 2, 3226: 8, 3227: 4, 3228: 1, 3229: 3, 3230: 6, 3231: 15, 3232: 2, 3233: 12, 3234: 36, 3235: 2, 3236: 7, 3237: 12, 3238: 4, 3239: 3, 3240: 36, 3241: 5, 3242: 1, 3243: 10, 3244: 5, 3245: 3, 3246: 2, 3247: 3, 3248: 1, 3249: 16, 3250: 14, 3251: 3, 3252: 9, 3253: 4, 3254: 1, 3255: 7, 3256: 1, 3257: 17, 3258: 7, 3259: 13, 3260: 3, 3261: 7, 3262: 6, 3263: 2, 3264: 7, 3265: 8, 3266: 2, 3267: 7, 3268: 13, 3269: 2, 3270: 9, 3271: 16, 3272: 30, 3273: 3, 3274: 6, 3275: 1, 3276: 8, 3277: 3, 3278: 5, 3279: 10, 3280: 8, 3281: 12, 3282: 2, 3283: 10, 3284: 15, 3285: 2, 3286: 4, 3287: 10, 3288: 4, 3289: 5, 3290: 7, 3291: 32, 3292: 10, 3293: 4, 3294: 3, 3295: 1, 3296: 5, 3297: 6, 3298: 3, 3299: 3, 3300: 12, 3301: 3, 3302: 2, 3303: 3, 3304: 13, 3305: 9, 3306: 13, 3307: 10, 3308: 2, 3309: 6, 3310: 2, 3311: 8, 3312: 2, 3313: 1, 3314: 22, 3315: 11, 3316: 16, 3317: 9, 3318: 2, 3319: 10, 3320: 4, 3321: 3, 3322: 3, 3323: 5, 3324: 34, 3325: 5, 3326: 6, 3327: 1, 3328: 13, 3329: 3, 3330: 8, 3331: 2, 3332: 17, 3333: 2, 3334: 8, 3335: 7, 3336: 2, 3337: 1, 3338: 2, 3339: 34, 3340: 2, 3341: 11, 3342: 3, 3343: 5, 3344: 4, 3345: 2, 3346: 9, 3347: 2, 3348: 1, 3349: 1, 3350: 5, 3351: 5, 3352: 23, 3353: 6, 3354: 4, 3355: 14, 3356: 8, 3357: 16, 3358: 1, 3359: 1, 3360: 1, 3361: 8, 3362: 27, 3363: 21, 3364: 11, 3365: 6, 3366: 6, 3367: 8, 3368: 1, 3369: 2, 3370: 9, 3371: 5, 3372: 14, 3373: 2, 3374: 2, 3375: 9, 3376: 18, 3377: 11, 3378: 17, 3379: 5, 3380: 1, 3381: 22, 3382: 1, 3383: 1, 3384: 1, 3385: 13, 3386: 5, 3387: 2, 3388: 5, 3389: 2, 3390: 23, 3391: 4, 3392: 4, 3393: 2, 3394: 11, 3395: 8, 3396: 21, 3397: 7, 3398: 1, 3399: 3, 3400: 10, 3401: 1, 3402: 1, 3403: 3, 3404: 2, 3405: 12, 3406: 4, 3407: 2, 3408: 16, 3409: 5, 3410: 2, 3411: 2, 3412: 1, 3413: 3, 3414: 1, 3415: 2, 3416: 1, 3417: 8, 3418: 6, 3419: 2, 3420: 1, 3421: 5, 3422: 10, 3423: 5, 3424: 18, 3425: 10, 3426: 5, 3427: 2, 3428: 1, 3429: 6, 3430: 5, 3431: 4, 3432: 16, 3433: 3, 3434: 11, 3435: 6, 3436: 1, 3437: 1, 3438: 8, 3439: 1, 3440: 3, 3441: 24, 3442: 2, 3443: 14, 3444: 12, 3445: 16, 3446: 19, 3447: 1, 3448: 1, 3449: 5, 3450: 18, 3451: 10, 3452: 3, 3453: 2, 3454: 19, 3455: 5, 3456: 14, 3457: 1, 3458: 9, 3459: 9, 3460: 4, 3461: 3, 3462: 3, 3463: 4, 3464: 2, 3465: 6, 3466: 2, 3467: 12, 3468: 27, 3469: 3, 3470: 1, 3471: 15, 3472: 3, 3473: 1, 3474: 1, 3475: 3, 3476: 2, 3477: 5, 3478: 3, 3479: 7, 3480: 24, 3481: 18, 3482: 2, 3483: 5, 3484: 3, 3485: 1, 3486: 3, 3487: 10, 3488: 8, 3489: 18, 3490: 3, 3491: 37, 3492: 7, 3493: 4, 3494: 9, 3495: 8, 3496: 2, 3497: 5, 3498: 7, 3499: 21, 3500: 12, 3501: 23, 3502: 6, 3503: 3, 3504: 11, 3505: 5, 3506: 21, 3507: 6, 3508: 1, 3509: 11, 3510: 7, 3511: 9, 3512: 3, 3513: 1, 3514: 3, 3515: 5, 3516: 3, 3517: 4, 3518: 4, 3519: 11, 3520: 1, 3521: 13, 3522: 3, 3523: 5, 3524: 7, 3525: 4, 3526: 5, 3527: 6, 3528: 1, 3529: 1, 3530: 22, 3531: 1, 3532: 16, 3533: 6, 3534: 4, 3535: 5, 3536: 12, 3537: 4, 3538: 4, 3539: 20, 3540: 1, 3541: 1, 3542: 1, 3543: 1, 3544: 4, 3545: 8, 3546: 6, 3547: 1, 3548: 1, 3549: 1, 3550: 5, 3551: 5, 3552: 1, 3553: 5, 3554: 3, 3555: 14, 3556: 1, 3557: 1, 3558: 3, 3559: 3, 3560: 5, 3561: 4, 3562: 4, 3563: 2, 3564: 13, 3565: 6, 3566: 2, 3567: 4, 3568: 1, 3569: 3, 3570: 16, 3571: 12, 3572: 7, 3573: 3, 3574: 6, 3575: 3, 3576: 3, 3577: 3, 3578: 10, 3579: 2, 3580: 4, 3581: 3, 3582: 6, 3583: 9, 3584: 3, 3585: 19, 3586: 1, 3587: 6, 3588: 6, 3589: 1, 3590: 12, 3591: 20, 3592: 8, 3593: 13, 3594: 2, 3595: 13, 3596: 1, 3597: 1, 3598: 2, 3599: 1, 3600: 8, 3601: 1, 3602: 18, 3603: 5, 3604: 4, 3605: 8, 3606: 11, 3607: 6, 3608: 14, 3609: 13, 3610: 7, 3611: 3, 3612: 1, 3613: 12, 3614: 1, 3615: 14, 3616: 3, 3617: 4, 3618: 4, 3619: 9, 3620: 2, 3621: 9, 3622: 6, 3623: 4, 3624: 16, 3625: 5, 3626: 25, 3627: 1, 3628: 5, 3629: 1, 3630: 9, 3631: 1, 3632: 10, 3633: 5, 3634: 3, 3635: 2, 3636: 18, 3637: 8, 3638: 5, 3639: 8, 3640: 16, 3641: 10, 3642: 9, 3643: 17, 3644: 2, 3645: 1, 3646: 2, 3647: 2, 3648: 2, 3649: 6, 3650: 10, 3651: 2, 3652: 6, 3653: 2, 3654: 1, 3655: 9, 3656: 1, 3657: 8, 3658: 1, 3659: 1, 3660: 2, 3661: 5, 3662: 1, 3663: 9, 3664: 1, 3665: 11, 3666: 4, 3667: 2, 3668: 9, 3669: 3, 3670: 7, 3671: 13, 3672: 8, 3673: 9, 3674: 2, 3675: 4, 3676: 2, 3677: 6, 3678: 14, 3679: 4, 3680: 13, 3681: 2, 3682: 2, 3683: 3, 3684: 3, 3685: 1, 3686: 2, 3687: 5, 3688: 3, 3689: 1, 3690: 1, 3691: 2, 3692: 2, 3693: 11, 3694: 14, 3695: 3, 3696: 12, 3697: 5, 3698: 7, 3699: 1, 3700: 2, 3701: 1, 3702: 3, 3703: 8, 3704: 2, 3705: 2, 3706: 5, 3707: 12, 3708: 5, 3709: 6, 3710: 4, 3711: 1, 3712: 10, 3713: 6, 3714: 1, 3715: 9, 3716: 1, 3717: 3, 3718: 3, 3719: 4, 3720: 8, 3721: 6, 3722: 3, 3723: 9, 3724: 5, 3725: 6, 3726: 2, 3727: 7, 3728: 4, 3729: 5, 3730: 6, 3731: 1, 3732: 5, 3733: 1, 3734: 6, 3735: 3, 3736: 4, 3737: 3, 3738: 2, 3739: 1, 3740: 3, 3741: 10, 3742: 10, 3743: 8, 3744: 1, 3745: 1, 3746: 3, 3747: 6, 3748: 8, 3749: 4, 3750: 9, 3751: 2, 3752: 2, 3753: 9, 3754: 2, 3755: 5, 3756: 4, 3757: 1, 3758: 17, 3759: 3, 3760: 1, 3761: 3, 3762: 2, 3763: 14, 3764: 6, 3765: 1, 3766: 1, 3767: 8, 3768: 3, 3769: 9, 3770: 8, 3771: 7, 3772: 2, 3773: 8, 3774: 2, 3775: 17, 3776: 2, 3777: 3, 3778: 1, 3779: 8, 3780: 11, 3781: 1, 3782: 2, 3783: 21, 3784: 4, 3785: 20, 3786: 3, 3787: 1, 3788: 10, 3789: 7, 3790: 2, 3791: 15, 3792: 19, 3793: 1, 3794: 8, 3795: 6, 3796: 3, 3797: 5, 3798: 1, 3799: 1, 3800: 1, 3801: 6, 3802: 3, 3803: 2, 3804: 4, 3805: 2, 3806: 3, 3807: 4, 3808: 1, 3809: 2, 3810: 3, 3811: 1, 3812: 2, 3813: 5, 3814: 7, 3815: 9, 3816: 8, 3817: 7, 3818: 3, 3819: 5, 3820: 6, 3821: 1, 3822: 2, 3823: 4, 3824: 1, 3825: 1, 3826: 2, 3827: 23, 3828: 1, 3829: 7, 3830: 3, 3831: 9, 3832: 2, 3833: 3, 3834: 23, 3835: 1, 3836: 14, 3837: 6, 3838: 5, 3839: 1, 3840: 3, 3841: 5, 3842: 4, 3843: 3, 3844: 10, 3845: 2, 3846: 4, 3847: 5, 3848: 1, 3849: 7, 3850: 1, 3851: 4, 3852: 5, 3853: 7, 3854: 2, 3855: 8, 3856: 1, 3857: 3, 3858: 6, 3859: 2, 3860: 1, 3861: 8, 3862: 5, 3863: 2, 3864: 3, 3865: 12, 3866: 5, 3867: 10, 3868: 5, 3869: 3, 3870: 11, 3871: 1, 3872: 3, 3873: 2, 3874: 6, 3875: 2, 3876: 5, 3877: 6, 3878: 15, 3879: 1, 3880: 2, 3881: 2, 3882: 1, 3883: 6, 3884: 8, 3885: 6, 3886: 3, 3887: 7, 3888: 6, 3889: 6, 3890: 1, 3891: 6, 3892: 6, 3893: 4, 3894: 5, 3895: 7, 3896: 6, 3897: 2, 3898: 4, 3899: 2, 3900: 3, 3901: 12, 3902: 5, 3903: 1, 3904: 1, 3905: 8, 3906: 10, 3907: 2, 3908: 6, 3909: 1, 3910: 1, 3911: 7, 3912: 1, 3913: 4, 3914: 3, 3915: 10, 3916: 3, 3917: 4, 3918: 13, 3919: 8, 3920: 7, 3921: 4, 3922: 2, 3923: 5, 3924: 2, 3925: 4, 3926: 7, 3927: 1, 3928: 8, 3929: 2, 3930: 1, 3931: 11, 3932: 6, 3933: 4, 3934: 1, 3935: 2, 3936: 3, 3937: 1, 3938: 1, 3939: 2, 3940: 1, 3941: 1, 3942: 2, 3943: 2, 3944: 2, 3945: 1, 3946: 1, 3947: 3, 3948: 2, 3949: 2, 3950: 8, 3951: 1, 3952: 7, 3953: 5, 3954: 1, 3955: 7, 3956: 1, 3957: 3, 3958: 3, 3959: 9, 3960: 2, 3961: 1, 3962: 2, 3963: 4, 3964: 1, 3965: 8, 3966: 1, 3967: 1, 3968: 4, 3969: 7, 3970: 4, 3971: 1, 3972: 2, 3973: 2, 3974: 4, 3975: 1, 3976: 1, 3977: 1, 3978: 4, 3979: 22, 3980: 1, 3981: 3, 3982: 9, 3983: 13, 3984: 3, 3985: 2, 3986: 1, 3987: 1, 3988: 2, 3989: 1, 3990: 2, 3991: 5, 3992: 2, 3993: 10, 3994: 2, 3995: 5, 3996: 2, 3997: 2, 3998: 1, 3999: 2, 4000: 3, 4001: 6, 4002: 1, 4003: 1, 4004: 1, 4005: 1, 4006: 2, 4007: 4, 4008: 5, 4009: 3, 4010: 6, 4011: 3, 4012: 4, 4013: 1, 4014: 8, 4015: 1, 4016: 3, 4017: 1, 4018: 5, 4019: 6, 4020: 4, 4021: 6, 4022: 3, 4023: 1, 4024: 1, 4025: 2, 4026: 4, 4027: 7, 4028: 11, 4029: 7, 4030: 2, 4031: 6, 4032: 5, 4033: 2, 4034: 3, 4035: 8, 4036: 13, 4037: 13, 4038: 3, 4039: 1, 4040: 2, 4041: 7, 4042: 3, 4043: 1, 4044: 8, 4045: 2, 4046: 5, 4047: 2, 4048: 3, 4049: 2, 4050: 3, 4051: 9, 4052: 6, 4053: 15, 4054: 7, 4055: 2, 4056: 3, 4057: 1, 4058: 2, 4059: 2, 4060: 3, 4061: 5, 4062: 2, 4063: 1, 4064: 3, 4065: 3, 4066: 7, 4067: 1, 4068: 5, 4069: 1, 4070: 1, 4071: 3, 4072: 1, 4073: 7, 4074: 1, 4075: 1, 4076: 7, 4077: 2, 4078: 8, 4079: 2, 4080: 3, 4081: 9, 4082: 6, 4083: 2, 4084: 8, 4085: 5, 4086: 8, 4087: 2, 4088: 2, 4089: 2, 4090: 1, 4091: 2, 4092: 11, 4093: 1, 4094: 1, 4095: 1, 4096: 6, 4097: 1, 4098: 7, 4099: 2, 4100: 17, 4101: 12, 4102: 2, 4103: 3, 4104: 8, 4105: 3, 4106: 7, 4107: 1, 4108: 4, 4109: 12, 4110: 9, 4111: 1, 4112: 3, 4113: 1, 4114: 13, 4115: 1, 4116: 3, 4117: 22, 4118: 2, 4119: 1, 4120: 1, 4121: 1, 4122: 1, 4123: 2, 4124: 3, 4125: 1, 4126: 8, 4127: 1, 4128: 1, 4129: 8, 4130: 5, 4131: 7, 4132: 6, 4133: 4, 4134: 3, 4135: 2, 4136: 1, 4137: 8, 4138: 4, 4139: 1, 4140: 9, 4141: 6, 4142: 3, 4143: 3, 4144: 15, 4145: 1, 4146: 5, 4147: 10, 4148: 2, 4149: 5, 4150: 1, 4151: 3, 4152: 3, 4153: 1, 4154: 1, 4155: 3, 4156: 1, 4157: 1, 4158: 5, 4159: 1, 4160: 9, 4161: 1, 4162: 1, 4163: 1, 4164: 13, 4165: 2, 4166: 5, 4167: 3, 4168: 5, 4169: 2, 4170: 9, 4171: 5, 4172: 8, 4173: 2, 4174: 9, 4175: 4, 4176: 8, 4177: 13, 4178: 4, 4179: 9, 4180: 3, 4181: 5, 4182: 3, 4183: 14, 4184: 3, 4185: 4, 4186: 3, 4187: 2, 4188: 9, 4189: 6, 4190: 1, 4191: 7, 4192: 3, 4193: 2, 4194: 19, 4195: 1, 4196: 1, 4197: 2, 4198: 1, 4199: 1, 4200: 10, 4201: 3, 4202: 1, 4203: 1, 4204: 3, 4205: 11, 4206: 3, 4207: 2, 4208: 1, 4209: 2, 4210: 1, 4211: 1, 4212: 2, 4213: 8, 4214: 2, 4215: 2, 4216: 12, 4217: 2, 4218: 1, 4219: 6, 4220: 4, 4221: 1, 4222: 2, 4223: 13, 4224: 2, 4225: 1, 4226: 2, 4227: 2, 4228: 1, 4229: 2, 4230: 1, 4231: 4, 4232: 1, 4233: 2, 4234: 1, 4235: 1, 4236: 1, 4237: 5, 4238: 8, 4239: 1, 4240: 3, 4241: 7, 4242: 1, 4243: 5, 4244: 15, 4245: 8, 4246: 1, 4247: 1, 4248: 1, 4249: 3, 4250: 8, 4251: 1, 4252: 2, 4253: 1, 4254: 5, 4255: 16, 4256: 2, 4257: 13, 4258: 2, 4259: 1, 4260: 1, 4261: 9, 4262: 5, 4263: 3, 4264: 2, 4265: 3, 4266: 1, 4267: 2, 4268: 5, 4269: 1, 4270: 6, 4271: 2, 4272: 1, 4273: 5, 4274: 2, 4275: 4, 4276: 3, 4277: 2, 4278: 1, 4279: 2, 4280: 12, 4281: 4, 4282: 1, 4283: 2, 4284: 1, 4285: 7, 4286: 6, 4287: 6, 4288: 3, 4289: 1, 4290: 3, 4291: 4, 4292: 7, 4293: 6, 4294: 4, 4295: 1, 4296: 1, 4297: 1, 4298: 1, 4299: 1, 4300: 1, 4301: 10, 4302: 2, 4303: 5, 4304: 3, 4305: 8, 4306: 4, 4307: 6, 4308: 7, 4309: 7, 4310: 3, 4311: 3, 4312: 2, 4313: 5, 4314: 5, 4315: 10, 4316: 6, 4317: 9, 4318: 4, 4319: 1, 4320: 1, 4321: 6, 4322: 5, 4323: 4, 4324: 7, 4325: 4, 4326: 5, 4327: 1, 4328: 10, 4329: 4, 4330: 4, 4331: 9, 4332: 1, 4333: 3, 4334: 2, 4335: 1, 4336: 1, 4337: 3, 4338: 2, 4339: 3, 4340: 2, 4341: 10, 4342: 2, 4343: 4, 4344: 4, 4345: 1, 4346: 1, 4347: 16, 4348: 3, 4349: 2, 4350: 2, 4351: 3, 4352: 4, 4353: 1, 4354: 1, 4355: 1, 4356: 17, 4357: 2, 4358: 4, 4359: 9, 4360: 3, 4361: 6, 4362: 2, 4363: 1, 4364: 3, 4365: 5, 4366: 1, 4367: 2, 4368: 13, 4369: 2, 4370: 4, 4371: 3, 4372: 3, 4373: 1, 4374: 2, 4375: 2, 4376: 2, 4377: 4, 4378: 1, 4379: 2, 4380: 5, 4381: 11, 4382: 8, 4383: 1, 4384: 1, 4385: 1, 4386: 1, 4387: 11, 4388: 1, 4389: 5, 4390: 6, 4391: 2, 4392: 1, 4393: 3, 4394: 2, 4395: 3, 4396: 6, 4397: 7, 4398: 1, 4399: 1, 4400: 1, 4401: 1, 4402: 9, 4403: 15, 4404: 13, 4405: 1, 4406: 12, 4407: 1, 4408: 6, 4409: 1, 4410: 3, 4411: 1, 4412: 10, 4413: 2, 4414: 6, 4415: 1, 4416: 1, 4417: 1, 4418: 1, 4419: 1, 4420: 2, 4421: 3, 4422: 7, 4423: 1, 4424: 10, 4425: 6, 4426: 3, 4427: 3, 4428: 1, 4429: 2, 4430: 2, 4431: 1, 4432: 1, 4433: 8, 4434: 3, 4435: 3, 4436: 1, 4437: 3, 4438: 2, 4439: 8, 4440: 1, 4441: 2, 4442: 4, 4443: 6, 4444: 5, 4445: 5, 4446: 3, 4447: 2, 4448: 1, 4449: 3, 4450: 10, 4451: 1, 4452: 1, 4453: 7, 4454: 5, 4455: 4, 4456: 2, 4457: 1, 4458: 1, 4459: 5, 4460: 9, 4461: 2, 4462: 2, 4463: 1, 4464: 6, 4465: 5, 4466: 2, 4467: 2, 4468: 3, 4469: 1, 4470: 1, 4471: 1, 4472: 7, 4473: 2, 4474: 1, 4475: 1, 4476: 1, 4477: 1, 4478: 4, 4479: 1, 4480: 3, 4481: 5, 4482: 4, 4483: 1, 4484: 10, 4485: 5, 4486: 2, 4487: 4, 4488: 2, 4489: 1, 4490: 5, 4491: 7, 4492: 2, 4493: 1, 4494: 1, 4495: 4, 4496: 3, 4497: 3, 4498: 2, 4499: 1, 4500: 4, 4501: 1, 4502: 2, 4503: 1, 4504: 14, 4505: 3, 4506: 1, 4507: 3, 4508: 3, 4509: 1, 4510: 1, 4511: 2, 4512: 1, 4513: 1, 4514: 7, 4515: 7, 4516: 2, 4517: 5, 4518: 7, 4519: 5, 4520: 1, 4521: 1, 4522: 1, 4523: 5, 4524: 2, 4525: 5, 4526: 2, 4527: 1, 4528: 3, 4529: 1, 4530: 4, 4531: 12, 4532: 2, 4533: 3, 4534: 2, 4535: 2, 4536: 1, 4537: 6, 4538: 13, 4539: 1, 4540: 2, 4541: 2, 4542: 1, 4543: 9, 4544: 2, 4545: 10, 4546: 3, 4547: 7, 4548: 2, 4549: 2, 4550: 1, 4551: 1, 4552: 2, 4553: 3, 4554: 1, 4555: 1, 4556: 1, 4557: 5, 4558: 1, 4559: 3, 4560: 5, 4561: 6, 4562: 6, 4563: 9, 4564: 2, 4565: 2, 4566: 14, 4567: 3, 4568: 1, 4569: 1, 4570: 2, 4571: 2, 4572: 1, 4573: 4, 4574: 3, 4575: 1, 4576: 2, 4577: 5, 4578: 3, 4579: 2, 4580: 4, 4581: 1, 4582: 6, 4583: 3, 4584: 4, 4585: 4, 4586: 2, 4587: 1, 4588: 1, 4589: 1, 4590: 2, 4591: 13, 4592: 1, 4593: 7, 4594: 2, 4595: 2, 4596: 2, 4597: 1, 4598: 1, 4599: 1, 4600: 2, 4601: 1, 4602: 1, 4603: 1, 4604: 1, 4605: 3, 4606: 1, 4607: 7, 4608: 1, 4609: 3, 4610: 1, 4611: 1, 4612: 5, 4613: 4, 4614: 6, 4615: 3, 4616: 2, 4617: 3, 4618: 1, 4619: 3, 4620: 1, 4621: 10, 4622: 1, 4623: 1, 4624: 3, 4625: 3, 4626: 6, 4627: 5, 4628: 3, 4629: 1, 4630: 1, 4631: 2, 4632: 4, 4633: 6, 4634: 3, 4635: 2, 4636: 3, 4637: 2, 4638: 1, 4639: 5, 4640: 3, 4641: 9, 4642: 1, 4643: 1, 4644: 11, 4645: 5, 4646: 3, 4647: 1, 4648: 9, 4649: 2, 4650: 2, 4651: 9, 4652: 1, 4653: 9, 4654: 6, 4655: 3, 4656: 6, 4657: 3, 4658: 3, 4659: 5, 4660: 2, 4661: 7, 4662: 3, 4663: 1, 4664: 4, 4665: 4, 4666: 2, 4667: 7, 4668: 2, 4669: 10, 4670: 1, 4671: 2, 4672: 4, 4673: 3, 4674: 2, 4675: 2, 4676: 1, 4677: 1, 4678: 1, 4679: 1, 4680: 1, 4681: 1, 4682: 6, 4683: 3, 4684: 2, 4685: 5, 4686: 2, 4687: 1, 4688: 1, 4689: 6, 4690: 3, 4691: 3, 4692: 2, 4693: 6, 4694: 2, 4695: 1, 4696: 1, 4697: 1, 4698: 7, 4699: 2, 4700: 4, 4701: 1, 4702: 1, 4703: 7, 4704: 2, 4705: 4, 4706: 1, 4707: 2, 4708: 8, 4709: 4, 4710: 4, 4711: 2, 4712: 2, 4713: 4, 4714: 6, 4715: 7, 4716: 1, 4717: 4, 4718: 3, 4719: 1, 4720: 5, 4721: 1, 4722: 20, 4723: 2, 4724: 3, 4725: 4, 4726: 1, 4727: 1, 4728: 2, 4729: 4, 4730: 3, 4731: 5, 4732: 2, 4733: 3, 4734: 3, 4735: 1, 4736: 6, 4737: 2, 4738: 2, 4739: 1, 4740: 1, 4741: 2, 4742: 1, 4743: 1, 4744: 1, 4745: 1, 4746: 2, 4747: 2, 4748: 1, 4749: 2, 4750: 3, 4751: 4, 4752: 4, 4753: 7, 4754: 1, 4755: 1, 4756: 2, 4757: 7, 4758: 2, 4759: 2, 4760: 1, 4761: 1, 4762: 2, 4763: 1, 4764: 4, 4765: 2, 4766: 3, 4767: 10, 4768: 1, 4769: 5, 4770: 3, 4771: 2, 4772: 4, 4773: 3, 4774: 3, 4775: 2, 4776: 4, 4777: 4, 4778: 1, 4779: 1, 4780: 4, 4781: 5, 4782: 3, 4783: 3, 4784: 2, 4785: 3, 4786: 2, 4787: 1, 4788: 4, 4789: 2, 4790: 4, 4791: 2, 4792: 1, 4793: 1, 4794: 5, 4795: 1, 4796: 2, 4797: 8, 4798: 1, 4799: 1, 4800: 2, 4801: 4, 4802: 2, 4803: 7, 4804: 1, 4805: 3, 4806: 1, 4807: 9, 4808: 5, 4809: 5, 4810: 1, 4811: 10, 4812: 3, 4813: 1, 4814: 4, 4815: 1, 4816: 3, 4817: 3, 4818: 1, 4819: 2, 4820: 6, 4821: 1, 4822: 11, 4823: 12, 4824: 1, 4825: 1, 4826: 2, 4827: 1, 4828: 3, 4829: 4, 4830: 7, 4831: 7, 4832: 3, 4833: 8, 4834: 1, 4835: 4, 4836: 9, 4837: 8, 4838: 4, 4839: 2, 4840: 1, 4841: 4, 4842: 2, 4843: 1, 4844: 1, 4845: 12, 4846: 5, 4847: 3, 4848: 11, 4849: 1, 4850: 12, 4851: 1, 4852: 3, 4853: 2, 4854: 4, 4855: 1, 4856: 4, 4857: 2, 4858: 2, 4859: 4, 4860: 2, 4861: 1, 4862: 1, 4863: 5, 4864: 2, 4865: 2, 4866: 1, 4867: 3, 4868: 12, 4869: 1, 4870: 2, 4871: 2, 4872: 1, 4873: 1, 4874: 3, 4875: 2, 4876: 6, 4877: 6, 4878: 2, 4879: 4, 4880: 5, 4881: 6, 4882: 3, 4883: 1, 4884: 1, 4885: 3, 4886: 2, 4887: 3, 4888: 1, 4889: 6, 4890: 1, 4891: 3, 4892: 2, 4893: 1, 4894: 2, 4895: 2, 4896: 5, 4897: 8, 4898: 1, 4899: 7, 4900: 1, 4901: 9, 4902: 1, 4903: 2, 4904: 1, 4905: 6, 4906: 3, 4907: 6, 4908: 4, 4909: 1, 4910: 2, 4911: 2, 4912: 4, 4913: 2, 4914: 6, 4915: 5, 4916: 1, 4917: 1, 4918: 8, 4919: 4, 4920: 1, 4921: 6, 4922: 2, 4923: 2, 4924: 1, 4925: 2, 4926: 2, 4927: 3, 4928: 1, 4929: 1, 4930: 5, 4931: 1, 4932: 1, 4933: 2, 4934: 4, 4935: 2, 4936: 1, 4937: 2, 4938: 3, 4939: 1, 4940: 2, 4941: 4, 4942: 1, 4943: 3, 4944: 2, 4945: 1, 4946: 1, 4947: 2, 4948: 3, 4949: 2, 4950: 3, 4951: 2, 4952: 1, 4953: 1, 4954: 1, 4955: 1, 4956: 2, 4957: 1, 4958: 6, 4959: 6, 4960: 2, 4961: 3, 4962: 2, 4963: 1, 4964: 2, 4965: 1, 4966: 4, 4967: 5, 4968: 10, 4969: 5, 4970: 1, 4971: 2, 4972: 1, 4973: 1, 4974: 4, 4975: 6, 4976: 4, 4977: 3, 4978: 2, 4979: 1, 4980: 2, 4981: 12, 4982: 2, 4983: 1, 4984: 3, 4985: 1, 4986: 2, 4987: 1, 4988: 4, 4989: 1, 4990: 1, 4991: 4, 4992: 2, 4993: 2, 4994: 1, 4995: 1, 4996: 1, 4997: 2, 4998: 1, 4999: 1, 5000: 1, 5001: 3, 5002: 1, 5003: 3, 5004: 6, 5005: 1, 5006: 2, 5007: 2, 5008: 2, 5009: 2, 5010: 6, 5011: 1, 5012: 2, 5013: 3, 5014: 2, 5015: 1, 5016: 1, 5017: 1, 5018: 1, 5019: 3, 5020: 2, 5021: 1, 5022: 1, 5023: 2, 5024: 6, 5025: 3, 5026: 7, 5027: 2, 5028: 2, 5029: 2, 5030: 2, 5031: 9, 5032: 3, 5033: 1, 5034: 1, 5035: 1, 5036: 4, 5037: 1, 5038: 1, 5039: 4, 5040: 4, 5041: 4, 5042: 1, 5043: 1, 5044: 3, 5045: 4, 5046: 2, 5047: 6, 5048: 1, 5049: 1, 5050: 1, 5051: 4, 5052: 3, 5053: 1, 5054: 1, 5055: 4, 5056: 1, 5057: 1, 5058: 1, 5059: 2, 5060: 6, 5061: 1, 5062: 2, 5063: 2, 5064: 5, 5065: 6, 5066: 2, 5067: 4, 5068: 4, 5069: 2, 5070: 1, 5071: 1, 5072: 3, 5073: 1, 5074: 1, 5075: 1, 5076: 4, 5077: 2, 5078: 2, 5079: 4, 5080: 2, 5081: 1, 5082: 1, 5083: 1, 5084: 1, 5085: 1, 5086: 1, 5087: 1, 5088: 2, 5089: 2, 5090: 1, 5091: 3, 5092: 1, 5093: 1, 5094: 3, 5095: 1, 5096: 1, 5097: 2, 5098: 8, 5099: 1, 5100: 4, 5101: 7, 5102: 7, 5103: 3, 5104: 6, 5105: 3, 5106: 6, 5107: 4, 5108: 3, 5109: 2, 5110: 1, 5111: 4, 5112: 4, 5113: 1, 5114: 3, 5115: 7, 5116: 5, 5117: 1, 5118: 4, 5119: 3, 5120: 1, 5121: 2, 5122: 2, 5123: 2, 5124: 2, 5125: 2, 5126: 1, 5127: 2, 5128: 5, 5129: 1, 5130: 2, 5131: 1, 5132: 1, 5133: 3, 5134: 3, 5135: 3, 5136: 4, 5137: 1, 5138: 4, 5139: 2, 5140: 1, 5141: 5, 5142: 7, 5143: 2, 5144: 4, 5145: 4, 5146: 3, 5147: 1, 5148: 1, 5149: 1, 5150: 2, 5151: 1, 5152: 2, 5153: 2, 5154: 1, 5155: 1, 5156: 1, 5157: 1, 5158: 2, 5159: 3, 5160: 2, 5161: 3, 5162: 1, 5163: 3, 5164: 1, 5165: 1, 5166: 2, 5167: 2, 5168: 5, 5169: 2, 5170: 5, 5171: 2, 5172: 1, 5173: 1, 5174: 2, 5175: 4, 5176: 4, 5177: 3, 5178: 1, 5179: 3, 5180: 2, 5181: 3, 5182: 4, 5183: 1, 5184: 2, 5185: 1, 5186: 3, 5187: 9, 5188: 1, 5189: 5, 5190: 1, 5191: 3, 5192: 1, 5193: 2, 5194: 1, 5195: 1, 5196: 2, 5197: 4, 5198: 1, 5199: 2, 5200: 3, 5201: 1, 5202: 1, 5203: 1, 5204: 3, 5205: 1, 5206: 4, 5207: 5, 5208: 4, 5209: 5, 5210: 1, 5211: 1, 5212: 6, 5213: 7, 5214: 2, 5215: 1, 5216: 2, 5217: 2, 5218: 2, 5219: 4, 5220: 1, 5221: 2, 5222: 1, 5223: 1, 5224: 1, 5225: 2, 5226: 4, 5227: 1, 5228: 5, 5229: 4, 5230: 1, 5231: 1, 5232: 3, 5233: 1, 5234: 3, 5235: 2, 5236: 1, 5237: 1, 5238: 8, 5239: 4, 5240: 2, 5241: 3, 5242: 1, 5243: 1, 5244: 1, 5245: 2, 5246: 1, 5247: 1, 5248: 5, 5249: 1, 5250: 2, 5251: 2, 5252: 1, 5253: 2, 5254: 1, 5255: 1, 5256: 5, 5257: 1, 5258: 1, 5259: 3, 5260: 3, 5261: 3, 5262: 1, 5263: 1, 5264: 1, 5265: 1, 5266: 1, 5267: 2, 5268: 1, 5269: 1, 5270: 4, 5271: 1, 5272: 2, 5273: 1, 5274: 4, 5275: 2, 5276: 1, 5277: 1, 5278: 2, 5279: 4, 5280: 1, 5281: 1, 5282: 4, 5283: 3, 5284: 9, 5285: 1, 5286: 2, 5287: 1, 5288: 2, 5289: 2, 5290: 2, 5291: 1, 5292: 1, 5293: 2, 5294: 1, 5295: 4, 5296: 1, 5297: 2, 5298: 1, 5299: 5, 5300: 1, 5301: 2, 5302: 2, 5303: 4, 5304: 2, 5305: 3, 5306: 2, 5307: 1, 5308: 1, 5309: 1, 5310: 1, 5311: 3, 5312: 4, 5313: 1, 5314: 3, 5315: 2, 5316: 6, 5317: 1, 5318: 1, 5319: 2, 5320: 1, 5321: 4, 5322: 1, 5323: 2, 5324: 1, 5325: 2, 5326: 4, 5327: 1, 5328: 1, 5329: 1, 5330: 3, 5331: 2, 5332: 4, 5333: 2, 5334: 3, 5335: 9, 5336: 3, 5337: 4, 5338: 3, 5339: 3, 5340: 3, 5341: 2, 5342: 2, 5343: 1, 5344: 1, 5345: 2, 5346: 2, 5347: 1, 5348: 2, 5349: 1, 5350: 1, 5351: 5, 5352: 1, 5353: 3, 5354: 4, 5355: 1, 5356: 1, 5357: 1, 5358: 2, 5359: 2, 5360: 2, 5361: 1, 5362: 1, 5363: 2, 5364: 5, 5365: 4, 5366: 2, 5367: 1, 5368: 3, 5369: 1, 5370: 1, 5371: 4, 5372: 1, 5373: 3, 5374: 1, 5375: 1, 5376: 3, 5377: 1, 5378: 3, 5379: 1, 5380: 3, 5381: 5, 5382: 2, 5383: 2, 5384: 2, 5385: 2, 5386: 4, 5387: 2, 5388: 2, 5389: 3, 5390: 5, 5391: 3, 5392: 2, 5393: 1, 5394: 1, 5395: 2, 5396: 2, 5397: 1, 5398: 1, 5399: 5, 5400: 1, 5401: 2, 5402: 1, 5403: 1, 5404: 3, 5405: 2, 5406: 6, 5407: 1, 5408: 1, 5409: 1, 5410: 1, 5411: 1, 5412: 1, 5413: 5, 5414: 2, 5415: 1, 5416: 1, 5417: 5, 5418: 2, 5419: 1, 5420: 7, 5421: 1, 5422: 1, 5423: 1, 5424: 2, 5425: 1, 5426: 2, 5427: 1, 5428: 2, 5429: 3, 5430: 1, 5431: 1, 5432: 1, 5433: 1, 5434: 4, 5435: 1, 5436: 2, 5437: 2, 5438: 5, 5439: 2, 5440: 1, 5441: 1, 5442: 4, 5443: 1, 5444: 1, 5445: 1, 5446: 2, 5447: 1, 5448: 2, 5449: 1, 5450: 1, 5451: 1, 5452: 2, 5453: 1, 5454: 3, 5455: 1, 5456: 2, 5457: 4, 5458: 1, 5459: 4, 5460: 2, 5461: 4, 5462: 1, 5463: 1, 5464: 1, 5465: 3, 5466: 1, 5467: 2, 5468: 1, 5469: 6, 5470: 2, 5471: 1, 5472: 3, 5473: 1, 5474: 1, 5475: 4, 5476: 1, 5477: 1, 5478: 2, 5479: 1, 5480: 1, 5481: 3, 5482: 5, 5483: 2, 5484: 1, 5485: 1, 5486: 1, 5487: 3, 5488: 1, 5489: 2, 5490: 1, 5491: 2, 5492: 1, 5493: 1, 5494: 3, 5495: 3, 5496: 1, 5497: 2, 5498: 2, 5499: 1, 5500: 1, 5501: 1, 5502: 2, 5503: 3, 5504: 1, 5505: 2, 5506: 2, 5507: 1, 5508: 1, 5509: 2, 5510: 3, 5511: 1, 5512: 3, 5513: 3, 5514: 2, 5515: 2, 5516: 1, 5517: 4, 5518: 1, 5519: 1, 5520: 1, 5521: 1, 5522: 1, 5523: 1, 5524: 1, 5525: 1, 5526: 1, 5527: 1, 5528: 1, 5529: 1, 5530: 1, 5531: 1, 5532: 4, 5533: 2, 5534: 1, 5535: 1, 5536: 1, 5537: 1, 5538: 2, 5539: 3, 5540: 2, 5541: 1, 5542: 1, 5543: 3, 5544: 1, 5545: 1, 5546: 4, 5547: 2, 5548: 1, 5549: 1, 5550: 4, 5551: 3, 5552: 1, 5553: 3, 5554: 1, 5555: 2, 5556: 2, 5557: 5, 5558: 1, 5559: 2, 5560: 2, 5561: 1, 5562: 3, 5563: 1, 5564: 1, 5565: 6, 5566: 1, 5567: 1, 5568: 2, 5569: 1, 5570: 1, 5571: 1, 5572: 3, 5573: 1, 5574: 2, 5575: 2, 5576: 1, 5577: 1, 5578: 2, 5579: 1, 5580: 1, 5581: 1, 5582: 2, 5583: 2, 5584: 1, 5585: 1, 5586: 3, 5587: 2, 5588: 2, 5589: 1, 5590: 3, 5591: 3, 5592: 1, 5593: 1, 5594: 1, 5595: 1, 5596: 1, 5597: 2, 5598: 1, 5599: 1, 5600: 1, 5601: 2, 5602: 4, 5603: 1, 5604: 1, 5605: 1, 5606: 2, 5607: 1, 5608: 2, 5609: 1, 5610: 1, 5611: 1, 5612: 1, 5613: 1, 5614: 2, 5615: 1, 5616: 3, 5617: 3, 5618: 1, 5619: 1, 5620: 1, 5621: 2, 5622: 1, 5623: 1, 5624: 6, 5625: 2, 5626: 2, 5627: 3, 5628: 6, 5629: 1, 5630: 1, 5631: 2, 5632: 2, 5633: 4, 5634: 1, 5635: 2, 5636: 1, 5637: 1, 5638: 3, 5639: 1, 5640: 2, 5641: 2, 5642: 1, 5643: 1, 5644: 1, 5645: 2, 5646: 1, 5647: 1, 5648: 2, 5649: 2, 5650: 1, 5651: 1, 5652: 2, 5653: 4, 5654: 1, 5655: 2, 5656: 1, 5657: 3, 5658: 1, 5659: 1, 5660: 3, 5661: 1, 5662: 1, 5663: 1, 5664: 2, 5665: 3, 5666: 2, 5667: 1, 5668: 1, 5669: 1, 5670: 1, 5671: 2, 5672: 2, 5673: 1, 5674: 1, 5675: 1, 5676: 1, 5677: 1, 5678: 1, 5679: 1, 5680: 1, 5681: 1, 5682: 1, 5683: 2, 5684: 2, 5685: 1, 5686: 1, 5687: 1, 5688: 1, 5689: 3, 5690: 3, 5691: 1, 5692: 1, 5693: 1, 5694: 1, 5695: 1, 5696: 2, 5697: 1, 5698: 1, 5699: 2, 5700: 1, 5701: 1, 5702: 1, 5703: 1, 5704: 1, 5705: 2, 5706: 2, 5707: 2, 5708: 2, 5709: 2, 5710: 1, 5711: 2, 5712: 2, 5713: 1, 5714: 1, 5715: 1, 5716: 1, 5717: 2, 5718: 3, 5719: 1, 5720: 1, 5721: 1, 5722: 1, 5723: 1, 5724: 1, 5725: 1, 5726: 2, 5727: 4, 5728: 2, 5729: 1, 5730: 2, 5731: 2, 5732: 1, 5733: 1, 5734: 2, 5735: 3, 5736: 2, 5737: 1, 5738: 1, 5739: 2, 5740: 3, 5741: 1, 5742: 2, 5743: 2, 5744: 3, 5745: 1, 5746: 1, 5747: 6, 5748: 1, 5749: 2, 5750: 1, 5751: 4, 5752: 1, 5753: 2, 5754: 3, 5755: 1, 5756: 1, 5757: 2, 5758: 2, 5759: 1, 5760: 2, 5761: 1, 5762: 2, 5763: 1, 5764: 3, 5765: 1, 5766: 2, 5767: 3, 5768: 1, 5769: 3, 5770: 1, 5771: 2, 5772: 1, 5773: 1, 5774: 1, 5775: 2, 5776: 1, 5777: 2, 5778: 1, 5779: 1, 5780: 2, 5781: 1, 5782: 1, 5783: 1, 5784: 1, 5785: 1, 5786: 5, 5787: 1, 5788: 1, 5789: 3, 5790: 3, 5791: 1, 5792: 1, 5793: 2, 5794: 1, 5795: 1, 5796: 1, 5797: 1, 5798: 1, 5799: 2, 5800: 1, 5801: 3, 5802: 1, 5803: 4, 5804: 2, 5805: 1, 5806: 1, 5807: 1, 5808: 2, 5809: 2, 5810: 1, 5811: 1, 5812: 1, 5813: 1, 5814: 1, 5815: 1, 5816: 1, 5817: 1, 5818: 2, 5819: 1, 5820: 2, 5821: 3, 5822: 4, 5823: 2, 5824: 1, 5825: 2, 5826: 1, 5827: 2, 5828: 3, 5829: 2, 5830: 1, 5831: 1, 5832: 1, 5833: 1, 5834: 1, 5835: 1, 5836: 1, 5837: 1, 5838: 1, 5839: 1, 5840: 1, 5841: 2, 5842: 1, 5843: 2, 5844: 1, 5845: 3, 5846: 1, 5847: 1, 5848: 2, 5849: 2, 5850: 2, 5851: 1, 5852: 1, 5853: 2, 5854: 1, 5855: 1, 5856: 4, 5857: 1, 5858: 1, 5859: 1, 5860: 4, 5861: 1, 5862: 1, 5863: 1, 5864: 2, 5865: 1, 5866: 1, 5867: 1, 5868: 1, 5869: 1, 5870: 1, 5871: 3, 5872: 2, 5873: 1, 5874: 1, 5875: 1, 5876: 1, 5877: 1, 5878: 2, 5879: 1, 5880: 1, 5881: 1, 5882: 3, 5883: 1, 5884: 1, 5885: 1, 5886: 1, 5887: 1, 5888: 1, 5889: 1, 5890: 3, 5891: 1, 5892: 2, 5893: 1, 5894: 1, 5895: 1, 5896: 1, 5897: 1, 5898: 1, 5899: 2, 5900: 1, 5901: 1, 5902: 1, 5903: 1, 5904: 2, 5905: 1, 5906: 1, 5907: 1, 5908: 2, 5909: 3, 5910: 1, 5911: 1, 5912: 1, 5913: 1, 5914: 1, 5915: 4, 5916: 2, 5917: 2, 5918: 3, 5919: 3, 5920: 2, 5921: 1, 5922: 1, 5923: 4, 5924: 1, 5925: 2, 5926: 1, 5927: 1, 5928: 4, 5929: 1, 5930: 2, 5931: 3, 5932: 2, 5933: 3, 5934: 1, 5935: 1, 5936: 3, 5937: 1, 5938: 1, 5939: 2, 5940: 1, 5941: 2, 5942: 1, 5943: 2, 5944: 1, 5945: 2, 5946: 2, 5947: 3, 5948: 1, 5949: 1, 5950: 1, 5951: 2, 5952: 2, 5953: 1, 5954: 2, 5955: 2, 5956: 1, 5957: 1, 5958: 3, 5959: 1, 5960: 1, 5961: 1, 5962: 1, 5963: 1, 5964: 1, 5965: 1, 5966: 1, 5967: 1, 5968: 1, 5969: 5, 5970: 2, 5971: 1, 5972: 3, 5973: 1, 5974: 1, 5975: 1, 5976: 1, 5977: 1, 5978: 2, 5979: 1, 5980: 1, 5981: 1, 5982: 1, 5983: 1, 5984: 1, 5985: 1, 5986: 1, 5987: 1, 5988: 2, 5989: 1, 5990: 1, 5991: 3, 5992: 1, 5993: 1, 5994: 1, 5995: 1, 5996: 1, 5997: 1, 5998: 1, 5999: 1, 6000: 3, 6001: 6, 6002: 1, 6003: 1, 6004: 1, 6005: 3, 6006: 1, 6007: 2, 6008: 2, 6009: 1, 6010: 1, 6011: 2, 6012: 3, 6013: 1, 6014: 1, 6015: 1, 6016: 3, 6017: 1, 6018: 1, 6019: 2, 6020: 1, 6021: 1, 6022: 1, 6023: 1, 6024: 1, 6025: 1, 6026: 3, 6027: 2, 6028: 1, 6029: 1, 6030: 1, 6031: 2, 6032: 1, 6033: 2, 6034: 1, 6035: 1, 6036: 1, 6037: 1, 6038: 1, 6039: 2, 6040: 1, 6041: 1, 6042: 1, 6043: 1, 6044: 2, 6045: 1, 6046: 1, 6047: 1, 6048: 1, 6049: 2, 6050: 1, 6051: 1, 6052: 3, 6053: 1, 6054: 1, 6055: 1, 6056: 1, 6057: 1, 6058: 1, 6059: 1, 6060: 2, 6061: 1, 6062: 1, 6063: 1, 6064: 3, 6065: 1, 6066: 1, 6067: 1, 6068: 1, 6069: 3, 6070: 1, 6071: 1, 6072: 1, 6073: 1, 6074: 1, 6075: 1, 6076: 1, 6077: 1, 6078: 1, 6079: 1, 6080: 1, 6081: 1, 6082: 2, 6083: 1, 6084: 2, 6085: 1, 6086: 1, 6087: 1, 6088: 1, 6089: 1, 6090: 2, 6091: 2, 6092: 1, 6093: 1, 6094: 2, 6095: 1, 6096: 1, 6097: 1, 6098: 1, 6099: 1, 6100: 1, 6101: 1, 6102: 1, 6103: 1, 6104: 1, 6105: 1, 6106: 2, 6107: 1, 6108: 1, 6109: 1, 6110: 3, 6111: 3, 6112: 1, 6113: 1, 6114: 3, 6115: 1, 6116: 1, 6117: 2, 6118: 1, 6119: 2, 6120: 1, 6121: 1, 6122: 1, 6123: 1, 6124: 2, 6125: 3, 6126: 1, 6127: 1, 6128: 1, 6129: 3, 6130: 1, 6131: 1, 6132: 1, 6133: 1, 6134: 1, 6135: 1, 6136: 1, 6137: 2, 6138: 2, 6139: 1, 6140: 2, 6141: 2, 6142: 1, 6143: 1, 6144: 1, 6145: 1, 6146: 1, 6147: 3, 6148: 1, 6149: 1, 6150: 3, 6151: 1, 6152: 1, 6153: 1, 6154: 1, 6155: 1, 6156: 1, 6157: 1, 6158: 1, 6159: 2, 6160: 2, 6161: 2, 6162: 1, 6163: 1, 6164: 4, 6165: 1, 6166: 1, 6167: 2, 6168: 1, 6169: 2, 6170: 2, 6171: 1, 6172: 2, 6173: 1, 6174: 1, 6175: 1, 6176: 1, 6177: 1, 6178: 1, 6179: 1, 6180: 1, 6181: 3, 6182: 2, 6183: 1, 6184: 3, 6185: 1, 6186: 1, 6187: 2, 6188: 1, 6189: 1, 6190: 1, 6191: 2, 6192: 1, 6193: 1, 6194: 1, 6195: 1, 6196: 2, 6197: 1, 6198: 1, 6199: 2, 6200: 2, 6201: 1, 6202: 1, 6203: 2, 6204: 2, 6205: 1, 6206: 1, 6207: 1, 6208: 1, 6209: 1, 6210: 1, 6211: 1, 6212: 3, 6213: 1, 6214: 1, 6215: 2, 6216: 1, 6217: 1, 6218: 1, 6219: 1, 6220: 1, 6221: 2, 6222: 1, 6223: 1, 6224: 1, 6225: 1, 6226: 1, 6227: 1, 6228: 1, 6229: 1, 6230: 5, 6231: 1, 6232: 2, 6233: 2, 6234: 1, 6235: 2, 6236: 1, 6237: 1, 6238: 2, 6239: 1, 6240: 1, 6241: 2, 6242: 1, 6243: 1, 6244: 1, 6245: 1, 6246: 1, 6247: 1, 6248: 2, 6249: 1, 6250: 1, 6251: 1, 6252: 1, 6253: 1, 6254: 1, 6255: 2, 6256: 1, 6257: 1, 6258: 1, 6259: 1, 6260: 1, 6261: 2, 6262: 1, 6263: 2, 6264: 1, 6265: 2, 6266: 1, 6267: 1, 6268: 1, 6269: 1, 6270: 1, 6271: 1, 6272: 2, 6273: 1, 6274: 1, 6275: 1, 6276: 1, 6277: 1, 6278: 1, 6279: 1, 6280: 1, 6281: 1, 6282: 2, 6283: 2, 6284: 1, 6285: 1, 6286: 1, 6287: 1, 6288: 1, 6289: 2, 6290: 1, 6291: 2, 6292: 1, 6293: 1, 6294: 1, 6295: 1, 6296: 4, 6297: 1, 6298: 2, 6299: 1, 6300: 2, 6301: 3, 6302: 1, 6303: 1, 6304: 2, 6305: 1, 6306: 1, 6307: 2, 6308: 1, 6309: 2, 6310: 1, 6311: 1, 6312: 1, 6313: 1, 6314: 1, 6315: 1, 6316: 2, 6317: 1, 6318: 1, 6319: 1, 6320: 1, 6321: 2, 6322: 1, 6323: 2, 6324: 1, 6325: 2, 6326: 1, 6327: 1, 6328: 2, 6329: 1, 6330: 3, 6331: 1, 6332: 2, 6333: 1, 6334: 1, 6335: 1, 6336: 1, 6337: 1, 6338: 1, 6339: 1, 6340: 1, 6341: 1, 6342: 1, 6343: 1, 6344: 1, 6345: 1, 6346: 1, 6347: 1, 6348: 1, 6349: 2, 6350: 1, 6351: 1, 6352: 1, 6353: 1, 6354: 1, 6355: 1, 6356: 2, 6357: 1, 6358: 2, 6359: 1, 6360: 1, 6361: 1, 6362: 1, 6363: 1, 6364: 1, 6365: 1, 6366: 1, 6367: 1, 6368: 2, 6369: 1, 6370: 1, 6371: 1, 6372: 2, 6373: 1, 6374: 1, 6375: 1, 6376: 1, 6377: 1, 6378: 1, 6379: 1, 6380: 2, 6381: 1, 6382: 1, 6383: 1, 6384: 1, 6385: 1, 6386: 1, 6387: 1, 6388: 1, 6389: 1, 6390: 1, 6391: 1, 6392: 1, 6393: 1, 6394: 1, 6395: 1, 6396: 1, 6397: 1, 6398: 1, 6399: 1, 6400: 1, 6401: 2, 6402: 2, 6403: 2, 6404: 1, 6405: 1, 6406: 1, 6407: 1, 6408: 1, 6409: 1, 6410: 2, 6411: 1, 6412: 2, 6413: 2, 6414: 1, 6415: 1, 6416: 1, 6417: 2, 6418: 1, 6419: 1, 6420: 1, 6421: 1, 6422: 1, 6423: 2, 6424: 1, 6425: 2, 6426: 1, 6427: 3, 6428: 1, 6429: 1, 6430: 1, 6431: 2, 6432: 2, 6433: 1, 6434: 1, 6435: 1, 6436: 1, 6437: 1, 6438: 1, 6439: 1, 6440: 1, 6441: 2, 6442: 1, 6443: 1, 6444: 2, 6445: 1, 6446: 1, 6447: 1, 6448: 1, 6449: 1, 6450: 2, 6451: 1, 6452: 3, 6453: 1, 6454: 1, 6455: 1, 6456: 1, 6457: 1, 6458: 1, 6459: 1, 6460: 1, 6461: 1, 6462: 1, 6463: 1, 6464: 1, 6465: 1, 6466: 1, 6467: 1, 6468: 1, 6469: 2, 6470: 1, 6471: 1, 6472: 1, 6473: 1, 6474: 1, 6475: 1, 6476: 1, 6477: 1, 6478: 1, 6479: 1, 6480: 1, 6481: 1, 6482: 1, 6483: 1, 6484: 2, 6485: 1, 6486: 1, 6487: 1, 6488: 1, 6489: 1, 6490: 1, 6491: 1, 6492: 1, 6493: 1, 6494: 2, 6495: 1, 6496: 1, 6497: 1, 6498: 2, 6499: 1, 6500: 1, 6501: 1, 6502: 1, 6503: 1, 6504: 2, 6505: 1, 6506: 1, 6507: 1, 6508: 1, 6509: 1, 6510: 1, 6511: 1, 6512: 1, 6513: 1, 6514: 1, 6515: 1, 6516: 1, 6517: 1, 6518: 1, 6519: 1, 6520: 1, 6521: 1, 6522: 1, 6523: 1, 6524: 1, 6525: 1, 6526: 1, 6527: 1, 6528: 1, 6529: 1, 6530: 1, 6531: 1, 6532: 1, 6533: 1, 6534: 1, 6535: 1, 6536: 1, 6537: 1, 6538: 1, 6539: 1, 6540: 1, 6541: 1, 6542: 1, 6543: 1, 6544: 1, 6545: 1, 6546: 1, 6547: 1, 6548: 1, 6549: 1, 6550: 1, 6551: 1, 6552: 1, 6553: 1, 6554: 1, 6555: 1, 6556: 1, 6557: 1, 6558: 1, 6559: 1, 6560: 1, 6561: 1, 6562: 1, 6563: 2, 6564: 2, 6565: 1, 6566: 1, 6567: 2, 6568: 1, 6569: 1, 6570: 1, 6571: 1, 6572: 1, 6573: 1, 6574: 1, 6575: 1, 6576: 1, 6577: 1, 6578: 1, 6579: 1, 6580: 1, 6581: 1, 6582: 1, 6583: 1, 6584: 1, 6585: 1, 6586: 1, 6587: 1, 6588: 1, 6589: 1, 6590: 1, 6591: 1, 6592: 1, 6593: 1, 6594: 1, 6595: 1, 6596: 1, 6597: 1, 6598: 1, 6599: 1, 6600: 2, 6601: 1, 6602: 1, 6603: 1, 6604: 1, 6605: 1, 6606: 1, 6607: 1, 6608: 1, 6609: 1, 6610: 1, 6611: 1, 6612: 1, 6613: 1, 6614: 1, 6615: 1, 6616: 1, 6617: 1, 6618: 1, 6619: 1, 6620: 1, 6621: 1, 6622: 1, 6623: 2, 6624: 1, 6625: 1, 6626: 1, 6627: 1, 6628: 1, 6629: 1, 6630: 1, 6631: 1, 6632: 1, 6633: 1, 6634: 1, 6635: 1, 6636: 1, 6637: 1, 6638: 1, 6639: 1, 6640: 1, 6641: 1, 6642: 2, 6643: 1, 6644: 1, 6645: 1, 6646: 1, 6647: 1, 6648: 1, 6649: 1, 6650: 1, 6651: 1, 6652: 1, 6653: 1, 6654: 1, 6655: 1, 6656: 1, 6657: 1, 6658: 1, 6659: 1, 6660: 1, 6661: 1, 6662: 1, 6663: 1, 6664: 1, 6665: 1, 6666: 1, 6667: 1, 6668: 1, 6669: 1, 6670: 1, 6671: 1, 6672: 1, 6673: 1, 6674: 1, 6675: 1, 6676: 1, 6677: 1, 6678: 1, 6679: 1, 6680: 1, 6681: 1, 6682: 1, 6683: 1, 6684: 1, 6685: 1, 6686: 1, 6687: 1, 6688: 1, 6689: 1, 6690: 1, 6691: 1, 6692: 1, 6693: 1, 6694: 1, 6695: 1, 6696: 1, 6697: 1, 6698: 1, 6699: 1, 6700: 1, 6701: 1, 6702: 1, 6703: 1, 6704: 1, 6705: 1, 6706: 1, 6707: 1, 6708: 1, 6709: 1, 6710: 1, 6711: 1, 6712: 1, 6713: 1}

Задание 2. У объекта dictionary2 есть переменная dfs — это словарь, ключами которого являются id токена, а элементами — число раз, сколько слово встретилось во всей коллекции. Сохраните в отдельный список ингредиенты, которые встретились в коллекции больше 4000 раз. Вызовите метод словаря filter_tokens, подав в качестве первого аргумента полученный список популярных ингредиентов. Вычислите две величины: dict_size_before и dict_size_after — размер словаря до и после фильтрации.

Затем, используя новый словарь, создайте новый корпус документов, corpus2, по аналогии с тем, как это сделано в начале ноутбука. Вычислите две величины: corpus_size_before и corpus_size_after — суммарное количество ингредиентов в корпусе (для каждого документа вычислите число различных ингредиентов в нем и просуммируйте по всем документам) до и после фильтрации.

Передайте величины dict_size_before, dict_size_after, corpus_size_before, corpus_size_after в функцию save_answers2 и загрузите сгенерированный файл в форму.


In [15]:
too_often_tokens = [x[0] for x in dictionary2.dfs.items() if x[1] > 4000]
print(len(too_often_tokens))


12

In [16]:
dictionary2.filter_tokens(too_often_tokens)

In [17]:
dict_size_before = len(dictionary) 
dict_size_after = len(dictionary2)
print(dict_size_before)
print(dict_size_after)


6714
6702

In [18]:
new_corpus = [dictionary2.doc2bow(text) for text in texts]

In [19]:
corpus_size_before = 0
corpus_size_after = 0
for doc1, doc2 in zip(corpus, new_corpus):
    corpus_size_before += len(doc1)
    corpus_size_after += len(doc2)

In [20]:
print(corpus_size_before)
print(corpus_size_after)


428249
343665

In [21]:
def save_answers2(dict_size_before, dict_size_after, corpus_size_before, corpus_size_after):
    with open("cooking_LDA_pa_task2.txt", "w") as fout:
        fout.write(" ".join([str(el) for el in [dict_size_before, dict_size_after, corpus_size_before, corpus_size_after]]))

In [22]:
save_answers2(dict_size_before, dict_size_after, corpus_size_before, corpus_size_after)

Сравнение когерентностей

Задание 3. Постройте еще одну модель по корпусу corpus2 и словарю dictionary2, остальные параметры оставьте такими же, как при первом построении модели. Сохраните новую модель в другую переменную (не перезаписывайте предыдущую модель). Не забудьте про фиксирование seed!

Затем воспользуйтесь методом top_topics модели, чтобы вычислить ее когерентность. Передайте в качестве аргумента соответствующий модели корпус. Метод вернет список кортежей (топ токенов, когерентность), отсортированных по убыванию последней. Вычислите среднюю по всем темам когерентность для каждой из двух моделей и передайте в функцию save_answers3.


In [23]:
np.random.seed(76543)
lda2 = LdaModel(new_corpus, id2word=dictionary2, num_topics=40, passes=5)

In [24]:
coherensions = lda.top_topics(corpus)
coherensions2 = lda2.top_topics(new_corpus)


---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-24-928136ac209c> in <module>()
----> 1 coherensions = lda.top_topics(corpus)
      2 coherensions2 = lda2.top_topics(new_corpus)

/usr/lib/python3.5/site-packages/gensim/models/ldamodel.py in top_topics(self, corpus, num_words)
    878                 # Sum of top words l=1..m-1
    879                 # i.e., all words ranked higher than the current word m
--> 880                 for l in top_words[:m_index - 1]:
    881                     # l_docs is v_l^(t)
    882                     l_docs = doc_word_list[l]

TypeError: only integer scalar arrays can be converted to a scalar index

In [25]:
coherence = np.array(x[1] for tup in coherensions for x in tup).mean()
coherence2 = np.array(x[1] for tup in coherensions2 for x in tup).mean()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-25-7147afe481f4> in <module>()
----> 1 coherence = np.array(x[1] for tup in coherensions for x in tup).mean()
      2 coherence2 = np.array(x[1] for tup in coherensions2 for x in tup).mean()

NameError: name 'coherensions' is not defined

In [26]:
def save_answers3(coherence, coherence2):
    with open("cooking_LDA_pa_task3.txt", "w") as fout:
        fout.write(" ".join(["%3f"%el for el in [coherence, coherence2]]))

In [27]:
save_answers3(coherence, coherence2)


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-27-ceb8701e3ac5> in <module>()
----> 1 save_answers3(coherence, coherence2)

NameError: name 'coherence' is not defined

Считается, что когерентность хорошо соотносится с человеческими оценками интерпретируемости тем. Поэтому на больших текстовых коллекциях когерентность обычно повышается, если убрать фоновую лексику. Однако в нашем случае этого не произошло.

Изучение влияния гиперпараметра alpha

В этом разделе мы будем работать со второй моделью, то есть той, которая построена по сокращенному корпусу.

Пока что мы посмотрели только на матрицу темы-слова, теперь давайте посмотрим на матрицу темы-документы. Выведите темы для нулевого (или любого другого) документа из корпуса, воспользовавшись методом get_document_topics второй модели:


In [28]:
print(lda2.get_document_topics(new_corpus[2]))


[(8, 0.11190603090029384), (9, 0.30280255182012816), (25, 0.11941289292746549), (29, 0.10250000002233003), (34, 0.27587852432978166)]

Также выведите содержимое переменной .alpha второй модели:


In [29]:
print(lda2.alpha)


[ 0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025
  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025
  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025
  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025  0.025]

У вас должно получиться, что документ характеризуется небольшим числом тем. Попробуем поменять гиперпараметр alpha, задающий априорное распределение Дирихле для распределений тем в документах.

Задание 4. Обучите третью модель: используйте сокращенный корпус (corpus2 и dictionary2) и установите параметр alpha=1, passes=5. Не забудьте про фиксацию seed! Выведите темы новой модели для нулевого документа; должно получиться, что распределение над множеством тем практически равномерное. Чтобы убедиться в том, что во второй модели документы описываются гораздо более разреженными распределениями, чем в третьей, посчитайте суммарное количество элементов, превосходящих 0.01, в матрицах темы-документы обеих моделей. Другими словами, запросите темы модели для каждого документа с параметром minimum_probability=0.01 и просуммируйте число элементов в получаемых массивах. Передайте две суммы (сначала для модели с alpha по умолчанию, затем для модели в alpha=1) в функцию save_answers4.


In [30]:
np.random.seed(76543)
lda3 = LdaModel(corpus=new_corpus, id2word=dictionary2, alpha=1, num_topics=40, passes=5)

In [31]:
print(lda3.get_document_topics(new_corpus[0]))


[(0, 0.049222639807988522), (1, 0.021411957364250226), (2, 0.021510683232129294), (3, 0.021477919699259957), (4, 0.021329030925219348), (5, 0.022383298549744989), (6, 0.021533358234605872), (7, 0.021370125755751618), (8, 0.022026440223727115), (9, 0.021294590638625457), (10, 0.021315618800681342), (11, 0.021508183960369274), (12, 0.021276595744680847), (13, 0.02127659664581763), (14, 0.021329910635610155), (15, 0.06462184141183161), (16, 0.021280788116641806), (17, 0.021460292726044581), (18, 0.042331183185875788), (19, 0.021294054489917297), (20, 0.022666791703334938), (21, 0.021482728711562381), (22, 0.021302182020845255), (23, 0.021302994966119732), (24, 0.022248493189795871), (25, 0.021904724770591431), (26, 0.021432880992007197), (27, 0.021445835844897402), (28, 0.023633740777977544), (29, 0.021276595744680847), (30, 0.021382503332463235), (31, 0.021276611643730153), (32, 0.021276595744680847), (33, 0.06644800350029037), (34, 0.02129567914881067), (35, 0.02131419837481318), (36, 0.022779343537754019), (37, 0.021375025653311314), (38, 0.021276595744680847), (39, 0.021623364448879894)]

In [32]:
sum2 = 0
sum3 = 0
for text in new_corpus:
    sum2 += len(lda2.get_document_topics(text, minimum_probability=0.01))
    sum3 += len(lda3.get_document_topics(text, minimum_probability=0.01))

In [33]:
def save_answers4(count_model2, count_model3):
    with open("cooking_LDA_pa_task4.txt", "w") as fout:
        fout.write(" ".join([str(el) for el in [count_model2, count_model3]]))

In [34]:
save_answers4(sum2, sum3)

Таким образом, гиперпараметр alpha влияет на разреженность распределений тем в документах. Аналогично гиперпараметр eta влияет на разреженность распределений слов в темах.

LDA как способ понижения размерности

Иногда, распределения над темами, найденные с помощью LDA, добавляют в матрицу объекты-признаки как дополнительные, семантические, признаки, и это может улучшить качество решения задачи. Для простоты давайте просто обучим классификатор рецептов на кухни на признаках, полученных из LDA, и измерим точность (accuracy).

Задание 5. Используйте модель, построенную по сокращенной выборке с alpha по умолчанию (вторую модель). Составьте матрицу $\Theta = p(t|d)$ вероятностей тем в документах; вы можете использовать тот же метод get_document_topics, а также вектор правильных ответов y (в том же порядке, в котором рецепты идут в переменной recipes). Создайте объект RandomForestClassifier со 100 деревьями, с помощью функции cross_val_score вычислите среднюю accuracy по трем фолдам (перемешивать данные не нужно) и передайте в функцию save_answers5.


In [35]:
from sklearn.ensemble import RandomForestClassifier
from sklearn.cross_validation import cross_val_score

In [36]:
X = np.zeros((len(recipes), lda2.num_topics))
for doc_num in range(len(new_corpus)):
    for topic_num, topic_proba in lda2.get_document_topics(new_corpus[doc_num]):
        X[doc_num][topic_num] = topic_proba

In [37]:
y = np.array([recipe['cuisine'] for recipe in recipes])
print(len(y))


39774

In [38]:
rfc = RandomForestClassifier(n_estimators=100)
rfc.fit(X, y)
cv_score = cross_val_score(rfc, X, y, cv=3).mean()
print(cv_score)


0.543069390185

In [39]:
def save_answers5(accuracy):
     with open("cooking_LDA_pa_task5.txt", "w") as fout:
        fout.write(str(accuracy))

In [40]:
save_answers5(cv_score)

Для такого большого количества классов это неплохая точность. Вы можете попроовать обучать RandomForest на исходной матрице частот слов, имеющей значительно большую размерность, и увидеть, что accuracy увеличивается на 10–15%. Таким образом, LDA собрал не всю, но достаточно большую часть информации из выборки, в матрице низкого ранга.

LDA — вероятностная модель

Матричное разложение, использующееся в LDA, интерпретируется как следующий процесс генерации документов.

Для документа $d$ длины $n_d$:

  1. Из априорного распределения Дирихле с параметром alpha сгенерировать распределение над множеством тем: $\theta_d \sim Dirichlet(\alpha)$
  2. Для каждого слова $w = 1, \dots, n_d$:
    1. Сгенерировать тему из дискретного распределения $t \sim \theta_{d}$
    2. Сгенерировать слово из дискретного распределения $w \sim \phi_{t}$.

Подробнее об этом в Википедии.

В контексте нашей задачи получается, что, используя данный генеративный процесс, можно создавать новые рецепты. Вы можете передать в функцию модель и число ингредиентов и сгенерировать рецепт :)


In [124]:
def generate_recipe(model, num_ingredients):
    theta = np.random.dirichlet(model.alpha)
    for i in range(num_ingredients):
        t = np.random.choice(np.arange(model.num_topics), p=theta)
        topic = model.show_topic(t, topn=model.num_terms)
        topic_distr = [x[1] for x in topic]
        terms = [x[0] for x in topic]
        w = np.random.choice(terms, p=topic_distr)
        print(w)

In [125]:
generate_recipe(lda2, 5)


beer
coarse salt
low sodium vegetable broth
sunflower oil
red potato

Интерпретация построенной модели

Вы можете рассмотреть топы ингредиентов каждой темы. Большиснтво тем сами по себе похожи на рецепты; в некоторых собираются продукты одного вида, например, свежие фрукты или разные виды сыра.

Попробуем эмпирически соотнести наши темы с национальными кухнями (cuisine). Построим матрицу $A$ размера темы $x$ кухни, ее элементы $a_{tc}$ — суммы $p(t|d)$ по всем документам $d$, которые отнесены к кухне $c$. Нормируем матрицу на частоты рецептов по разным кухням, чтобы избежать дисбаланса между кухнями. Следующая функция получает на вход объект модели, объект корпуса и исходные данные и возвращает нормированную матрицу $A$. Ее удобно визуализировать с помощью seaborn.


In [41]:
import pandas
import seaborn
from matplotlib import pyplot as plt
%matplotlib inline

In [42]:
def compute_topic_cuisine_matrix(model, corpus, recipes):
    # составляем вектор целевых признаков
    targets = list(set([recipe["cuisine"] for recipe in recipes]))
    # составляем матрицу
    tc_matrix = pandas.DataFrame(data=np.zeros((model.num_topics, len(targets))), columns=targets)
    for recipe, bow in zip(recipes, corpus):
        recipe_topic = model.get_document_topics(bow)
        for t, prob in recipe_topic:
            tc_matrix[recipe["cuisine"]][t] += prob
    # нормируем матрицу
    target_sums = pandas.DataFrame(data=np.zeros((1, len(targets))), columns=targets)
    for recipe in recipes:
        target_sums[recipe["cuisine"]] += 1
    return pandas.DataFrame(tc_matrix.values/target_sums.values, columns=tc_matrix.columns)

In [43]:
def plot_matrix(tc_matrix):
    plt.figure(figsize=(10, 10))
    seaborn.heatmap(tc_matrix, square=True)

In [44]:
plot_matrix(compute_topic_cuisine_matrix(lda2, new_corpus, recipes))


/usr/lib/python3.5/site-packages/matplotlib/font_manager.py:1297: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))

Чем темнее квадрат в матрице, тем больше связь этой темы с данной кухней. Мы видим, что у нас есть темы, которые связаны с несколькими кухнями. Такие темы показывают набор ингредиентов, которые популярны в кухнях нескольких народов, то есть указывают на схожесть кухонь этих народов. Некоторые темы распределены по всем кухням равномерно, они показывают наборы продуктов, которые часто используются в кулинарии всех стран.

Жаль, что в датасете нет названий рецептов, иначе темы было бы проще интерпретировать...

Заключение

В этом задании вы построили несколько моделей LDA, посмотрели, на что влияют гиперпараметры модели и как можно использовать построенную модель.