Как я научился получать удовольствие от pet-проектов


Скрин последнего pet-проекта

Термин pet-проект каждый трактует для себя по-своему, сам я его объясняю следующим образом: разработка, отличная от работы.

Классификаций pet-проектов тоже предостаточно. Я определил для себя следующие:

  • краткосрочные/долгосрочные
  • коммерческие/некоммерческие

Думаю, комментарии тут излишне, помимо одного — под краткосрочными я понимаю те проекты, которые занимают 1-2 вечера или же выходные, но не более.

Понятно, что две эти классификации можно и нужно между собой комбинировать: краткосрочные & коммерческие, долгосрочные & некоммерческие и т.д.

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

Но были конечно и долгосрочные проекты (об одном из них я уже писал пост) и вот с ними то у меня большие проблемы, а именно с мотивацией. Помимо того, что вы до конца не уверены, что проект окупится(если речь конечно идет про коммерцию), так и сам проект превращается в рутинную вторую работу: все те же таски, бэклог, приоритеты и т.д. Не знаю, как на других, но на меня это очень сильно давит. Хоть я лично и встречал людей, которые делают свои pet-проекты в одиночку по 6 лет, свои долгосрочные проекты я либо сразу забрасывал, либо даже не начинал делать, зная чем это закончится. Исключением из правил для меня являются проекты, в кооперативе с кем-то: так и интереснее и процесс быстрее идет, да и ответственность как никак появляется не только перед собой.

Проблему поставили: как начать и не забросить разработку долгосрочного некоммерческого pet-проекта в одиночку?

В моем случае, мне помогли 2 вещи, которые мне посоветовали 2 товарища:

  1. книга «Вы, конечно, шутите, мистер Фейнман!»
  2. спонтанное планирование

Если вкратце, рекомендованная книга – эта автобиография физика-ядерщика, рассказывающая о том как подходить к решению бытовых проблем аналитически, используя науку (внезапно, выяснилось, что данную книгу рекомендуют преподаватели на многих технических специальностях и что она много у кого на слуху). На меня же наибольшее впечатление произвела глава «Семипроцентная поправка», после прочтения которой сразу же появилось желание, что либо сделать.

Спонтанное планирование, как и pet-проект, тоже каждый определяет для себя по-разному, для себя я охарактеризовал это следующим образом: «делай то, что нравится». Т.е. при таком подходе я сохранил бэклог, но избавился от приоритезации задач: настроение сегодня реализовать расширение для редактора, а не пилить основную игровую механику — пожалуйста, нет сил напрягать мозги — можно заняться подготовкой иконок к релизу под различные экраны, бессонница — иди разбираться, как накатить новейший Xcode на MacBook 8-летней давности, а заодно и почистить его и т.д.

Понятно, что я не открыл Америку и такой подход вряд ли можно заюзать на работе (хотя я где-то слышал, что Valve так когда-то делали), но в рамках долгосрочного одиночного некоммерческого pet-проекта — почему бы и нет?

Мне эти 2 кейса сильно помогли: я зарелизил продукт, который в одиночку делал 3 месяца. Да, не слишком долго, но начало положено и останавливаться пока не собираюсь.

Надеюсь, моя история будет кому-нибудь полезна, поможет и замотивирует на создание собственного pet-проекта.

Делитесь своими историями и методами которые помогли именно вам сдвинутся с мертвой точки.

ссылка на оригинал статьи https://habr.com/ru/post/530678/

А есть ли интеллект и прогресс? или по мотивам «Будущего здесь нет или что останавливает прогресс»

«Разумный гонится не за тем, что приятно, а за тем, что избавляет от неприятностей»
Аристотель

Чтобы найти ответы на вопросы из заголовка, попробуем разобраться что такое прогресс и как он связан с разумом. Кто-то считает, что прогресс ускоряется, но есть и те, кто считает, что прогресс замедляется.

Как измерить прогресс?

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

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


Вообще, статьи о прогрессе обычно изобилуют перечислениями великих достижений, которые должны вдохновлять на ещё большие достижения. Сразу встречается и другая крайность, утверждается, что прогресс настолько стремителен, что его необходимо ограничивать искусственно. Однако нечасто можно встретить и описание обратной стороны этой ярко блестящей медали.

Попробуем рассмотреть отдельные составляющие как признаки прогресса и понять, как говорится, а есть ли мальчик?

Итак, первая составляющая — социальная. Придётся рассмотреть несколько аспектов и сразу же можно наткнуться на препятствия.

Первый аспект касается организации власти. Будет опрометчиво утверждать, что в настоящий момент найден удачный способ осуществления политической власти. Даже нельзя сказать что лучше демократия, единовластие, тоталитаризм или какое-нибудь сочетание существующих типов управления. Что-то подсказывает, что эти способы далеки от идеала, кроме того все они известны практически столько, сколько существует человечество. Может быть, это всё устарело и пора придумать что-то новое в условиях глобализации? Но, к сожалению, среди основных государств, включающих в себя подавляющее большинство населения планеты, вряд ли можно найти такое, которое пытается реализовать, или хотя бы предложить что-то такое, что было бы шагом вперёд. И здесь все пристально и вопросительно уставились на Китай, и ждут. Как говорится, время покажет, созрело ли человечество на этот раз. Что же получается в плане власти, куда движемся мы по ступенькам прогресса, вверх или вниз? Пока создаётся ощущение, что вообще ступеньки отсутствуют, тысячелетия проходят а воз и ныне там.

Следующим аспектом считается социальное равенство в экономическом плане. Если посмотреть на степень разрыва между доходами самых богатых и самых бедных, то и здесь трудно утверждать, что наблюдается движение к лучшему, скорее наоборот. А если попробовать заглянуть в будущее? Существуют ли возможности реализовать социализм? Можно ли сказать, что капитализм это идеал, к которому стоило стремиться на протяжении всей истории человечества? Есть ли продвижение вперёд за последние 100 или 200 лет? И опять — вряд ли.

Однако с точки зрения третьего аспекта — качества жизни — достижение в социальном плане, всё-таки, есть. Непрерывный рост населения и средней продолжительности жизни человека красноречиво свидетельствует о медленном, но всё-таки продвижении вперёд (по данным ВОЗ средняя продолжительность жизни на земле составляет более 60 лет, а когда-то в древности люди кое-как дотягивали до 30-40, как утверждают старожилы). Пока нельзя сказать, что человечество победило старость, но жить оно в среднем действительно стало дольше. Много это или мало можно понять, глянув на порог выхода на пенсию. И снова попробуем устремить взгляд чуть дальше носа. Собирается ли человечество побеждать старость? Нет, не болезни, а именно старение, «запрограммированный» износ организма? Что-то не видно сообщений о том, как учёным были выделены крупные суммы на изыскания в этой области, может быть, кто-то поправит? Всё это были аспекты социальной составляющей прогресса, как видим если и есть какая-то ступенька вверх, то она очень небольшая, пока особенно гордиться нечем.

Вторая составляющая прогресса — материальная, то есть производство и удовлетворение потребностей. И здесь, наверняка большинство согласится, без сомнений, человечество достигло небывалых объёмов производства любой продукции, будь это продукты питания, различная техника, медикаменты и проч., практически всё, что угодно и всё это великолепие можно получить с небольшими затратами. Казалось бы, вот они плоды прогресса, живи да радуйся. Но если взглянуть на доступность этих благ, то возникают большие сомнения в том, что потребности каждого человека сейчас могут быть удовлетворены более-менее одинаково. Всё же современное экономическое устройство далеко от идеала. И здесь опять пристально все смотрят в сторону Китая, а вдруг мы когда-то что-то упустили? А там, в Китае, похоже, есть успехи, недавно они заявили, что победили бедность. Получается, что в материальном плане на данный момент из всего человечества есть продвижение вперёд только в Китае.

Третья составляющая — духовная — касается нравственности, религии и толерантности. Говорить о развитии в таких деликатных вопросах сложно. Можно ли утверждать, что нет угнетения человека человеком? Можно ли считать развитием ограничение на право рождения детей в том же Китае. Более того, существует такое «прекрасное» выражение «золотой миллиард», это что, мечта человечества такая, всех и каждого? Да, ведьм уже не сжигают на кострах, но смертная казнь всё-таки есть. Последнюю ведьму казнили около двухсот лет назад, и с тех пор разного рода гадалки даже зарабатывают на своём «ремесле». Неужели и это шаг вперёд? И не смотря на наличие социальных наук, вряд ли кто-то скажет нужны здесь изменения или нет и в какую сторону. Одним словом, если за последние сотни лет и есть какое-то движение вперёд в плане духовности, то увидеть его достаточно сложно.

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

Действительно, наука помогает получать прибыль, но в этом ли заключается основное назначение науки? Разумеется не в этом.

Вот ещё немного неудобных примеров.

  1. Уделяет ли наука достаточно внимания гармонии жизни людей друг с другом, например, внутри одного государства или же между государствами? Ответ скорее всего отрицательный. Веками люди пытаются ужиться друг с другом, самыми серьёзными достижениями к настоящему времени можно назвать лишь появление нескольких социологический теорий, точное количество которых даже трудно определить. Существующие, по большей части философские, объяснительные теории успешно конкурируют друг с другом, а некоторые исследователи даже утверждают, что единой теории вообще нет, поэтому говорить о том, что просматривается или хотя бы угадывается путь построения гармоничного общества не приходится. Что касается конфликтов между людьми, то их количество не особенно пытаются сокращать, и даже наоборот, конфликты планируют и реализуют для того, чтобы извлекать выгоду. Есть ли в этом что-то прогрессивное?
  2. Уделяет ли наука достаточно внимания экологии? — вряд ли. Если от чего-то и надо охранять природу, то именно от своей же деятельности. А всё потому, что изготавливать продукцию так, чтобы она быстро не превращалась в мусор невыгодно. Свалки мы стали гордо называть полигонами. Кроме этого существует проблема накопления углекислого газа в атмосфере. Его доля составляет всего лишь какие-то сотые доли процента. Но что бы мы ни делали, количество СО2 неуклонно растёт, а вместе с ним растёт, а может быть нагнетается, страх, вот вам и возможности тераформирования. «Вот если бы был Марс, тогда-то мы бы ого-го!» — говорят некоторые. Жаль только, что на земле всё «тераформирование», на которое способен человек сейчас, исчерпывается увеличением количества и размеров «полигонов» и прочих могильников.
  3. Уделяет ли наука достаточно внимания доступности и качеству образования? Постепенно популярной становится идея, согласно которой нет нужды в большом количестве хорошо образованных людей. Если когда-то пытались ликвидировать безграмотность, то сейчас уже можно говорить о ликвидации грамотности, в подтверждение этим словам даже есть открытые заявления видных политиков о том, что общее образование, не требуется, видите ли, люди превращаются в непокорных вольнодумцев. А из остатков образования, как из процесса, опять же хотят извлечь лишь выгоду. И судя по всему, даже общее образование скоро станет платным и не всем доступным, как в старые добрые времена существования царей. Неужели прогресс и должен быть таким?
  4. Уделяет ли наука достаточно внимания доступности и качеству здравоохранения, ведь это именно то, чего хотелось бы каждому? И опять — нет. Тут можно вспомнить об условности бесплатной медицины или ценообразовании медикаментов. Да, технологии совершенствуются, объёмы производства растут, но цены по отношению к зарплате, почему-то не падают, медицина доступнее не становится. А как обстоит дело с тем, чтобы начать побеждать вирусы? О победе над болезнями и старостью говорить не приходится. Кто знает, сколько бы ещё всего мог сделать какой-нибудь великий учёный, если бы не болезни и старость? В конце концов, решив эти проблемы и проблему продуктов питания можно лететь сколь угодно долго к какой-нибудь другой звёздной системе, о том, зачем это надо — ниже. Никто не заинтересован в долгой и счастливой жизни, так как это невыгодно. Некоторые известные политики утверждают, что на земле случилось перенаселение. И какой мы должны сделать вывод, что здравоохранение вообще не нужно, потому что людей якобы слишком много?
    Это тоже такой шаг вперёд?

    И, наконец.

  5. Уделяется ли достаточно внимания самой себе, фундаментальной науке? И пятый раз — нет. В настоящее время наука не нужна никому, потому что убыточна по своей природе. Кому захочется тратить дорогие денежки просто на то, чтобы появилось какое-то знание, которое в карман не положить, и которое непонятно как применить или хотя бы как продать. А попытки получить выгоду сразу почему-то в науку превращаться упорно не хотят. Кроме того, есть мнение, что количество значимых научных достижений в единицу времени сейчас снизилось примерно до уровня начала 17 века.

Ещё кое-что о науке. При всех видимых и значимых успехах науки, тем не менее, далеко не всё об окружающем мире нам известно. Например, не до конца известна и понятна причина массового вымирания практически всего живого на планете. Такое случалось неоднократно. И вообще говоря, происходило это не по вине человека, ведь тогда его просто не было. И сейчас отдельные виды живых существ исчезают, и человек неплохо прикладывает к этому делу свои руки. Но факт остаётся фактом: виды живых существ исчезали и исчезают на планете, это естественный процесс, он может быть медленным, а может быть очень быстрым. И если уж идти до конца в этом вопросе, то можно сделать весьма грустный вывод, что исчезновение человека как вида это лишь вопрос времени до тех пор, пока человек не предпримет какие-то меры, чтобы этого не произошло. Хотелось бы обратить на это внимание отдельно.

