Размещено на http://www.allbest.ru/

Пермь, 2018 год

Пермский филиал федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский университет «Высшая школа экономики»

Факультет экономики, менеджмента и бизнес-информатики

Выпускная квалификационная работа

ВЫЯВЛЕНИЕ ПАТТЕРНОВ ПЕРЕХОДОВ ФУТБОЛИСТОВ МЕЖДУ КЛУБАМИ

Язева Мария Сергеевна



Оглавление

• Аннотация

Введение

Глава 1. Анализ предметной области

1.1 Описание процесса перехода футболистов между клубами

1.2 Обзор исследований в области футбола

Глава 2. Теоретическое обоснование решения

2.1 Практическое применение поиска закономерностей

2.2 Методы поиска закономерностей

2.3 Метод анализа формальных понятий для поиска закономерностей

2.4 Методы отбора интересных паттернов

2.5 Уточнение задачи

Глава 3. Практическая часть

3.1 Подготовка данных

3.2 Выявление и проверка закономерностей на устойчивость

3.3 Интерпретация результатов для достижения целей футболистов

Заключение

Библиографический список

Приложение



Аннотация

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

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

Объем работы: 43 страницы, включая приложение.



Введение

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

Однако процесс поиска удачных сочетаний игрок-команда достаточно сложен. Наиболее часто получается так, что и у игроков, и у клубов возникают трудности. Не всегда и не всем талантливым футболистам удается достичь успеха в спорте, около 44% футболистов не могут найти новый клуб после окончания текущего контракта, и дело не в отсутствии навыков игры и желания футболиста продолжать карьеру, а в отсутствии новых предложений.

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

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

Объектом исследования является процесс перехода футболистов между клубами, а предметом выступают паттерны переходов футболистов между клубами. Цель работы - анализ переходов футболистов между клубами и интерпретация результатов для формирования практических рекомендаций для заинтересованных сторон, в том числе для футболистов, клубов, откуда игрок уходит, клубов, куда футболист переходит, и футбольных агентов, на основе полученных результатов. Для достижения поставленной цели выделяются следующие задачи:

1. Подготовить данные о переходах футболистов между клубами.

2. Проанализировать данные с помощью подходов поиска закономерностей (pattern mining).

3. Дать интерпретацию результатам.

4. Сформулировать рекомендации для заинтересованных сторон.

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

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

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

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

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

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



Глава 1. Анализ предметной области

1.1 Описание процесса перехода футболистов между клубами

Область футбольных трансферов имеет ряд процедурных и правовых особенностей. Основным документом, регламентирующим переходы игроков из клуба в клуб, является Регламент по статусу и переходам игроков [1]. Однако данный документ претерпел немало изменений за последние 30 лет, о чем говорится в [2]. Наиболее значимые изменения произошли в 1995 году после вступления в силу Правила Босмана. Процедура трансфера и обязанности сторон были модифицированы и зафиксированы в правовых документах, что в общем повлияло и на политику клубов при поиске игроков, и на размер компенсаций. Этот факт является существенным для данного исследования при выборе данных о трансферах. Типичные алгоритмы при анализе трансферов до 1996 года и после могут значительно отличаться.

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

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

Рынок труда в сфере профессионального футбола имеет несколько особенностей, которые описаны в [3]. Первое, профессиональный футбол - маленький, но очень видимый сегмент высококвалифицированных специалистов в своей области, то есть в футболе. Второе, именно в области футбола практически стерты какие-либо границы между странами и рынок труда является одним из наиболее глобализированных, а значит, география клубов, которые участвуют в трансферах, не ограничена. Данная область также отличается тем, что уже относительно давно ведется учет всех переходов, совершенных игроками различных уровней, с помощью СОТ. И наконец, в области профессионального футбола распространена такая практика, когда крупные футбольные клубы самостоятельно выращивают будущих игроков для команды, однако таких мер все же недостаточно. Это привело к появлению на данном рынке таких клубов, которые специализируются на воспитании молодых игроков и их продаже.

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

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

