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

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

В алгоритмах данного типа кластеры определяются как области с наиболее высокой плотностью по сравнению с остальной частью набора данных. Самым популярным представителем данного класса является алгоритм DBSCAN [7]. Большинство алгоритмов, основанных на плоском разбиении, создают кластеры приблизительно сферической формы, поскольку минимизируют расстояние от объектов до центров кластеров. Экспериментальным путем показано, что алгоритм DBSCAN распознает кластеры различной формы. Идея алгоритма формулируется следующим образом: каждый кластер имеют некую плотность, причем плотность объектов внутри кластера выше, чем плотность объектов снаружи, а плотность в областях с шумовыми данными ниже, чем плотности любого кластера. Более того для каждой точки кластера её соседство заданного радиуса  должно содержать не менее некоторого порогового числа точек. Для работы данному алгоритму не требуется указывать число кластеров, однако нужно указать -окрестность и пороговое значение для числа точек, входящих в указанную окрестность.

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

2. Описание данных

.1 Содержание исходного набора данных

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

Все контракты, как уже было сказано ранее, проведены в соответствии с 44 ФЗ.

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

В рассматриваемом наборе данных все контракты объединены по подкатегориям.

Таблица 2.1. Пример иерархии кода на примере 22 класса

Класс	22	Продукция печатная и носители информации записанные
Подкласс	22.1	Книги, газеты и прочие материалы печатные и носители информации записанные
Группа	22.14	Звукозаписи
Подгруппа	22.14.1	Грампластинки, ленты, компакт-диски (CD), видео-диски цифровые (DVD) и прочие носители для записи звука
Вид	22.14.12	Ленты магнитные только со звукозаписью
Категория	22.14.12.110	Ленты магнитные записанные шириной не более 4 мм
Подкатегория	22.14.12.111	Ленты магнитные записанные шириной не более 4 мм в кассетах

Ссылка на данные: <#"896825.files/image015.jpg">

Рис 2.1. Гистограмма размера файлов, содержащихся в наборе данных

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

Рис. 2.2. Пример содержания файла (первые 3 строки)

2.2 Обработка и очистка

Из каждого файла выделена релевантная информация - код региона, сумма контракта, ИНН заказчика, ИНН поставщика.

Информация сгруппирована в 62 группы в соответствии с классами ОКПД, встречающимися в наборе данных (первые 2 цифры кода ОКПД, являющегося именем файла). Заметим, что классы с номерами от 1 до 50 описывают товары, а с 50 до 99 - услуги.

В ходе подготовки данных к дальнейшему анализу были выполнены следующие действия:

)        Удаление незначимых файлов, размер которых - 228 КБ (они содержат только строку с описанием полей). После удаления осталось 21016 файлов.

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

Рис. 2.3. Пример строки c разрывом

)        Данные считаны с условием уникальности реестрового номера контракта. То есть не принимались во внимание так называемые строки-дубликаты.

Рис. 2.4. Пример строк-дубликатов

4)      Некоторые сделки проводились по устаревшим кодам регионов.

Такие коды заменены на те, которые актуальны сейчас.

Таблица 2.2. Соответствие старых кодов субъектов РФ действующим

Старый код	Действующий код субъекта	Наименование субъекта РФ
80	75	Забайкальский край
81	59	Пермский край
82	91
85	38	Иркутская область
88	24	Красноярский край
93	23	Краснодарский край
97, 99	77	Москва

.3 Итоговый набор данных

После обработки данных получены:

Матрица  - суммарная стоимость договоров (контрактов), заключенных в каждом из 86 регионов для каждого представленного класса классификатора (из перечня в 100 различных категорий контракты заключены по 62 категориям товаров/услуг).

Число различных поставщиков и покупателей товаров/услуг в каждом регионе.

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

3. Математическая модель

На основе обработанных данных может быть построено несколько моделей.

.1 Прямоугольная вещественнозначная матрица

