درختان سریع و مقرون به صرفه

در دانش پروسه تصمیم گیری، که شامل روانشناسی، هوش مصنوعی و علم مدیریت می‌شود، درخت سریع و مقرون به صرفه (FFT یا Fast-and-frugal tree) یکی از انواع درختان طبقه بندی یا درخت تصمیم است. همانطور که در تصویر شماره 1 – در ادامه آن را با جزئیات توضیح می‌دهیم – درختان سریع و مقرون به صرفه، ساختار گرافیکی ساده ای هستند که در هر مرحله یک سوال میپرسد. هدف این است که یک شئ را ( در شکل 1: یک مریض که به سکته قلبی مشکوک است) در یک دسته بندی با دیدگاه تصمیم گیری طبقه بندی کنیم (در شکل 1 دو احتمال وجود داد، اینکه مریض در بخش بستری شود یا دربخش مراقبت های عروق کرونر). برخلاف درختان طبقه بندی و تصمیم گیری دیگر، مانند Leo Breimans’s CART، درختان سریع و مقرون به صرفه عمداً ساده تعریف شده اند، هم در ساخت و هم در اجرا آن‌ها و با اطلاعات کمتر و با سرعت بیشتر کار می‌کنند. به عنوان مثال، درخت شکل 1 فقط یک تا حداکثر سه سوال میپرسد.

درختان سریع و مقرون به صرفه در سال 2003 توسط لورا مارتینیون (Laura Martignon ) ، ویتوش (Vitouch) ، تاکزاوا (Takezawa) و فورستر (Forster ) ^[۱] معرفی و مفهوم سازی شدند و خانواده ای از رهیافت‌های آنی ساده را در سنت Gerd Gigerenzer و Herbert A. Simon در مورد مدل‌های رسمی اکتشافی به وجود آوردند. قبل از اینکه اصطلاح درختان سریع و مقرون به صرفه در سال 2003 ابداع شود ، این مدل های اکتشافی در زمینه های مختلفی مورد استفاده قرار گرفته بود بدون اینکه صریحاً مفهوم سازی یا تعریف شده باشد.

در کارهایی که باید یک تصمیم دودویی یا طبقه بندی انجام شود (به عنوان مثال ، پزشک باید تصمیم بگیرد که بیمار با درد شدید قفسه سینه را به بخش مراقبت های عروق کرونر یا یک تخت پرستاری عادی اختصاص دهد) و m نشانه ( این اصطلاحاتی است که در روانشناسی برای آنچه در هوش مصنوعی feature، و در علوم مدیریت attribute نامیده می شود، استفاده می شود) ، برای تصمیم گیری در دسترس است ، FFT به شرح زیر تعریف می شود:

درخت سریع و مقرون به صرفه، درخت تصمیم گیری است که دارای m +1 خروجی باشد، که برای هر m – 1 نشانه اول فقط یک خروجی و برای نشانه آخر دو خروجی داشته باشد.

از نظر ریاضی ، درختان سریع و مقرون به صرفه را می توان به عنوان اکتشافی واژگانی یا به عنوان مدل های خطی با وزن غیر جبرانی که توسط مارتینیون (Martignon) ، کاتسیکوپولوس (Katsikopoulos) و وویکه (Woike) در سال 2008 اثبات شده است، مشاهده کرد. خصوصیات رسمی و ساخت آنها نیز با استفاده از تئوری تشخیص سیگنال توسط Luan ، Schooler و Gigerenzer در سال 2011 تحلیل شده است ^[۲] .

یک درخت سریع و مقرون به صرفه چگونه کار می کند ویرایش

در این بخش نحوه ساخت و استفاده از یک درخت سریع و مقرون به صرفه شرح داده شده است.

مراحل ساخت ویرایش

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