· На перспективу (поиск молодых игроков для будущего развития).

· Плановое усиление (набор в связи с повышением или расширением команды).

· Точечное усиление (замена уходящих игроков или заполнение проблемных мест).

· Экстренное усиление - срочная, вынужденная замена, например, в связи с травмами.

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

В контракте, заключаемом между клубами, оговариваются размер компенсации и другие условия перехода игрока, в личном же контракте между футболистом и клубом указываются срок контракта, заработная плата, премиальные и бонусы игрока, а также обязанности сторон. Как правило, заработная плата футболиста составляет около 10% от общей стоимости трансфера. Если игроку еще нет 23 лет или исполнилось в текущем сезоне, то помимо уже обозначенных выплат, существует также так называемая плата за подготовку специалиста, которая распределяется между предыдущими клубами игрока.

По причине того, что сделки по обмену или покупке игроков являются крайне важными, рисковыми и дорогими, в процессе перехода футболиста из клуба в клуб, помимо клубов и самого игрока, часто участвует еще одна заинтересованная сторона - агент [4]. Они наиболее часто выступают на стороне футболиста и продвигают его в различные футбольные клубы. За свои услуги агенты взымают отступные, которые могут достигать 10% от суммы контракта. Это лишь основные позиции, которые закладываются в стоимость перехода, поэтому размер компенсаций может достигать самых различных значений.

Не так давно в области футбола появилась еще одна особенность - такой феномен, как бренд футболиста. Исторически игроки не воспринимались как бренды, только иногда, когда футболист долгое время был связан с каким-либо брендом, они выстраивались в ассоциативный ряд. Но начиная с Дэвида Бекхема, игроки все чаще становятся самостоятельными брендами. В основе данного явления лежит набор из 7 факторов ("TOPSTAR") [5]. Одной из таких причин известности футболиста является команда, в которой играет или играл футболист. Стремясь к популярности, игрок должен особенно осторожно подходить к выбору клуба, с которым он подписывает контракт. Репутация игрока и клуба должны быть схожи, например, человек, который позиционирует себя как жесткого футболиста, не добьется популярности, играя в команде со слабой дисциплиной.

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

Цели покупающего клуба могут быть следующими:

1. Покупка игрока с хорошими показателями для укрепления команды.

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

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

4. Покупка перспективного футболиста с целью в будущем продать его по более высокой цене.

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

1. Переход в более элитный клуб уровнем выше.

2. Увеличение заработной платы и уровня доходов.

3. Смена места жительства.

4. Продление карьеры за счет перехода в клуб уровнем ниже.

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

1.2 Обзор исследований в области футбола

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

Наиболее распространенными исследованиями в области футбольных трансферов являются работы по определению размера компенсации, которую новый клуб обязан заплатить прежнему клубу. Например, в работе [6] описывается возможность применения количественных методов для прогнозирования суммы выплаты. На первом этапе авторы используют метод регрессии для определения объективного рейтинга игрока на основе таких параметров, как количество забитых футболистом голов, полученных красных карточек и др. Выдвигая гипотезу, что полученный рейтинг игрока является значимым фактором при расчете размера компенсации, ученые выявляют еще несколько важных аспектов, которые, помимо рейтинга, определяют искомую величину. В итоге получается регрессионная модель, включающая в себя 26 различных переменных и способная примерно спрогнозировать размер компенсации для конкретной сделки.

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