После обработки данных получена прямоугольная вещественная матрица . Данная матрица отражает информацию о суммарной стоимости контрактов, заключенных в m регионах (напомним, что m=86) для n классов классификатора ОКПД (все контракты проведены по 62 различным кодам классификатора). Итак, полученная матрица состоит из m n-мерных векторов.

Элементы матрицы имеют сильный разброс в диапазоне от 0 до  рублей. Такой большой диапазон может создать проблемы для дальнейшего анализа данных. Тем более что некоторые классификаторы являются «популярными» и по ним проводятся частые и большие объемы закупок, как, например, по классификатору с кодом 45. В то же время код классификатора 12 (Руды урановые и ториевые) содержит очень редкие закупки на небольшие суммы. В связи с вышеописанным важно каким-то образом уравнять вклад этих величин и произвести нормировку данных. Нормировка данных - это процесс изменения исходных данных и приведения их к безразмерному виду. Данный процесс приводит к повышению качества данных.

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

)        Нормировка по регионам

Для любого региона нахождение доли участия каждого классификатора в формировании суммы стоимости контрактов в регионе i.

)        Нормировка по кодам классификатора

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

)        Нормировка по численности регионов

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

Также можно рассмотреть стандартные способы нормирования данных [13]:

)        Мини-максная линейная нормализация

где - минимальное и максимальное значения затрат для каждого региона i в векторе .

Эта нормализация приводит все данные к значениям в диапазоне .

)        Приведение к распределению вида N[0,1] (стандартизация данных)

где матем. ожидание,

среднеквадратическое отклонение вектора .

)        Нелинейная нормализация

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

.2 Квадратная матрица расстояний

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

Рассмотрим самые распространённые метрики:

)        Евклидово расстояние

Самая распространённая метрика - представляет собой геометрическое расстояние в многомерном пространстве.

)        Метрика Минковского

Так называемое степенное расстояние. В данном случае r отвечает за взвешивание больших разностей расстояний, а р - за взвешивание разностей по координатам. Отметим, что при r,p=2 совпадает с расстоянием Евклида.

)        Манхэттэнская метрика

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

)        Косинусное сходство

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

)        Расстояние Хэмминга

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

3.3 Граф близости

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

Вышеописанные модели универсальны в рамках рассматриваемой задачи.

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

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

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

4. Вычислительные эксперименты

.1. Выбросы

Итак, определим нетипичные регионы, отличающиеся своим «поведением» от остальных.

Отнормируем вещественнозначную матрицу  по регионам. Далее, для каждого классификатора определим 25- и 75- процентиль, с помощью которых будет образован интервал по статистике Тьюки. Значения, не вошедшие в этот интервал, отмечены на Рис. 4.5 значениями 1. Далее для каждого региона просуммируем все значения полученной матрицы в соответствующей строке и получим число отклонений (нетипичных поведения) от типичного поведения в том или ином классификаторе. Выделим первые 7 субъектов, показавшие наибольшее число отклонений.

Ими являются:

Москва (отклонения в 22 классификаторах),

Приморский край (11),

Республика Саха (Якутия) (10),

Красноярский край (10),

Республика Татарстан (9),

Алтайский край (9).

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

Рис. 4.1. Нахождение выбросов с помощью статистики Тьюки

алгоритм кластеризация файл матрица

