مردم در کشورهای مختلف چه چیزهایی می‌خورند؟

تغییرات پروژه از تاریخ 1396/08/29 تا تاریخ 1396/11/11
غذاهای هر کشور و منطقه‌ی جغرافیایی و نوع موادی غذایی که در آن‌ها مصرف می‌کنند، جزئی از فرهنگ کشورها قلمداد می‌شود. به نحوی که می‌شود این جمله «غذایت را سفارش بده تا بگویم کجایی هستی!» را می‌شود یک قانون قلمداد کرد. در این پروژه می‌خواهیم همین کار را انجام دهید. یعنی باید با داشتن لیستی از مواد اولیه یک غذا، پیش‌بینی خواهیم کرد که این غذا در متعلق به کدام کشور است.
# مقدمه
امروزه کارشناسان، تغذیه را یکی از فاکتورهای بسیار مؤثر در سلامت انسان می‌دانند. از این‌رو با افزایش نگرانی‌ها در مورد سلامت مواد غذایی، جمع‌آوری اطلاعات در زمینه‌ی عادت‌های غذایی باتوجه به جغرافیای محل زندگی بسیار مورد توجه قرار گرفته است. فرهنگ یک کشور، میزان دسترسی به منابع غذایی، آب‌وهوا و حتی مذهب غالب در یک کشور را می‌توان از فاکتورهای بسیار مؤثر در عادات غذایی مردم آن‌ درنظر گرفت. علاوه‌بر این دانستن علایق عمده‌ی مردم یک کشور درزمینه‌های مختلف، در این پروژه به‌طور خاص درمورد مواد غذایی، نقش بسیار مهمی در به‌دست گرفتن بازار هدف کشور آن مختلف دارد. از این‌رو، به‌دست آوردن عادت‌های غذایی غالب در هرکشور علاوه بر برخورداری از اهمیت در حوزه سلامت، کاربرد اقتصادی فراوانی نیز دارد.

## شرح مسئله