Другая же группа исследователей, изучая футбольные трансферы в своей работе [8], пришла к выводу, что использование одной только регрессионной модели в данном случае недостаточно. Обусловлено это тем, что при построении регрессии игнорируется селективность или субъективность выбора, которая затрудняет анализ такого процесса, как переход футболистов между клубами. Ученые опровергают теорию, которая является относительно распространенной, о сильной корреляции между зарплатой футболиста, размером компенсации и продуктивностью данного игрока. При проведении исследования дополнительно учитываются исходы, когда игрок не смог найти новый клуб, и используется пробит-модель. Таким образом, наиболее значимыми факторами при совершении трансфера оказываются время, которое футболист провел на поле, позиция игрока и возраст, причем он важен только до достижения игроком 26 лет, после же значимость фактора снижается. Однако, даже зная факторы, влияющие на трансфер, вероятность того, что переход будет удачным, до сих пор является нестабильной, так как наем игрока - это рисковые инвестиции.

Авторы работы [7] внесли свой вклад в исследовании переходов футболистов, описав карьеру среднестатистического футболиста. Так, обычно карьера начинается в возрасте 16 лет, если игрок показывает прогресс и потенциал, то через 2 года с ним заключают полноценный контракт, далее он играет 1 или 2 матча в неделю в течение сезона до достижения им возраста 30-35 лет. Тенденция такова, что если футболист начал играть в высшем дивизионе, то он, вероятнее всего, и останется в нем на протяжении всей карьеры, однако иногда возможны переходы в команды более низкого уровня перед завершением карьеры с целью продлить ее. В случае, когда футболист начинает играть в дивизионах пониже, у него есть шансы подняться, но он также может остаться на этом же уровне до конца.

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

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



Глава 2. Теоретическое обоснование решения

Понятие паттерн широко используется в самых различных сферах. Наиболее распространенными синонимами паттернов являются узоры, типичные алгоритмы, свойства, закономерности или шаблоны. В области финансов и экономики под паттерном понимается сущность явления, имеющего повторяющиеся черты, а в техническом анализе - это "свойство повторяющихся компонентов, объединенных общей структурой" [9], а в прогнозной аналитике - это процесс формирования модели взаимодействия объектов на основе повторений. Этот термин также встречается в медицине, в торговле, в криминалистике и многих других областях знаний. Таким образом, смысл понятия "паттерн" зависит от контекста [9].

В данной работе под паттернами переходов футболистов понимаются типичные закономерности, цепочки или последовательности переходов футболистов из одного клуба в другой. Например, было выявлено, что относительно часто игроки, начавшие карьеру в клубе А, затем переходят в клуб Б, откуда потом попадают в клуб В, значит можно предположить, что последовательность клубов А-Б-В является паттерном в области футбольных трансферов. Выявление паттернов, или частых закономерностей, (pattern mining) является отдельным широко развивающимся направлением в области компьютерных наук.

2.1 Практическое применение поиска закономерностей

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

Есть и другие примеры применения методов поиска закономерностей в потребительском поведении, но уже с учетом последовательностей. Например, если в магазине введена система клубных карт и ведется статистика по каждой из них, то на основе этих данных можно определить типичные последовательности покупок, например, клиенты приобретают сначала ноутбук, потом камеру, а затем телефон в течение 6 месяцев. В этом случае можно ввести рекламу соответствующих товаров для клиентов с похожими запросами. Поиск частых последовательностей также применяют для определения закономерностей поведения пользователей в глобальной сети и на сайте конкретно. Эта информация может быть использована при разработке сайта и размещении рекламы [10].

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

2.2 Методы поиска закономерностей

Основная задача поиска закономерностей (pattern mining) - это поиск отношений среди элементов в базе данных [10]. Ее также можно сформулировать следующим образом: в представленной базе данных D, которая содержит транзакции T1 … Tn, определить все паттерны P, которые встречаются хотя бы в S случаях. Показатель S, определяющий минимальное количество транзакций, удовлетворяющих условиям для того, чтобы паттерн был признан, называется минимальной поддержкой и может быть представлен как конкретным числом, так и долей от общего числа транзакций.

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