Найдем выбросы вторым способом. Сделаем это с помощью матрицы расстояний , посчитанной сначала по Евклидовой метрике (), а потом с помощью Манхэттенского расстояния ( из отнормированной по регионам вещественнозначной матрицы. Естественно, что эта матрица расстояний симметрична относительно главной диагонали, а на этой диагонали стоят 0.

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

Рис. 4.2. Минимальные расстояния для регионов в матрице расстояний с Евклидовой (слева) и Манхэттенской (справа) метриками

Теперь необходимо проанализировать полученные результаты. Как и ожидалось, каждый метод определил разный набор субъектов РФ, претендующих на право называться «выбросами». Отметим, что среди всех наборов присутствует Севастополь (92 регион). Его мы точно отнесем к выбросам.

Практическим путем было выявлено, что нетипичными являются в среднем около 8 регионов (в среднем такое число регионов ведет себя нетипичным образом на различных тестах данного набора). Поэтому сформируем список выбросов, включив в него топ-3 первых регионов из каждого метода.

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

Краснодарский край (23 регион);

Приморский край (25);

Москва (77);

Ненецкий автономный округ (83);

Таймырский Долгано-Ненецкий район (84);

Республика Крым (91);

Севастополь (92).

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

.2 Кластеры

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

Для начала создадим граф близости. Для этого из матрицы евклидовых расстояний оставим 5 ближайших расстояний от каждой вершины до каждой. Выделим центральные компоненты и получим следующий граф (рис. 4.3). Центральные компоненты отражают влияние региона на все остальные. Чем больше вершина, тем больше ее центральная компонента.

Рис 4.3. Граф близости по топ-5 вершин для Евклидового расстояния

Немного изменим масштаб, чтобы отчетливее были видны компоненты.

Рис 4.4. Граф близости по топ-5 вершин для Евклидового расстояния (другой масштаб)

В данном случае особо выделяются Пермский край, Бурятия и Тыва.

Построив дендограмму и определив, что число кластеров = 5 представляется оптимальным, отобразим регионы, объединенные в кластеры по алгоритму k-means.

Рис. 4.5. Распределение регионов по группам

Можно заметить явное сходство рис. 4.6 и 4.8, так как 4.8 - это примерное вертикальное разбиение 4.6 и 4.7.

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

Заключение

В ходе работы был рассмотрен большой набор открытых данных, состоящий из примерно 39000 файлов и содержащий информацию о госзакупках, проводимых в соответствии с ФЗ № 44. После обработки и отчистки данных посчитана вполне обозримая матрица , элементы которой - общая стоимость договоров (контрактов), заключенных в каждом из 86 регионов для каждого из 62 представленных классов классификатора. Описаны теоретические подходы к выделению выбросов и разбиению объектов на кластеры с различными способами нормировки данных и с использованием различных метрик для подсчета меры близости (расстояния). Построены математические модели, позволяющие проанализировать выборку с помощью вещественнозначной матрицы расстояний, прямоугольных матрицы расстояния и графа близости. Эти модели использованы для нахождения выбросов и разбиения оставшихся субъектов РФ на похожие группы.

Завершает работу экспериментальная часть, в которой выделяется 7 субъектов РФ, поведение которых существенно отличается от остальной выборки. В число этих субъектов входят Севастополь и Крым, присоединившиеся лишь в марте 2014 года. Естественно, что судьба этих регионов складывается нетипичным по сравнению с остальными субъектами путем. Также в число нетипичных субъектов входят Москва (политический центр страны), Красноярский и Приморский края, Ненецкий автономный округ (самый малонаселенный субъект РФ) и Таймырский Долгано-Ненецкий район (самый большой по площади район). После исключения вышеописанных регионов из дальнейшего анализа была проведена кластеризация, в ходе которой оставшиеся субъекты были разбиты на 5 групп, одна из которых включает все субъекты, являющиеся центральными компонентами графа близости, т.е. эта группа самая значимая среди остальных. Стоит отметить, что построенные математические модели применимы для неоднократного использования в различных ситуациях в рамках анализа данных о госзакупках.

Список используемой литературы

[1] Федеральный закон от 05.04.2013 N 44-ФЗ (ред. от 05.04.2016) "О контрактной системе в сфере закупок товаров, работ, услуг для обеспечения государственных и муниципальных нужд".

[2] Общероссийский классификатор продукции по видам экономической деятельности ОК 034-2007 (КПЕС 2002).

[3] Бериков, В. С. Всероссийский конкурсный отбор обзорно-аналитических статей по приоритетному направлению «Информационно-телекоммуникационные системы». - 2008. - 26 с.

[4] Низаметдинов, Ш.У. Анализ данных: учебное пособие / Ш.У. Низаметдинов, В.П. Румянцев. - М. МИФИ, 2012. - 288с.

[5] Bolstad, B.M. A comparison of normalization methods for high density oligonucleotide array data based on variance and bias / B.M. Bolstad <http://bioinformatics.oxfordjournals.org/search?author1=B.M.+Bolstad&sortspec=date&submit=Submit> et al. // Bioinformatics, 2003, vol. 19, no. 2, pp. 185-193.

[6] Grubbs, F. E. Procedures for detecting outlying observations in sample / F. E. Grubbs // Technometrics, 1969, vol. 11, no. 1, pp. 1-21. doi <https://en.wikipedia.org/wiki/Digital_object_identifier>: 10.1080/00401706.1969.10490657 <https://dx.doi.org/10.1080%2F00401706.1969.10490657>.

[7] Martin, E. A density-based algorithm for discovering clusters in large spatial databases with noise / E. Martin et al. // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), pp. 226-231.

[8] Ripley, Brian D. Robust statistics <http://www.stats.ox.ac.uk/pub/StatMeth/Robust.pdf>. / Brain D. Ripley // M.Sc. in Applied Statistics MT2004, 2004, pp. 1-11.

[9] Zimek, A. A survey on unsupervised outlier detection in high-dimensional numerical data / A. Zimek, E. Schubert, H.-P. Kriegel // Statistical Analysis and Data Mining, 2012, vol. 5, no. 5, pp. 363-387. doi <https://en.wikipedia.org/wiki/Digital_object_identifier>:10.1002/sam.11161 <https://dx.doi.org/10.1002%2Fsam.11161>.

[10] Бегтин И. Открытые данные - это возможность понять, как устроено наше государство [Электронный ресурс] // polit.ru - электронное СМИ. 2015. 11 декабря.

[11] Бегтин И. Открытые данные против коррупции: в чем Россия перегнала Запад [Электронный ресурс] // РБК - электронное СМИ. 2016. 27 января. (дата обращения: 20.05.2016).

[12] Информационная открытость. Открытые данные [Электронный ресурс] // ar.gov.ru - портал административной реформы.

[13] CSV файлы для хакатона [Электронный ресурс] // 2015. 7 ноября.

Приложение 1

Описание полей файлов

)        Уникальный реестровый номер контракта regNum. Длина этого номера фиксирована и всегда равна 19 символов от 0 до 9.

)        Дата заключения контракта signDate. Имеет формат ГГГГ-ММ-ДД ЧЧ:ММ:СС.