در ادبیات مربوط به درختان سریع و مقرون به صرفه ، الگوریتم های مختلفی پیشنهاد شده است ^[۱] ^[۳] برای (1) مربت سازی نشانه ها و (2) تصمیم گیری در مورد اینکه کدام پاسخ احتمالی به یک سوال مربوط به نشانه، بلافاصله به یک خروجی منجر می‌شود.توجه داشته باشید که اگر (1) و (2) با موفقیت انجام شود ، یک درخُت سریع و به صرفه به طور کامل ساخته و تعریف شده است. غالباً ، به منظور ساده سازی و شهودی سازی، الگوریتم ها از (1) معیارهایی ساده در مورد نشانه "خوب بودن" استفاده می کنند (به عنوان مثال ، همبستگی بین نشانه و دسته بندی ، با در نظر گرفتن هر نشانه مستقل از نشانه های دیگر) و (2) انتخاب هایی ساده در مورد خروجی ها (به عنوان مثال ، تصمیم گیری مستقل در مورد هر خروجی با دیگر خروجی ها) ، با این حال الگوریتم های پیچیده تری نیز ارائه شده است.

اجرا ویرایش

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

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

شکل 1، یک درخت سریع و مقرون به صرفه را برای طبقه بندی یک بیمار به عنوان "خطر بالا"ی سکته قلبی که در این صورت باید به "بخش مراقبت های عروق کرونر" ارسال شود یا "کم خطر" که در این صورت به یک "تخت پرستاری عادی" ارسال شود، را نشان می ده. (گرین و مهر ، 1997) .

سه بیمار جان ، مری و جک را در نظر بگیرید:

جان دارای تغییر در بلوک ST است بنابراین "پر خطر" طبقه بندی می شود و به بخش مراقبت های عروق کرونر فرستاده می شود - بدون در نظر گرفتن نشانه های دیگر
مری هیچ تغییری در بلوک ST ندارد ،او به عنوان اصلی ترین مشکل خود، درد در ناحیه قفسه سینه دارد ، اما هیچ یک از پنج عامل باقی مانده را ندارد ، بنابراین پس از بررسی هر سه نشانه ، به عنوان "کم خطر" طبقه بندی می شود و به یک تخت پرستار عادی ارسال می شود.
جک هیچ تغییری در بلوک ST ندارد و درد قفسه سینه اصلی ترین مشکل او نیست ، بنابراین با در نظر گرفتن این دو نشانه "کم خطر" طبقه بندی می شود و به یک تخت پرستاری عادی ارسال می شود.

کارایی ویرایش

در مطالعات Laskey and Martignon (2014) نشان داده شده است که دقت و قدرت درختان سریع و مقرون به صرفه با معیارهای Bayesian قابل مقایسه است. مطالعات گسترده ای در مقایسه عملکرد درختان سریع و مقرون به صرفه با الگوریتم های طبقه بندی مورد استفاده در علم آمار و یادگیری ماشین ، مانند Naive Bayes ، CART ، جنگل های تصادفی و رگرسیون لجستیک نیز، با استفاده از بیش از ده‌ها مجموعه داده که از دنیای واقعی بدست آمده، انجام شده است^[۳].

تجزیه و تحلیل تشخیص سیگنال از درختان سریع و مقرون به صرفه ویرایش

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

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

شکل 2. قسمت بالا شکل ، فرضیات تئوری تشخیص سیگنال را در یک عمل تصمیم گیری باینری نشان می دهد. سه خط عمودی نشان دهنده سه معیار تصمیم است که نماینده و تصمیم گیرنده ممکن است اتخاذ کنند. قسمت پایین شکل، چهار FFT ممکن را نشان می دهد که می توانند در صورت مشورت با سه ویژگی به ترتیب ثابت ساخته شوند. بر اساس طبقه بندی های انجام شده توسط دو خروجی اول ، درختان از چپ به راست FFTss و FFTsn و FFTns و FFTnn نامگذاری شده اند. فلشهایی که قسمتهای شکل را به هم متصل می کنند تقریباً مکان چهار معیار تصمیم گیری FFT را نشان می دهند ، وقتی که آنها برای طبقه بندی یا تصمیم گیری باینری s / n استفاده می شوند (به ترتیب برای سیگنال (s) و نویز(n)). در میان چهار مورد ، FFTss معتدل ترین معیار تصمیم گیری و FFTnn محافظه کارترین معیار را دارد. معیارهای تصمیم گیری FFTsn و FFTns نسبت به دو مورد دیگر بسیار افراطی است و FFTsn معتدل تر از FFTns است.