На данный момент уже создано множество алгоритмов для решения задач в области поиск частых последовательностей, однако исследования в этой области не закончены, и ведется активная работа по совершенствованию существующих алгоритмов. Наиболее распространенными считаются подходы двух классов: алгоритмы типа Apriori и Pattern growth, среди же алгоритмов, которые расширяют и дополняют классические подходы, можно выделить CloSpan (Closed Sequential Pattern Mining) [10].

Алгоритмы Apriori

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

Для начала необходимо определить величину поддержки - минимальное количество или процент транзакций, содержащих определенный общий набор элементов для исключения редких и неинтересных последовательностей. На первом этапе происходит просмотр базы данных и определение частоты вхождения для всех возможных одиночных элементов. Затем все элементы, которые не удовлетворяют уровню минимальной поддержки отсекаются. Следующим шагом создаются уже всевозможные двухкомпонентные наборы из частых одиночных элементов, а потом снова происходит проход по базе данных и подсчет количества вхождений для каждой комбинации уже из двух элементов. Количество повторений алгоритма зависит от размера последовательностей, которые нужно получить в конце. Таким образом, частые последовательности формируются из частых подпоследовательностей [11].

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

Алгоритмы Frequent Pattern-Growth

Главная идея алгоритма - избежать создания многочисленных кандидатов и многократно сузить область постоянного поиска последовательностей за счет трансформации базы данных в древовидную структуру - FP-дерево. Каждая вершина дерева включает в себя один элемент и количество транзакций, в которые входит данный элемент, - поддержку. В дерево попадают только те элементы, поддержка которых больше минимальной поддержки, и при построении дерева элементы сортируются именно по поддержке. Общий принцип первого этапа прост: если вершина с таким элементом уже существует, то поддержка для этого элемента увеличивается на 1, иначе создается новая вершина. Далее происходит извлечение частых закономерностей из построенного дерева. Для данного подход требует всего 2 прохода по базе данных.

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

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

2.3 Метод анализа формальных понятий для поиска закономерностей

Основным методом решения поставленной задачи является анализ формальных понятий (АФП) - раздел прикладной теории решеток, описывающий отношение между множеством объектов - объемом и множеством признаков - содержанием [12]. Отношения описываются с помощью формального контекста и формальных понятий. На первом этапе строится формальный контекст - смежная таблица, где по горизонтали перечисляются все объекты, а по вертикали - все признаки. В случае, если объект обладает соответствующим признаком, то ячейка на этом пересечении заполнена. Пример формального контекста показан в Табл. 2.1.

Таблица 2.1. Формальный контекст

	m1	m2	m3	m4	m5
g1	Ч		Ч		Ч
g2		Ч
g3	Ч			Ч
g4					Ч

С помощью контекста формируется множество формальных понятий - пар объектов и признаков (A, B), где всем объектам A соответствуют все признаки B и, наоборот, B содержит только те признаки, которые свойственны всем объектам A. Пример одного из формальных понятий из Табл. 2.1 - ({g1, g3}; {m1}).

Все формальные понятия одного контекста могут быть сравнены и иерархически упорядочены согласно отношению ?. Например, (A1, B1) ? (A2, B2) или (A1, B1) - подпонятие (A2, B2), если они относятся к одному контексту и A1 ? A2 или B1 ? B2, что соответственно. Такой упорядоченный набор всех формальных понятий контекста называется решеткой понятий данного контекста. Пример решетки понятий для формального контекста из Табл. 2.1 приведен на Рис. 2.1. Благодаря возможности построения решетки формальных понятий АФП хорошо подходит для визуализации объектно-признаковых зависимостей.

АФП применяется для решения множества практических задач. Например, на основе АФП была разработана методология по определению подозреваемых в торговле людьми [12]. Проанализировав 266 157 полицейских отчетов, ученые выделили признаки, соответствующие преступникам в области торговли людьми. Разработанный метод определения потенциальных преступников был успешно протестирован и применяется на практике [13]. АФП также используется в области анализа текста для навигации и поиска в большом объеме литературы. Например, взяв работы из одной научной области и наиболее частые поисковые запросы в этой области, с помощью построения решетки формального понятия данные были визуализированы и проанализированы, что в результате позволило улучшить навигацию в данной области [14].

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