3)      Price - цена контракта (руб.).

)        Fz - номер федерального закона, по которому был заключен контракт.

Напомним, что все контракты в этих файлах заключены в рамках государственных закупок, проводимых в соответствии с федеральным законом ФЗ № 44. Поэтому в данных файлах Fz всегда 44.

)        Код региона РФ regionCode - это число от 1 до 92, которое соответствует полному названию региона.

)        Название заказчика госконтракта customer_name. Описывается строкой - полное наименование заказчика.

)        ИНН заказчика госконтракта customer_inn. Состоит из 10 символов от 0 до 9.

)        КПП заказчика госконтракта customer_kpp. Также состоит из 10 символов от 0 до 9.

)        Название поставщика госконтракта supplier_name. Описывается строкой - полное наименование поставщика.

)        ИНН поставщика госконтракта supplier_inn. Состоит из 10 символов от 0 до 9.

)        КПП поставщика госконтракта supplier_kpp. Также состоит из 10 символов от 0 до 9.

)        Код единицы измерения OKEI_code. Отражает количество купленных единиц товара / услуги.

)        Название единицы измерения OKEI_name. Например, ШТ, КГ, Т, ЧЕЛ и т.д.

)        Код ОКПД предмета закупки OKPD/OKDP_code. Для каждого файла уникален и совпадает с именем файла.

)        Цена (руб.) предмета контракта product_sum.

)        Цена (руб.) за 1 единицу измерения продукции product_price.

)        Число единиц продукции в контракте product_quantity.

)        Link - ссылка на запись контракта в clearspending.ru.