В один «прекрасный» момент может внезапно понадобиться решать очень (много раз слово «очень») сложную задачу. Решать эту задачу придётся сразу всему человечеству, не какой-то одной стране, не какому-то одному учёному и, возможно, придётся делать это за очень короткий промежуток времени. Да и вообще, времени на решение задачи может вовсе не оказаться. За примером далеко ходить не надо. Последние события довольно красноречиво показали готовность системы здравоохранения (и не только её, и не только в какой-то отдельной стране) к такой проблеме как очередной явно не самый смертельный вирус. Говорить о какой-нибудь по-настоящему серьёзной угрозе и вовсе не приходится, всё, что останется сделать в этом случае это просто обернуться простынёй и тихонько ползти в сторону кладбища, и совершенно неважно откуда эта угроза появится, прилетит с метеоритом, или люди сами её создадут. Только давайте не будем который раз говорить о серьёзности происходящего в настоящий момент, дабы не отвлекаться от сути. Сценариев конца всего известно довольно много, даже отдельный пост был посвящён этому, вроде бы.

А суть вопроса такова: готовы ли мы не исчезнуть бесследно вместе с большинством исчезнувших видов на земле? По всей видимости, ответ будет отрицательным. А это означает, что наш отрыв от остальных видов на планете пока минимален и с точки зрения миллионолетней эволюции мимолётен во времени. И ступень развития, на которую мы поднялись на данный момент может оказаться не такой уж и высокой, потому что особенно гордиться пока нечем. Как бы нам не хотелось раздуть щёки пошире, одна вспышка на солнце может сдуть всю атмосферу, а то и всю планету и уже нельзя будет сказать, что в солнечной системе появилась разумная жизнь. Кто должен или может заплатить за решение этого вопроса и кому, и что немаловажно, может ли кто-то этот вопрос решить?

Выгода, выгода, кругом выгода, казалось бы, при чём здесь капитализм? И вот в сухом остатке, пожалуй, самым заметным продвижением вперёд с точки зрения прогресса можно назвать только зарождение науки у человечества как явление само по себе и совершенствование с её помощью мотыги в комбайн. А все неудобные вопросы трудно назвать прогрессом.

А как же интеллект?

И вот здесь хочется поговорить об интеллекте. Нет, к сожалению, не о модном искусственном, а о немодном естественном интеллекте, ведь в этих условиях он должен проявиться в полную силу. Так вот, чтобы исчезновения человека как вида не произошло, необходимо чтобы интеллект как-то проявил себя. И что мы видим с точки зрения хотя бы самого заметного научного прогресса? А там интеллект преследует лишь выгоду, а это есть «поесть-подоминировать-поразмножаться», то есть больше похоже не на интеллект, а на обычные животные потребности и рефлексы. То есть торжества разумного начала, к сожалению, пока не видно. Главные атрибуты разума — образование и наука — на настоящий момент невыгодны и не являются приоритетом. Скорее это удел небольшого количества энтузиастов. Да, мы повернули реки вспять, но, уж простите за аналогию и бобёр умел строить плотины ещё до человека. Можно ли утверждать, что на планете земля появился разум, если он в своих действиях ничем здравым и разумным пока себя не выдаёт? Собственно, в этом и заключается ответ на вопрос куда подевалось наше будущее. В его основу не закладывается ничего разумного.

Что в итоге?

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

Наверняка многие будут говорить, что образование уже доступно, мол, кладезь знаний — интернет — доступен любому. Безусловно, интернет это замечательно, он позволяет распространять знания. И действительно, слово «образование» от слова знать. Но вот что интересно, а много ли есть таких людей, которые без интернета знают какие растения съедобны в незнакомой местности, а какие нет? А много ли таких, кто знает как правильно вырастить много съедобных растений? Много ли таких, которые могут создать какой-нибудь механизм, облегчающий жизнь? Есть ли такие, которые могут вообще добыть хоть какой-нибудь металл, найти, отличить и добыть механически, химически? А много ли таких, кто знает всё это сразу?
Надо ли говорить, что знать это всего лишь половина дела? Чтобы образование было полным кроме «знать» необходимо ещё и «уметь», это, кстати, тоже ещё Аристотель говорил. Много ли таких, кто знает и умеет всё это сразу? Как видим, всё указывает на то, что знаниями и умениями не обладает каждый, а обладает только всё человечество сообща.

А что, если интеллект находится вне человека, как у каких-нибудь насекомых? Ведь на самом деле знания хранятся не в головах у отдельных индивидуумов, а вне их, то есть в книгах, или в том же модном интернете. Получается, что память интеллекта хранится вне любого из нас. Мы можем только почерпнуть оттуда знания на время и попользоваться. Это во-первых. А во-вторых, как на счёт того, чтобы создать что-нибудь новое? Что-либо создать люди могут тоже лишь сообща. Ни один человек сейчас не в состоянии создать что-то новое в одиночку. Это означает, что и способность создавать, видимо, тоже принадлежит не каждому из нас, а только всем вместе.

И что же делать?

А остаётся лишь надеяться, что интеллект, если он и правда есть и если он не спит, то принадлежит человеческому виду и без него существовать не сможет. И чтобы можно было утверждать, что на планете земля появился разум и он развивается, необходимо, чтобы этот разум хотя бы научился держаться «на плаву». Как сказал Джордж Карлин в одном из своих монологов — планете земля вряд ли что-то угрожает, она переживала и не такое, и людей переживёт, а вот человечеству — что-то угрожает однозначно, и вероятнее всего, оно само себя уничтожит (это если перевести на цензурный русский). Необходимо, чтобы интеллект, разум, здравый смысл, наконец, пробудился, иначе собственные усилия людей или катаклизм планетарного масштаба (не говоря уже о космическом стихийном бедствии) просто напросто приведут к исчезновению этой короткой по космическим меркам вспышки разума.

ссылка на оригинал статьи https://habr.com/ru/post/530680/

Участвуем в соревновании по Data Science. Первый опыт

Привет, Хабр!

Давно я не писал никаких статей и, вот думаю, пришло время написать о там, как мне пригодились знания по data science, полученные по ходу обучения небезывестной специализации от Яндекса и МФТИ «Машинное обучение и анализ данных». Правда, справедливости ради надо отметить, что знания до конца не получены — спецуха не завершена 🙂 Однако, решать простенькие реальные бизнесовые задачи уже можно. Или нужно? На этот вопрос будет ответ, буквально через пару абзацев.

Итак, сегодня в этой статье я расскажу уважаемому читателю о своем первом опыте участия в открытом соревновании. Хотелось бы сразу отметить, что моей целью соревнования было не получение каких-либо призовых мест. Единственное желание было попробовать свои силы в реальном мире 🙂 Да, в добавок так вышло, что тематика соревнования практически никак не пересекалась с материалом из пройденных курсов. Это добавило некоторые сложности, но с этим соревнование стало еще интереснее и ценнее опыт вынесенный оттуда.

По сложившейся традиции, обозначу кому может быть интересна статья. Во-первых, если Вы уже прошли первые два курса указанной выше специализации, и хотите попробовать свои силы на практических задачах, но стесняетесь и переживаете, что может не получиться и Вас засмеют и т.д. После прочтения статьи, такие опасения, надеюсь, развеятся. Во-вторых, возможно, Вы решаете схожую задачу и совсем не знаете с чего зайти. А здесь готовенький простенький, как говорят настоящие датасайнтисты, бэйзлайн 🙂

Здесь следовало бы уже изложить план исследования, но мы немного отвлечемся и попробуем ответить на вопрос из первого абзаца — нужно ли новичку в датасайнсе пробовать свои силы в подобных соревнованиях. Мнения на этот счет расходятся. Лично мое мнение — нужно! Объясню почему. Причин много, все перечислять не буду, укажу наиболее важные. Во-первых, подобные соревнования помогают закрепить теоретические знания на практике. Во-вторых, на моей практике, почти всегда, опыт, полученный в условиях приближенных к боевым, очень сильно мотивирует на дальнейшие подвиги. В-третьих, и это самое главное — во время соревнований у Вас появляется возможность пообщаться с другими участниками в специальных чатах, можно даже не общаться, можно просто почитать, о чем пишут люди и это а) частенько наводит на интересные мысли о том, какие еще изменения провести в исследовании и б) придает уверенность в подтверждении своих собственных идей, особенно, если они высказываются в чате. К этим плюсам нужно подходить с определенной предусмотрительностью, чтобы не возникло ощущения всезнания…

Теперь немного о том, как я решился на участие. О соревновании я узнал буквально за несколько дней до его начала. Первая мысль «ну если бы я знал о соревновании месяц назад, то подготовился бы, по изучал бы какие-нибудь дополнительные материалы, которые могли бы пригодиться для проведения исследования, а так, без подготовки могу не уложиться в сроки…», вторая мысль «собственно, что может не получиться, если целью является не приз, а участие, тем более, что участники в 95% случаях говорят на русском языке, плюс есть специальные чаты для обсуждения, будут какие-то вебинары от организаторов. В конце концов, можно будет вживую увидеть настоящих датасайнтистов всех мастей и размеров…». Как вы догадались, вторая мысль победила, и не зря — буквально несколько дней плотной работы и я получил ценнейший опыт пусть и простенькой, но вполне себе бизнесовой задачи. Поэтому, если Вы на пути покорения вершин науки о данных и видите намечающееся соревнование, да на родном языке, с поддержкой в чатах и, у Вас есть свободное время — не задумывайтесь надолго — пробуйте и да прибудет с Вами сила! На мажорной ноте мы переходим к задаче и плану исследования.

Сопоставление названий

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

Задача

При поиске новых клиентов СИБУРу приходится обрабатывать информацию о миллионах новых компаний из различных источников. Названия компаний при этом могут иметь разное написание, содержать сокращения или ошибки, быть аффилированными с компаниями, уже известными СИБУРу.

Для более эффективной обработки информации о потенциальных клиентах, СИБУРу необходимо знать, связаны ли два названия (т.е. принадлежат одной компании или аффилированным компаниям).

В этом случае СИБУР сможет использовать уже известную информацию о самой компании или об аффилированных компаниях, не дублировать обращения в компанию или не тратить время на нерелевантные компании или дочерние компании конкурентов.

Тренировочная выборка содержит пары названий из разных источников (в том числе, пользовательских) и разметку.

Разметка получена частично вручную, частично — алгоритмически. Кроме того, разметка может содержать ошибки. Вам предстоит построить бинарную модель, предсказывающую, являются ли два названия связанными. Метрика, используемая в данной задаче — F1.

В этой задаче можно и даже нужно пользоваться открытыми источниками данных для обогащения датасета или поиска дополнительной важной для определения аффилированных компаний информации.

Дополнительная информация о задаче

Раскрой меня для получения дополнительной информации

Аффилированными компаниями считаются компании, принадлежащие одному холдингу или группе компаний. Например, все компании из списка: Сибур Нефтехим, ООО Сибур, Sibur Digital, СИБУР ИТ, Sibur international GMBH являются вариациями названий аффилированных компаний, а компания “Сибирь International GMBH” не является.
Названия компаний могут писаться на разных языках: тренировочная и тестовая выборки содержат названия компаний на русском, английском и китайском языках.
В названиях могут присутствовать сокращения, опечатки и дополнительная информация о компании, например, названия стран и провинций.
Публичная (50%) и приватная (50%) части тестового множества не пересекаются.

Правила использования внешних источников

Безвозмездность Источник должен быть бесплатен для всех. Например, нельзя пользоваться данными, к которым у вас есть корпоративный доступ.

Верифицируемость У организаторов должна быть возможность воспроизвести ваш способ сбора данных за 1 день для выборки в 1 000 000 уникальных компаний.
На практике количество проверяемых компаний намного больше данных в рамках соревнования (миллионы компаний). К тому же, одним и тем же способом сбора данных могут пользоваться сразу несколько участников и в случае строгих лимитов мы не сможем верифицировать решение.

Публичность Источник должен быть заявлен в чате до 24:00 6 декабря 2020 с хэштегом #внешниеданные и одобрен организаторами.

Добросовестность Способ, который вы используете при работе с источником, и происхождение данных не должны нарушать законы РФ и правила, которые установлены оператором источника.
Если, например, автоматический парсинг какого-либо сайта запрещен владельцами сайта, то вы можете пользоваться им только вручную.

Источник должен допускать коммерческое использование.

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

Один участник может заявить не более 10 источников информации.

Использование API поисковых систем, к сожалению, противоречит пункту 2.

Правила относительно строгих замен, ручной разметки и данных, собранных вручную, в т.ч. с использованием crowdsource

Все “ручные” данные должны быть собраны участниками команды без использования crowdsource платформ и аналогичных методов. Вряд ли мы сможем это проверить, но давайте играть честно:)

Замены общего характера можно использовать без ограничений, если при необходимости вы можете объяснить их происхождение.

Это касается legel entities, стран, городов и т.д. Например, исключение слова Industries из всех названий допустима.

Замена значимых элементов названия компании возможна только на основании внешних данных. Ручная замена не разрешается.

Нельзя использовать строгие правила сравнения названий, использующие значимые элементы. Например, нельзя проверять вхождение подстроки “Сибур” в каждый элемент пары и на основании этого вычислять целевую переменную.

Все данные, использованные при решении задачи, должны опираться только на обучающую выборку и данные, полученные из разрешенных внешних источников. Использовать данные, полученные при анализе тестовой выборки, нельзя.

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

Использование open source

Вы можете пользоваться любыми open source инструментами, выпущенными под разрешительными лицензиями. Если инструмент явным образом включает в себя словари замены или аналогичные данные — о нем нужно сообщить в чате соревнования или в чате задачи в соответствии с правилами для внешних источников. В противном случае сообщать о таком инструменте не нужно.