Рисунок 2.1 Решетка формальных понятий

2.4 Методы отбора интересных паттернов

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

Другим показателем для отбора является устойчивость - доказательство того, что найденные понятия не являются случайными и не зависят от выборки, которое считается как отношение объема, чье описание совпадает с содержанием, к числу всех подмножеств понятия. Чем выше значение устойчивости, тем вероятнее, что результат действительно свойственен объектам, а не случайное сочетание [15]. Данный показатель позволяет выявить более интересные и нетипичные на первый взгляд закономерности, однако количество паттернов также может достигать большого числа.

Еще одной мерой интересности закономерностей является энтропийность. Набор можно назвать интересным, если распределение данных сильно искажено, то есть данные или крайне структурированы, или случайны. Такой подход рассматривает не только те бинарные отношения, когда связь между признаком и объектом равна 1, но и случаи, когда связь равна 0, то есть низкоэкнтропийные множества рассматривают данные симметрично и ищут связь не только среди объектов, но и среди признаков [16]. Алгоритмы, описывающие данные с точки зрения сильной зависимости между переменными, дают качественное описание данных с небольшим количеством наборов закономерностей, которые легко анализировать.

Авторы работы [17] предлагают для отбора паттернов определять независимость данного паттерна. Множество независимо, если его частота больше, чем частота какого-либо из его подмножеств или надмножеств по отдельности. Предполагается, что если паттерн не является независимым, то он представляет небольшой интерес для анализа. То есть данный подход не выбирает потенциально интересные для рассмотрения паттерны, а отсеивает потенциально неинтересные. Были получены хорошие результаты при тестировании подхода на наборе данных из нескольких тысяч транзакций, однако, когда в базе становится сотни тысяч записей, алгоритм становится вычислительно тяжелым.

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



2.5 Уточнение задачи

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

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

Помимо прочего, при определении границ исследования учитывается также тот факт, что в сфере профессионального футбола существует устойчивая система, где футболисты играют за определенный клуб, который в свою очередь входит в состав одной или нескольких лиг и, кроме того, относится к определенной стране. Таким образом, можно выделить 3 характеристики для определения положения игрока: клуб, лига, страна. Границы клуба не выходят за рамки определенных лиг и стран, другими словами, клуб всегда является подмножеством таких множеств, как лига и страна. В то время как деление по лигам часто не ограничено одной страной, а может включать в себя клубы различных стран, то есть лига не всегда является подмножеством одной страны.

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

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



Глава 3. Практическая часть

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

3.1 Подготовка данных

В основе исследования лежит база данных переходов футболистов между клубами с 1996 по 2017 года, которая включает в себя 501 650 записей для 96 384 игроков. Структура базы данных представлена в Табл. 3.1.

Таблица 3.1 Структура базы данных

Поле	Описание
Player_ID	Идентификатор игрока
Date	Дата перехода
Type	Тип игрока
Age	Возраст игрока
FromClub	Название предыдущего клуба
FromType	Название предыдущей лиги
FromCountry	Название страны предыдущего клуба
ToClub	Название нового клуба
ToType	Название новой лиги
ToCountry	Название страны нового клуба
Fee	Размер компенсации

За тот период, который покрывает база данных, некоторые футбольные клубы были переименованы, название отдельных клубов менялось более 1 раза. Этот факт может повлиять на результаты работы, так как подразумевается, что каждое отличное название клуба означает 1 уникальный футбольный клуб. Однако в исходных данных имеется сводная таблица, часть которой показан в Табл. 3.2, где собраны все встречающиеся вариации названий различных клубов. Таким образом, для решения данной проблемы достаточно заменить в основной базе данных все различные варианты названий одного клуба на исходное на основе имеющейся информации из второй таблицы.

