Курсовая работа (т): Построение математической модели для использования в различных ситуациях в рамках анализа данных о госзакупках

Построение математической модели для использования в различных ситуациях в рамках анализа данных о госзакупках

1. Актуальность открытых данных

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

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

Открытые данные - информация о деятельности государственных органов и органов местного самоуправления, размещенная в сети Интернет в формате, обеспечивающем ее автоматическую обработку в целях повторного использования без предварительного изменения человеком (информация должна иметь единый машиночитаемый формат). Эта информация может свободно использоваться в любых соответствующих закону целях любыми лицами независимо от формы ее размещения [12].

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

Когда мы смотрим на это более системно, и эти же данные у нас доступны в виде цельной базы, то мы можем не просто посмотреть информацию по конкретному случаю. Мы можем взять какую-нибудь определенную тему, взять любой город или муниципальный район и узнать всю карту госрасходов по всем учреждениям. Потом это можно наложить на карту, узнать, как устроены госрасходы вокруг вас, а также вы можете физически сходить туда и посмотреть, что там на самом деле делается» [10].

В ходе работы рассматривается набор данных [14], который содержат информацию о расходах бюджетных организаций в России за 2015 год (с января по октябрь) в рамках государственных закупок, проводимых в соответствии с федеральным законом ФЗ № 44[1]. Кстати, стоит отметить, что российские данные в секторе госзакупок имеют значительно более высокий уровень открытости, чем в большинстве западных стран. Однако в целом Россия занимает пока лишь 119 место (2015 г.) в рейтинге ИВК (индекс восприятия коррупции), опубликованным международной антикоррупционной организацией Transperancy International. Все же положительная динамика по раскрытию информации присутствует, поскольку страна сделала большие шаги в области раскрытия данных благодаря пропаганде открытых данных, хоть и лимитированной, но существующей государственной политике, а в основном за счет естественного хода автоматизации власти в условиях рыночной экономики [11]. К раскрытию и публикации данных в свободном доступе обязывает, в частности, ФЗ № 44. Далее опишем сферу распространения данного закона.

Федеральный закон № 44 - это ФЗ от 05.04.2013 “О контрактной системе в сфере закупок, товаров, услуг для обеспечения государственных и муниципальных нужд”. Данный закон регулирует отношения, направленные на обеспечение государственных и муниципальных нужд в целях повышения эффективности, результативности осуществления закупок товаров, работ услуг, обеспечения гласности и прозрачности осуществления этих закупок, предотвращения коррупции и других злоупотреблений в сфере данных закупок. Закон имеет широкую сферу применения, включая [1, гл. 1, ст.1]:

1) планирование закупок товаров, работ, услуг;

) определение поставщиков (подрядчиков, исполнителей);

) заключение гражданско-правового договора, предметом которого являются поставка товара, выполнение работы, оказание услуги (в том числе приобретение недвижимого имущества или аренда имущества), от имени Российской Федерации, субъекта Российской Федерации или муниципального образования, а также бюджетного учреждения согласно частям 1, 4 и 5 статьи 15 настоящего Федерального закона;

) особенности исполнения контрактов;

) мониторинг закупок товаров, работ, услуг;

) аудит в сфере закупок товаров, работ, услуг;

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

Документ имеет достаточно сложную историю принятия, он был принят Госдумой в третьем чтении 22.03.2013. За двухлетнюю редакцию в закон было внесено более 800 поправок. В конечном счете, на смену ФЗ № 94 пришла новая контрактная система, более понятная и открытая, обеспечивающая широкие возможности для общественного контроля.

Сформулируем основные цели работы:

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

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

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

1.1 Выявление выбросов

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

Существует три основные причины возникновения выбросов [6].

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

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

Основные типы выбросов:

)        Точечные выбросы

Самый легко определимый тип выброса. Точка считается выбросам, если она «аномально» располагается по сравнению с остальными точками выборки.

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

)        Контекстные выбросы

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

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

)        Массовые выбросы

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

Наличие выбросов также связано с распределением данных. Если данные распределены по нормальному закону распределения, то по «правилу трех сигм» каждое 375-ое значение будет отличаться от стандартного отклонения в 3 раза (а каждое 22-ое - в 2 раза).

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

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

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

где нижняя (25-ая) и верхняя (75-ая) квантили.

Значение k=1.5 указывает на выброс, а k=3 на «хвосты» выборки.

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

Способ обработки выбросов зависит от того, каких целей хочет достичь исследователь.

)        Сохранение

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

)        Исключение

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

)        Негауссовские распределения

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

.2 Методы кластеризации

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

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

Цели кластеризации:

·        Понять структуру множества объектов , разбив это множество на группы схожих объектов

·        Выделить нетипичные объекты, которые не схожи ни с одним из выделенных кластеров

Алгоритмы кластеризации можно условно разбить на две классификации

·        Иерархические и плоские

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

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

·        Четкие и нечеткие

Четкие (непересекающиеся) алгоритмы [3] каждому объекту выборки сопоставляют номер кластера, т.е. получается сюръективное отображение. Нечеткие (соответственно, пересекающиеся) алгоритмы каждому объекту ставят в соответствие некий набор вещественных значений, отражающих вероятность объекта быть отнесенным к определенному кластеру.

Прежде чем перейти к основным алгоритмам кластеризации стоит описать требования к входным данным:

)        Признаковые характеристики объектов

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

)        Матрица расстояний

Квадратная матрица, которая отражает расстояние между объектами метрического пространства.

)        Матрица сходства

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

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

)        Иерархическая кластеризация

)        Кластеризация с выбором центроидов

В данном виде кластеризации каждый кластер имеет свой центр (причем этот центр-вектор не обязательно должен являться каким-либо объектом выборки). При фиксированном числе кластеров k можно формально сформулировать задачу: найти k центров кластеров и присвоить объекты этим кластером так, чтобы квадрат расстояния от центра до объекта было минимальным:

где число кластеров, - полученные кластеры, центроиды кластеров.

Самой известной реализацией является алгоритм k-means, разработанный в середине 20 века одновременно Гуго Штейнхайзом и Стюардом Ллойдом. Основным недостатком является необходимость заранее указать число кластеров, также результат кластеризации очень сильно зависит от начального выбора центроидов, поэтому усовершенствованные алгоритмы повторяют алгоритм несколько раз, затем выбирая наилучшую реализации.

)        Кластеризация на основе распределения

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

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