Санкт-Петербургский Государственный Университет
Направление Математическое Обеспечение и Администрирование
Информационных Систем
Профиль Информационные Системы и Базы Данных
Вахрушев Артем Андреевич
Прогнозирование уровня преступности на
основе статистических данных
Магистерская диссертация
Научный руководитель:
к. ф.-м. н., доцент Графеефа Н. Г.
Рецензент:
ИТ эксперт Денисенко А. В.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Main Field of Study Program Software and Administration of Information
Systems
Area of Specialisation Information Systems and Databases
Vakhrushev Artem
Crime rate prediction based on statistics
Master’s Thesis
Scientific supervisor:
docent Grafeeva Natalia
Reviewer:
IT expert Denisenko Aleksandr
Saint-Petersburg
2016
Оглавление
Введение
4
1. Обзор существующих работ
6
2. Постановка задачи
7
3. Обзор методов предсказания временных рядов
3.1. Регрессионные модели . . . . . . . . . . . . . . .
3.2. Линейная авторегрессия . . . . . . . . . . . . . .
3.3. Модели экспоненциального сглаживания . . . .
3.4. Нейросетевые модели . . . . . . . . . . . . . . . .
3.5. Модели на основе цепей Маркова . . . . . . . . .
.
.
.
.
.
8
8
9
11
12
14
.
.
.
.
16
16
17
23
25
5. Построение моделей прогнозирования
5.1. Описание моделей . . . . . . . . . . . . . . . . . . . . . . .
5.2. Построение моделей предсказания преступности . . . . .
5.3. Задача классификации . . . . . . . . . . . . . . . . . . . .
27
28
31
32
Заключение
35
Список литературы
36
4. Описание и предварительный анализ данных
4.1. Описание данных . . . . . . . . . . . . . . . . .
4.2. Визуализация аггрегированных данных . . . .
4.3. Связь температуры и числа преступлений . . .
4.4. Географические температурные карты . . . . .
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Введение
Сегодня проблема снижения уровня преступности стоит очень остро. С давних времен существуют государственные структуры, которые занимаются розыском и поимкой преступников, а также стремятся
предотвратить преступления. В современном мире технологий очень
развиты системы видеонаблюдения, которые позволяют быстро разыскать человека, совершившего преступление, а методы криминалистики
практически не оставляют преступнику шансов уйти от правосудия,
даже если он не попал в объективы камер. Но гораздо лучше, если
благодяря действию правоохранительных органов преступление не прозошло вовсе. Благодаря развитию информационных технологий уже
существует несколько экспериментальных систем, позволяющих предсказывать вспышки числа преступлений в том или ином районе города.
Но пока эти системы распространены только в развитых странах мира,
таких, например, как США или Великобритания.
В настоящей работе планируется разработать методы предсказания
преступлений. В качестве данных для построения моделей используются реальные данные о преступлениях в городе Чикаго. Эти данные
содержат подробное описание каждого преступления произошедшего в
период с 2001 по 2015 года. Такое детальное описание позволяет заметить закономерности, которое не так очевидны, узнать когда, где и
каких преступлений происходит больше, тем самым, возможно, придумать модели, которые позволят заранее узнать о том, куда стоит
направить дополнительный патруль.
Структура работы имеет следующий вид. В 1 главе приводится обзор существующих работ по предсказанию преступности. Для построения прогнозов авторы данных работ применяют методы анализа временных рядов, но в своих прогнозах они опираются только на исторические данные о преступности и не учитывают влияние различных
внешних факторов. В главе 2 формируются основные цели и задачи исследования, а именно построения качаственных прогнозов уровня преступности. В главе 3 приводится описание наиболее популярных моде4
лей анализа временных рядов, таких как регрессионные модели, авторегрессионные модели, модели экспоненциального сглаживания, нейросетевые модели и модели на основе марковских цепей. Глава 4 посвящена подробной визуализации данных и построению интерактивных карт
преступности, которые позволяют наглядно представить данные о самых опасных районах и улицах города. В главе 5 на основе найденных
закономерностей подбираются алгоритмы для построения прогнозов,
строятся сами прогнозы и приводятся их оценки. Далее задача восстановления временного ряда сводится к задаче классификации для определения наиболее опасных дней с точки зрения количества преступлений. Данная задача решается поредством построения нейросетевой
модели.
5
1. Обзор существующих работ
Основная литература, посвященная анализу данных, на основе которого строятся модели предсказания уровня преступности являются
англоязычными. Вероятно, это связано с тем, что в анализ данных на
современном этапе больше всего развит в США, а также именно в Штатах в открытом доступе можно найти официальные массивы данных
полиции о преступности.
В современном мире очень остро стоит проблема безопасности, поэтому уровень преступности является важным фактором, например,
при выборе места для переезда, выборе жилья или просто выборе ресторана для ужина в том или ином районе города. На предсказание уровня
преступности влияет множество факторов разного рода, поэтому эта
проблема находит свое отражение в научных работах ученых разных
направлений. Так в работе ”Predicting crime: a review of the research”
[1] исследуется влияние демографических, экономических, психологических и других факторов на уровень преступности. Также в данной
работе представлен обзор методов прогнозирования, однако самих прогнозов не делается.
В работе ”Forecasting Crime: A City Level Analysis” [2] строятся линейные регрессионные модели прогнозирования числа убийств в городах США. Работа ”Predicting Crime” [3] использует методы предсказания рыночных временных рядов для предсказания преступности. В
этих двух работах модели основаны исключительно на исторических
данных о преступности и не учитывают различные внешние факторы,
которые могли бы помочь улучшить прогноз, а сами прогнозы строятся
лишь по определенному виду преступления.
Как видно, основным средством для прогнозирования преступности
являются методы анализа временных рядов. Так же для улучшения
качества прогноза могут быть применены различные внешние факторы,
которые оказывают влияние на число преступлений.
6
2. Постановка задачи
Целью настоящей работы является построение качественных прогнозов уровня преступности в городе Чикаго, на основании которых
могут быть определы неблагоприятные дни, в которые число преступлений значительно превосходит средний уровень.
Для этого приводится описание наиболее известных моделей прогнозирования, исследуется взаимосвязь количества преступлений и различных внешних факторов (например, дня недели или погодных условий). Также на основании найденных данных приводится подробная визуализация - графики и таблицы, которые отражают наиболее опасное
время суток, дни недели и месяцы в году, в которые необходимо усиливать полицейский контроль на улицах города. Помимо этого строятся
интерактивные карты, которые легко позволяют найти наиболее опасные районы и улицы города. На основе полученных закономерностей
строятся модели прогнозирования уровня преступности, которые учитывают как исторические данные по преступлениям так и различные
внешние факторы. Приводятся оценки точности полученных результатов, которые позволяют судить о качестве прогнозов.
7
3. Обзор методов предсказания временных
рядов
В классическом определении временным рядом называется совокупность измерений y1 , y2 , . . . , yn , . . ., где yi ∈ IR некоторой величины через
определенные (часто равные) промежутки времени.
Задача предсказания временного ряда записывается следующим образом:
ŷt+d = ft (y1 , y2 , ..., yt ; α, z),
где ŷt+d - предсказанное значение искомой величины в некоторый момент в будущем, α - параметр модели, а z - другие факторы влияющие
на измеряемую величину [4]. То есть требуется найти некоторую функцию ft , которая на основании предыдущих значений временного ряда и,
возможно, других факторов будет предсказывать следующие его значения.
Основные явления, которые могут наблюдаться во временных рядах:
• Тренды
• Сезонности
• Смена модели
Далее представлен обзор наиболее распространенных методов предсказания временных рядов.
3.1. Регрессионные модели
Часто на предсказываемую величину оказывают действия множество сторонних факторов. Так целью регрессионного анализа для прогнозирования временных рядов является построение некоторой функциональной зависимости между прогнозируемой величиной и этими
факторами [5]. Самый простой вариант регрессионной модели - это линейная регрессия. Суть данного метода очень проста. Имеется неко8
торая переменная x, и мы пытаемся предсказать значение временного
ряда yt на основе значения этой переменной:
yt = α0 + α1 xt + ϵt ,
где α0 и α1 коэффициенты регрессии; ϵt ошибка модели.
Когда имеется несколько факторов влияющих на модель, то используется множественная регрессия:
yt = α 0 +
n
∑
αi xit + ϵt
i=1
Если значения временного ряда имеют нелинейную зависимость от
факторов, то стоит применять нелинейную регрессию:
yt = F (xt , α) + ϵt
где F - функция, которая, как мы предполагаем, хорошо описывает взаимосвязь между значениями факторов и значениями временного ряда,
а α, xt вектора коэффициентов и факторов соответсвенно.
Коэффициенты модели подбираются на основе имеющихся данных
путем минимизации ошибки, например, методом наименьших квадратов [6] или методом максимального правдоподобия [7].
На практике часто бывает трудно получить значение внешних факторов в тот же момент времени, в который очуществляется прогноз,
что является большим недостатком регрессионных моделей.
3.2. Линейная авторегрессия
Рассмотрим следующую формулу для предсказания значения временного ряда:
n
∑
ŷt+1 =
αi f (yt−i ), αi ∈ IR ∀i,
i=0
то есть для предсказания следующего значения используется n предыдущих значений ряда. Отсюда можно получить следующую матрицу
9
признаков и вектор ответов
yt−1 yt−2
yt−2 yt−3
X=
...
...
yn−1 yn−2
на для каждого набора признаков:
yt−3 ... yt−n
yt
yt−1
yt−4 ... yt−n−1
, y =
... ...
...
...
yn−3 ...
y0
yn
В такой постановке задача может решаться самыми различными
методами машинного обучения, поскольку входными данными для них
являются матрицы признаков и ответов на них. Например, можно применить методы построения CART (Classification and Regression Tree)
[8]. На рисунке представлен пример построения деревьев классификации для тестового временного ряда.
10
3.3. Модели экспоненциального сглаживания
Помимо авторегрессионных моделей существуют различные модели сглаживания. Одна из первых моделей сглаживания - это экспоненциальное сглаживание. Модель экспоненциального сглаживания представляет собой рекуррентное соотношение, в котором каждое последующее предсказываемое значение выражается через значение предсказанное на предыдущем шаге и истинное значение на предыдущем шаге:
ŷt+1 = ŷt + α(yt − ŷt )
Однако, данная модель не учитывает различных явлений, которые
могут наблюдаться в данных. Поэтому разрабатывались и другие модели, в которых учитываются тренды и сезонность.
Модель Хольта [9] описывает поведение временного ряда с линейным трендом по следующей формуле:
ŷt+d = at + dbt ,
где at , bt - адаптивные компоненты линейного тренда, которые получаются из рекуррентных соотношений:
at = α1 yt + (1 − α1 )(at−1 + bt−1 )
bt = α2 (at − at−1 ) + (1 − α2 )bt−1
Модель Тейла-Вейджа [10] описывает данные с линейным трендом
и аддитивной сезонностью:
ŷt+d = at + dbt Θt+(d mod s)−s ,
at = α1 (yt − Θt−s ) + (1 − α1 ) (at−1 + bt−1 ) ,
bt = α3 (at − at−1 ) + (1 − α3 ) bt−1 ,
Θt = α2 (yt − at ) + (1 − α2 ) Θt−s ,
где s период сезонности, Θi , i ∈ 0, . . . , s − 1 сезонный профиль, bt
трендовый параметр, at параметр прогноза, очищенный от тренда
и сезонности. А α1 , α2 , α3 ∈ (0, 1) параметры модели.
11
Модель Хольта-Уинтерса [11] описывает данные с экспоненциальным трендом и аддитивной сезонностью:
ŷt+d = at (rt )d Θt+(d mod s)−s ,
yt
at = α1 ·
+ (1 − α1 ) at−1 rt−1 ,
Θt−s
at
+ (1 − α3 ) rt−1 ,
rt = α3 ·
at−1
yt
Θt = α2 · + (1 − α2 ) Θt−s ,
at
здесь, как и ранее, s период сезонности, Θi , i ∈ 0, . . . , s−1 сезонный
профиль, rt параметр тренда, at параметр прогноза, очищенный
от влияния тренда и сезонности. Параметры α1 , α2 , α3 ∈ (0, 1)
Все параметры рассмотренных моделей могут быть получены, например, минимизацией среднеквадратичной ошибки между предсказываемым значением ŷt и наблюдаемым yt :
ϵ2t = (yt − ŷt )2 .
Здесь представлены наиболее распространенные модели сглаживания. Кроме того существует еще много моделей, различающихся видами сезонности и трендов.
3.4. Нейросетевые модели
В настоящее время нейросетевые модели довольно часто используются для предсказания временных рядов [12]. Нейросетевые модели
строятся из нейронов. Стандартная модель нейрона приведена на рисунке ниже:
12
Как видно из рисунка модель нейрона для временного ряда можно
описать следующими функциями:
ut =
m
∑
ωi xt−i + ω0
i=1
zt = ϕ(ut )
здесь предыдущие значения ряда yt−1 , yt−2 , . . . , yt−n представляются как
входные сигналы, ωi - веса сигналов, а ϕ - функция активации.
Функция активации бывает трех основных типов:
• функция единичного скачка
• кусочно-линейная функция
• сигмоидальная функция
• функция гиперболического тангенса
Из нейронов можно построить нейронные сети с различным числом
слоев, например:
13
Таким образом можно строить достаточно сложные модели на основе предыдущих значений временного ряда. Модели могу быть нелинейными - это определяется числом слоев и функцией активации в каждом
из них.
3.5. Модели на основе цепей Маркова
Так же для краткосрочного прогнозирование применяются Марковские цепи [13]. Схематичный вид такой цепи представлен ниже.
14
Здесь события i, j, k, l - некоторые состояния временного ряда, а pij
- соответствующие вероятности переходов. Если известна предыстория
временного ряда, то моделируя процесс посредством марковской цепи
можно получить вероятности нахождения системы в каждом из состояний через какой-то промежуток времени. Однако данная модель имеет
явную сложность - это определение вероятностей переходов, которые
должны быть заданы заранее.
15
4. Описание и предварительный анализ данных
Для анализа был выбран набор данных о преступлениях совершенных в Чикаго в период с 2001 по 2015 год [14].
4.1. Описание данных
Полученный набор данных имел следующий набор признаков:
1. Время совершения преступления
2. День недели
3. Район совершения преступления
4. Координаты широты
5. Координаты долготы
6. Тип преступления
Всего в наборе данных представлено более сорока типов преступлений. Однако, большая часть из них представлена очень небольшой
выборкой, что делает данные типы преступлений непригодными для
анализа. Поэтому для дальнейшего рассмотрения были выбраны наиболее распространённые и опасные виды преступлений, число которых
в неделю превосходит 100:
• Нападение
• Побои
• Кражи со взломом
• Причинение ущерба
• Посягательство на преступление
16
• Мошеничество
• Похищение транспортных средств
• Преступления связанные с наркотиками
• Грабеж
• Воровство
Как видно, набор данных содержит небольшое число признаков, однако, такие признаки, как время и географичесие координаты, позволяют более подробно взглянуть на то, от чего зависит количество преступлений.
4.2. Визуализация аггрегированных данных
Посмотрим на графики различных преступлений (Рис. 1), на которых приведены аггрегированные данные об общем количестве преступлений. Сплошная линия на графике представляет собой экспоненциальное сглаженное количество преступлений.
Как видно таким преступлениям как нападения, побои, кражи со
взломом, причинение ущерба, грабежи, воровство, присуща годовая сезонность. Также видно, что общее число случаев нападений, побоев,
причинения ущерба , посягательство на преступление, распространения
наркотиков, краж транспортных средств, грабежей, воровства снижается к 2015 году, а число случаев мошеничества, наоборот, возрастает.
Однако стоит отметить, что в таких преступлениях, как кражи со взломом и кража транспортных средств, наблюдаются пики в 2005, 2011
годах соответсвенно.
Остановимся подробнее на календарной зависимоти. Ниже приведены две гистограммы для побоев и нападаний, на которых показана
зависимость числа преступлений от месяца (Рис. 2). Видно, что больше
преступлений совершается в теплые месяцы. Так же на каждой гистограмме видно, что в январе происходит больше преступлений, чем в
другие зимние месяцы.
17
Рис. 1: Число преступлений каждого типа в разбивке по неделям
18
Рис. 2: Число преступлений по месяцам
Кроме того, влияние оказывает также время внутри дня и, например, номер дня в месяце (Рис. 3). Тепловая карта показывает, что намного больше преступлений совершается в первый день месяца в самом
начале дня (0 часов). Так же наблюдается пик в полдень каждого дня,
и, как и следовало ожидать, больше преступлений совершается вечером. Любопытно также что в середине месяца (15 числа) преступлений
больше.
Следующий график дает представление о том, как распределены
преступления по дням недели и часам (Рис. 4). Опять же можно заметить, что больше преступлений происходит в полдень, вечером, а так
же ночью с пятницы на субботу и с субботы на восресенье. Также видно
что ночью преступлений в целом совершается меньше, а на выходных
этот минимум смещен.
19
Рис. 3: Тепловая карта числа преступлений в зависимости от часа и дня
месяца
20
Рис. 4: Тепловая карта числа преступлений в зависимости от часа и дня
недели в месяце
Теперь рассмотрим данные, по которым был построен Рис. 4, в разрезе по типам преступлений, и для каждого типа построим гистограмму
(Рис. 5). Отчетливо видно, что побои, причинение ущерба чаще происходят в выходные, нападения, кражи со взломом, мошеничество, распространение наркотиков и обычные кражи, напротив, чаще происходят в будние дни и особенно в пятницу. Угон транспортных средств
также выше в пятницу, чем в другие дни.
21
Рис. 5: Диаграмма разброса для каждого типа приступления по дням
недели
22
4.3. Связь температуры и числа преступлений
Наибольшее число преступлений, как было показано, совершается
в более теплые месяцы. Для проверки этой гипотезы, были получены архивные данные о погоде в Чикаго [15] и построен сравнительный
график (Рис. 6). Хорошо видно, что средняя температура и количество
преступлнений, для которых ранее была показана сезонность, связаны,
причем больше преступленний происходит в теплую погоду. Для каждого преступления был подсчитан коэффициент корреляции Пирсона
(результаты приведены в таблице 2):
∑m
(ci − c̄) (wi − w̄)
rcw = √∑ i=1
,
m
2 ∑m
2
i=1 (ci − c̄)
i=1 (wi − w̄)
где ci , wi - i-e измерения числа преступлнений и средней температуры
соответсвенно, а c̄, w̄ их средние значения. Любопытно что все коэффициенты получились больше 0, а все значения p-value,кроме значения
для мошеничества и угонов, меньше 0.05 (p-value показывает значимость корреляции и определяется по критерию Стьюдента).
Константа 0.05 стандартный порог для p-value. Значения p-value
меньшие 0.05 говорят о том, что если принять гипотезу о значимости
корреляции можно ошибиться только в 5% случаев. Таким образом,
корреляция средней температуры и количества преступлений статистически значима в большинстве случаев (в таблице выделены красным),
и данные о температуре могут помочь в построении моделей предсказания количества преступлений.
Тип преступления
Коэффициент корреляции
p-value
Нападение
Побои
Кражи со взломом
Приченение ущерба
Посягательство на преступление
Мошеничество
Угон транспортных средств
Распространение наркотиков
Грабежи
Воровство
0.800
0.885
0.531
0.816
0.494
0.200
0.245
0.401
0.417
0.866
1.865 · 10−12
6.855 · 10−18
6.052 · 10−5
2.860 · 10−13
2.293 · 10−4
0.160
0.083
0.132
2.342 · 10−3
2.522 · 10−16
Таблица 1: Корреляция средней температуры и числа преступлений
23
Рис. 6: Cредняя температура и количество преступлений преступлений
24
4.4. Географические температурные карты
Также для более наглядной демонастрации были построены географические температурные карты(Рис. 7). Видно, что много преступлений происходит вдоль побережья, а также в восточной и южной частях
города.
Также была построена интерактивная версия карты, на которой
можно рассмотреть наиболее преступные районы подробнее и получить
описание преступления [16].
Криминальность района может влиять на цену недвижимости или
выбор места проживания. Поэтому были построенны интерактивные
карты, по которым можно судить о безопасности того или иного жилого
района [17]. Наиболее криминальные районы находятся, как и описано
выше, вдоль побережья, на востоке и юге города.
25
Рис. 7: Наиболее преступные улицы и районы города
26
5. Построение моделей прогнозирования
Для дальнейшего анализа и построение моделей были отобраны преступления следующих типов:
• Нападения
• Побои
• Кражи со взломом
• Причинение ущерба
• Мошеничество
• Грабежи
• Воровство
поскольку в предыдущие главе было показано что эти преступления
имеют некоторую зависимость от временных и погодных факторов.
Кроме того, если брать данные о преступности отдельно по каждому
району, то их оказывается недостаточно для построения точных прогнозов.
Набор данных был преобразован для анализа, и для каждого вида
преступления был представлен следующими признаками: число преступлений данного типа, совершенных в текущий день (целевая переменная); год; месяц; число месяца; номер дня в году; день недели; температура воздуха; влажность воздуха; давление воздуха и 14 предыдущих
измерений числа преступлений.
Как видно, для построения наряду с предыдущими значениями временного ряда будут использоваться внешние факторы, такие как день
недели или погодные условия. Поэтому исключительно авторегрессионные модели здесь не подходят, и необходимо использовать алгоритмы
регрессии и авторегрессии совместно. Для этого отлично подходят модели на основе алгоритмов машинного обучения, которые принимают
27
на вход простую матрицу признаков, а на выходе дают значение целевой переменной.
В нашем случае матрица признаков получается достаточно просто, cтрока такой матрицы будет представлять совокупность описанных
признаков для одного дня (год, месяц, день недели и т.д.), а ответом
для одного такого набора признаков будет значение числа преступлений, произошедших в этот день. Таким образом, весь набор данных был
преобразован к матрице признаков X, имеющей следующий вид:
x11 x12 x13 ... x1m
x21 x22 x23 ... x2m
X=
... ... ... ... ...
xn1 xn2 xn3 ... xnm
.
И вектору ответов Y :
Y = (y1 , y2 , y3 , ...yn )T
5.1. Описание моделей
Для построения моделей использовался язык Python и пакет sklearn.
Так как прогнозы строились для 7 типов преступлений, то, вполне ожидаемо, что одна модель не в состоянии описать каждый из типов преступлений, поэтому были выбраны 4 алгоритма для построения регрессии:
• Ридж регрессии [18]
• Регрессия на базе случайных лесов [8]
• Регресиия на базе решающих деревьев [19]
• Регрессия на базе SVM [20]
Ранее нами была получена матрица признаков X и вектор ответов Y для каждого типа преступления. Строки матрицы X называются объектами, а соответвующие элементы вектора Y ответами на этих
28
объектах. Каждый из представленных алгоритмов пытается восстановить неизвестную зависимоть y : X → Y путем построения некоторого
приближения a : X → Y , именно методом построения приближения
a алгоритмы отличаются друг от друга. Остановимся на каждом из
алгоритмов подробнее.
Чтобы описать алгоритм ридж регрессии стоит обратиться к алгоритму линейной регресси. Алгоритм линейной регрессии предполагает
линейную связь каждого из параметров матрицы признаков и вектора ответов, то есть a = (X, θ), где θ - неизвестный параметр, а скобки
означают скалярное произведение. Параметр θ ищется методом наименьших квадратов, то есть путем минимизации функционала:
Q = ∥(X, θ) − Y ∥2
Часто случается так, что признаки матрицы X оказываются мультиколлинеарными, то есть между ними наблюдается линейная зависимость. Что приводит к тому что решение задачи линейной регресси
получается неустойчивым (элементы вектора θ получаются большими
и разных знаков) . Алгоритм ридж регрессии пытается устранить данный недостаток путем добавления к функционалу Q регуляризатора:
Q = ∥(X, θ) − Y ∥2 + τ ∥θ∥2
где τ > 0 - параметр регуляризации. Большим параметрам τ соответсвует более сильная регуляризация, то есть коэффициенты должны не
сильно отклоняться от 0. Настраиваемым параметром в данной модели
является параметр регуляризации τ .
Решающее дерево представляет собой дерево в листьях которого находятся значения апроксимирующей функции a, а узлы представляют
собой условия перехода по ребрам (к примеру ”температура больше 20
градусов”). На каждом шаге алгоритма по каждому признаку строится разделяющая плоскость, и для каждой части выборки, разделенных
плоскостью, предсказывается среднее значение ответов объектов, попавших в эту часть пространства, и на основе этого считается средне29
квадратичная ошибка для каждого из полупространств. В итоге выбирается плоскость, которая разбивает пространство так, что суммарная
среднеквадратичная ошибка минимальна. Вообще разделяющая плоскость может строиться по нескольким признакам, но это ведет к росту вычислительной сложности алгоритма. Критерием остановки алгоритма является либо достижение им максимальной начально заданной
глубины дерева, либо наперед заданнай точности прогноза. Настраиваемыми параметрами модели являются глубина дерева, число измерений, по которым выбирается лучшее разбиение в узле, минимальное
количество объектов в листе.
Алгоритм регрессии на базе случайных лесов представляет собой
композицию множества решающих деревьев, которые представляют собой сильно усеченные, и построенные лишь на подмножестве признаков
деревьев, обученных как описано выше. Дело в том, что в отдельности
эти деревья не несут никакой ценности, поскольку делают очень неточные прогнозы, однако если взять большое число таких деревьев (больше
20) и усреднить все их показания, то прогнозы получаются достаточно точными. Настраиваемыми параметрами в данной модели являются
число деревьев, количество признаков для обучения одного дерева, а
так же параметры, используемые при обучении обычных деревьев.
Алгоритм регрессии на базе SVM ищет функция a в следующем
виде:
a(x) = (ω, x) + ω0
где в скобках указано скалярное произведение. Для нахождения вектора Ω = (ω0 , ω1 , . . . , ωn ) решается задача мимнимизации функционала:
n
∑
1
∥ω∥2
Q=
(|(ω, xi ) + ω0 − yi | − δ)+ +
2C
i=1
где δ некоторая допустимая ошибка предсказания, функция (z)+ = z
1
как и ранее параметр
если z < 0, в противном случае равна 0, 2C
регуляризации. заменной переменных ζi+ = ((ω, xi ) + ω0 − yi − δ)+ и
ζi− = (−(ω, xi ) − ω0 + yi − δ)+ задача сводится к задаче квадратичного
30
программирования с линейными ограничениями:
n
∑
1
2
∥ω∥ + C
(ζi+ + ζi− ) → minΩ,ζi+ ,ζi−
2
i=1
yi − δ − ζi− ≤ (ω, xi ) + ω0 ≤ yi + δ + ζi+ ∀i
ζ − , ζ + ≥ 0 ∀i
i
i
Решение данной задачи может быть найдено в следующем виде:
n
∑
−
a(x) =
(λ+
i + λi )(xi , x) + ω0 ,
i=1
λ−
i ,
λ+
i
где
двойственные переменные, возникающие при решении задачи квадратичного программирования. Скалярное произведение (xi , x)
может представлять собой не только классическое скалярное произведение, но и любую другую функцию от двух векторов обладающую
всеми свойствами скалярного произведения, такая функция называется ядром, тогда выражение для a(x) может быть записано в следующем
виде:
n
∑
−
a(x) =
(λ+
i + λi )K(xi , x) + ω0 ,
i=1
, где K(x, y)-ядро.
Настраиваемыми параметрами описанного алгоритма являются ядро, параметры самого ядра, коэффициент при регуляризаторе C и допустимая ошибка δ.
5.2. Построение моделей предсказания преступности
Для поиска оптимальной модели часть данных за 2015 год была отложена для потроения и оценки самого прогноза. На оставшейся части
данных методом перекрестной проверки по сетке параметров подбирался наилучший алгоритм и его параметры. Результат каждого алгоритма с каждым набором параметров оценивался по метрике MAPE (mean
31
absolute percentage error), которая позволяет судить о среденй ошибке
прогноза:
(
M AP E =
k
∑
|yi − ŷi |
yi
i=1
.
)
· 100%
Результаты работы наилучших алгоритмов для каждого типа преступлений приведены в таблице.
Тип преступления
Ридж Регрессия
Дерево решений
Случайный лес
SVM регрессия
Нападение
Побои
Кражи со взломом
Приченение ущерба
Мошеничество
Грабежи
Воровство
14.94 %
17.01 %
24.33 %
19.09 %
10.77 %
12.93 %
8.73 %
14.41 %
10.06 %
14.15 %
17.54 %
18.28 %
17.57 %
16.52 %
7.92 %
11.55 %
14.90 %
12.40 %
9.09 %
12.29 %
9.65 %
25.32 %
26.19 %
9.98 %
25.72 %
12.08 %
20.93 %
17.47 %
Таблица 2: Результаты построенных моделей
Результаты работы наилучшего для каждого преступления алгоритма выделены красным. Наилучшие результаты показал алгоритм
регреccии на основе случайного леса.
5.3. Задача классификации
Построенные прогнозы кажутся весьма точными, однако, более полезным является предсказание аномальных дней, когда число преступлений гораздо выше чем в среднем. Для того чтобы показать как можно
классифицировать преступления, были выбраны данные о побоях. Если
рассмотреть данные о побоях в пределах любых 30-100 дней, то распределение числа побоев окажется нормальным. Поэтому можно, например, классифицировать число побоев следующим образом: если число
побоев превосходит среднее число побоев за предыдущие 30 дней больше чем на одно среднеквадратичное отклонение, то этот день считается
аномальным и относится к первому классу, остальные дни относятся
к нулевому классу. Таким образом, задача восстановления регрессии
может быть сведена к задаче бинарной классификации. В среднем оказывается, что на один год приходится порядка 70 аномальных дней.
32
Задача классификации решалась путем построения нейронной сети
с тремя скрытыми слоями. Первый скрытый слой содержал 100 нейронов, второй 50, третий 10, данные цифры были подобраны экспериментально путем сравнения большого числа различных нейросетей.
Входной слой имел линейную структуру, а все три скратых слоя были
представлены сигмоидальными нейронами [21]. Выходной слой состоял
из одного сигмоидального нейрона.
Сигмоидальная функция имеет значение от 0 до 1, поэтому будем
интерпретировать значение выходного слоя как вероятность принадлежности к классу, если она больше 0.5, то относим объект (день) к
класу 1, иначе к классу 0.
Нейронная сеть обучалась алгоритмом обратного распространения
ошибки путем мимимизации среднеквадратичной ошибки [22]. Для оценки результатов работы нейросети использовались метрики точности
(precision):
P
precicion =
N
, где P число объестов данного класса, которые классифицируются правильно, а N общее число объестов классифицированных как данный
класс. Так же используется мера полноты (recall):
recall =
P
M
, где P как и выше, число объестов данного класса, которые классифицируются правильно, а M число объектов в тестовой выборке которые
реально принадлежат нашему классу. Оценивать точность и полноту
будем для первого класса, то есть класса, который описывает аномальные дни. В данной задаче классификации более важной является метрика полноты. Поскольку мы стремимся находить все опасные дни, которые присутствуют в тестовом наборе данных.
В резудьтате работы нейросети на тестовом наборе данных за 2015
33
год, были получены следущие значения точности и полноты:
precision = 0.70
recall = 0.55
Таким образом можно утверждать, что мы предсказываем порядка
55% плохих дней с точностью прогноза 70%. Что является неплохим
результатом.
Такой подход сведения задачи регрессии к задаче классификации
может быть применен так же и к другим типам преступлений, поскольку число преступлений в пределах 30-100 дней оказывается распределенным по нормальному закону для каждого из них. Далее теми же
методами может быть построена нейронная сеть которая позволит находить аномальные дни. Однако эта задача требует больших временных затрат, так как расчет cложной нейросети вычислительно cложная
задача.
34
Заключение
В данной работе приведен подробный анализ уровня преступности
в Чикаго за 2001-2015 года. Была проанализирована связь уровня преступности и различных внешних факторов, таких как погодные условия, день недели, номер дня в году. Приведена визуализация данных,
которая позволяет увидеть интересные закономерности. На основе географических данных о преступлениях, были построены интерактивные
карты, на которых можно легко найти наиболее опасные улицы и районы города.
На основании выявленных закономерностей построены модели для
прогнозирования уровня преступности для таких преступлений как нападения, побои, кражи со взломом, причинение ущерба, мошеничество,
грабежи и воровство. Модели строились на данных за 2001-2014 года, а
оценка проводилась на данных за 2015 год. Для построения моделей использовались алгоритмы машинного обучения, которые учитывают как
исторические данные о преступлениях, так и другие внешние факторы.
Приведен сравнительный анализ алгоритмов. Построеные модели показали достаточно высокую точность. Но наилучший результат показал
алгоритм регресси на основе случайных лесов.
Далее задача прогнозирования числа преступлений сведена к задаче
классификации для выявления наиболее опасных дней c точки зрения
количества преступлений. Данная задача решалась путем построения
нейросетевой модели. Полученные результаты так же кажутся достаточно удволетворительными.
Результаты полученные в рамках данного исследования могут оказаться полезными для прогнозирования уровня преступности и в других городах.
Данные методы прогнозирования временных рядов могут быть полезны для снижения уровня преступности, так как позволяют предсказывать неблагоприятные периоды, в которые необходимо усиливать
патрулирование улиц города.
35
Список литературы
[1] Schneider S. Predicting crime: a review of the research. page 37, 2002.
[2] John V. Forecasting crime: A city level analysis. page 33, 2007.
[3] Henderson T., Wolfers J., and Zitzewitz E. Predicting crime. page 63,
2008.
[4] Бокс Дж. and Дженкинс Г.М. Анализ временных рядов, прогноз и
управление. M., 1974.
[5] Draper N. and Smith H. Applied regression analysis. N.Y., 1981.
[6] Айвазян С.А. Прикладная статистика. Основы эконометрики.
М., 2001.
[7] Andersen and Erling B.
Asymptotic properties of conditional
maximum likelihood estimators. Journal of the Royal Statistical
Society, pages 283–301, 1970.
[8] Meek C., Chickering D.M., and Heckerman D. Autoregressive tree
models for time-series analysis. 2002.
[9] Holt C.C. Forecasting trends and seasonals by exponentially weighted
moving averages, 1957.
[10] Theil H. and Wage S. Some observations on adaptive forecasting. 1964.
[11] Winters P.R. Forecasting sales by exponentially weighted moving
averages. Management Science, (6):324–342, 1960.
[12] Ginzburg I. and Horn.D. Combined neural networks for time series
analysis. pages 1–2.
[13] Liu T. Application of markov chains to analyze and predict the time
series. 2009.
36
[14] City of Chicago.
Crimes - 2001 to present.
https://data.
cityofchicago.org/Public-Safety/Crimes-2001-to-present/
ijzp-q8t2, 2016.
[15] Historical weather data.
Weather in chicago.
wunderground.com/history/airport/ORD, 2016.
https://www.
[16] Interactive geo heatmap. https://drive.google.com/uc?id=0BzDO_
U5QbqF5U1poZjR1UUJwbWs, 2016.
[17] Neighborhood geo heatmap. https://drive.google.com/uc?id=
0BzDO_U5QbqF5aldVUXY3M2taTXc, 2016.
[18] Тихонов А.Н. О решении некорректно поставленных задач и методе регуляризации. Доклады Академии Наук СССР 151, page 4,
1963.
[19] Breiman L. Random forests. page 33, 2001.
[20] Drucker H., Burges C., and Kaufman L. Support vector regression
machines. page 9, 1997.
[21] Martin A. Discrete mathematics of neural networks: Selected topics.
page 3, 2001.
[22] Хайкин. C. Нейронные сети. Полный курс. М., 2006.
37
Отзывы:
Авторизуйтесь, чтобы оставить отзыв