Таблица 3.2 Изменения в названиях клубов

№	team_long_name	league_name	club1	club2
1.	Tubize	Belgium Jupiler League	AFC Tubize Belgium	AFC Tubize Jupiler Pro League
2.	FCV_Dender_EH	Belgium Jupiler League	FCV Dender EH Belgium	FCV Dender EH Jupiler Pro League
3.	KV_Mechelen	Belgium Jupiler League	KV Mechelen Belgium	KV Mechelen Jupiler Pro League
4.	Club_Bruges	Belgium Jupiler League	Club Brugge Belgium	Club Brugge Jupiler Pro League
5.	Kortrijk	Belgium Jupiler League	KV Kortrijk Belgium	KV Kortrijk Jupiler Pro League
…	…	…	…	…

На первом этапе анализа необходимо подготовить данные, на основе которых осуществляется поиск закономерностей, для этого необходимо привести их к определенному виду, который подходит для обработки приложением FCAPS. В Приложении А приведен пример файла данных для программы, состоящий из 3 частей, которые необходимо сформировать: множество объектов, множество признаков и список признаков для каждого объекта. На основе данного файла и заданных настроек приложение FCAPS может построить наборы закономерностей в виде решеток формальных понятий. Рассмотрим подробнее процесс формирования каждой из частей файла.

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

Так как поиск паттернов осуществляется на нескольких уровнях и множествах, необходимо подготовить различные наборы данных, которые будут являться множествами признаков при построении решеток. Описание базовых наборов признаков для рассмотрения трансферов на разных уровнях приведено в Табл. 3.3.

При рассмотрении базы данных были выявлены две тенденции:

· Название лиги часто совпадают с названием страны.

· В разных странах лиги могут иметь одинаковое название.

Во избежание неоднозначных ситуаций и для более удобного анализа обозначение лиги сформировано из названия лиги и страны, например, "Ligue I Pro Tunisia".

Для формирования всех наборов признаков применяется общий принцип создания вектора уникальных значений путем прохода по соответствующим столбцам таблицы и проверки, включено ли значение в вектор или еще нет. При создании множеств признаков, которые являются переходом и включают в себя сочетание двух элементов из таблицы, значения сначала объединяются в одну запись и после этого проверяются на наличие в формирующемся списке. Пример функции приведен в Приложении B, функция "buildAttributesSet".

Таблица 3.3 Описание наборов данных

№	Название	Описание	Общий вид элемента	Пример элемента
1.1	clubs_mix	Список всех клубов, встречающихся в таблице	Название_клуба	Badgers
1.2	types_mix	Список всех лиг, встречающихся в таблице	Название_лиги	Premier League
1.3	countries_mix	Список всех стран, где совершались трансферы	Название_страны	England
2.1	from_to_clubs_mix	Список всех встречающихся переходов игроков из клуба в клуб	Название_старого_клуба - название_нового_клуба	Los Angeles - Houston
2.2	from_to_types_mix	Список всех встречающихся переходов футболистов из лиги в лигу	Название_старой_лиги - название_новой_лиги	League One England - England England
2.3	from_to_countries_mix	Список всех встречающихся переходов игроков из одной страны в другую	Название_старой_страны - название_новой_страны	Monaco - Switzerland
3.1	from_clubs_to_types	Список всех вариаций переходов из клуба одной лиги в другую лигу	Название_старого_клуба - название_новой_лиги	Los Angeles - MLS
3.2	from_types_to_clubs	Список всех вариаций переходов из одной лиги в клуб другой лиги	Название_старой_лиги - название_нового_клуба	MLS - Houston
3.3	from_clubs to_countries	Список всех вариаций переходов из клуба одной страны в любой клуб другую страну	Название_старого_клуба - название_новой_страны	Crewe Alexandra - Iceland
3.4	from_countries to_clubs	Список всех вариаций переходов из одной страны в клуб другой страны	Название_старой_страны - название_нового_клуба	England - Dunbee FC