در راستای پیش‌بینی سبد غذایی مردم یک کشور، [این مسابقه](https://www.kaggle.com/c/whats-cooking) نیز طراحی شده است که روش کاری ما در این پروژه نیز شبیه به آن است. 
در این مسئله یک [دیتاست](https://www.kaggle.com/c/whats-cooking/data) متشکل از مواد غذایی تشکیل‌دهنده‌ی غذاهایی که در کشورهای مختلف، به تفکیک غذا و کشور، سرو می‌شوند در اختیار ما قرار گرفته‌است. باتوجه به این دیتاست ما باید به روشی برسیم که با گرفتن مواد تشکیل‌دهنده یک غذا، تشخیص دهیم آن غذا متعلق به کدام کشور است، یا به‌عبارتی درکدام کشور متقاضی بیش‌تری دارد. 

## اهمیت مسئله

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

## کاربردها

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

## توضیح مقاله اول[^KYUNG-JOONG KIM AND CHANG-HO CHUNG-Tell Me What You Eat, and I Will Tell You Where You Come From: A Data Science Approach for Global Recipe Data on the Web-2016]

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

+ Hierarchical clustering
+ Ingredient network analysis
+ Classification
+ مرحله اول - خوشه‌بندی سلسه مراتبی
خوشه‌بندی سلسله‌مراتبی یکی از روش‌های رایج در آنالیز اطلاعات است. ایده‌ی اصلی این روش، ایجاد یک درخت دودویی از اطلاعات است که در آن اطلاعات       مشابه در یک خوشه قرار می‌گیرند.[^COS424 Princton University-David M. Blei-2008] 
برای استفاده از این روش برای حل مسئله فوق، مقاله مورد نظر به صورت زیر عمل کرده است:
ابتدا توسط یکی از الگوریتم‌های خوشه‌بندی، ارتباطات پنهان بین دستورهای غذایی کشورهای مختلف را باتوجه به مواد غذایی سازنده آن به‌دست می‌آوریم. درحیقت این عمل را بدین منظور انجام می‌دهیم که کشورهای مشابه و غیرمشابه ازنظر عادت غذایی را دسته‌بندی کنیم. یک نمونه از خوشه‌بندی صورت گرفته شده توسط این مقاله را در ادامه می‌بینیم:
![مثالی از خوشه‌بندی کشورها](https://boute.s3.amazonaws.com/250-clus.png) 
درمثال فوق، نقطه‌چین مرز خوشه‌ها را مشخص می‌کند، برای مثال اگر نقطه‌چین پایینی را مرز قرار دهیم،تنها دو کشور کره و ژاپن در یک خوشه قرار می‌گیرند.
برای استفاده از این الگوریتم باید دو چیز را بتوانیم مشخص کنیم،
+ مرز خوشه‌بندی را به چه صورت قرار دهیم؟
+ از چه الگوریتمی برای خوشه بندی استفاده کنیم.
این مقاله برای خوشه‌بندی از الگوریتمی استفاده می‌کند که در آن از مؤلفه‌ای تحت عنوان **dissimilarity** استفاده شده است که تفاوت‌های میان دو کشور را مشخص می‌کند و پس از تعیین آن عمل خوشه‌بندی را انجام می‌دهد.
![فرمول محاسبه میزان تفاوت میان کشور 1 و 2](https://boute.s3.amazonaws.com/250-d.png)
که در آن
![فرمول محاسبه احتمال رخداد ماده i در دستور غذایی کشور c در دیتاست](https://boute.s3.amazonaws.com/250-Untitled.png)میزان تفاوت ماده غذایی i در دو کشور](https://boute.s3.amazonaws.com/250-CodeCogsEqn.gif)
که در آن
$$P_{c}^{i} = \frac {\mathrm{n_{c}^{i}}}{\mathrm{N_{c}}}$$

+ مرحله دوم - آنالیز شبکه مواد غذایی تشکیل‌دهنده
در این مرحله شبکه‌ای از مواد غذایی تشکیل‌دهنده ایجاد می‌شود، این شبکه یک گراف است که به‌صورت زیر تولید می‌شود:
	+ هر رأس یک ماده‌ی غذایی تشکیل دهنده دستور غذاست.
	+ اگر هر دو ماده در یک دستور غذایی موجود باشند، یک یال میان آن‌ها رسم می‌شود.
	+ وزن هر یال عبارت است از تعداد دفعاتی که هر دو ماده در یک دستور غذایی دیده شده‌اند.
گراف INc، بیانگر شبکه مواد غذایی کشور c است که شامل داده‌های آماری مواد غذایی تشکیل‌دهنده دستورهای غذایی آن کشور هستند و توسط الگوریتم استخراجی backbone به دست آمده‌اند.
![نمونه گراف مواد غذای در دو کشور فیلیپین و اسکاتلند](https://boute.s3.amazonaws.com/250-Untitled1.png)
+ مرحله سوم - تقسیم‌بندی
در این بخش، توسط مدل‌های تقسیم‌بندی، برنامه اقدام به تصمیم‌گیری درمورد دستورهای غذایی جدید می‌کند. در این مرحله برنامه به‌وسیله الگوریتم‌های پیاده‌سازی شده در بخش قبل دستورهای غذایی موجود را مورد بررسی قرار می‌دهد و  پیش‌بینی خود را با جواب موجود مقایسه می‌کند و به این شکل خود را بهبود می‌بخشد. بهترین الگوریتم، الگوریتمی است که توسط آن بتوانیم برای هرکشور الگویی متفاوت با سایر کشورها به‌دست آوریم. 
![نمونه‌ای از مدل تقسیم‌بندی-درخت تصمیم گیری](https://boute.s3.amazonaws.com/250-tree.png)
در شکل بالا رأس‌های میانی، مواد غذایی و برگ‌ها کشورها هستند. 
درحالت کلی نحوه‌ی آنالیز مسئله به‌صورت زیر است:
![نگاه کلی به راهکار حل مسئله](https://boute.s3.amazonaws.com/250-Untitled2.png)

## مقالات مشابهه دوم
مقاله **Recipe recommendation using ingredient networks**[^Chun-Yuen Teng, Yu-Ru Lin, Lada.A Adamic-Recipe recommendation using ingredient network-2012] نیز رویکردی تقریباً مشابه مقاله بیان شده دارد اما رویکرد مقاله اول کامل‌تر و به‌روزتر است لذا همان مقاله را به‌صورت کامل توضیح داده و پیاده‌سازی کردیم.

## مقالات با رویکرد مشابه در سایر زمینه‌ها
کارهای بسیار زیاد و مشابهی در زمینه‌های مختلف صورت گرفته، اما برای حل مسئله روش ذکر شده در مقاله فوق بهترین و بهینه‌ترین روش است. بااین وجود در این بخش به بررسی اجمالی برخی دیگر از مقاله‌ها نیز می‌پردازیم.
+ پیش‌بینی میزان سودآوری از مشتری [^https://technet.microsoft.com/en-us/library/dd883232(v=sql.100).aspx]   
این مقاله با استفاده از روش‌های داده‌کاوی به بررسی میزان سودآوری کار باتوجه به فاکتوهای مختلف ازجمله مکان جغرافیایی می‌پردازد.
+ پیش بینی شرایط محیط زیستی باتوجه به فاکتورهای مؤثر در شرایط اقلیمی

# آزمایش‌ها
درحال حاضر پیاده‌سازی کامل انجام نشده‌است اما به‌منظور پیاده‌سازی مناسب پروژه به‌صورت زیر فازبندی شد و اکنون فاز یک درحال انجام است.
**فاز اول- محاسبه درصد احتمال رخداد ماده غذایی در دستور غذایی یک کشور برای تمامی مواد غذایی**
**فاز دوم - خوشه بندی**
**فاز سوم - ایجاد شبکه مواد غذایی**
**فاز چهارم - تقسیم‌بندی و بهینه‌سازی**

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

## پیاده‌سازی به کمک الگوریتم‌های بیان شده در مقاله اول
در این قسمت، سعی بر این بود که الگوریتم‌های مطرح شده در مقاله اول باتوجه به دیتاست موجود در سایت مسابقه پیاده سازی شوند، سپس باتوجه به نتایج به دست آمده، فایل نهایی مورد بررسی قرار گیرد.
برای پیاده‌سازی این بخش از زبان برنامه‌نویسی سی‌شارپ استفاده شد چراکه این زبان برنامه‌نویسی قابلیت‌های زیادی برای پشتیبانی از فایل با فرمت *json* دارد. 
ما برای این‌که بتوانیم اطلاعات موجود در دیتاست را مورد تحلیل قرار دهیم ابدا باید بتوانیم داده‌های موجود در آن را استخراج و تقسیم‌بندی کنیم. 
همان‌طور که پیش‌تر نیز به آن اشاره شده‌است، دیتاست شامل دستور غذاهایی است که در کشورهای مختلف مصرف می‌شوند. هر دستور غذا یک *id* دارد و شامل *ingredients* یا همان محتویات غذای مدنظر است. هم‌چنین هردستور غذایی توسط تگ *cuisine* به یک کشور نسبت داده می‌شود.
همان‌طور که در قسمت قبل نیز به آن اشاره شد، 
$$P_{c}^{i} = \frac {\mathrm{n_{c}^{i}}}{\mathrm{N_{c}}}$$
لذا باید ابتدا فراوانی هریک از مواد غذایی را در هریک از کشورها و نیز به‌صورت کلی به‌دست آوریم.
ابتدا توسط قطعه کد زیر تمامی مواد غذایی موجود در دیتاست استخراج می‌کنیم:

	using System;
	using System.Collections.Generic;using System.Linq;
	using System.Text;using System.Threading.Tasks;
	using System.IO;
	using Newtonsoft.Json;
	namespace ConsoleApp1{
    class Program
    {
        static void Main(string[] args)
        {
            LoadJson();
            Console.ReadLine();
        }
        public static void LoadJson()
        {
            using (StreamReader r = new StreamReader("train.json"))
            {
                string json = r.ReadToEnd();
                dynamic array = JsonConvert.DeserializeObject(json);
                foreach (var item in array)
                {
                    Console.WriteLine("{0} {1}", item.id, item.ingredients);
                }            }
        }
    }
    }

بعد از استخراج کشورها و مواد غذایی آن‌ها باید فراوانی هریک از مواد تشکیل‌دهنده را به‎دست آوریم. توسط قطعه کدهای زیر این عمل را انجام می‌دهیم.

    using Newtonsoft.Json;
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace Read_Json_2
    {
        class Program
        {
            static Dictionary<Tuple<string, string>, int> myList = new Dictionary<Tuple<string, string>, int>();
            static void Main(string[] args)
            {
                LoadJson();
                Console.ReadLine();
    
            }
            private static int findElement(string c, string d)
            {
                if (myList.Count == 0)
                    return 0;
                try
                {
                    return myList[new Tuple<string, string>(c, d)];
                }
                catch (Exception e)
                {
    
                    return 0;
                }
    
            
            }
            private static void updateElement(string c, string d)
            {
                myList[new Tuple<string, string>(c, d)]++;
          
            }
            public static void LoadJson()
            {
                try
                {
    
                    using (StreamReader r = new StreamReader("train.json"))
                    {
                        string json = r.ReadToEnd();
                        dynamic array = JsonConvert.DeserializeObject(json);
           
                        foreach (var item in array)
                        {
                           
                            foreach (string ingredient in item.ingredients)
                            {
                                if (findElement((string)item.cuisine, ingredient) == 0)
                                {
                                    try
                                    {
                                        myList.Add(new Tuple<string, string>((string)item.cuisine, ingredient), 1);
    
    
                                    }catch(Exception ex)
                                    {
                                        Console.WriteLine("C {0} ,  i {2}", (string)item.cuisine, ingredient);
                                    }
                                  }
                                else
                                {
                                    updateElement((string)item.cuisine, ingredient);
                                  
                                }
                            }
    
                        }
                        foreach (var item in myList)
                        {
                            Console.WriteLine("{0} {1} {2} \n ", item.Key.Item1, item.Key.Item2, item.Value);
                        }
    
                    }
                }
                catch (Exception ex)
                {
    
                    throw ex;
                }
    
            }
    
    
        }
    }

کد بالا جهت محاسبه فراوانی هریک از مواد در منوی هریک از کشورهاست.

    using Newtonsoft.Json;
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace Read_Json_2
    {
        class Program
        {
            static Dictionary<Tuple<string>, int> myList = new Dictionary<Tuple<string>, int>();
            static void Main(string[] args)
            {
                LoadJson();
                Console.ReadLine();
    
            }
            private static int findElement( string d)
            {
                if (myList.Count == 0)
                    return 0;
                try
                {
                    return myList[new Tuple< string>(d)];
                }
                catch (Exception e)
                {
    
                    return 0;
                }
    
            
            }
            private static void updateElement( string d)
            {
                myList[new Tuple<string>( d)]++;
          
            }
            public static void LoadJson()
            {
                try
                {
    
                    using (StreamReader r = new StreamReader("train.json"))
                    {
                        string json = r.ReadToEnd();
                        dynamic array = JsonConvert.DeserializeObject(json);
           
                        foreach (var item in array)
                        {
                           
                            foreach (string ingredient in item.ingredients)
                            {
                                if (findElement( ingredient) == 0)
                                {
                                    try
                                    {
                                        myList.Add(new Tuple< string>( ingredient), 1);
    
    
                                    }catch(Exception ex)
                                    {
                                        Console.WriteLine("C {0} ",  ingredient);
                                    }
                                  }
                                else
                                {
                                    updateElement(ingredient);
                                  
                                }
                            }
    
                        }
                        foreach (var item in myList)
                        {
                            Console.WriteLine("{0} {1}  \n " ,item.Key.Item1, item.Value);
                        }
    
                    }
                }
                catch (Exception ex)
                {
    
                    throw ex;
                }
    
            }
    
    
        }
    }

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

    public static int Main(string[] args)
    {
        System.Console.WriteLine("{0}", alglib.ap.format(rep.z)); // EXPECTED: [[2,4],[0,1],[3,6],[5,7]]
        // In our example we have:
        // * P=[3,4,0,2,1]
        // * PZ=[[0,0,1,1,0,0],[3,3,4,4,0,0],[2,2,3,4,0,1],[0,1,2,4,1,2]]
        //
        // Permutation array P tells us that P0 should be moved to position 3,
        // P1 moved to position 4, P2 moved to position 0 and so on:
        //
        //   (P0 P1 P2 P3 P4) => (P2 P4 P3 P0 P1)
        //
        // Merges array PZ tells us how to perform merges on the sorted dataset.
        // One row of PZ corresponds to one merge operations, with first pair of
        // elements denoting first of the clusters to merge (start index, end
        // index) and next pair of elements denoting second of the clusters to
        // merge. Clusters being merged are always adjacent, with first one on
        // the left and second one on the right.
        System.Console.WriteLine("{0}", alglib.ap.format(rep.p)); // EXPECTED: [3,4,0,2,1]
        System.Console.WriteLine("{0}", alglib.ap.format(rep.pm)); // EXPECTED: [[0,0,1,1,0,0],[3,3,4,4,0,0],[2,2,3,4,0,1],[0,1,2,4,1,2]]
        System.Console.ReadLine();
        return 0;
    }
    

توضیحات به‌صورت کامل درون کد بیان شده، از این الگوریتم برای خوشه بندی داده‌ها استفاده کردیم. (ازآنجایی‌که امکان آپلود فایل وجود ندارد فایل ویژوال استودیوی برنامه به همراه خروجی آن ایمیل می‌شود.)
متریک اسفاده شده در این مرحله همان d بیان شده در قسمت قبل است.

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

### روش اول- استفاده از کتابخانه **pandas** جهت تحلیل داده‌ها و کتابخانه **scikit-learn** جهت خوشه‌بندی و اجرای الگوریتم‌های یادگیری ماشین
همان‌طور که در قسمت اول نیز توضیح داده شد ما درابتدا باید داده‌ها را از فایل ورودی بخوانیم و فراوانی آن‌ها را در هریک از منوها و به صورت‌کلی در تمامی منوها به‌دست آوریم. کتابخانه **pandas** این امکان را فراهم آورده که بتوانیم به راحتی این عملیات را روی فایل ورودی انجام دهیم.  
درابتدا توسط دستورات زیر فایل جیسون را باز کرده و محتویات آن را می‌خوانیم.

	import pandas as pd
	df_train = pd.read_json('train.json')
	df_train.head()

همان‌طور که پیش‌تر نیز اشاره کردیم، هر دستور غذایی سه مؤلفه *id* و *cuisine* و *ingredients* را دارد.
درابتدا باید بررسی کنیم و ببینیم که از هرکشوری چند منوی غذایی در دیتاست ما وجود دارد. بدیهی است هرچه تعداد منوهای غذایی هرکشور بیش‌تر باشد، امکان پیش‌بینی منوهای غذایی آن کشور بالاتر است. 
بااستفاده از قطعه کد مقابل تعداد کل منوها را به‌دست می‌آوریم.

	%matplotlib inline
	import matplotlib.pyplot as plt
	plt.style.use('ggplot')
	df_train['cuisine'].value_counts().plot(kind='bar')

کد بالا برای ما به‌صورت بصری نموداری رسم کرده و خروجی را نمایش می‌دهد. نمودار به‌صورت زیر است.

![نمودار فراوانی منوهای هرکشور در دیتاست مسابقه](https://boute.s3.amazonaws.com/250-nemoodar.png)

حال باید مؤلفه‌ای را که در قسمت قبل تحت عنوان احتمال رخداد از آن یاد کردیم محاسبه کنیم. برای این کار به صورت زیر عمل می‌کنیم:

	df_train['all_ingredients'] = df_train['ingredients'].map(";".join)
	df_train.head()
	df_train['all_ingredients'].str.contains('garlic cloves')

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

![فراوانی سیر در منوهای مختلف غذاییی در کشورها](https://boute.s3.amazonaws.com/250-sir.png)

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

	from sklearn.feature_extraction.text import CountVectorizer
	from sklearn.preprocessing import LabelEncoder
	from sklearn.cross_validation import train_test_split
	from sklearn.linear_model import LogisticRegression
	cv = CountVectorizer()
	X = cv.fit_transform(df_train['all_ingredients'].values)
	enc = LabelEncoder()
	y = enc.fit_transform(df_train.cuisine)
	X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
	logistic = LogisticRegression()
	logistic.fit(X_train, y_train)
	logistic.score(X_test, y_test)

روش فوق درانتها میزان دقت پاسخ‌گویی را هم پیش‌بینی می‌کند که در این‌جا حدود 77 درصد است.
یک روش دیگر که دقت پاسخ‌گویی بالاتری دارد نیز در ادامه ذکر شده‌است.

	from sklearn.metrics import confusion_matrix
	plt.figure(figsize=(10, 10))
	cm = confusion_matrix(y_test, logistic.predict(X_test))
	cm_normalized = cm.astype('float') / cm.sum(axis=1)[:, np.newaxis]
	plt.imshow(cm_normalized, interpolation='nearest')
	plt.title("confusion matrix")
	plt.colorbar(shrink=0.3)cuisines = df_train['cuisine'].value_counts().index
	tick_marks = np.arange(len(cuisines))
	plt.xticks(tick_marks, cuisines, rotation=90)
	plt.yticks(tick_marks, cuisines)
	plt.tight_layout()
	plt.ylabel('True label')
	plt.xlabel('Predicted label')

خروجی کد بالا ماتریس درهم‌ریختگی سؤال مسابقه است که به‌صورت زیر نمایش داده می‌شود.

![ماتریس درهم‌ریختگی دیتاست مسابقه](https://boute.s3.amazonaws.com/250-matrix.png)

طبق ماتریس بالا مشاهده می‌کنیم که منوی هریک از کشورها با چه دقتی پیش‌بینی شده است.

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

## روش دوم - استفاده از نرم افزار R جهت تحلیل داده

	#- load packages
	library(jsonlite)
	library(tm)library(data.table)
	library(Matrix)
	library(caret)
	library(SnowballC)
	library(xgboost)
	library(Ckmeans.1d.dp)
	#- load data files and flatten
	train_raw  <- fromJSON("../input/train.json", flatten = TRUE)
	submit_raw <- fromJSON("../input/test.json", flatten = TRUE)
	#- pre-process the ingredients 
	(basic)train_raw$ingredients <- lapply(train_raw$ingredients, FUN=tolower)
	train_raw$ingredients <- lapply(train_raw$ingredients, FUN=function(x) gsub("-", "_", x)) # allow dash e.g. "low-fat"
	train_raw$ingredients <- lapply(train_raw$ingredients, FUN=function(x) gsub("[^a-z0-9_ ]", "", x)) # allow regular character and spaces
	submit_raw$ingredients <- lapply(submit_raw$ingredients, FUN=tolower)
	submit_raw$ingredients <- lapply(submit_raw$ingredients, FUN=function(x) gsub("-", "_", x)) # allow dash e.g. "low-fat"
	submit_raw$ingredients <- lapply(submit_raw$ingredients, FUN=function(x) gsub("[^a-z0-9_ ]", "", x)) # allow regular character and spaces
	#- create a matrix of ingredients in both the TRAIN and SUBMIT set
	c_ingredients <- c(Corpus(VectorSource(train_raw$ingredients)), Corpus(VectorSource(submit_raw$ingredients)))
	#- create simple DTMc_ingredients
	DTM <- DocumentTermMatrix(c_ingredients)
	c_ingredientsDTM <- removeSparseTerms(c_ingredientsDTM, 1-3/nrow(c_ingredientsDTM)) # remove if < 3 occurancesc_ingredients
	DTM <- as.data.frame(as.matrix(c_ingredientsDTM))
	#- feature engineering (basic)
	#- add cuisine for TRAIN set, default to "italian" for the SUBMIT set
	c_ingredientsDTM$cuisine <- as.factor(c(train_raw$cuisine, rep("italian", nrow(submit_raw))))
	#- split the DTM into TRAIN and SUBMIT
	setsdtm_train  <- c_ingredientsDTM[1:nrow(train_raw), ]
	dtm_submit <- c_ingredientsDTM[-(1:nrow(train_raw)), ]
	#- Model 4: xgboost (single model for all cuisine types)
	#- prepare the spare matrix (note: feature index in xgboost starts from 0)xgbmat     <- xgb.DMatrix(Matrix(data.matrix(dtm_train[, !colnames(dtm_train) %in% c("cuisine")])), label=as.numeric(dtm_train$cuisine)-1)
	#- train our multiclass classification model using softmax
	xgb        <- xgboost(xgbmat, max.depth = 25, eta = 0.3, nround = 200, objective = "multi:softmax", num_class = 20)
	#- predict on the SUBMIT set and change cuisine back to string
	xgb.submit      <- predict(xgb, newdata = data.matrix(dtm_submit[, !colnames(dtm_submit) %in% c("cuisine")]))
	xgb.submit.text <- levels(dtm_train$cuisine)[xgb.submit+1]
	#- load sample submission file to use as a template
	sample_sub <- read.csv('../input/sample_submission.csv')
	#- build and write the submission file
	submit_match   <- cbind(as.data.frame(submit_raw$id), as.data.frame(xgb.submit.text))
	colnames(submit_match) <- c("id", "cuisine")
	submit_match   <- data.table(submit_match, key="id")
	submit_cuisine <- submit_match[id==sample_sub$id, as.matrix(cuisine)]
	submission <- data.frame(id = sample_sub$id, cuisine = submit_cuisine)
	write.csv(submission, file = 'xgboost_multiclass.csv', row.names=F, quote=F)
	# plot the most important features
	names <- colnames(dtm_train[, !colnames(dtm_train) %in% c("cuisine")])
	importance_matrix <- xgb.importance(names, model = xgb)
	xgb.plot.importance(importance_matrix[1:30,])
```
کدی که در بالا ارائه شد توسط کتابخانه‌های پیش‌فرض ارائه شده توسط R پیاده سازی شد. ایده‌ کد از نفر اول شرکت‌کننده در مسابقه گرفته شد و یادگیری پیاده‌سازی آن ازطریق [این سایت](https://www.analyticsvidhya.com/blog/2015/12/kaggle-solution-cooking-text-mining-competition/) صورت گرفت.
باتوجه به ثبتی که در سایت مسابقه انجام گرفت، این کد با زمان اجرای بسیار کوتاه و دقت حدود 82 درصد بهترین پاسخ‌گویی را برای ما داشت.
(ازآنجایی‌که امکان آپلود فایل وجود ندارد فایل برنامه به همراه خروجی آن ایمیل می‌شود.)

## روش سوم - استفاده از کتابخانه **numpy** و **scikit-learn**  درزبان پایتون
این روش توسط خود ما پیاده سازی نشد و ما صرفاً از کد یکی از شرکت‌کنندگان مسابقه در محیط لینوکس اجرا گرفتیم و روش وی را جهت مقایسه با سایر روش‌ها و یافتن بهینه‌ترین روش بررسی کردیم. کدهای استفاده شده توسط این شرکت کننده بسیار مشابه روش اول ذکر شده بود. درادامه به بررسی کد و تحلیل پیچیدگی زمانی و فضایی آن می‌پردازیم.
کد برنامه که از [سایت گیت هاب](https://github.com/ogencoglu/WhatsCooking/blob/master/cook_it_up.py) قابل مشاده است، کاملاً مشابه روش اول عمل کرده. ابتدا داده‌ها از فایل ورودی استخراج شده‌اند و فراوانی آن‌ها مورد بررسی قرار گرفته است. سپس بااستفاده از قابلیت‌های کتابخانه *scikit-learm*ماتریس دیتاست جهت تحلیل داده‌ها ایجاد شده است و درانتها فایل خروجی ایجاد شده است.
این روش نیز همانند روش اول حافظه بسیار زیادی برای اجرا نیاز به‌نحوی تنها یک‌بار از سه بار کامپیوتر با رم 8 گیگ توانست خروجی مطلوب را برای ما ایجاد کند. دقت این روش حدود 77 درصد است.

## مقایسه نهایی
در بالا چهار روش مختلف برای حل مسئله پیش‌بینی منوی غذایی کشورها بیان شد. البته روش‌های دیگری هم مانند روش بیان شده در [این صفحه](https://github.com/T1anyuZhu/WhatsCooking) یا بسیاری روش‌های دیگر وجود دارد. روش‌های بیان شده در عین سادگی برنامه‌نویسی دقت بالایی دارند اما همان‌طور که مشاهده کردیم با چالش بسیار بزرگ فضای حافظه مواجه هستند. 
کد اول که به زبان سی‌شارپ پیاده‌سازی شده بود، باوجود این‌که زمان اجرای آن بسیار پایین بود دقت حدوداً 50 درصدی داشت که دقت خوبی به‌حساب نمی‌آید 
همچنین به‌دلیل این‌که تمامی اطلاعات منوها را برای ایجاد شبکه غذایی در حافظه بارگذاری می‌کرد، با مشکل حافظه نیز مواجه بود.
  کد دوم باوجود داشتن دقت حدوداً 70 درصد که دقت نسبتاً خوبی به‌شمار می‌آید هنوز هم با مشکل فضای حافظه مواجه بود. این روش درمواجهه با دیتاست‌های نسبتاً بزرگ نمی‌تواند در دستگاه‌هایی با رم کم‌تر از 16 گیگ به خوبی پاسخ‌گو باشد. این مشکلی است که کد چهارم هم با آن مواجه است. درمقام عمل کد چهارم ازلحاظ زمانی حتی از کد اول هم کندتر عمل می‌کند(به‌علت کتابخانه استفاده شده) اما دقت آن حدوداً سه چهار درصد بالاتر از دقت روش اول است. پس درعمل این دو روش دقت حدوداً یکسانی دارند و اگر بنابر انتخاب از میان این دو روش باشد بهتر است که روش اول انتخاب شود.
  درنهایت روش سوم با ارائه دقت بیش از 80 درصد و زمان اجرایی بسیار پایین دررتبه اول روش‌ها قرار گرفت. گرچه در این روش هم ما هم‌چنان با مشکل حافظه مواجه هستیم اما استفاده بهینه R از فضای حافظه باعث شده تا ما دیرتر با چالش حافظه در این روش مواجه شویم.
  قطعاً روش‌های بهتری از روش‌های بیان شده وجود دارد. هرکدام ازین روش‌ها بخشی از نیازهای ما را فراهم می‌کنند. برخی سرعت پاسخ‌گویی مناسبی دارند و برخی فضای کم‌تری اشغال می‌کنند. تجمیع همه مؤلفه‌ها به بهترین صورت در یک روش کار بسیار مشکلی است اما روش سوم تاحدودی همه این‌ نیازها را درکنار هم قرار داده است.  
  (لازم به ذکر است ازلحاظ تکنیک برنامه‌نویسی و حجم کد نیز روش سوم بهینه‌ترین روش موجود است.)

# کارهای آینده
ایده‌ای که به ذهن خود من رسید و نتوانستم روی آن در این بخش مطالعه کنم، استفاده از روش حل این مسئله برای تبلیغات اینترتی بود. یعنی تحقیق روی این مسئله که آیا سامانه‌ای وجود دارد که باتوجه به منطقه‌ی جغرافیایی و ... تبلیغات را محلی کند یا نه.

# مراجع
[1] KYUNG-JOONG KIM, CHANG-HO CHUNG, “Tell me what you eat and I will tell you where you come from : a data science approach for global recipe data on the web,” Sejong University, Seoul, 2016.
[2] L. I. Kuncheva, "Combining Pattern Classifiers, Methods and Algorithms," New York, NY, USA, Wiley 2004.
[3] E. Alpaydin, "Introduction to Machine Learning," Cambridge, MA, USA, MIT Press, 2009.
[4] C.-Y. Teng, Y.-R. Lin, and L. A. Adamic, ‘‘Recipe recommendation using ingredient networks,’’ in Proc. 3rd Annu. ACM Web Sci. Conf., 2012, pp. 298–307.
[5] Y.Ahn,S.Ahnert,J.Bagrow,andA.-L.Barabasi,‘‘Flavor network and the principles of food pairing,’’ Sci. Rep., vol. 1, Art.no. 196, Dec. 2011.
[6]Princton university course, David M. Blei, COS424
[7]https://technet.microsoft.com/en-us/library/dd883232(v=sql.100).aspx