به نام خدا
# مقدمه
مبنای این پروژه بر اساس مسابقه‌‌ای است که در سایت Kaggle.com قرار داده شده است. برای مشاهده صفحه اصلی این مسابقه [اینجا](https://www.kaggle.com/c/sf-crime) را کلیک کنید. در این مسابقه از ما خواسته شده است که برنامه با یادگیری سابقه ۱۲ ساله جرم و جنایت در شهر سانفرانسیسکو، بتواند نوع جرم را برای هر جنایت جدیدی که به وقوع می‌پیوندد پیش‌بینی کند. لیست اطلاعات این داده های ۱۲ ساله عبارتند از
+ تاریخ و ساعت وقوع جرم
+ نوع جرم ( موضوعی که قرار است توسط برنامه در دیتا ست های آزمون ، تشخیص داده شود)
+ توضیحات بیشتر در باره ی جرم ( که این توضیحات فقط در داده های واقعی موجود است)
+ روز هفته ی وقوع جرم
+ نام دپارتمان پلیس مسئول رسیدگی به پرونده
+ نتیجه ی بررسی پرونده ( که این توضیحات فقط در داده های واقعی موجود است)
+ آدرس محل وقوع جرم
+ طول جغرافیایی محل وقوع جرم
+ عرض جغرافیایی محل وقوع جرم
این اطلاعات که از [مرکز داده های شهر سانفرانسیسکو](https://datasf.org) جمع آوری شدند تعداد 878050 رکورد را در اختیار ما میگذارند تا برنامه توسط آن ها یادگیری و تست صحت یادگیری را انجام دهد و پس از آن باید به یک دیتا ست جدید توسط سایت آزموده میشود.
منطق طراحی این پروژه به این صورت است که مثلا در منطقه ای از شهر امکان دزدیدن ماشین بیشتر خواهد بود یا در منطقه ی دیگر خرید و فروش مواد مخدر و یا این که در مناطقی وقوع جرم به طور کلی بیشتر از مناطق دیگر است. در ساعات پایانی شبانه روز جرائم بیشتری رخ داده یا در روز های پایانی هفته.
از آنجا که این پروژه مدت هاست روی سایت kaggle قرار دارد، کار های زیادی روی آن انجام شده است. در این سایت موضوعات زیادی که مثل پروژه ی ما یک مجموعه داده ی بزرگ دارند ، به صورت متغییر با زمان نشان داده میشود. مانند [نقشه ی حرکت ادم ها با دوچرخه در شهر نیویورک](http://coolmaps.esri.com/#1)(با تفکیک ساعت و جنیست و ... ) یا [ترافیک کشتی های باری](http://coolmaps.esri.com/#3) طی سال های مختلف و یا [طرح سه بعدی ترافیک ماشین و انسان](http://coolmaps.esri.com/#13).
البته موضوع بحث ما نیز به خوبی در این سایت با [عنوان زمان بندی جرم در سانفرانسیسکو](http://coolmaps.esri.com/#4) به تفکیک نوع جرم ، ساعت و روز هفته نمایش داده شده که در زیر نمونه هایی از آن را میبینید.
این صفحه در واقع به ما یک دید و شهود کلی در باره ی ذات دسته ای بودن جرائم می دهد و این که چگونه در واقعیت یک سری الگوی خاص در انجام آن ها وجود دارد. این دید ما را به سمت الگوریتم های دسته بندی قابل مشاهده سوق میدهد
# کارهای مرتبط
یکی دیگر از صفحات مرتبطی که خود سایت Kaggle.com به ما برای آشنایی بیشتر با مسئله معرفی میکند [نقشه ی جرائم در شهر سانفرانسیسکو](https://www.kaggle.com/benhamner/san-francisco-top-crimes-map/code) میباشد که حالت جزئی تری از چیزیست که در مقدمه دیدید.
در ابتدا دو الگورتیم برای پیاده سازی یک مدل که از طریق یادگیری مجموعه داده بتواند به داده های جدید پاسخ دهد مطرح میشود و سپس با هم مقایسه می شوند[1] . و بعد هم چند الگوریتم دیگر. لازم به ذکر است تمامی این راه حل ها برای اعمال دسته بندی (classification) روی داده های زیاد به کار برده می شوند و بخش های مشترک زیادی با علم آمار و علم داده کاوی دارند.
1. الگوریتم بیزین
الگوریتم دسته بندی بیز که بر اساس قاعده ی بیز در احتمالات مطرح میشود. قاعده ی بیز با معادله اصلی زیر مطرح میکند که فرض می‌کنیم B_1,... ,B_k] یک افراز برای فضای نمونه‌ایS تشکیل دهند. طوری که به ازای هر j=1,... ,k داشته باشیمP(B_j)>0] و فرض کنید A پیشامدی با فرضP(A)>0 باشد، در اینصورت به ازای i=1,... ,k داریم:
برای نمونه یک میوه ممکن است پرتغال باشد. اگر نارنجی و کروی با شعاع حدود ده سانتی‌متر باشد. اگر این احتمالات به درستی به همدیگر وابسته باشند نایو بیز در تشخیص اینکه این میوه پرتغال است یا نه بدرستی عمل خواهد کرد.
الگوریتم بیزین ساده به دلیل سرعت بالا و سادگی پیاده سازی در بسیاری از کاربردها مورد استفاده گسترده قراره گرفته اند . فرض کنیم تعداد ثابتی کلاس در اختیار داریم ، برای هر کلاس cِ بردار احتمال Θ که در آن n نشان دهنده تعداد کل داده ها و تتای ci بیانگر احتماد رخداد داده ی i ام در کلاس c است به این ترتیب برچسب هر مجموعه بنا بر رابطه ی زیر تعیین خواهد شد
2. درخت تصمیم
ساختار درخت تصمیم در یادگیری ماشین، یک مدل پیش بینی کننده می باشد که حقایق مشاهده شده در مورد یک پدیده را به استنتاج هایی در مورد مقدار هدف آن پدیده نقش می کند. تکنیک یادگیری ماشین برای استنتاج یک درخت تصمیم از داده ها، یادگیری درخت تصمیم نامیده می شود که یکی از رایج ترین روش های داده کاوی است.
این ساختار تصمیم گیری می تواند به شکل تکنیک های ریاضی و محاسباتی که به توصیف، دسته بندی و عام سازی یک مجموعه از داده ها کمک می کنند نیز معرفی شوند. داده ها در رکوردهایی به شکل (x, y) = (x, x, x3…, x, y) داده می شوند. با استفاده از متغیرهای x,x,..,x سعی در درک، دسته بندی یا عام سازی متغیر وابستهء Y داریم.
3. مقایسه بین دو الگوریتم
بعد از پیاده سازی هر دو الگوریتم روی مسئله ی مطرح شده مقایسه بین میزان کارایی و صحت برنامه ها به این صورت بوده است
| تابع |دسته بندی درست| دسته بندی غلط | دقت | فراخوانی |F-Measure [^ ترکیبی]|
|:-----------------|:---------:|:-------------:|:----------:|:---------:|:---------:|
| الگوریتم بیزین | 70.8124% | 29.1876% | 0.664 | 0.708 | 0.675 |
| درخت تصمیم گیری | 83.9519% | 16.0481% | 0.835 | 0.84 | 0.826 |
نتایج حاصل از بررسی کار های مرتبط با این پروژه نشان میدهد راه حل یادگیری درخت تصمیم گیری مناسب ترین برای ادامه ی پروژه میباشد [1]
در مقاله ای دیگر [7] برای اولین بار برای پیش بینی جرائم از ترکیب ضریب همبستگی و fp growth استفاده شده است.
3. ضریب همبستگی[پیوند](https://fa.wikipedia.org/wiki/%D8%B6%D8%B1%DB%8C%D8%A8_%D9%87%D9%85%D8%A8%D8%B3%D8%AA%DA%AF%DB%8C) ابزاری برای تعیین نوع و درجهٔ رابطهٔ یک با متغیر کمی دیگر است. ضریب همبستگی، یکی از معیارهای مورد استفاده در تعیین همبستگی دو متغیر است. ضریب همبستگی شدت رابطه و همچنین نوع رابطه (مستقیم یا معکوس) را نشان میدهد. این ضریب بین ۱ تا ۱- است و در صورت عدم وجود رابطه بین دو متغیر، برابر صفر است.
4. پیدا کردن الگو های تکرار شونده در یک دیتابیس بزرگ بسیار مهم و با اهمیت است اما متاسفانه از نظر محاسباتی بسیار سنگین است . الگوریتم fp growth [پیوند](https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Frequent_Pattern_Mining/The_FP-Growth_Algorithm) الگوریتمی است که توسط پرفسور هن طراحی شده و کارایی بالایی دارد.
البته طی ازمایشات انجام شده مشخص شد که استفاده از الگوریتم fp max موارد تکرار شونده ی بیشتری پیدا میشود و کارایی بیشتری از الگورتیم fp growth دارد ، همچنین پیچیدگی زمانی کمتر و حافظه ی کمتری مورد نیاز است.
برای دسته بندی زدن (classification) روی داده ها بر مبنا ی CIP از انواع الگوریتم ها استفاده می شود و بعد بررسی می شود کدام جواب بهتری می دهند. قبل از هر چیز اطلاعات را از حالت تفصیلی به حالت عددی تبدیل می کنند و بعد از آن ویژگی های مختلف را مثل نوع جرم ، میزان تحصیلات و سواد و مشکالت روانی مجرم را طبقه بندی میکنند. و سپس تبدیل داده ی عددی به داده ی دودویی به منظور استفاده در الگوریتم های دسته بندی به شرح زیر :
Input: Crime Numeric Data (CND)
Output: Crime Binary Data (CBD)
Variables: m – Total rows of Dataset (tuples)
n–Total columns of Dataset (attributes)
1.procedure DTA(cnd,m,n)
2.for column = 1 to n do
3. sum = column.m
4.min_range = sum/m
5.if min_range < 3m then
6. for row = 1 to m do
7. if row.value > 0 then
8. row.value = 1
9. else
10. row.value = 0
11. endif
12. endfor
13. else
14. for row = 1 to m do
15. if row.value > min_range then
16. row.value = 1
17. else row.value = 0
18. End if
19. End for
20. End if
21. End for
در این مقاله قرار است مکان جرم پیش بینی شود و به راه پیش گیری از آن کمک کند برای این کار از الگورتیم fp max استفاده میکنند که خود نیس از درخت fp استفاده می کند. در این چهارچوب میزان حداقلی(minimum support) داده های دودویی به دست امده نیست محسابه میشود. بعد میخواهیم درصد حد اقل موارد (minimum factor) را پیدا کنیم
1. procedure m_s(binary data,m,n)
2. count = 0
3. for column = 1 to n do // n is total number of columns
4. for row = 1 to m do //m is the number of crime type attributes
5. if (column.row == 1) then
6. count++
7. endif
8. endfor
9. endfor
10. tot = m*n
11. min_factor = (count/(m*n))*100
12. min_sup = m*min_factor/100
13. return (min_support)
برای استفاده از الگوریتم fp max ابتدا داده های دوتایی را به fp tree میدهیم و به ما درخت جرم (crime tree) داده می شود، سپس درخت را به fp max میدهیم تا به ما تکرار شونده ترین نوع جرم (Maximum FrequentCrime Type (MFCT).) را برگرداند.
input : ct an fp tree // ct = crime tree
output : mfc (maximum frequent crime set)
variables : h-head
1. procedure cpmax(ct , mfct)
2. if(ct contains a branch b)
3. insert (hub) in mfct
4. else
5. for (each i in header table of ct)
6. append i to h
7. construct the cpb bi for i //crime pattern branch
8. t = {frequent crime sets in bi}
9. if not (head union tail in mfct)
10. construct the ct with head th
11. cpmax(cth)
12. end if
13. remove i from h
14. end for
15. end if
16. end
سپس باید به تجزیه و تحلیل همبستگی اطلاعات که نقش کلیدی ای در تحلیل داده ها دارد پرداخته شود، در این مقاله از ضریب همبستگی پیرسون استفاده شده که فرمول آن ب شرح زیر است
![ضریب همبستگی در مقاله ی [7]](https://boute.s3.amazonaws.com/242-7-1.jpg)
که r عددی بین -1 تا 1 است که هر چه به صفر نزدیک تر باشد ب معنی نداشتن همبستگی بیشتر داده هاست.
و استانه نیز از فرمول زیر محاسبه می شود که R مقدار قرار گرفته از سطر و ستون مشخص است. و rو c نیز هر کدام تعداد سطر و ستون ها می باشند
![آستانه در مقاله ی [7]](https://boute.s3.amazonaws.com/242-7-2.jpg)
علاوه بر پیدا کردن الگوریتم های مناسب، راه دیگری که ما را به نتیجه ی بهتر می رساند اعمال تغییرات روی داده ها می باشد. در مقاله ی [2] از آن جایی که فکر کردن این اطلاعات برای تشخیص کافی نیست اطلاعات دیگه ای را از سایت داده های آماری آمریکا استخراج کردند مثل متوسط درآمد یک محله، تنوع نژادی و ... . از طرفی برای این که دسته بندی جرائم بسیار دانه ریز بوده آن ها را دوباره دسته بندی کردند به این صورت که هر جرمی یا جرم دفتری ست یا جرم فنی/کارگری (Blue Collar Crimes vs White Collar Crimes) و هر جرمی یا جرم خشونت آمیز است یا جرم خشونت آمیز نیست (Violent vs Non-Violent Crimes:)
آن ها در اینجا از الگوریتم نیو بیز استفاده کرده اند که بر پایه ی مدل کردن چند متغییره توسط صاف کننده ی لاپلاس اطلاعات را دسته بندی می کند. در اینجا y یکی از چند نوع جرم میباشد و فی مدل چند جمله ای آن است. هم چنین هر کدام از ایکس ها یکی از ویژگی های دیگر هر سطر از داده ها میباشد.
اگر m داده ی اموزشی داشته باشیم پارامتر های زیر با استفاده از صاف کننده ی لاپلاس به دست می آیند
4. جنگل های تصادفی
یک روش گروهی بسیار معروف برای یاد گیریست که چند جداکننده (classifier) روی داده های اموزشی می سازد و بعد خروجی آن ها را ترکییب می کند که بهترین پیش بینی را روی داده های اعتبار سنجی انجام دهد. این الگوریتم یک الگوریتم بهینه سازی واریانس است که از تصمیم گیری تقسیم شده برای کمک به اجتناب از اضافه کردن بر روی داده های آموزشی استفاده می کند.
- نتیجه ی آزمایشات روی داده های اصلی با استفاده از دو الگوریتم بالا
این راه 30% روی داده های اموزشی و 25% روی داده های اعتبار سنجی جواب داده است. با این که با اندازه های مختلفی از داده تست شده است اما درصد درستی از 30 بیشتر نشد ، البته همین هم عدد خوبیست چرا که در این جا 39 نوع جرم متفاوت داریم.
همچنین از الگوریتم جنگل تصادفی استفاده کردیم که الگوریتم مناسب تری برای یادگیری ماشین در ویژگی هایی که عددی نمایش داده میشنود میباشد که ویژگی های دیتابیس ما هم در این موضوع دسته بندی شده می باشند و قابل انتساب به عدد هستند.
بعد از مدل سازی از طریق این الگورتیم خطا در مدل آموزشی 5% بود که عدد خیلی خوبی می باشد اما وقتی روی داده های اعتبار سنجی امتحان شد این عدد به 84% رسید که خطای بزرگی است و نشان میدهد واریانس زیاد است.
- نتیجه ی آزمایشات روی داده های کاهش یافته با استفاده از دو الگوریتم بالا
برای الگوریتم های جنگل های تصادفی، پارامترهای تعدیل، تعداد درخت ها و حداکثر عمق هر درخت است. برای انتخاب مقادیر بهینه برای این، الگوریتم را بر روی داده ها برای ترکیب های مختلف پارامترها آزمایش کردند. در نهایت، مجموعه ای از پارامترها را انتخاب کردند که نه تنها به بالاترین دقت کلی، بلکه همچنین بالاترین دقت و ارزش محاسبه را برای هر دو کلاس جرم داد. نمودار زیر نشان دهنده تغییرات دقت، دقت و فراخوانی برای مقادیر پارامتر برای طبقه بندی آزار و شکن آبی و سفید می باشد. از این تعداد، حداکثر دقت به دست آمده برای تعداد درختان 200 و حداکثر عمق 15٪، 79.18٪ بوده است. بنابراین، جنگل های تصادفی به خصوص در مورد جنایات یقه آبی نسبتا خوب عمل کردند.
البته مقالاتی مانند [6] نیز وجود دارند که ادعا می کنند استفاده از روش های خوشه بندی[^clustering] به کمک درخت تصمیم راه حل بهتری برای این مسئله می باشند اما به دلیل تاکید سایت مسابقه برای استفاده از دسته بندی به شرح آن نمی پردازیم.
برای پیاده سازی میتوان اول فاصله ها را از فایل csv با علامت ^ جایگزین کرد تا با ویرگول های داخل خود داده قاطی نشود. استفاده از این نماد برای جدا سازی در بسیاری از برنامه های متن کاوی مرسوم است. بعد داده هارا در قالب داده ی پاندا قرار داد که بتوان بعد از آن توسط تابع train_test_split موجود در Scikit-learn داده های آموزشی را به قسمت های کاملا رندوم تقسیم کرد.
# مراجع
[1] Rizwan Iqba ,Masrah Azrifah Azmi Murad, Aida Mustapha,Payam Hassany Shariat Panahy, and Nasim Khanahmadliravi, "An Experimental Study of Classification Algorithms for Crime Prediction"Indian Journal of Science and Technology| March 2013| Print ISSN: 0974-6846 | Online ISSN: 0974-5645
[2]Crime Prediction and Classification in San Francisco City ,Addarsh Chandrasekar, Abhilash Sunder Raj and Poorna Kumar
[3]San Francisco Crime Classification, Yehya Abouelnaga, School of Sciences and Egnineering, Department of Computer Science and Engineering, The American University in Cairo, New Cairo 11835, Egypt,arXiv:1607.03626v1 [cs.LG] 13 Jul 2016
[5]San Francisco Crime Classification, CSE 255 Assignment 2 Report, Shen Ting Ang, Weichen Wang, Silvia Chyou, 2015 Fall
[6]crime Analysis and Prediction Using Data Mining ,Shiju Sathyadevan, Devan M.S ,Amrita Center for Cyber Security ,Amrita Vishwa Vidyapeetham, Amritapuri, Kerala, India,978-1-4799-3486-7 114/$31.00©20 14 IEEE
[7]A Novel Approach for Intelligent Crime ,Pattern Discovery and Prediction,K.R Sai Vineeth , Ayush Pandey, Tribikram Pradhan,Dept. of Information and Communication Technology,Manipal Institute of Technology,Manipal University, Karnataka, Manipal, India ISBN No.978-1-4673-9545-8
## پیوندهای مفید
+ [صفحه مسابقه و مجموعه داده](https://www.kaggle.com/c/sf-crime)