در سال 2011 ، Luan ، Schooler و Gigerenzer ویژگی های درختان سریع و مقرون به صرفه را از منظر تئوری تشخیص سیگنال تجزیه و تحلیل کردند. چندین یافته کلیدی از این تجزیه و تحلیل وجود دارد. اول ، انتخاب ساختار خروج یک درخت سریع و مقرون به صرفه با نحوه تنظیم معیار تصمیم گیری در تشخیص سیگنال مطابقت دارد. به طور خلاصه ، هرچه زودتر "خروج سیگنال" در یک درخت سریع و مقرون به صرفه ظاهر شود ، درخت معتدل تر برخورد می کند. تمایل نسبی دو درخت سریع و مقرون به صرفه با اولین خروجی مشخص می شود که در آن دو تفاوت دارد ، با یک خروجی "خروجی سیگنال" - با "s" مشخص می شود - همیشه معتدل تر از آن است که "خروجی نویز "- با " n "نشان داده شده است - را دارد (شکل 2). به عنوان مثال ، یک FFTsnnn (در اینجا دوباره s = "خروج سیگنال" ، n = "خروجی نویز") بامعتدل تر از FFTnsss است. از این اصل به عنوان "تمایل تصمیم واژگانی" درختان سریع و مقرون به صرفه یاد می شود.

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

سوم ، حساسیت کلی یک درخت سریع و مقرون به صرفه - یعنی اینکه درخت چقدر می تواند سیگنال را از یک نویز تشخیص دهد و می تواند توسط d 'یا A' از تئوری تشخیص سیگنال اندازه گیری شود - که تحت تأثیر خواص نشانه‌هایی است که درخت را تشکیل می دهند ، مانند میانگین و واریانس حساسیت‌های نشانه‌ها و همبستگی ها بین نشانه ها ، اما ساختار خروجی درخت آن چنان تاثیری ندارد. و سرانجام، درخت‌های سریع و مقرون به صرفه، دقت و قدرت بیشتری خواهند داشت، که با الگوریتم های تصمیم گیری بسیار پیچیده تری که در تئوری تشخیص سیگنال تهیه شده است، از جمله مدل تجزیه و تحلیل ناظر ایده‌آل (Ideal observer analysis) و مدل نمونه گیری بهینه متوالی(optimal sequential sampling)، قابل مقایسه‌اند. در چارچوب پیش بینی های خارج از نمونه، زمانی که اندازه نمونه یادگیری نسبتاً کوچک است (به عنوان مثال ، کمتر از 80 آزمایش)، درختان سریع و مقرون به صرفه بهترین عملکرد را نسبت به سایر مدل ها دارند .

شکل 3. یک درخت سریع و مقرون به صرفه که می تواند به سربازان مستقر در افغانستان کمک کند تا تشخیص دهند آیا اتومبیلی که به یک ایست بازرسی نزدیک می شود توسط غیرنظامیان اداره می شود یا بمب گذاران انتحاری بالقوه (Keller & Katsikopoulos، 2016)

شکل 4. درختان سریع و مقرون به صرفه که چگونگی تصمیم گیری در مورد عفو و بخشش شخص دیگری برای جرمی را که شخص دوم در طی تعاملات اجتماعی انجام داده است توصیف می کند (چپ ؛ تان (Tan) ، لوان (Luan) و کاتسیکوپولوس (Katsikopoulos) ، 2017) الگو:Ran و نحوه تصمیم گیری قضات بریتانیایی برای این که آیا برای مجازات وثیقه اتخاذ کنند یا خیر (راست. Dhami ، 2003).

پشتیبانی در رایانه ویرایش