Если Вы сомневаетесь в том, можно ли использовать какой-то конкретный источник – просто спросите в чате. Возможно, нам придется в будущем расширить этот список, если будет найден какой-то очевидно нечестный по отношении к другим участникам способ, который, тем не менее, соответствует этим правилам.

Данные

train.csv — тренировочное множество

test.csv — тестовое множество

sample_submission.csv — пример решения в правильном формате

Naming baseline.ipynb — код базовое решение

baseline_submission.csv — базовое решение

Обратите внимание, организаторы конкурса позаботились о подрастающем поколении и выложили базовое решение задачи, которое дает качество по f1 около 0.1. Я первый раз участвую в соревнованиях и первый раз такое вижу 🙂

Итак, ознакомившись с самой задачей и требованиями по ее решению, перейдем к плану решения.

План решения задачи

Настройка технических инструментов

Загрузим библиотеки
Напишем вспомогательные функции

Предобработка данных

Загрузим данные
Посмотрим на данные и сделаем копии
Переведем все символы из текста в нижний регистр
Удалим названия стран
Удалим знаки и спецсимволы
Удалим цифры
Удалим… первый список стоп-слов. Вручную!
Проведем транслитерацию русского текста в латиницу
Запустим автоматическое составление списка топ 50 самых часто встречающихся слов & Drop it smart. Первый ЧИТ

Генерация и анализ фич

Посчитаем дистанцию Левенштейна
Посчитаем нормированную дистанцию Левенштейна
Визуализируем фичи
Сопоставим слова в тексте для каждой пары и сгенерим большую кучу признаков
Сопоставим слова из текста со словами из названий топ 50 холдинговых брендов нефтехимической, строительной отраслей. Получим вторую большую кучу признаков. Второй ЧИТ
Готовим данные для подачи в модель

Настройка и обучение модели

Итоги соревнования

Источники информации

Теперь, когда мы ознакомились с планом проведения исследования, перейдем к его реализации.

Настройка технических инструментов

Загрузка библиотек

Собственно здесь все просто, для начала установим недостающие библиотеки

Установим библиотеку для определения списка стран и последующего их удаления из текста

pip install pycountry

Установим библиотеку для определения дистанции Левенштейна между словами из текста друг сдругом и со словами из различных списков

pip install strsimpy

Установим библиотеку, с помощью которой проведем транслитерацию русского текста в латиницу

pip install cyrtranslit

Подтянем библиотеки

import pandas as pd import numpy as np  import warnings warnings.filterwarnings('ignore')  import pycountry import re  from tqdm import tqdm tqdm.pandas()  from strsimpy.levenshtein import Levenshtein from strsimpy.normalized_levenshtein import NormalizedLevenshtein  import matplotlib.pyplot as plt from matplotlib.pyplot import figure  import seaborn as sns sns.set() sns.set_style("whitegrid")  from sklearn.model_selection import train_test_split from sklearn.model_selection import StratifiedKFold from sklearn.model_selection import StratifiedShuffleSplit  from scipy.sparse import csr_matrix  import lightgbm as lgb from sklearn.linear_model import LogisticRegression  from sklearn.metrics import accuracy_score from sklearn.metrics import recall_score from sklearn.metrics import precision_score from sklearn.metrics import roc_auc_score  from sklearn.metrics import classification_report, f1_score   # import googletrans # from googletrans import Translator import cyrtranslit

Напишем вспомогательные функции

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

Утверждать, что качество кода в функциях отлиное не буду. Местами его точно следует оптимизировать, но в целях быстрого исследования, достаточно будет только точности расчетов.

Итак, первая функция переводит текст в нижний регистр

Код

# convert text to lowercase def lower_str(data,column):     data[column] = data[column].str.lower()

Следующие четыре функции помогают визуализировать пространство исследуемых признаков и их способность разделять объекты по целевым меткам — 0 или 1.

Код

# statistic table for analyse float values (it needs to make histogramms and boxplots) def data_statistics(data,analyse,title_print):      data0 = data[data['target']==0][analyse]     data1 = data[data['target']==1][analyse]      data_describe = pd.DataFrame()     data_describe['target_0'] = data0.describe()     data_describe['target_1'] = data1.describe()     data_describe = data_describe.T          if title_print == 'yes':         print ('\033[1m' + 'Дополнительные статистики по признаку',analyse,'\033[m')      elif title_print == 'no':         None          return data_describe  # histogramms for float values def hist_fz(data,data_describe,analyse,size):     print ()     print ('\033[1m' + 'Information about',analyse,'\033[m')     print ()          data_0 = data[data['target'] == 0][analyse]     data_1 = data[data['target'] == 1][analyse]          min_data = data_describe['min'].min()     max_data = data_describe['max'].max()          data0_mean = data_describe.loc['target_0']['mean']     data0_median = data_describe.loc['target_0']['50%']     data0_min = data_describe.loc['target_0']['min']     data0_max = data_describe.loc['target_0']['max']     data0_count = data_describe.loc['target_0']['count']               data1_mean = data_describe.loc['target_1']['mean']     data1_median = data_describe.loc['target_1']['50%']      data1_min = data_describe.loc['target_1']['min']     data1_max = data_describe.loc['target_1']['max']     data1_count = data_describe.loc['target_1']['count']               print ('\033[4m' + 'Analyse'+ '\033[m','No duplicates')          figure(figsize=size)     sns.distplot(data_0,color='darkgreen',kde = False)          plt.scatter(data0_mean,0,s=200,marker='o',c='dimgray',label='Mean')     plt.scatter(data0_median,0,s=250,marker='|',c='black',label='Median')     plt.legend(scatterpoints=1,                loc='upper right',                ncol=3,                fontsize=16)     plt.xlim(min_data, max_data)     plt.show()     print ('Quantity:', data0_count,            '         Min:', round(data0_min,2),            '         Max:', round(data0_max,2),            '         Mean:', round(data0_mean,2),            '         Median:', round(data0_median,2))          print ()     print ('\033[4m' + 'Analyse'+ '\033[m','Duplicates')          figure(figsize=size)     sns.distplot(data_1,color='darkred',kde = False)     plt.scatter(data1_mean,0,s=200,marker='o',c='dimgray',label='Mean')     plt.scatter(data1_median,0,s=250,marker='|',c='black',label='Median')     plt.legend(scatterpoints=1,                loc='upper right',                ncol=3,                fontsize=16)     plt.xlim(min_data, max_data)     plt.show()     print ('Quantity:', data_1.count(),            '         Min:', round(data1_min,2),            '         Max:', round(data1_max,2),            '         Mean:', round(data1_mean,2),            '         Median:', round(data1_median,2))  # draw boxplot def boxplot(data,analyse,size):     print ('\033[4m' + 'Analyse'+ '\033[m','All pairs')          data_0 = data[data['target'] == 0][analyse]     data_1 = data[data['target'] == 1][analyse]          figure(figsize=size)     sns.boxplot(x=analyse,y='target',data=data,orient='h',                 showmeans=True,                                 meanprops={"marker":"o",                            "markerfacecolor":"dimgray",                             "markeredgecolor":"black",                           "markersize":"14"},                palette=['palegreen', 'salmon'])     plt.ylabel('target', size=14)     plt.xlabel(analyse, size=14)     plt.show()  # draw graph for analyse two choosing features for predict traget label def two_features(data,analyse1,analyse2,size):     fig = plt.subplots(figsize=size)          x0 = data[data['target']==0][analyse1]     y0 = data[data['target']==0][analyse2]     x1 = data[data['target']==1][analyse1]     y1 = data[data['target']==1][analyse2]          plt.scatter(x0,y0,c='green',marker='.')     plt.scatter(x1,y1,c='black',marker='+')     plt.xlabel(analyse1)     plt.ylabel(analyse2)     title = [analyse1,analyse2]     plt.title(title)     plt.show()

Пятая функция предназначена для формирования таблицы угадываний и ошибок алгоритма, более известной как таблица сопряжения.

Иными словами, после формирования вектора прогнозов, нам потребуется сопоставить прогноз с целевыми метками. Результатом такого сопоставления должна получиться таблица сопряжения для каждой пары компаний из обучающей выборки. В таблице сопряжения для каждой пары будет определен результат соответствия прогноза к классу из обучающей выборки. Классификация соответствия принята такой: ‘True positive’, ‘False positive’, ‘True negative’ или ‘False negative’. Эти данные очень важны для анализа работы алгоритма и принятия решений по доработке модели и признакового пространства.

Код

def contingency_table(X,features,probability_level,tridx,cvidx,model):     tr_predict_proba = model.predict_proba(X.iloc[tridx][features].values)     cv_predict_proba = model.predict_proba(X.iloc[cvidx][features].values)      tr_predict_target = (tr_predict_proba[:, 1] > probability_level).astype(np.int)     cv_predict_target = (cv_predict_proba[:, 1] > probability_level).astype(np.int)      X_tr = X.iloc[tridx]     X_cv = X.iloc[cvidx]      X_tr['predict_proba'] = tr_predict_proba[:,1]     X_cv['predict_proba'] = cv_predict_proba[:,1]      X_tr['predict_target'] = tr_predict_target     X_cv['predict_target'] = cv_predict_target      # make true positive column     data = pd.DataFrame(X_tr[X_tr['target']==1][X_tr['predict_target']==1]['pair_id'])     data['True_Positive'] = 1     X_tr = X_tr.merge(data,on='pair_id',how='left')      data = pd.DataFrame(X_cv[X_cv['target']==1][X_cv['predict_target']==1]['pair_id'])     data['True_Positive'] = 1     X_cv = X_cv.merge(data,on='pair_id',how='left')      # make false positive column     data = pd.DataFrame(X_tr[X_tr['target']==0][X_tr['predict_target']==1]['pair_id'])     data['False_Positive'] = 1     X_tr = X_tr.merge(data,on='pair_id',how='left')      data = pd.DataFrame(X_cv[X_cv['target']==0][X_cv['predict_target']==1]['pair_id'])     data['False_Positive'] = 1     X_cv = X_cv.merge(data,on='pair_id',how='left')      # make true negative column     data = pd.DataFrame(X_tr[X_tr['target']==0][X_tr['predict_target']==0]['pair_id'])     data['True_Negative'] = 1     X_tr = X_tr.merge(data,on='pair_id',how='left')      data = pd.DataFrame(X_cv[X_cv['target']==0][X_cv['predict_target']==0]['pair_id'])     data['True_Negative'] = 1     X_cv = X_cv.merge(data,on='pair_id',how='left')      # make false negative column     data = pd.DataFrame(X_tr[X_tr['target']==1][X_tr['predict_target']==0]['pair_id'])     data['False_Negative'] = 1     X_tr = X_tr.merge(data,on='pair_id',how='left')      data = pd.DataFrame(X_cv[X_cv['target']==1][X_cv['predict_target']==0]['pair_id'])     data['False_Negative'] = 1     X_cv = X_cv.merge(data,on='pair_id',how='left')          return X_tr,X_cv

Шестая функция предназначена для формирования матрицы сопряжения. Не путайте с таблицей сопряжения. Хотя одно следует из другого. Вы сами все увидете дальше

Код

def matrix_confusion(X):      list_matrix = ['True_Positive','False_Positive','True_Negative','False_Negative']      tr_pos = X[list_matrix].sum().loc['True_Positive']     f_pos = X[list_matrix].sum().loc['False_Positive']     tr_neg = X[list_matrix].sum().loc['True_Negative']     f_neg = X[list_matrix].sum().loc['False_Negative']     matrix_confusion = pd.DataFrame()     matrix_confusion['0_algorythm'] = np.array([tr_neg,f_neg]).T     matrix_confusion['1_algorythm'] = np.array([f_pos,tr_pos]).T     matrix_confusion = matrix_confusion.rename(index={0: '0_target', 1: '1_target'})          return matrix_confusion

Седьмая функция предназначена для визуализации отчета о работе алгоритма, который включает в себя матрицу сопряжения, значения метрик precision, recall, f1

Код

def report_score(tr_matrix_confusion,                  cv_matrix_confusion,                  data,tridx,cvidx,                  X_tr,X_cv):     # print some imporatant information     print ('\033[1m'+'Matrix confusion on train data'+'\033[m')     display(tr_matrix_confusion)     print ()     print(classification_report(data.iloc[tridx]["target"].values, X_tr['predict_target']))     print ('******************************************************')     print ()     print ()     print ('\033[1m'+'Matrix confusion on test(cv) data'+'\033[m')     display(cv_matrix_confusion)     print ()     print(classification_report(data.iloc[cvidx]["target"].values, X_cv['predict_target']))     print ('******************************************************')

С помощью восьмой и девятой функции проведем анализ на полезность признаков для используемой модели из Light GBM с точки зрения значения коэффициента ‘Information gain’ для каждого исследуемого признака

Код

def table_gain_coef(model,features,start,stop):          data_gain = pd.DataFrame()     data_gain['Features'] = features     data_gain['Gain'] = model.booster_.feature_importance(importance_type='gain')     return data_gain.sort_values('Gain', ascending=False)[start:stop]  def gain_hist(df,size,start,stop):     fig, ax = plt.subplots(figsize=(size))     x = (df.sort_values('Gain', ascending=False)['Features'][start:stop])     y = (df.sort_values('Gain', ascending=False)['Gain'][start:stop])     plt.bar(x,y)     plt.xlabel('Features')     plt.ylabel('Gain')     plt.xticks(rotation=90)     plt.show()

Десятая функция нужна для формирования массива количества совпадающих слов для каждой пары компаний.

Эту функцию также можно использовать для формирования массива НЕ совпадающих слов.

Код