Третьим необходимым для построения решетки формальных понятий элементом является множество формальных понятий, которые состоят из одного объекта и набора признаков, соответствующих ему. Для этого необходимо сформировать для каждого игрока вектор индексов признаков, которые соответствуют ему. Пример функции приведен в Приложении B, функция "buildConcepts". В результате получается список векторов, количество которых равно количеству всех игроков.

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

3.2 Выявление и проверка закономерностей на устойчивость

Для отбора наиболее интересных последовательностей был выбран Аппарат узорных структур, который расширяет методы АФП и дает возможность работать с более сложными типами данных, например с последовательностями. Описание применяемого метода представлено в [13].

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

Результатом тестирования каждого набора данных является следующая информация о наиболее интересных паттернах:

· Количество и название объектов, которым свойственен данный паттерн.

· Количество и название признаков, которые входят в паттерн.

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

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

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

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

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

База данных содержит 600 различных лиг. Во время проведения эксперимента было найдено значительное количество паттернов длиной 2-4 лиги, которые имеют хорошие показатели по количеству футболистов, побывавших в данной лиге и дельта-меру. Например, объем формального понятия “Indonesia, Cote d'Ivoire” включает в себя 131 игрока, что почти равно его дельта-мере - 115, это можно интерпретировать как факт, что практически все футболисты, игравшие в одной лиге, были и в другой лиге. Кроме того, нельзя добавить дополнительной информации к этой закономерности без потери 115 объектов.

Встречаются также и отдельные закономерности длиной 5 элементов, например, цепочка «Tunisia, BGL Ligue, Kuwait, 2 B - Grupo IV, Paraguay». Данная последовательность составлена на основе подпоследовательностей, которые также являются устойчивыми, начиная с формального понятия с содержанием из 1 признака. На Рис. 3.1 приведен пример полученной решетки для трех футбольных лиг: Tunisia, Kuwait, BGL Ligue. Как видно, связь хорошо просматривается: количество игроков (extent) на каждом новом уровне меньше, чем на предыдущем. Однако дельта-мера (In) для большинства элементов является не лучшей, поэтому данное понятие может быть интересным, но не самым устойчивым. Стоит также добавить, что в данном случае получился трехмерный граф, однако форма решетки зависит от имеющихся в формальном понятии сочетании признаков и может быть представлена самыми различными формами.

Рисунок 3.1. Решетка формального понятия

Таким образом, предположение о том, что на уровне лиг закономерности просматриваются лучше, подтвердилось. Наибольшее число игроков в одной лиге зафиксировано в лиге "Primavera C", где за все время поиграли 9 236 футболистов, что примерно равно 10% от всего числа игроков. Ниболее же популярным сочетанием 2 лиг являются "Primavera C" и "Turkey", которые имеют 2 017 общих футболистов. Результаты данного эксперимента получились значимыми, не смотря на то, что количество игроков, которые были замечаны в двух лигах, обычно не превышает 2% от общего числа футболистов.

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

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

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

Поиск закономерностей как множества переходов между клубами

На следующем шаге в качестве признаков формальных понятий берется сочетание двух элементов одного уровня, между которыми совершался переход, например "клуб - клуб". Здесь уже важен не тот факт, что футболист был в данном клубе, а то, откуда он в него попал, а также куда потом из него перешел.

При подготовке признаков типа "клуб клуб" было получено 278 680 различных вариантов при общем количестве уникальных клубов 24 037. По причине наличия такого количества признаков итоговый набор данных получился большим, что привело к невозможности завершить проверку. Связано это с тем, что поиск устойчивых закономерностей с помощью приложения FCAPS предполагает загрузку всего массива в оперативную память, и при выполнении обработки текущего множества ресурсов памяти оказалось недостаточно.