در سال 2017 ، فیلیپس (Phillips) ، نت (Neth) ، وایك (Woike) و گایسمایر (Gaissmaier) بسته R از FFTrees را كه در CRAN برگزار شده (با یک برنامه همراه) معرفی كردند، كه درختان سریع و مقرون به صرفه را به روشهای كاربر پسندانه ساخته، ترسیم می‌کند، و از لحاظ مقداری ارزیابی می‌کند.

مثال های بیشتری از درختان سریع و مقرون به صرفه ویرایش

در تعیین کردن نحوه تصمیم گیری و همچنین توصیف نحوه تصمیم گیری واقعی افراد ، کاربردهای زیادی از درختان سریع و مقرون به صرفه وجود داشته است. فراتر از رشته پزشکی ، نمونه ای از کاربردهای تجویزی آنها این است که به سربازان مستقر در افغانستان راهنمایی می کنند که چگونه تشخیص دهند اتومبیلی که به یک ایست بازرسی نزدیک می شود توسط غیرنظامیان یا بمب گذاران انتحاری بالقوه رانده می شود ^[۴] . این درخت در شکل 3 نشان داده شده است. دو نمونه از کاربردهای توصیفی درختان سریع و صرفه جو در شکل 4 نشان داده شده است. درختان سمت چپ و راست به ترتیب چگونگی تصمیم گیری یک شخص در بخشیدن شخص دیگر که در تعاملات اجتماعی به ایشان توهین کرده کرده است و نحوه تصمیم گیری قضات بریتانیایی در دریافت پول به جای حبس یا به زندان انداختن مجرم، را نشان می‌دهند . به طور کلی ، از درختان سریع و مقرون به صرفه می توان برای کمک یا مدل سازی هرگونه فرایند تصمیم گیری باینری که شامل چندین نشانه است استفاده کرد.

منابع ویرایش

↑ ^۱٫۰ ^۱٫۱ Martignon, Laura; Vitouch, Oliver; Takezawa, Masanori; Forster, Malcolm. "Naive and Yet Enlightened: From Natural Frequencies to Fast and Frugal Decision Trees", published in Thinking : Psychological perspectives on reasoning, judgement and decision making (David Hardman and Laura Macchi; editors), Chichester: John Wiley & Sons, 2003.
↑ Luan, Schooler and Gigerenzer, 2011 A signal-detection analysis of fast-and-frugal trees.
↑ ^۳٫۰ ^۳٫۱ Şimşek, Özgür; Buckmann, Marcus (2015), Cortes, C.; Lawrence, N. D.; Lee, D. D.; Sugiyama, M. (eds.), "Learning From Small Samples: An Analysis of Simple Decision Heuristics" (PDF), Advances in Neural Information Processing Systems 28, Curran Associates, Inc., pp. 3159–3167, retrieved 2019-09-01
↑ Keller, N., & Katsikopoulos, K. V. (2016) - On the role of psychological heuristics in operational research; and a demonstration in military stability operations. European Journal of Operational Research, 249, 1063–1073.

[naive-1] ۱٫۰ ^۱٫۱ Martignon, Laura; Vitouch, Oliver; Takezawa, Masanori; Forster, Malcolm. "Naive and Yet Enlightened: From Natural Frequencies to Fast and Frugal Decision Trees", published in Thinking : Psychological perspectives on reasoning, judgement and decision making (David Hardman and Laura Macchi; editors), Chichester: John Wiley & Sons, 2003.

[2] Luan, Schooler and Gigerenzer, 2011 A signal-detection analysis of fast-and-frugal trees.

[:0-3] ۳٫۰ ^۳٫۱ Şimşek, Özgür; Buckmann, Marcus (2015), Cortes, C.; Lawrence, N. D.; Lee, D. D.; Sugiyama, M. (eds.), "Learning From Small Samples: An Analysis of Simple Decision Heuristics" (PDF), Advances in Neural Information Processing Systems 28, Curran Associates, Inc., pp. 3159–3167, retrieved 2019-09-01

[4] Keller, N., & Katsikopoulos, K. V. (2016) - On the role of psychological heuristics in operational research; and a demonstration in military stability operations. European Journal of Operational Research, 249, 1063–1073.

[۱]

[۲]

[۳]

[۴]