def compair_metrics(data):     duplicate_count = []     duplicate_sum = []     for i in range(len(data)):         count=len(data[i])         duplicate_count.append(count)         if count <= 0:             duplicate_sum.append(0)         elif count > 0:             temp_sum = 0             for j in range(len(data[i])):                 temp_sum +=len(data[i][j])             duplicate_sum.append(temp_sum)      return duplicate_count,duplicate_sum    

Одинадцатая функция проводит транслитерацию русского текста в латиницу

Код

def transliterate(data):     text_transliterate = []     for i in range(data.shape[0]):         temp_list = list(data[i:i+1])         temp_str = ''.join(temp_list)         result = cyrtranslit.to_latin(temp_str,'ru')         text_transliterate.append(result) Двенадцатая функция нужна для переименования столбцов таблицы после агрегирования данных.   Дело в том, что после агрегации данных, названия столбцов, как бы распадаются на два уровня. В итоге, для приведения таблицы к принятому в исследовании формату, используем самописную функцию <spoiler title="Код"> <source lang="python">def rename_agg_columns(id_client,data,rename):     columns = [id_client]     for lev_0 in data.columns.levels[0]:         if lev_0 != id_client:             for lev_1 in data.columns.levels[1][:-1]:                 columns.append(rename % (lev_0, lev_1))     data.columns = columns     return data

return text_transliterate

Тринадцатая и четырнадцатая функции нужны для просмотра и формирования таблицы дистанции Левенштейна и других важных показателей.

Что это вообще за таблица, какие в ней метрики и как она формируется? Давайте рассмотрим пошагово формирование таблицы:
— Шаг 1. Определим какие данные нам будут нужны. ID пары, финишная обработка текста — оба столбца, список названий холдингов (топ 50 компаний нефтехимической и строительной индустрии).
— Шаг 2. В столбце 1 в каждой паре от каждого слова замерим дистанцию Левенштейна до каждого слова из списка названий холдингов, а также длину каждого слова и отношение дистанции к длине.
— Шаг 3. В случае, если значение отношения окажется меньше или равно 0.4, то от сравниваемого слова из списка названий топ холдингов определим дистанцию до каждого слова из второго столбца соответствующей id пары, а также длину каждого из слов и отношение дистанции к длине.
— Шаг 4. В случае, если в очередной раз отношение оказывается меньше или равно 0.4, то все собранные метрики фиксируются.
— Шаг 5. По завершению алгоритма будет сформирована таблица, в которой первый столбец ID пары, а последующие столбцы — метрики. Данные в таблице необходимо агрегировать по id пары (так как могут быть случаи сильного соответствия слов из одной id пары двум названиям холдингов). При агрегировании данных выбираем минимальные значения.
— Шаг 6. Склеиваем полученную таблицу с таблицей исследования.

Важная особенность: расчет занимает продолжительное время из-за написанного на скорую руку кода

Код

def dist_name_to_top_list_view(data,column1,column2,list_top_companies):     id_pair = []     r1 = []     r2 = []     words1 = []     words2 = []     top_words = []      for n in range(0, data.shape[0], 1):         for line1 in data[column1][n:n+1]:             line1 = line1.split()             for word1 in line1:                 if len(word1) >=3:                     for top_word in list_top_companies:                         dist1 = levenshtein.distance(word1, top_word)                         ratio = max(dist1/float(len(top_word)),dist1/float(len(word1)))                         if ratio <= 0.4:                             ratio1 = ratio                             break                     if ratio <= 0.4:                         for line2 in data[column2][n:n+1]:                             line2 = line2.split()                             for word2 in line2:                                 dist2 = levenshtein.distance(word2, top_word)                                 ratio = max(dist2/float(len(top_word)),dist2/float(len(word2)))                                 if ratio <= 0.4:                                     ratio2 = ratio                                     id_pair.append(int(data['pair_id'][n:n+1].values))                                     r1.append(ratio1)                                     r2.append(ratio2)                                     break      df = pd.DataFrame()     df['pair_id'] = id_pair     df['levenstein_dist_w1_top_w'] = dist1     df['levenstein_dist_w2_top_w'] = dist2     df['length_w1_top_w'] = len(word1)     df['length_w2_top_w'] = len(word2)     df['length_top_w'] = len(top_word)     df['ratio_dist_w1_to_top_w'] = r1     df['ratio_dist_w2_to_top_w'] = r2     feature = df.groupby(['pair_id']).agg([min]).reset_index()     feature = rename_agg_columns(id_client='pair_id',data=feature,rename='%s_%s')      data = data.merge(feature,on='pair_id',how='left')     display(data)     print ('Words:', word1,word2,top_word)     print ('Levenstein distance:',dist1,dist2)     print ('Length of word:',len(word1),len(word2),len(top_word))     print ('Ratio (distance/length word):',ratio1,ratio2)  def dist_name_to_top_list_make(data,column1,column2,list_top_companies):     id_pair = []     r1 = []     r2 = []     dist_w1 = []     dist_w2 = []     length_w1 = []     length_w2 = []     length_top_w = []      for n in range(0, data.shape[0], 1):         for line1 in data[column1][n:n+1]:             line1 = line1.split()             for word1 in line1:                 if len(word1) >=3:                     for top_word in list_top_companies:                         dist1 = levenshtein.distance(word1, top_word)                         ratio = max(dist1/float(len(top_word)),dist1/float(len(word1)))                         if ratio <= 0.4:                             ratio1 = ratio                             break                     if ratio <= 0.4:                         for line2 in data[column2][n:n+1]:                             line2 = line2.split()                             for word2 in line2:                                 dist2 = levenshtein.distance(word2, top_word)                                 ratio = max(dist2/float(len(top_word)),dist2/float(len(word2)))                                 if ratio <= 0.4:                                     ratio2 = ratio                                     id_pair.append(int(data['pair_id'][n:n+1].values))                                     r1.append(ratio1)                                     r2.append(ratio2)                                     dist_w1.append(dist1)                                     dist_w2.append(dist2)                                     length_w1.append(float(len(word1)))                                     length_w2.append(float(len(word2)))                                     length_top_w.append(float(len(top_word)))                                     break      df = pd.DataFrame()     df['pair_id'] = id_pair     df['levenstein_dist_w1_top_w'] = dist_w1     df['levenstein_dist_w2_top_w'] = dist_w2     df['length_w1_top_w'] = length_w1     df['length_w2_top_w'] = length_w2     df['length_top_w'] = length_top_w     df['ratio_dist_w1_to_top_w'] = r1     df['ratio_dist_w2_to_top_w'] = r2     feature = df.groupby(['pair_id']).agg([min]).reset_index()     feature = rename_agg_columns(id_client='pair_id',data=feature,rename='%s_%s')      data = data.merge(feature,on='pair_id',how='left')     return data

Предобработка данных

Из моего небольшого опыта именно предобработка данных в широком смысле этого выражения занимает большее время. Пойдем по порядку.

Загрузим данные

Здесь все очень просто. Загрузим данные и заменим название столбца с целевой меткой «is_duplicate» на «target». Это делается для удобства использования функций — некоторые из них были написаны в рамках более ранних исследований и они используют название столбца с целевой меткой как «target».

Код

 # DOWNLOAD DATA text_train = pd.read_csv('train.csv') text_test = pd.read_csv('test.csv')  # RENAME DATA text_train = text_train.rename(columns={"is_duplicate": "target"})

Посмотрим на данные

Данные загрузили. Давайте посмотрим сколько всего объектов и насколько они сбалансированны.

Код

# ANALYSE BALANCE OF DATA target_1 = text_train[text_train['target']==1]['target'].count() target_0 = text_train[text_train['target']==0]['target'].count()  print ('There are', text_train.shape[0], 'objects') print ('There are', target_1, 'objects with target 1') print ('There are', target_0, 'objects with target 0') print ('Balance is', round(100*target_1/target_0,2),'%')

Таблица №1 «Баланс меток»

Объектов не мало — почти 500 тысяч и они вообще никак не сбалансированы. То есть из почти 500 тысяч объектов, всего менее 4 тысяч — имеют целевую метку 1 (менее 1%)

Давайте посмотрим на саму таблицу. Посмотрим на первые пять объектов с разметкой 0 и первые пять объектов с разметкой 1.

Код

display(text_train[text_train['target']==0].head(5))  display(text_train[text_train['target']==1].head(5))

Таблица №2 «Первые 5 объектов класса 0», таблица №3 «Первые 5 объектов класса 1»

Сразу напрашиваются некоторые простые шаги: привести текст к одному регистру, убрать всякие стоп-слова, типа ‘ltd’, удалить страны и заодно названия географических объектов.

Собственно, примерно так в этой задаче может проходить решение — делаешь какую-нибудь предобработку, убеждаешься в том, что она работает как надо, запускаешь модель, смотришь качество и анализируешь выборочно объекты, на которых модель ошибается. Именно так я и проводил исследование. Но в самой статье дано итоговое решение и качество работы алгоритма после каждой предобработки не разбирается, в конце статьи мы проведем итоговый разбор. Иначе статья была бы неописуемых размеров 🙂

Сделаем копии

Если честно, то не знаю зачем я это делаю, но почему-то всегда это делаю. Сделаю и в этот раз

Код

baseline_train = text_train.copy() baseline_test = text_test.copy()

Переведем все символы из текста в нижний регистр

Код

# convert text to lowercase columns = ['name_1','name_2'] for column in columns:     lower_str(baseline_train,column) for column in columns:     lower_str(baseline_test,column)

Удалим названия стран

Надо отметить, что организаторы конкурса — большие молодцы! Вместе с заданием они дали ноутбук с очень простым baseline, в котором был предоставлен, в том числе и нижеприведенный код.

Код

# drop any names of countries countries = [country.name.lower() for country in pycountry.countries] for country in tqdm(countries):     baseline_train.replace(re.compile(country), "", inplace=True)     baseline_test.replace(re.compile(country), "", inplace=True)

Удалим знаки и спецсимволы

Код

# drop punctuation marks baseline_train.replace(re.compile(r"\s+\(.*\)"), "", inplace=True) baseline_test.replace(re.compile(r"\s+\(.*\)"), "", inplace=True)  baseline_train.replace(re.compile(r"[^\w\s]"), "", inplace=True) baseline_test.replace(re.compile(r"[^\w\s]"), "", inplace=True)

Удалим цифры

Удаление цифр из текста прямо в лоб, в первой попытке сильно испортило качество модели. Код я здесь приведу, но по факту он не использовался.

Также обратите внимание, что до этого момента мы проводили преобразование прямо в столбцах, которые нам были даны. Давайте теперь будем создавать новые столбцы для каждой предобработки. Столбцов получится больше, зато если где-то на каком-то этапе предобработки произойдет сбой — ничего страшного, делать все с самого начала не нужно, ведь у нас будут столбы с каждого этапа предобработки.

Код, который испортил качество. Нужно деликатнее быть

# # first: make dictionary of frequency every word # list_words = baseline_train['name_1'].to_string(index=False).split() +\ #                 baseline_train['name_2'].to_string(index=False).split() # freq_words = {} # for w in list_words: #     freq_words[w] = freq_words.get(w, 0) + 1      # # second: make data frame of frequency words # df_freq = pd.DataFrame.from_dict(freq_words,orient='index').reset_index() # df_freq.columns = ['word','frequency'] # df_freq_agg = df_freq.groupby(['word']).agg([sum]).reset_index() # df_freq_agg = rename_agg_columns(id_client='word',data=df_freq_agg,rename='%s_%s') # df_freq_agg = df_freq_agg.sort_values(by=['frequency_sum'], ascending=False)  # # third: make drop list of digits # string = df_freq_agg['word'].to_string(index=False) # digits = [int(digit) for digit in string.split() if digit.isdigit()] # digits = set(digits) # digits = list(digits)  # # drop the digits # baseline_train['name_1_no_digits'] =\ #     baseline_train['name_1'].apply( #     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)])) # baseline_train['name_2_no_digits'] =\ #     baseline_train['name_2'].apply( #     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)]))  # baseline_test['name_1_no_digits'] =\ #     baseline_test['name_1'].apply( #     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)])) # baseline_test['name_2_no_digits'] =\ #     baseline_test['name_2'].apply( #     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)]))

Удалим… первый список стоп-слов. Вручную!

Теперь предлагается определить и удалить стоп-слова из списка слов в названиях компаний.

Список мы составили на основании ручного просмотра обучающей выборки. По логике, такой список нужно составлять автоматически, используя следующие подходы:
— во-первых, использовать топ 10 (20,50,100) часто встречающихся слов.
— во-вторых, использовать стандартные библиотеки стоп-слов на различных языках. Например, обозначения организационно-правовых форм организаций на различных языках (ООО, ПАО, ЗАО, ltd, gmbh, inc и др.)
— в-третьих, имеет смысл составить список географических названий на различных языках

К первому варианту автоматического составления списка топ часто встречающихся слов мы еще вернемся, а пока смотрим на ручную предобработку.

Код

