پیش‌بینی نوع جرم

مبنای این پروژه بر اساس مسابقه‌‌ای است که در سایت Kaggle.com  قرار داده شده است. برای مشاهده صفحه اصلی این مسابقه  [اینجا](https://www.kaggle.com/c/sf-crime) را کلیک کنید. در این مسابقه از ما خواسته شده است که برنامه با یادگیری سابقه ۱۲ ساله جرم و جنایت در شهر سان‌فرانسیسکو، بتواند نوع جرم را برای هر جنایت جدیدی که به وقوع می‌پیوندد پیش‌بینی کند.

# مقدمه
امروزه جرم، جنایت و تروریسم خطری است که همواره شهروندان یک شهر را تهدید میکند. اولین شیوه‌های پیش‌گیری از جرم بر پایه افزایش مجازات‌های فرد مجرم بوده است. در این شیوه‌ها پس از کشف جرم و دستگیری مجرم با اعمال مجازات‌های مختلف سعی بر مهار میزان وقوع جرم در جامعه شده است.در این روش‌ها پلیس پس از وقوع جرم،‌ به کشف آن پرداخته و در نهایت برای دستگیری مجرم اقدام می‌کند؛  از این رو پلیس دارای رویکردی انفعالی خواهد بود. یکی از رویکرد‌های جدید مقابله با جرم پیش‌بینی جرم قبل از وقوع آن است که باعث می‌شود نقش پلیس از ماهیت انفعالی به ماهیتی فعال و پویا تبدیل شود. 
در اکثر جرم و جنایت‌ها، حضور یک پلیس یا اتومبیل گشت‌زنی ،می‌تواند از فعالیت‌های مجرمانه جلوگیری می‌کند. سیستم پیش‌بینی جرم به پلیس کمک می‌کند تا در زمان‌های مختلف در محل‌هایی که احتمال وقوع جرم بیشتر است به گشت زنی بپردازند که دراین حالت نیروهای پلیس به صورت بهینه تر و هدفمندتر میتوانند به انجام وظیفه خود بپردازند و آمار وقوع جرم نیز کاهش خواهد یافت. در حال حاضر در چند ایالت آمریکا، و در شهرهایی از انگلستان [1]  پلیس در حال استفاده از این سیستم‌ها است و کاهش قابل توجهی در آمار وقوع جرم و جنایت ثبت شده است.
 سیستم‌های پیش‌بینی جرم به طور کلی  با یادگیری از داده‌های جرم‌های رخ داده در یک شهر در یک بازه زمانی به پیش‌بینی مناطقی که احتمال وقوع جرم در آن بیشتر است [^Crime hotspot] می پردازد. این سیستم ها قادر به پیش بینی هویت سارق نیستند بلکه نوع جرم و مکان و زمان احتمالی وقوع آن را پیش بینی می کند.
داده‌های مسئله شامل جرم هایی است که از تاریخ 1/1/2003 تا 5/13/2015 توسط سازمان پلیس سانفرانسیکو ثبت شده است.


# کارهای مرتبط
در این مقاله بیشتر سعی خواهد شد که خواسته مسابقه که همان تشخیص نوع جرم است بررسی شود اما در بخش کارهای مرتبط برای فهم بهتر مسئله به طور کلی به شناخت سیستم‌های تشخیص جرم که به بررسی مکانی و زمانی جرم هم میپردازند خواهیم پرداخت.
##روش ترسیم نقاط حساس
یکی از روش‌های ابتدایی بررسی جرم‌ها روشی به اسم ترسیم نقاط حساس[^Hotspot mapping] است[2]. نکته‌ی کلیدی در این روش دانستن این موضوع است که اغلب جرائم در محیط‌هایی خاص و تکراری رخ می‌دهند و احتمال تکرار جرم در محلی که قبلا قربانی آن جرم بوده بسیار بیشتر است[3]. در روش ترسیم نقاط حساس با بهره گیری از سابقه‌ی جرم های رخ داده در گذشته، مناطقی که در آن‌ها مقدار بیشتری جرم رخ داده است در نقشه مشخص می‌گردد تا پلیس نیروهای خود را به صورت بهینه تری بتواند در شهر تقسیم کند. روش های ترسیم شامل نگاشت نقطه‌‌‌‌‌‌‌‌‌‌‌‌‌‌ای[^Point mapping](شکل۲-a)، بیضی‌های مکانی[^Spatial ellipses](شکل۲-b)، ‌‌نگاشت موضوعی واحد‌های اجرایی [^ Thematic mapping of administrative units](شکل۲-c)، نگاشت شبکه‌ای موضوعی[^Grid thematic mapping] (شکل۲-d)و پرکاربردترین آنها[4] که روش تخمین چگالی هسته [^Kernel density estimation](شکل۲-e)است. این روش های ترسیم هریک دارای مزایا و معایبی هستند که در مقاله ذکر شده[2] به آن ها اشاره شده است. 
![شکل ۱-انواع روش های ترسیم نقاط حساس ](https://boute.s3.amazonaws.com/206-hotspot_mapping.png)
##روش یادگیری نظارت شده
روش دیگر پیش بینی‌جرم استفاده از الگوریتم‌های یادگیری نظارت شده[^Supervised learning] است[5]. در این روش داده‌گانی از جرم‌های رخ داده در شهرهای مختلف در طول یک بازه زمانی برای یادگیری استفاده میشود.این داده‌گان دارای اطلاعاتی هچون نام شهر، تعداد جمعیت، میزان درآمد قشرهای مختلف مردم و میزان جرم به ازای هر ۱۰۰ هزار نفر است.الگوریتم های طبقه‌بندی[^Classification] بیزساده[^Naive Bayes] و درخت تصمیم گیری[^Decision tree] برای این مسئله استفاده شده‌اند.
###طبقه بندی بیز ساده
الگوریتم طبقه بندی  بیز ساده بدین گونه است که اگر برای هر نمومه $X=({ X }_{ 1 },{ X }_{ 2 },...,X_{ n })$ و ${ X }_{ 1 }$  مقدار ویژگی یکم باشد مقدار  $P(X|C)$ به وسیله الگوریتم طبقه بندی بیز ساده برای همه‌ی مقادیر ممکن C محاسبه میشود و مقدار${ C }^{ * }={ argma }_{ xc }P(X|C)$ برای همه‌ی مقادیر X پیش بینی می‌شود.برای اطلاعات بیشتر به[ اینجا](https://en.wikipedia.org/wiki/Naive_Bayes_classifier) مراجعه کنید.
###طبقه بندی درخت تصمیم
الگوریتم درخت تصمیم گیری همانطور که از نامش پیداست تشکیل ساختار داده‌ای درختی می‌دهد که در آن گره‌های میانی نقش یک گره تصمیم‌گیری بر اساس یک ویژگی را ایفا می‌کنند و برگ‌ها مشخص کننده‌ی ویژگی هدف می‌باشند.در این درخت سعی می‌شود تا با استفاده از انتخاب شروط مناسب در هر گره تصمیم‌گیری درختی بسازیم که پیشبینی بهتری ارایه دهد.الگوریتم‌هایی که برای ایجاد درخت تصمیم استفاده می‌شوند معمولا بشکل بالا به پایین کار می‌کنند به این صورت که در هر مرحله متغیری را که به بهترین شکل مجموعه داده ها را تقسیم می‌کند انتخاب می‌کند.برای اطلاعات بیشتر به [اینجا](https://en.wikipedia.org/wiki/Decision_tree_learning) مراجعه کنید.
###نتیجه
 نتیجه بدست آمده به صورت زیر است:
![شکل ۲-نتیجه بدست آمده از الگوریتم های بیز ساده و درخت تصمیم‌گیری](https://boute.s3.amazonaws.com/206-result.png)
همانطور که نتایج بدست آمده در  شکل ۳  نشان میدهد برای این مسئله خاص الگوریتم درخت تصمیم گیری از دقت بهتری برخوردار بوده است.

# آزمایش‌ها
##دادگان
داده‌های مسئله شامل جرم هایی است که از تاریخ 1/1/2003 تا 5/13/2015 توسط سازمان پلیس سانفرانسیکو ثبت شده است و از [اینجا](https://www.kaggle.com/c/sf-crime/data)   قابل دریافت است.
هر سطر از جدول دادگان حاوی اطلاعاتی در مورد یک جرمی که رخ داده است می‌باشد. و شامل اطلاعات زیر است:
+ تاریخ و زمان دقیق وقوع جرم
+ روز وقوع جرم در هفته
+ نام واحد پلیس منطقه
+ آدرس وقوع جرم
+ عرض جغرافیایی وقوع جرم
+ طول جغرافیایی وقوع جرم
+ دسته‌ای که جرم در آن قرار می‌گیرد.(هدف پیش بینی مقدار این ستون است)
+  شرح کوتاهی از جرم
+ شرح کوتاهی از اقدام پلیس و مقامات قضایی با جرم
شکل زیر اطلاعات داده شده در این داده‌ها را نشان می‌دهد.
![شکل۳-ااطلاعات داده شده برای هر جرم](https://boute.s3.amazonaws.com/206-dataset.png)

بعضی اطلاعات موجود در این دادگان در پیش‌بینی جرم از طریق طبقه‌بندی کمک چدانی نمی‌کنند و قابل حذف شدن هستند.شرح جرم و نحوه برخورد پلیس از جمله اطلاعاتی بودند که دانستن آنان تاثیر زیادی در پیش‌بینی جرم ندارد و نادیده گرفته خواهند شد.همچنین آدرس وقوع جرم نیز با وجود دانستن طول و عرض جغرافیایی حاوی اطلاعات جدیدی نمی‌باشد و نادیده گرفته خواهد شد.
بسیاری از الگوریتم‌های یادگیری ماشین قادر به آنالیز داده‌های متنی نمی‌باشند. بنابراین لازم است داده‌های																																																																																																																																																																																																																																																																																																																																																																																										 متنی همچون نام واحد پلیس منطقه یا نوع جرم از نوع متنی به نوع داده‌ای دودویی یا عدد صحیح تبدیل شوند.

##ابزارهای استفاده شده در پیاده‌سازی
تمام پیاده‌سازی ها با زبان پایتون انجام شده‌اند. این زبان دارای ابزارهای بسیار خوبی در زمینه یادگیری ماشین و هوش مصنوعی است. همچنین خواندن و نوشتن اطلاعات از فایل‌ها، و نرمال‌سازی داده‌ها در این زبان به راحتی انجام می‌شوند. [sklearn](http://scikit-learn.org/stable/) کتابخانه اصلی استفاده شده برای پیاده‌سازی الگوریتم‌های یادگیری ماشین است. همچنین کتاب‌خانه‌های [pandas](http://pandas.pydata.org/)  و [numpy](http://www.numpy.org/) برای استخراج و تحلیل داده‌ها استفاده شدند. 

##روش‌های پیاده‌سازی شده
کد تمام پیاده‌سازی ها در سایت [گیت‌هاب](https://github.com/Farzin-S-Amini/SF-crime-classification) قرار داده شده است.
برای پیاده‌سازی چهار الگوریتم رایج طبقه بندی بیز‌ساده،نزدیک‌ترین k  همسایه[^k-nearest neighbors] ، رگرسیون منطقی[^logistic regression] و جنگل‌های تصادفی[^random forests] را در نظر گرفته‌ایم.
روش بیز ساده در قسمت کار‌های مرتبط توضیح داده‌شد. اکنون به بررسی سه روش دیگر می‌پردازیم.
### نزدیک‌ترین k همسایه
در این روش هر نمونه از داده به عنوان یک گره در نظر گرفته می‌شود سپس فاصله هر دو گره میزان تفاوت آن دو گره را نشان می‌دهد. برای دسته بندی هر گره جدید  فاصله آن با سایر گره ها محاسبه شده و به دسته بندی نزدیک ترین k گره توجه می شود(k ثابتی است که بسته به نوع مسئله مشخص می شود).مقدار k نه خیلی کوچک و نه خیلی بزرگ باید باشد.کوچک بودن بیش از حد k باعث می‌شود تاثیر گره‌های نامرتبط در تصمیم‌گیری چشم‌گیر باشد و همچنین زیاد بودن بیش از حد k نیز فلسفه‌ی اصلی این الگوریتم که مقایسه یک گره با گره‌های مجاور است را به خطر می‌اندازد. گره‌ی جدید در بیشترین دسته‌بندی مشاهده شده در این k گره قرار می گیرد. بنابراین در این روش نوع هر جرم با توجه به نوع جرمی که بیشتر از همه در k همسایه مجاور تکرار شده است پیش‌بینی می‌شود.


###رگرسیون منطقی
روش دیگر حل مسئله استفاده از الگوریتم طبقه بندی رگرسیون منطقی است. اما این روش برای پیش بینی متغیر های دو حالته به کار می رود  و برای پیش بینی نوع جرم که متغیری چند حالتی است از یک حالت خاص این روش که طبقه بندی رگرسیون چند متغیری[^Multinomial logistic regression]نام دارد استفاده 
 می کنیم. در این روش اگر متغیر هدف که قصد ما پیش بینی آن است n حالت مجزا داشته باشد با استفاه از الگوریتم یکی در مقابل همه [^one-vs-all] مسئله را به n مسئله طبقه بندی دوتایی تبدیل می کنیم.	سپس برای هر کدام از این مسائل طبقه بندی مقدار عبارت زیر را محاسبه می کنیم:
$${ { h }^{ (i) } }_{ \theta  }(x)=P(y=i|x;\theta )\quad (i=1,2,3)$$
سپس به ازای هر ورودی جدید x مقدار پیش بینی شده برابر i ای است که به ازای آن بیشترین مقدار برای ${ { h }^{ (i) } }_{ \theta  }(x)$  بدست آید.

###جنگل های تصادفی
در این روش درخت های طبقه بندی مختلفی را ایجاد می کنیم. در این روش برای طبقه بندی یک ورودی جدید، این ورودی را با هر یک از درخت ها ارزیابی می کنیم . هر درخت رای[^vote] خود را در مورد آن ورودی مشخص می کند. سپس طبقه بندی که بیشترین رای را بین همه ی درخت ها کسب کرده است را به عنوان طبقه بندی داده ورودی اعلام می کنیم.

##ارزیابی‌ها
در این بخش هدف این است که میزان دقت الگوریتم‌های طبقه‌بندی پیاده‌سازی شده در تشخیص نوع جرم را بدست آوریم.
###روش بیز ساده و رگرسیون منطقی
ابتدا فرایند یادگیری را بر اساس پارامترهای روز وقوع جرم در هفته و نام واحد پلیس منطقه انجام دادیم که میزان دقت تشخیص جرم در روش بیز ساده برابر ۰.۲۲۱۱   و در روش رگرسیون منطقی برابر ۰.۲۲۱۳ شد.
سپس با اضافه کردن  ساعت وقوع جرم  به ویژگی های بالا و انجام مجدد  یادگیری میزان دقت در روش بیز ساده به ۰.۲۲۳۶ و در رگرسیون خطی به ۰.۲۲۳۷ افزایش یافت.
###روش نزدیک‌ترین k همسایه
در این روش، یادگیری بر اساس پارامترهای طول و عرض جغرافیایی محل وقوع جرم انجام می‌شود. پارامتر ثابت k که در بخش معرفی روش توضیح داده شد نقش مهمی در عملکرد یادگیری و میزان دقت آن دارد. بنابراین آزمایش را با مقدار kهای مختلف انجام داده و میزان دقت هرکدام را بدست آوردیم.

|۶۰|۵۰|۴۰| ۳۰| ۲۰ | k (تعداد همسایه‌ها)  |
|:------|:-------:|:--------:|:-------:|:------:|:-------:|
|۰.۲۷۲۴|۰.۲۷۴۳|۰.۲۷۶۰|۰.۲۷۰۹|۰.۲۶۵۹|دقت|

###روش جنگل‌های تصادفی
در این روش یادگیری  پارامترهای درگیر طول و عرض جغرافیایی محل وقوع جرم، روز وقوع جرم در هفته و نام واحد پلیس منطقه هستند. تعداد درخت‌های تشکیل شده هنگام یادگیری یک پارامتر تاثیر‌گذار در عملکرد الگوریتم است. بنابراین با در نظر گرفتن مقادیر مختلف تعداد درخت میزان دقت الگوریتم را اندازه می‌گیریم.

|۱۵|۱۱|۱۰|۵| ۲| ۱ | تعداد درخت  |
|:------|:-------:|:--------:|:-------:|:------:|:-------:|:-------:|
|۰.۲۲۱۳|۰.۲۲۱۱|۰.۲۲۰۲|۰.۲۱۴۹|۰.۲۰۶۸|۰.۲۰۰۷|دقت|
افزایش تعداد درخت ها باعث افزایش دقت هم می‌شود اما افزایش آن‌ها به مقدار بیشتر از ۱۵ سربار بسیار زیادی خواهد داشت و زمان اجرا را بسیار طولانی خواهد کرد.
###بررسی نتایج
نتایج به دست آمده نشان می‌دهد روش نزدیک‌‌ترین k همسایه توانست عملکرد بهتری نسبت به سه روش دیگر از خود نشان بدهد. دلیل این امر استفاده از طول و عرض جغرافیایی برای یادگیری است و نوع جرم بر اساس سایر جرم‌هایی که در آن منطقه و نزدیکی رخ داده است  پیش‌بینی می‌شود. تجربه ثابت کرده است که جرم‌های رخ داده در یک محله بسیار مشابه یکدیگر هستند به طور مثال در محله‌هایی که شهروندان ثروتمندتر زندگی می‌کنند سرقت و دزدی نسبت به  سایر جرم‌ها بسیار رایج‌تر هستند و در مناطق فقیرنشین تر و حاشیه شهر نزاع خیابانی نسبت به سایر جرم‌ها رایج‌تر است. به همین دلیل در تشخیص نوع جرم،  محل وقوع جرم نسبت به سایر ویژگی‌ها از اهمیت بیشتری برخوردار است و می‌توان نوع جرم را با توجه به سایر جرم‌های رایج در آن منطقه پیش‌بینی کرد.
# کارهای آینده
روشهای تشخیص جرم یا مفهوم کلی‌تر آن که تلاش برای جلوگیری از رخ دادن جرم  است امروزه به سرعت در حال گسترش و پیشرفت است. امروزه شبکه‌های اجتماعی به یک منبع غنی از اطلاعات تبدیل گشته‌اند که حتی مجرمین نیز برای برقراری ارتباط با یکدیگر از آن‌ها استفاده می‌کنند. به همین دلیل در شیوه‌های جدید پیش‌بینی جرم تاکید بسیاری به استفاده از داده های موجود در این شبکه‌ها می‌شود. در [این](http://www.cardiff.ac.uk/news/view/134592-social-data-science-lab-finds-link-between-social-media-and-crime-patterns) مقاله به ارتباط موجود بین توییت‌های شبکه اجتماعی توییتر و الگوهای جرم و جنایت پرداخته شده‌است. بهتر است در فاز های بعدی این پروژه از قابلیت‌های موجود در این شبکه‌ها نیز استفاده گردد.
# مراجع

[1] http://www.theguardian.com/cities/2014/jun/25/predicting-crime-lapd-los-angeles-police-data-analysis-algorithm-minority-report
[2] Chainey, Spencer, Lisa Tompson, and Sebastian Uhlig. "The utility of hotspot mapping for predicting spatial patterns of crime." _Security Journal_ 21.1 (2008): 4-28.
[3] Cohen, Lawrence E., and Marcus Felson. "Social change and crime rate trends: A routine activity approach." _American sociological review_ (1979): 588-608.
[4] Chainey, Spencer, Svein Reid, and Neil Stuart. _When is a hotspot a hotspot? A procedure for creating statistically robust hotspot maps of crime_. Taylor & Francis, London, England, 2002.
[5] Iqbal, Rizwan, et al. "An experimental study of classification algorithms for crime prediction." _Indian Journal of Science and Technology_ 6.3 (2013): 4219-4225.