# drop some stop-words drop_list = ["ltd.", "co.", "inc.", "b.v.", "s.c.r.l.", "gmbh", "pvt.",                            'retail','usa','asia','ceska republika','limited','tradig','llc','group',              'international','plc','retail','tire','mills','chemical','korea','brasil',              'holding','vietnam','tyre','venezuela','polska','americas','industrial','taiwan',              'europe','america','north','czech republic','retailers','retails',                          'mexicana','corporation','corp','ltd','co','toronto','nederland','shanghai','gmb','pacific',             'industries','industrias',                          'inc', 'ltda', 'ооо', 'ООО', 'зао', 'ЗАО', 'оао', 'ОАО', 'пао', 'ПАО', 'ceska republika', 'ltda',              'sibur', 'enterprises', 'electronics', 'products', 'distribution', 'logistics', 'development',             'technologies', 'pvt', 'technologies', 'comercio', 'industria', 'trading', 'internacionais',              'bank', 'sports',                          'express','east', 'west', 'south', 'north', 'factory', 'transportes', 'trade', 'banco',             'management', 'engineering', 'investments', 'enterprise', 'city', 'national', 'express', 'tech',              'auto', 'transporte', 'technology', 'and', 'central', 'american',                          'logistica','global','exportacao', 'ceska republika', 'vancouver', 'deutschland',                          'sro','rus','chemicals','private','distributors','tyres','industry','services','italia','beijing',                          'рус','company','the','und']  baseline_train['name_1_non_stop_words'] =\     baseline_train['name_1'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)])) baseline_train['name_2_non_stop_words'] =\     baseline_train['name_2'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)]))  baseline_test['name_1_non_stop_words'] =\     baseline_test['name_1'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)])) baseline_test['name_2_non_stop_words'] =\     baseline_test['name_2'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)]))

Давайте выборочно проверим, что наши стоп слова были действительно удалены из текста

Код

baseline_train[baseline_train.name_1_non_stop_words.str.contains("factory")].head(3)

Таблица №4 «Выборочная проверка работы кода по удалению стоп-слов»

Вроде все работает. Удалены все стоп-слова, которые отделены пробелом. То, что мы и хотели. Двигаемся дальше.

Проведем транслитерацию русского текста в латиницу

Я использую для этого свою самописную функцию и библиотеку cyrtranslit. Вроде работает. Проверял вручную.

Код

# transliteration to latin baseline_train['name_1_transliterated'] = transliterate(baseline_train['name_1_non_stop_words']) baseline_train['name_2_transliterated'] = transliterate(baseline_train['name_2_non_stop_words']) baseline_test['name_1_transliterated'] = transliterate(baseline_test['name_1_non_stop_words']) baseline_test['name_2_transliterated'] = transliterate(baseline_test['name_2_non_stop_words'])

Давайте посмотрим на пару с id 353150. В ней второй столбец («name_2») имеет слово «мишлен», после предобработки слово уже пишется так «mishlen» (см. столбец «name_2_transliterated»). Не совсем правильно, но явно лучше.

Код

pair_id = 353150 baseline_train[baseline_train['pair_id']==353150]

Таблица №5 «Выборочная проверка кода по транслитерации»

Запустим автоматическое составление списка топ 50 самых часто встречающихся слов & Drop it smart. Первый ЧИТ

Немного мудреный заголовок. Давайте по порядку разберем, что мы тут будем делать.

Во-первых, мы объединим текст из первого и второго столбца в один массив и посчитаем для каждого уникального слова, количество раз, которое оно встречалось.

Во-вторых, выберем топ 50 таких слов. И казалось бы можно их удалить, но нет. В этих словах могут быть названия холдингов (‘total’, ‘knauf’, ‘shell’,…), а это очень важная информация и ее нельзя потерять, так как далее мы будем ее использовать. Поэтому мы пойдем на читерский (запрещенный) прием. Для начала, на основании внимательного, выборочного изучения обучающей выборки, составим список названий часто встречающихся холдингов. Список будет не полный, иначе это было бы совсем не честно 🙂 Хотя, так как мы не гонимся за призовым местом, то почему бы и нет. Затем мы сравним массив топ 50 часто встречающихся слов со списком названий холдингов и выкинем из списка слова, которые совпадают с названиями холдингов.

Теперь второй список стоп-слов готов. Можно удалять слова из текста.

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

Код

list_top_companies = ['arlanxeo', 'basf', 'bayer', 'bdp', 'bosch', 'brenntag', 'contitech',                       'daewoo', 'dow', 'dupont', 'evonik', 'exxon', 'exxonmobil', 'freudenberg',                       'goodyear', 'goter', 'henkel', 'hp', 'hyundai', 'isover', 'itochu', 'kia', 'knauf',                       'kraton', 'kumho', 'lusocopla', 'michelin', 'paul bauder', 'pirelli', 'ravago',                       'rehau', 'reliance', 'sabic', 'sanyo', 'shell', 'sherwinwilliams', 'sojitz',                       'soprema', 'steico', 'strabag', 'sumitomo', 'synthomer', 'synthos',                       'total', 'trelleborg', 'trinseo', 'yokohama']  # drop top 50 common words (NAME 1 & NAME 2) exept names of top companies  # first: make dictionary of frequency every word list_words = baseline_train['name_1_transliterated'].to_string(index=False).split() +\                 baseline_train['name_2_transliterated'].to_string(index=False).split() freq_words = {} for w in list_words:     freq_words[w] = freq_words.get(w, 0) + 1      # # second: make data frame df_freq = pd.DataFrame.from_dict(freq_words,orient='index').reset_index() df_freq.columns = ['word','frequency'] df_freq_agg = df_freq.groupby(['word']).agg([sum]).reset_index() df_freq_agg = rename_agg_columns(id_client='word',data=df_freq_agg,rename='%s_%s') df_freq_agg = df_freq_agg.sort_values(by=['frequency_sum'], ascending=False) drop_list = list(set(df_freq_agg[0:50]['word'].to_string(index=False).split()) - set(list_top_companies))  # # check list of top 50 common words # print (drop_list)   # drop the top 50 words baseline_train['name_1_finish'] =\     baseline_train['name_1_transliterated'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)])) baseline_train['name_2_finish'] =\     baseline_train['name_2_transliterated'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)]))  baseline_test['name_1_finish'] =\     baseline_test['name_1_transliterated'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)])) baseline_test['name_2_finish'] =\     baseline_test['name_2_transliterated'].apply(     lambda x: ' '.join([word for word in x.split() if word not in (drop_list)])) 

На этом мы закончили с предобработкой данных. Начнем генерировать новые фичи и визуально их оценивать на способность разделять объекты на 0 или 1.

Генерация и анализ фич

Посчитаем дистанцию Левенштейна

Воспользуемся библиотекой strsimpy и в каждой паре (после всех предобработок) посчитаем дистанцию Левенштейна от названия компании из первого столбца до названия компании во втором столбце.

Код

# create feature with LEVENSTAIN DISTANCE levenshtein = Levenshtein() column_1 = 'name_1_finish' column_2 = 'name_2_finish'  baseline_train["levenstein"] = baseline_train.progress_apply(     lambda r: levenshtein.distance(r[column_1], r[column_2]), axis=1) baseline_test["levenstein"] = baseline_test.progress_apply(     lambda r: levenshtein.distance(r[column_1], r[column_2]), axis=1)

Посчитаем нормализованную дистанцию Левенштейна

Все тоже самое, что и выше, только считать мы будем нормированную дистанцию.

Заголовок спойлера

# create feature with NORMALIZATION LEVENSTAIN DISTANCE normalized_levenshtein = NormalizedLevenshtein() column_1 = 'name_1_finish' column_2 = 'name_2_finish'  baseline_train["norm_levenstein"] = baseline_train.progress_apply(     lambda r: normalized_levenshtein.distance(r[column_1], r[column_2]),axis=1) baseline_test["norm_levenstein"] = baseline_test.progress_apply(     lambda r: normalized_levenshtein.distance(r[column_1], r[column_2]),axis=1)

Посчитали, а теперь визуализируем

Визуализируем фичи

Посмотрим на распределение признака ‘levenstein’

Код

data = baseline_train analyse = 'levenstein' size = (12,2) dd = data_statistics(data,analyse,title_print='no') hist_fz(data,dd,analyse,size) boxplot(data,analyse,size)

Графики №1 «Гистограмма и ящик с усами для оценки значимости признака»

На первый взгляд, метрика может размечать данные. Очевидно не очень хорошо, но использовать ее можно.

Посмотрим на распределение признака ‘norm_levenstein’

Заголовок спойлера

data = baseline_train analyse = 'norm_levenstein' size = (14,2) dd = data_statistics(data,analyse,title_print='no') hist_fz(data,dd,analyse,size) boxplot(data,analyse,size)

Графики №2 «Гистограмма и ящик с усами для оценки значимости признака»

Уже лучше. А теперь, давайте посмотрим на то, как две вместе взятые фичи будут разделять пространство на объекты 0 и 1.

Код

data = baseline_train analyse1 = 'levenstein' analyse2 = 'norm_levenstein' size = (14,6) two_features(data,analyse1,analyse2,size)

График №3 «Диаграмма рассеяния»

Очень даже неплохая разметка получается. Значит не зря мы столько предобрабатывали данные 🙂
Всем же понятно, что по горизонтали — значения метрики «levenstein», а по вертикали — значения метрики «norm_levenstein», а зелененькие и черненькие точки это объекты 0 и 1. Двигаемся дальше.

Сопоставим слова в тексте для каждой пары и сгенерим большую кучу признаков

Ниже мы проведем сравнение слов в названиях компаний. Создадим следующие признаки:
— список слов, которые дублируются в столбцах №1 и №2 каждой пары
— список слов, которые НЕ дублируются

На основании этих списков слов, создадим признаки, которые мы подадим в обучаемую модель:
— количество дублирующихся слов
— количество НЕ дублирующихся слов
— сумма символов, дублирующихся слов
— сумма символов, НЕ дублирующихся слов
— средняя длина дублирующихся слов
— средняя длина НЕ дублирующихся слов
— отношение количества дубликатов к количеству НЕ дубликатов

Код здесь, наверное, не очень дружелюбный, так как опять-таки, написан был на скорую руку. Но он работает, а для быстрого исследования пойдет.

Код

# make some information about duplicates and differences for TRAIN column_1 = 'name_1_finish' column_2 = 'name_2_finish'  duplicates = [] difference = []  for i in range(baseline_train.shape[0]):     list1 = list(baseline_train[i:i+1][column_1])     str1 = ''.join(list1).split()     list2 = list(baseline_train[i:i+1][column_2])     str2 = ''.join(list2).split()          duplicates.append(list(set(str1) & set(str2)))     difference.append(list(set(str1).symmetric_difference(set(str2))))      # continue make information about duplicates duplicate_count,duplicate_sum = compair_metrics(duplicates) dif_count,dif_sum = compair_metrics(difference)  # create features have information about duplicates and differences for TRAIN baseline_train['duplicate'] = duplicates baseline_train['difference'] = difference  baseline_train['duplicate_count'] = duplicate_count baseline_train['duplicate_sum'] = duplicate_sum baseline_train['duplicate_mean'] = baseline_train['duplicate_sum'] / baseline_train['duplicate_count'] baseline_train['duplicate_mean'] = baseline_train['duplicate_mean'].fillna(0)  baseline_train['dif_count'] = dif_count baseline_train['dif_sum'] = dif_sum baseline_train['dif_mean'] = baseline_train['dif_sum'] / baseline_train['dif_count'] baseline_train['dif_mean'] = baseline_train['dif_mean'].fillna(0)  baseline_train['ratio_duplicate/dif_count'] = baseline_train['duplicate_count'] / baseline_train['dif_count']  # make some information about duplicates and differences for TEST column_1 = 'name_1_finish' column_2 = 'name_2_finish'  duplicates = [] difference = []  for i in range(baseline_test.shape[0]):     list1 = list(baseline_test[i:i+1][column_1])     str1 = ''.join(list1).split()     list2 = list(baseline_test[i:i+1][column_2])     str2 = ''.join(list2).split()          duplicates.append(list(set(str1) & set(str2)))     difference.append(list(set(str1).symmetric_difference(set(str2))))      # continue make information about duplicates duplicate_count,duplicate_sum = compair_metrics(duplicates) dif_count,dif_sum = compair_metrics(difference)  # create features have information about duplicates and differences for TEST baseline_test['duplicate'] = duplicates baseline_test['difference'] = difference  baseline_test['duplicate_count'] = duplicate_count baseline_test['duplicate_sum'] = duplicate_sum baseline_test['duplicate_mean'] = baseline_test['duplicate_sum'] / baseline_test['duplicate_count'] baseline_test['duplicate_mean'] = baseline_test['duplicate_mean'].fillna(0)  baseline_test['dif_count'] = dif_count baseline_test['dif_sum'] = dif_sum baseline_test['dif_mean'] = baseline_test['dif_sum'] / baseline_test['dif_count'] baseline_test['dif_mean'] = baseline_test['dif_mean'].fillna(0)  baseline_test['ratio_duplicate/dif_count'] = baseline_test['duplicate_count'] / baseline_test['dif_count'] 

Визуализируем некоторые признаки.

Код

data = baseline_train analyse = 'dif_sum' size = (14,2) dd = data_statistics(data,analyse,title_print='no') hist_fz(data,dd,analyse,size) boxplot(data,analyse,size)

Графики №4 «Гистограмма и ящик с усами для оценки значимости признака»

Код

data = baseline_train analyse1 = 'duplicate_mean' analyse2 = 'dif_mean' size = (14,6) two_features(data,analyse1,analyse2,size)

График №5 «Диаграмма рассеяния»

Какая никакая, а разметка. Обратим внимание на то, что очень много компаний с целевой меткой 1 имеют ноль дублей в тексте и также очень много компаний, имеющих дубли в названиях в среднем более 12 слов относятся к компаниям с целевой меткой 0.

Давайте взглянем на табличные данные, подготовим запрос по первому случаю: дублей в названии компаний ноль, а компании одинаковые.

Код

baseline_train[     baseline_train['duplicate_mean']==0][     baseline_train['target']==1].drop(         ['duplicate', 'difference',         'name_1_non_stop_words',         'name_2_non_stop_words', 'name_1_transliterated',         'name_2_transliterated'],axis=1)


Очевидно, есть системная ошибка в нашей обработке. Мы не учли, что слова могут писаться не только с ошибками, но и просто слитно или наоборот раздельно там, где этого не требуется. Например, пара №9764. В первом столбце ‘bitmat’ во втором ‘bit mat’ и вот уже это не дубль, а компания та одинаковая. Или другой пример, пара №482600 ‘bridgestoneshenyang’ и ‘bridgestone’.

Что можно было бы сделать. Первое, что мне пришло в голову — сопоставлять не напрямую в лоб, а с помощью метрики Левенштейна. Но и здесь нас подстерегает засада: расстояние между ‘bridgestoneshenyang’ и ‘bridgestone’ будет не маленьким. Возможно на помощь придет лемматизация, но опять-таки сходу не ясно как можно лемматизировать названия компаний. Или можно использовать коэффициент Тамимото, но оставим этот момент для более опытных товарищей и двигаемся дальше.

Сопоставим слова из текста со словами из названий топ 50 холдинговых брендов нефтехимической, строительной и других отраслей. Получим вторую большую кучу признаков. Второй ЧИТ

На самом деле здесь целых два нарушения правил участия соревнования:

— во-первых, мы сопоставим прямо в лоб, выявленные раннее дубликаты слов из каждой пары на соответствие названий холдингов и получим столбец «duplicate_name_company»
— во-вторых, мы проведем более хитрое сопоставление. Будем сверять данные не напрямую, а через дистанцию Левенштейна.

Оба приема запрещены правилами соревнований. Обойти запрет можно. Для этого нужно составить список названий холдингов не вручную на основании выборочного просмотра обучающей выборки, а автоматически — из внешних источников. Но тогда, во-первых, список холдингов получится большим и предложенное в работе сопоставление слов займет очень, ну просто очень много времени, а во-вторых, этот список еще нужно составить 🙂 Поэтому для целей простоты исследования проведем проверку насколько улучшиться качество модели с этими признаками. Забегу вперед — качество растет просто потрясающе!

С первым способом вроде все должно быть понятно, а вот ко второму подходу требуются пояснения.

Итак, определим дистанцию Левенштейна от каждого слова в каждой строчке первого столбца с названием компании до каждого слова из списка топ нефтехимических компаний (и не только).

В случае, если отношение дистанции Левенштейна к длине слова менее или равно 0.4, то мы определяем отношение дистанции Левенштейна до выбранного слова из списка топ компаний к каждому слову из второго столбца — названия второй компании.

Если и второй коэффициент (отношение дистанции к длине слова из списка топ компаний) оказывается ниже или равен 0.4, то мы фиксируем следующие значения в таблицу:
— дистанция Левенштейна от слова из списка №1 компаний до слова в списке топ компаний
— дистанция Левенштейна от слова из списка №2 компаний до слова в списке топ компаний
— длина слова из списка №1
— длина слова из списка №2
— длина слова из списка топ компаний
— отношение длина слова из списка №1 к дистанции
— отношение длина слова из списка №2 к дистанции

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

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

Код

# create information about duplicate name of petrochemical companies from top list list_top_companies = list_top_companies  dp_train = [] for i in list(baseline_train['duplicate']):     dp_train.append(''.join(list(set(i) & set(list_top_companies))))      dp_test = [] for i in list(baseline_test['duplicate']):     dp_test.append(''.join(list(set(i) & set(list_top_companies))))      baseline_train['duplicate_name_company'] = dp_train baseline_test['duplicate_name_company'] = dp_test  # replace name duplicate to number baseline_train['duplicate_name_company'] =\     baseline_train['duplicate_name_company'].replace('',0,regex=True) baseline_train.loc[baseline_train['duplicate_name_company'] != 0, 'duplicate_name_company'] = 1  baseline_test['duplicate_name_company'] =\     baseline_test['duplicate_name_company'].replace('',0,regex=True) baseline_test.loc[baseline_test['duplicate_name_company'] != 0, 'duplicate_name_company'] = 1  # create some important feature about similar words in the data and names of top companies for TRAIN # (levenstein distance, length of word, ratio distance to length) baseline_train = dist_name_to_top_list_make(baseline_train,                       'name_1_finish','name_2_finish',list_top_companies)  # create some important feature about similar words in the data and names of top companies for TEST # (levenstein distance, length of word, ratio distance to length) baseline_test = dist_name_to_top_list_make(baseline_test,                       'name_1_finish','name_2_finish',list_top_companies) 

Посмотрим на полезность признаков сквозь призму графиков

Код

data = baseline_train analyse = 'levenstein_dist_w1_top_w_min' size = (14,2) dd = data_statistics(data,analyse,title_print='no') hist_fz(data,dd,analyse,size) boxplot(data,analyse,size)


Очень хорошо.

Готовим данные для подачи в модель

У нас получилась большая таблица и далеко не все данные для анализа нам нужны. Посмотрим на названия столбцов таблицы.

Код

baseline_train.columns


Выберем те столбцы, которые будем анализировать.

Зафиксируем seed для воспроизводимости результата.

Код

# fix some parameters features = ['levenstein','norm_levenstein',                          'duplicate_count','duplicate_sum','duplicate_mean',             'dif_count','dif_sum','dif_mean','ratio_duplicate/dif_count',                          'duplicate_name_company',                         'levenstein_dist_w1_top_w_min', 'levenstein_dist_w2_top_w_min',        'length_w1_top_w_min', 'length_w2_top_w_min', 'length_top_w_min',        'ratio_dist_w1_to_top_w_min', 'ratio_dist_w2_to_top_w_min'             ] seed = 42

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

Код

# provides train/test indices to split data in train/test sets split = StratifiedShuffleSplit(n_splits=1, train_size=0.8, random_state=seed)  tridx, cvidx = list(split.split(baseline_train[features],                                 baseline_train["target"]))[0]  print ('Split baseline data train',baseline_train.shape[0]) print (' - new train data:',tridx.shape[0]) print (' - new test data:',cvidx.shape[0])

Настройка и обучение модели

В качестве модели будем использовать решающее дерево из библиотеки Light GBM.

Сильно накручивать параметры не имеет смысла. Смотрим код.

Код

# learning Light GBM Classificier seed = 50 params = {'n_estimators': 1,           'objective': 'binary',           'max_depth': 40,           'min_child_samples': 5,           'learning_rate': 1,  #           'reg_lambda': 0.75, #           'subsample': 0.75, #           'colsample_bytree': 0.4, #           'min_split_gain': 0.02, #           'min_child_weight': 40,           'random_state': seed}   model = lgb.LGBMClassifier(**params) model.fit(baseline_train.iloc[tridx][features].values,           baseline_train.iloc[tridx]["target"].values)

Модель настроили и обучили. Теперь давайте посмотрим на результаты.

Код

# make predict proba and predict target probability_level = 0.99 X = baseline_train tridx = tridx cvidx = cvidx model = model  X_tr, X_cv = contingency_table(X,features,probability_level,tridx,cvidx,model)  train_matrix_confusion = matrix_confusion(X_tr) cv_matrix_confusion = matrix_confusion(X_cv)  report_score(train_matrix_confusion,              cv_matrix_confusion,              baseline_train,              tridx,cvidx,              X_tr,X_cv) 


Обратите внимание на то, что мы в качестве оценки модели используем метрику качества f1. Значит, имеет смысл регулировать уровень вероятности отнесения объекта к классу 1 или 0. Мы выбрали уровень 0.99, то есть при вероятности равной и выше 0.99 объект будет отнесен к классу 1, ниже 0.99 — к классу 0. Это важный момент — можно существенно поправить скор таким не хитрым простым трюком.

Качество вроде бы не плохое. На условно тестовой выборке алгоритм допустил ошибки при определении 222 объектов класса 0 и на 90 объектах, относящихся к классу 0 ошибся и отнес их к классу 1 (см.Matrix confusion on test(cv) data).

Давайте посмотрим какие признаки были наиболее важными, а какие нет.

Код

start = 0 stop = 50 size = (12,6)  tg = table_gain_coef(model,features,start,stop) gain_hist(tg,size,start,stop) display(tg)



Заметим, что для оценки значимости признаков мы использовали параметр ‘gain’, а не ‘split’. Это важно так как в очень упрощенном варианте первый параметр означает вклад признака в уменьшении энтропии, а второй указывает на то, сколько раз признак использовался для разметки пространства.

На первый взгляд, признак, который мы делали очень долго «levenstein_dist_w1_top_w_min» оказался совсем не информативным — его вклад равен 0. Но это только на первый взгляд. Он просто почти полностью дублируется по смыслу с признаком «duplicate_name_company». Если удалить «duplicate_name_company» и оставить «levenstein_dist_w1_top_w_min», то второй признак займет место первого и качество не поменяется. Проверено!

Вообще такая табличка — удобная штука особенно когда у тебя сотни признаков и модель с кучей прибамбасов и итераций 5000. Можно пачками удалять признаки и смотреть как растет от этого не хитрого действия качество. В нашем случае, удаление признаков не отразится на качестве.

Давайте посмотрим на таблицу сопряжения. В первую очередь посмотрим на объекты «False Positive», то есть те, которые наш алгоритм определил как одинаковые и отнес их к классу 1, а на самом деле они относятся к классу 0.

Код

X_cv[X_cv['False_Positive']==1][0:50].drop(['name_1_non_stop_words',        'name_2_non_stop_words', 'name_1_transliterated',        'name_2_transliterated', 'duplicate', 'difference',        'levenstein',        'levenstein_dist_w1_top_w_min', 'levenstein_dist_w2_top_w_min',        'length_w1_top_w_min', 'length_w2_top_w_min', 'length_top_w_min',        'ratio_dist_w1_to_top_w_min', 'ratio_dist_w2_to_top_w_min',        'True_Positive','True_Negative','False_Negative'],axis=1)


Да уж. Здесь и человек то сходу не определит 0 или 1. Например, пара №146825 «mitsubishi corp» и «mitsubishi corp l». Глаза говорят что это одно и тоже, а выборка говорит, что разные компании. Кому верить?

Скажем так, что сходу можно было выжать — мы выжали. Остальную работу оставим опытным товарищам 🙂

Давайте загрузим данные на сайт организатора и узнаем оценку качества работы.

Итоги соревнования

Код

model = lgb.LGBMClassifier(**params) model.fit(baseline_train[features].values,           baseline_train["target"].values)  sample_sub = pd.read_csv('sample_submission.csv', index_col="pair_id")  sample_sub['is_duplicate'] = (model.predict_proba(     baseline_test[features].values)[:, 1] > probability_level).astype(np.int)  sample_sub.to_csv('baseline_submission.csv') 

Итак, наш скор с учетом запрещенного приема: 0.5999

Без него, качество было где-то между 0.3 и 0.4. Надо перезапускать модель для точности, а мне немного лень 🙂

Давайте лучше резюмируем полученный опыт.

Во-первых, как можно видеть, у нас получился вполне себе воспроизводимый код и достаточно адекватная структура файла. Из-за малого опыта я в свое время набил очень много шишек именно из-за того, что оформлял работы наспех, лишь бы получить какой-либо более-менее приятный скор. В итоге файл получался таким, что через неделю его уже было страшно открывать — настолько ничего не понятно. Поэтому, мой посыл — пишите сразу код и делайте файл читаемым, так чтобы через год можно было вернуться к данным, посмотреть для начала на структуру, понять какие шаги были предприняты и потом, чтобы каждый шаг по отдельности можно было легко разобрать. Конечно, если Вы новичок, то с первой попытки файл не будет красивым, код будет ломаться, будут костыли, но если периодически, в процессе исследования, переписывать код заново, то на 5-7 раз переписывания Вы сами удивитесь тому, насколько код стал чище и возможно даже найдете ошибки и улучшите скор. Не забывайте про функции, очень облегчает читаемость файла.

Во-вторых, после каждой обработки данных, проверяйте, все ли прошло как задумано. Для этого надо уметь фильтровать таблицы в pandas. В этой работе много фильтрации, пользуйтесь на здоровье 🙂

В-третьих, всегда, прямо-таки всегда, в задачах классификации, формируйте и таблицу и матрицу сопряжения. По таблице Вы легко найдете на каких объектах ошибается алгоритм. Для начала старайтесь подмечать те ошибки, которые что называются системные, они требуют меньше работы по исправлению, а дают больший результат. Потом уже как разберете системные ошибки, переходите на частные случаи. По матрице ошибок Вы увидите где больше ошибается алгоритм: на классе 0 или 1. Отсюда Вы и будете копать ошибки. Например, я заметил, что мое дерево хорошо определяет классы 1, но допускает много ошибок на классе 0, то есть дерево часто «говорит», что этот объект класса 1, тогда как на самом деле он 0. Я предположил, что это может быть связано с уровнем вероятности отнесения объекта к классу 0 или 1. У меня уровень был зафиксирован на 0.9. Увеличение уровня вероятности отнесения объекта к классу 1 до 0.99, сделало отбор объектов класса 1 жестче и вуаля — наш скор дал существенный прирост.

Еще раз отмечу, что целью участия в соревновании у меня было не занятие призового места, а получение опыта. Учитывая, что до начала соревнования я понятия не имел как работать с текстами в машинном обучении, а в итоге за несколько дней получилась простая, но все же рабочая модель, то можно сказать цель достигнута. Также и для любого начинающего самурая в мире data science я считаю важно получение опыта, а не приз, вернее опыт — это и есть приз. Поэтому не бойтесь участия в соревнованиях, дерзайте, всем бобра!

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

А Вы — уважаемый читатель, если располагаете идеями о том, как увеличить скор уже сейчас, пишите в комментах. Сделаете доброе дело 🙂

Источники информации, вспомогательные материалы

1. «Гитхаб с данными и Jupyter Notebook»

2.«Платформа соревнования SIBUR CHALLENGE 2020»

3.«Сайт организатора соревнования SIBUR CHALLENGE 2020»

4.«Хорошая статья на Хабре „Основы Natural Language Processing для текста“»

5.«Еще одна хорошая статья на Хабре „Нечёткое сравнение строк: пойми меня, если сможешь“»

6.«Публикация из журнала АПНИ»

7.«Статья о не использованном здесь коэффициенте Танимото „Степень схожести строк“»

ссылка на оригинал статьи https://habr.com/ru/post/530628/

Четырёхмерные таблицы в комбинаторике — два странных способа посчитать сочетания

В комбинаторике сочетанием из $n$ по $k$ называют набор $k$ элементов, выбранных из $n$ элементов. В отличие от размещений, число сочетаний не учитывает последовательность размещения элементов, например: «Сколько групп из 4 человек, можно получить, если всего в классе 20 человек?». Хотя удобные способы подсчёта давно известны, на ещё два стоит взглянуть.

Обозначается сочетание из $n$ по $k$ так: $C_n^k$. В литературе они чаще обозначаются $ \binom nk$ (но мне больше нравится первый вариант, чтобы не путать с матрицами).

В комбинаторике известны несколько способов подсчёта:

$C_n^k = \frac{n!}{k!(n-k)!}$

$C_n^k=\frac{n(n-1)(n-2)…(n-k+1)}{k!}=\frac{\prod\limits_{i = n-k+1}^n i}{k!}$

Где $n!$ — эн факториал, произведение всех целых чисел от 1 до n (например: $4!=1\cdot2\cdot3\cdot4=24$), а $0!$ считается равным единице. Для вышесказанной задачи получается:

$C_{20}^4 = \frac{20!}{4!(20-4)!} = \frac{17\cdot18\cdot19\cdot20}{1\cdot2\cdot3\cdot4} = 4845$

Или так:

$C_{20}^4=\frac{20\cdot19\cdot18\cdot17}{4!}=\frac{116280}{24}=4845$

Вторая формула сочетаний выводится очень просто. Есть понятие числа размещений из $n$ по $k$, когда последовательность элементов имеет значение (то есть набор «первый со вторым с пятым» это не тоже самое, что «первый с пятым со вторым»), обозначается $A_n^k$.

Например все размещения из 3 по 2 выглядят так:

12 21
13 31
23 32

Первый элемент можно выбрать $n$ способами, второй — $(n-1)$ способами, последний — $(n-(k-1))$ способами. Поэтому число размещений из $n$ по $k$ равно $n(n-1)(n-2)…(n-k+1)$, всего $k$ множителей.

Для подсчёта сочетаний получившиеся число нужно разделить на $k!$, поскольку есть $k!$ способов разместить $k$ элементов. В данном случае — $2!=2$ способа (первый со вторым и второй с первым — это одно и тоже сочетание).

Вспомним, как идет счёт в шашках по круговой системе (когда все играют со всеми). Для этого пишут обычную таблицу:

По горизонтали и вертикали идут номера игроков. Диагональ можно закрасить — игрок не может играть сам с собой. Результат каждой партии записывают в таблицу два раза. Как сыграл второй с пятым и как сыграл пятый со вторым. Таким образом, количество партий в турнире — и есть число сочетаний по 2.

Число вычеркнутых клеток равно $n$, а число всех клеток — это $n^2$. Стало быть, число сочетаний по 2 можно посчитать так:

$C_n^2=\frac{n^2-n}{2}$

Когда я это заметил, не сразу увидел что это равно $\frac{n(n-1)}{2!}$. Решил сделать также для $k=3$, с трёхмерной таблицей:

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

Всего на каждом слое исключается $n+2(n-1)$ клеток.

$n+2(n-1)=3n-2$






Итак, на каждом слое исключается $3n-2$ клетки. Всего $n$ слоёв, поэтому общее число исключившихся ячеек:

$n(3n-2)=3n^2-2n$

А вся таблица — $n^3$. Значит, число сочетаний по 3 можно посчитать так:

$C_n^3=\frac{n^3-(3n^2-2n)}{3!}=\frac{n^3-3n^2+2n}{3!}$

Как уже сказано выше, это и есть общая формула, в которой просто раскрыли скобки:

$C_n^3=\frac{n^3-3n^2+2n}{3!}=\frac{n(n-1)(n-2)}{3!}$

И тут возник вопрос, можно ли посчитать сочетания, так же представив их через таблицы, не используя факториалы вообще? К слову, в комбинаторике уже известна рекуррентная формула для числа сочетаний: $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$ (число сочетаний по 0 равно 1, из любого количества элементов можно получить только одну группу в которой 0 элементов). Итак, я попробовал посмотреть, какие еще клетки исключаются в трёхмерной таблице, когда мы делим число оставшихся клеток на $k!$.

Клетки ниже диагонали дублируют клетки, которые выше диагонали — вычеркнем их (ячейка 431 — то же самое, что и 341). Для того, чтобы получить такое же количество клеток, просто поделим число размещений на 2. Цифрами в самой таблице я отметил, в какой строке встретилось данное сочетание. Например, сочетание 251 впервые встретилось здесь во второй строке, поэтому отмечено цифрой 2. Посмотрим на следующий слой:

Закрашенные клетки с цифрой означают, что данное сочетание уже встречалось. Например, комбинация 152 уже встречалась во второй строке (в виде 251), поэтому отмечена цифрой 2 в закрашенной клетке.

Итак, на втором слое исключается ещё $(n-2)$ клетки (кроме тех, которые вычеркнуты из-за повторяющихся чисел в них, и тех, которые вычеркнуты ниже диагонали, из-за того что дублируют верхние). Перебрав так всю таблицу, я получил следующее. На третьем слое исключается ещё $(n-2)+(n-3)$ клеток:

На четвертом слое вычеркивается ещё $(n-2)+(n-3)+(n-4)$ клеток:

На пятом — $(n-2)+(n-3)+(n-4)+(n-5)$:

На шестом, по видимому, $(n-2)+(n-3)+(n-4)+(n-5)+(n-n)$:

Получается, что для подсчёта сочетаний по 3, из числа $\frac{n(n-1)(n-2)}{2}$ нужно вычесть такую сумму:

$(n-2)+((n-2)+(n-3))+((n-2)+(n-3)+(n-4))+\\((n-2)+(n-3)+(n-4)+(n-5))+((n-2)+(n-3)+(n-4)+(n-5)+(n-n))$

Это можно переписать в таком виде:

$\sum_{i=2}^n{\sum_{j=2}^i(n-j)}$

Ещё можно переписать эту сумму так:

$5(n-2)+4(n-3)+3(n-4)+2(n-5)+(n-n)=\\(n-1)(n-2)+(n-2)(n-3)+(n-3)(n-4)+(n-4)(n-5)+(n-5)(n-n)$

То есть:

$\sum_{i=2}^{n-1}{(n-i)(n-i+1)}$

Значит, число сочетаний по 3 можно вычислить так:

$C_n^3=\frac{n(n-1)(n-2)}{2}-\sum_{i=2}^n\sum_{j=2}^i(n-j)=\frac{n(n-1)(n-2)}{2}-\sum_{i=2}^{n-1}{(n-i)(n-i+1)}$

Например число сочетаний из 8 по 3:

$C_8^3=\frac{8\cdot7\cdot6}{2}-\sum_{i=2}^7{(n-i)(n-i+1)}=\\ 168-(6\cdot7+5\cdot6+4\cdot5+3\cdot4+2\cdot3+1\cdot2)=\\ 168-112=56$

На этом этапе вряд ли видна какая-либо зависимость, посмотрим то же самое с четырёхмерной таблицей. Изобразить её можно в виде нескольких трёхмерных (у трёхмерной таблицы слои двухмерные, у четырёхмерной — трёхмерные). То есть, первый фрагмент четырёхмерной таблицы будет выглядеть так (первая ячейка будет иметь координаты 1111):

Весь первый двухмерный слой этого слоя исключается (на нем единица везде повторяется). В итоге на первом трёхмерном слое вычитается такая сумма:

$\begin{pmatrix}-\\0+\\(n-3)+\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+(n-n)\end{pmatrix}$

Слагаемые в столбик записаны лишь для наглядности. Прочерком я отметил первый двухмерный слой, который итак исключился весь. Посмотрим следующий «слой» четырёхмерной таблицы:

Значит, на втором слое исключается такая сумма:

$\begin{pmatrix}(n-3)+(n-4)+(n-5)+\\-\\(n-3)+\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}=\begin{pmatrix}-\\(n-3)+\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}$

Посмотрим на третий:

На третьем исключается сумма:

$\begin{pmatrix}(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\-\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}=\begin{pmatrix}-\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}$

Уже здесь видно, что общая сумма, которая будет вычитаться будет такой:

$\begin{pmatrix}-\\0+\\(n-3)+\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\(n-3)+\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}+\\\begin{pmatrix}-\\(n-3)+(n-4)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}+\\\begin{pmatrix}-\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)+\\(n-3)+(n-4)+(n-5)\end{pmatrix}$

её можно переписать в таком виде:

4(n-3)+3(n-4)+2(n-5)+1(n-n)+
5(n-3)+4(n-4)+3(n-5)+2(n-n)+
5(n-3)+5(n-4)+4(n-5)+3(n-n)+
5(n-3)+5(n-4)+5(n-5)+4(n-n)+
5(n-3)+5(n-4)+5(n-5)+5(n-n)+
5(n-3)+5(n-4)+5(n-5)+5(n-n)

Получаем:

$29(n-3)+27(n-4)+24(n-5)+20(n-n)$

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

$C_n^4=\frac{n(n-1)(n-2)(n-3)}{2}-\sum_{i=3}^{n-1}{(n-i)\left(30-\sum_{j=1}^{i-2}j\right)}$

Однако, получившаяся формула будет работать только для $n=6$, ведь для других $n$ коэффициенты будут другие. И, поскольку я не увидел зависимости от $k$ и здесь, решил посмотреть тоже самое для $k=5$, через пятимерную таблицу, весь её первый трёхмерный «слой» исключается, поскольку единица здесь повторяется во всех ячейках:

Для наглядности запишем это так:

$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}$

Смотрим дальше:

Тут, как видно, вычитается такая сумма:

$\begin{pmatrix}-\\-\\0\\(n-4)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}$

Третий:

Тут вычитается:

$\begin{pmatrix}-\\(n-4)+(n-5)+\\-\\(n-4)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n-4)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}$

$\begin{pmatrix}-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}$

$\begin{pmatrix}-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\-\\(n-4)+(n-5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}$

Затем, шестой фрагмент:

$\begin{pmatrix}-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\\-\end{pmatrix}=\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}$

На этом первый четырёхмерный слой заканчивается. Не сложно понять, что трёхмерный «слой» 21 будет дублировать слой 12, а слой 22 исключится весь, также как 11.

Перейдем к «слою» 23:

Здесь встретилось последнее сочетание из 6 по 5 — 56423 (клетки, которые встретились впервые отмечены белым, если кто забыл)). Напишем, какую в итоге надо вычесть сумму из $\frac{n(n-1)(n-2)(n-3)(n-4)}{2}$, чтобы получить число сочетаний из $n$ по 5. На первом четырёхмерном слое исключилось:

$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}+\begin{pmatrix}-\\-\\0+\\(n-4)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n-4)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\\\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}$

На втором:

$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}+\begin{pmatrix}-\\-\\(n-4)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\\\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)+\\(n-4)+(n-5)\end{pmatrix}$

Получается что каждая сумма в скобке обозначает исключившиеся ячейки на трёхмерных слоях. Всего $n$ четырёхмерных слоёв. Запишем это в виде суммы:

$\begin{aligned} &C_n^5=\frac{n(n-1)(n-2)(n-3)(n-4)}{2}-\sum_{i_3=1}^n\sum_{i_2=1}^{n-k+4}\sum_{i_1=a}^n\sum_{i_0=k-1}^b(n-i_0)\\ &a=\left\{ \begin{aligned} &k-1, \ если \ i_2=i_3=1 \\ &k-2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_1-2+i_2+i_3, \ если \ i_1-2+i_2+i_3\leqslant n-1 \\ &n-1, \ иначе \\ \end{aligned}\right. \end{aligned}$

Получается, что последняя сумма суммирует исключившиеся ячейки на одномерных слоях, образуя исключения на двухмерных. Предпоследняя сумма складывает исключившиеся ячейки на двухмерных слоях, образуя исключившиеся ячейки на трёхмерных и т.д.

Индекс второй суммы берем до $(n-k+4)$, поскольку она «образует» исключения на четырёхмерных слоях, суммируя вычеркнутые ячейки на трёхмерных, как мы могли видеть выше, у пятимерной таблицы на каждом четырёхмерном слое исключается один трёхмерный, то есть для $n=6$, на каждом четырёхмерном остается пять трёхмерных слоёв, $6-5+4=5$.

Для $k=6$, шестимерную таблицу можно не смотреть, достаточно выписать индексы её последних трёх измерений:

111 121 131 141 151 161
112 122 132 142 152 162
113 123 133 143 153 163
114 124 134 144 154 164
115 125 135 145 155 165
116 126 136 146 156 166

211
212

Опять же, вычеркнули мы те слои, где хоть одна цифра повторилась. Уже по первому пятимерному слою видно, что на пятимерных слоях для шестимерной таблицы останется на один четырёхмерный слой меньше. Количество оставшихся четырёхмерных слоёв равно $(n-k+5)$. А трёхмерных слоёв на каждом четырёхмерном остается все также $(n-k+4)$ (по 4 в данном случае: $6-6+4$). Запись в виде сумм получилась такой:

$\begin{aligned} &C_n^6=\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{2}-\sum_{i_4=1}^n\sum_{i_3=1}^{n-k+5}\sum_{i_2=1}^{n-k+4}\sum_{i_1=a}^n\sum_{i_0=k-1}^b(n-i_0)\\ &a=\left\{ \begin{aligned} &k-1, \ если \ i_2=i_3=i_4=1 \\ &k-2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_1-3+i_2+i_3+i_4, \ если \ i_1-3+i_2+i_3+i_4\leqslant n-1 \\ &n-1, \ иначе \\ \end{aligned}\right. \end{aligned}$

Запись для $k=3$ можно переписать так:

$\begin{aligned} &C_n^3=\frac{n(n-1)(n-2)}{2}-\sum_{i_1=a}^n\sum_{i_0=k-1}^b(n-i_0)\\ &a=k-1\\ &b=\left\{ \begin{aligned} &i_1, \ если \ i_1\leqslant n-1 \\ &n-1, \ иначе \\ \end{aligned}\right. \end{aligned}$

Для $k=4$ получается:

$\begin{aligned} &C_n^4=\frac{n(n-1)(n-2)(n-3)}{2}-\sum_{i_2=1}^n\sum_{i_1=a}^n\sum_{i_0=k-1}^b(n-i_0)\\ &a=\left\{ \begin{aligned} &k-1, \ если \ i_2=1 \\ &k-2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_1-1+i_2, \ если \ i_1-1+i_2\leqslant n-1 \\ &n-1, \ иначе \\ \end{aligned}\right. \end{aligned}$

Для $k=5$:

$\begin{aligned} &C_n^5=\frac{n(n-1)(n-2)(n-3)(n-4)}{2}-\sum_{i_3=1}^n\sum_{i_2=1}^{n-k+4}\sum_{i_1=a}^n\sum_{i_0=k-1}^b(n-i_0)\\ &a=\left\{ \begin{aligned} &k-1, \ если \ i_2=i_3=1 \\ &k-2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_1-2+i_2+i_3, \ если \ i_1-2+i_2+i_3\leqslant n-1 \\ &n-1, \ иначе \\ \end{aligned}\right. \end{aligned}$

В общем виде запись для $k\geqslant2$ получается такой (сумма, которую мы вычитаем вычисляется рекуррентно):

$\begin{aligned} &C_n^k=\frac{\prod\limits_{i=n-k+1}^ni}{2}-c_k\\ &k_0=k\\ &c_k=\left\{\begin{aligned} &0, \ k=2 \\ &\sum_{i_3=a}^{n}\sum_{i_2=k-1}^{b}(n-i_2), \ k=3 \\ &\sum_{i_k=1}^{n-k_0+k}c_{k-1}, \ k\geqslant4 \end{aligned}\right. \\ &a=\left\{ \begin{aligned} &k_0-1, \ если \ i_4=i_5=…=i_k=1 \ или \ k_0=3 \\ &k_0-2, \ иначе \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_3-(k_0-3)+i_4+i_5+…+i_k, \ если\ i_3-(k-3)+i_4+i_5+…+i_k\leqslant n-1 \ и \ k_0>3 \\ &i_3, \ если\ i_3\leqslant n-1 \ и\ k_0=3 \\ &n-1, \ иначе \end{aligned}\right. \end{aligned}$

Второй способ

Как я уже писал выше, число сочетаний по 3 можно записать через одну сумму:

$C_n^3=\frac{n(n-1)(n-2)}{2}-\sum_{i=2}^n\sum_{j=2}^i(n-j)=\frac{n(n-1)(n-2)}{2}-\sum_{i=2}^{n-1}{(n-i)(n-i+1)}$

А число сочетаний из 6 по 4 можно записать так:

$C_n^4=\frac{n(n-1)(n-2)(n-3)}{2}-\sum_{i=3}^{n-1}{(n-i)\left(30-\sum_{j=1}^{i-2}j\right)}$

Оказывается, что 30 во вторых скобках, это $n(n-1)$ (логического обоснования этому я так и не смог найти).

$C_n^4=\frac{n(n-1)(n-2)(n-3)}{2}-\sum_{i=3}^{n-1}{(n-i)\left(n(n-1)-\sum_{j=1}^{i-2}j\right)}$

Вторые скобки здесь представляют собой коэффициент, который умножается на $(n-i)$. Для $k=3$ этот коэффициент просто уменьшается на 1 с каждым слагаемым первой суммы. Для $4$ — число, на которое уменьшается этот коэффициент возрастает на 1. Затем я просто посчитал количество слагаемых $(n-4)$, $(n-5)$ и $(n-n)$ в сумме которая вычитается для $5$:

$119(n-4)+116(n-5)+110(n-n)$

Число, на которое увеличивается число, на которое уменьшается коэффициент, возрастает на 1. Этот коэффициент можно записать через две суммы:

$C_n^5=\frac{n(n-1)(n-2)(n-3)(n-4)}{2}-\sum_{i=4}^{n-1}{(n-i)\left(n(n-1)(n-2)-\sum_{j_1=1}^{i-3}\sum_{j_0=1}^{j_1}j_0\right)}$

Зависимость ясна — для $k=6$ эта формула будет выглядеть так:

$C_n^6=\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{2}\\-\sum_{i=5}^{n-1}{(n-i)\left(n(n-1)(n-2)(n-3)-\sum_{j_2=1}^{i-4}\sum_{j_1=1}^{j_2}\sum_{j_0=1}^{j_1}j_0\right)}$

А в общем виде (опять же, для $k\geqslant2$) получилось так:

$\begin{aligned} &C_n^k=\frac{\prod\limits_{i=n-k+1}^ni}{2}-c_k\\ &k_0=k\\ &c_k=\left\{ \begin{aligned} &0, \ k=2 \\ &\sum_{i=k-1}^{n-1}{(n-i)\left(\prod_{j_k=n-k+3}^nj_k-d_k\right)}, \ если \ k\geqslant3 \\ \end{aligned}\right.\\ &d_k=\left\{ \begin{aligned} &i-1, \ k=3 \\ &\sum_{j_4=1}^lj_4, \ k=4 \\ &\sum_{j_k=1}^ld_{k-1}, \ если \ k>4 \\ &l=j_{k+1}, \ если \ k\neq k_0 \\ &l=i-k_0+2, \ если \ k = k_0 \\ \end{aligned}\right.\\ \end{aligned}$

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

ссылка на оригинал статьи https://habr.com/ru/post/530098/

(не) Безопасный дайджест: сливы COVID-пациентов и незваный гость на министерской встрече в Zoom

Привет! Продолжая традицию, собрали «классические» и нетривиальные ИБ-инциденты, о которых писали зарубежные и российские СМИ в ноябре.

И кстати, всех причастных – с международным днем защиты информации!

У них

Аэромайнинг

Что случилось: Сотрудники аэропорта в итальянском городе Ламеция-Терме обнаружили аномалии в работе ИТ-систем и обратились в транспортную полицию. В ходе расследования полицейские нашли в технических помещениях ферму для майнинга Ethereum, подключенную к электросети аэропорта.

Кто виноват: Майнером оказался 41-летний техник компании-подрядчика Sacal, которая управляет аэропортами в провинции Калабрия. Мужчина отвечал за работу компьютерной инфраструктуры воздушного хаба. Он установил вредоносное ПО и использовал ИТ-мощности Sacal для майнинга криптовалюты. Выйти на след злоумышленника помогли камеры видеонаблюдения. О наказании СМИ не пишут, но предполагаем, что как минимум работы в Sacal мужчина лишился.

Купонщик-миллионер

Что случилось: Из онлайн-магазина Microsoft пропали подарочные сертификаты на 10 млн долларов.

Кто виноват: Вором оказался инженер компании Владимир Квашук (гражданин Украины), причем его «темные дела» оставались незамеченными на протяжении семи месяцев. Чтобы скрыть следы, он подключался к платформе через учетные записи коллег и использовал «сервисы для смешивания биткоинов» (позволяют «смешать» цифровую валюту из разных источников в одном большом хранилище и тем самым обеспечить конфиденциальность ее владельцам). На вырученные деньги инженер купил дом на берегу озера и автомобиль Tesla. Еще 2,8 млн долларов он перевел на свои банковские счета. А чтобы не попасться налоговой, указал в декларации, что биткоины ему подарил родственник.

Махинацию все же раскрыли, хотя расследование, по признанию правоохранителей, было непростым и потребовало от полиции специальных знаний по кибербезопасности. В итоге Квашука уволили, суд приговорил его к девяти годам тюрьмы за 18 преступлений. Он должен выплатить компании 8,3 млн долларов. А после тюремного заключения его могут депортировать в Украину.

«Культурный» обмен

Что случилось: Офис шерифа округа Санта-Клара в Калифорнии уличили в торговле разрешениями на ношение оружия. Фигурантом дела стал руководитель службы безопасности Apple.

Кто виноват: Окружная прокуратура Санта-Клары обвинила во взяточничестве руководителя службы безопасности Apple Томаса Мойера и двух помощников шерифа. По мнению следствия, топ-менеджер компании договорился с офисом шерифа «обменять» четыре лицензии на скрытое ношение оружия на 200 новых планшетов Apple iPad стоимостью 70 тыс. долларов.

Адвокат Мойера заявил, что подзащитный собирался передать планшеты офису шерифа в рамках совместного проекта по подготовке кадров. И этот факт не связан с обращением Мойера за разрешением на ношение оружия. Разбирательство только начинается, но очевидно, что 14-летний стаж работы в Apple вряд ли убережет сотрудника от увольнения. А случай красноречиво доказывает, что контроль топ-менеджеров – насущная ИБ-проблема, а не излишняя подозрительность.

«Мне только спросить!»

Что случилось: Журналист из Нидерландов Даниэль Верлаан подключился к закрытому Zoom-совещанию министров обороны стран ЕС, чем заметно смутил чиновников.

Кто виноват: О встрече Верлаан узнал из Twitter, где министр обороны Нидерландов Анка Бийлевельда опубликовала серию фотографий, на которых она работает из дома во время конференции. На фото попал экран ее ноутбука с PIN-кодом для доступа к вызову. Это позволило журналисту подключиться к беседе. После короткого диалога с шокированными министрами он отключился со словами: «Прошу прощения, что прерываю вашу конференцию, я ухожу».

Пока непонятно, ждет ли Верлаана наказание за взлом закрытой встречи. Премьер-министр Нидерландов Марк Рютте публично высказался об инциденте, указав на грубую ошибку Бийлевельды и службы безопасности, которая должна пресекать подобные случаи.

Онлайн-совещания вошли в практику не только политиков, но и сотрудников на удаленке еще со времен первой волны коронавируса. Казалось бы, секретному совещанию такого формата не место в Zoom, который неоднократно обвиняли в наличии уязвимостей. Но, как видим, воз и ныне там и возле него щедро рассыпаны грабли.

Провальный тест

Что случилось: В открытом доступе оказались персданные 16 млн бразильцев, заболевших COVID-19, в том числе информация о президенте страны Жаире Болсонару, семи министрах и 17 губернаторах штатов.

Кто виноват: Утечку допустил сотрудник больницы им. Альберта Эйнштейна, который выложил на GitHub таблицу с именами пользователей, паролями и ключами доступа к системам Минздрава Бразилии. В ней также можно было найти имена, адреса, историю болезни и режимы приема лекарств. Как рассказал мужчина, он выгрузил данные для тестирования, а потом забыл их удалить. После инцидента чиновники поменяли пароли и ключи доступа к системам Минздрава. А что будет с горе-тестером, пока неизвестно.

У нас

Нет дыма – есть утечка

Что случилось: В общий доступ попал архив на 1 Гб, содержащий 652 внутренних документа производителя систем нагревания табака IQOS. В них содержатся персданные клиентов, шаблоны презентаций и скрипты общения для менеджеров по продажам.

Кто виноват: Большая часть файлов имеет одного автора. По мнению, ИБ-исследователей, документы утекли с рабочего компьютера одного из сотрудников IQOS или были украдены с корпоративного файлового сервера. В любом случае – имя владельца документов может послужить ключом к обнаружению источника утечки.

Тайный покупатель

Что случилось: Злоумышленник взломал девять учетных записей интернет-магазина и оформил заказы на товары за счет их владельцев. Дело прогорело из-за бдительной службы безопасности.

Кто виноват: Вором оказался житель Екатеринбурга. Логины и пароли от учеток он купил в Интернете. Мужчина изменил регистрационные данные в личных кабинетах и оформил несколько покупок, расплачиваясь чужими электронными деньгами. Благодаря ИБ-службе из девяти попыток сделать заказ «покупателю» удалась только одна. В восьми случаях служба безопасности блокировала заказ – ее насторожило, что «владелец» аккаунта оформляет доставку в другой регион, не связанный с местом регистрации.

В итоге Кировский районный суд Екатеринбурга назначил вору штраф в 200 тыс. рублей.

Родственный жест

Что случилось: В Башкирии из микрокредитной компании ООО МКК «КредитЪка» утекли персданные 44 заемщиков.

Кто виноват: Утечку обнаружили сотрудники прокуратуры во время плановой проверки организации. Выяснилось, что сотрудница «КредитЪки» отправила анкеты клиентов по email по просьбе родственника. Женщину не смутило, что эти сведения по закону являются коммерческой тайной. Возбуждено уголовное дело.

ссылка на оригинал статьи https://habr.com/ru/company/searchinform/blog/530546/