عامل های هوشمند
تعریف عامل:
عامل هر چیزی است که میتواند محیطش را از طریق حسگرها درک کند و بر روی محیطش از طریق عمل‌کننده‌ها تأثیر گذارد. یک عامل انسانی دارای حس‌کننده‌هایی از قبیل چشم، گوش، لامسه و امثال آن میباشد. و میتوان از دست، پا، صحبت کردن و اعمال ارادی به عنوان عمل‌کننده‌ها نام برد. ورودی یک عامل نرم‌افزاری میتوانند چندین متغیر باشد که مقدار آنها را عامل میخواند سپس بر اساس مکانیزم تصمیم‌گیری یک تصمیم اخذ میکند و عملگرهای آن میتوانند دستورهای مقداردهی چند متغیر دیگر باشد. به عنوان مثال فرض کنید یک عامل قرار است متغیر x را بخواند و توان دوم آن را حساب کند و در y قرار دهد. این عامل x را میخوانند و سپس توان دوم آن را حساب میکند و در y قرار میدهد.
نحوه کار عامل:
یک عامل چگونه باید بفهمد که بهترین عمل ممکن چیست؟ عمل درست عملی است که باعث شود عامل موفق‌ترین باشد. این امر ما را با مسئله تصمیم‌گیری در مورد چگونگی و زمان ارزیابی کردن موفقیت عامل روبرو میکند. اصطلاح میزان کارایی برای موفقیت عامل تعریف می‌کنیم. گفتنی است که میزان کارایی برای عاملهای مختلف متفاوت میباشد. نکته خیلی مهم این است که میزان کارایی یک عامل باید بر اساس محیط تعریف شود. به عنوان مثال فرض کنیم که یک عامل کارش جمع‌آوری آشغال‌ها از یک اتاق و دفع آنها باشد، اگر عامل میزان کارایی اش بر حسب اشغال جمع شده تعریف شود آنگاه عامل میتواند آشغال‌ها را جمع کند و سپس دوباره در اباق بریزد تا بهترین کارایی را کسب کند. اما اگر میزان کارایی بر اساس محیط تعریف شود آنگاه عامل یک بار کار تمیز کردن را انجام میدهد. پس یک عامل محیطش را حس میکند و سپس بر اساس آن تصمیم میگیرد. این مستلزم آن است که با عامل خود مختار و انواع محیط‌ها آشنا شویم.
عامل خود مختار
به عاملی خود مختار میگوییم که تصمیم‌گیری اش بر اساس ادراکاتش باشد نه بر اساس دانش تزریق شده به آن. در واقع هر چه دانش قبلی یک عامل بیشتر باشد از خودمختاری آن کاهش مییابد و هر چه دانش قبلی کمتر باشد و مکانیزم یادگیری عامل قوی تر باشد، آن عامل خود مختار تر است.
انواع محیط ها
قابل مشاهده و غیر قابل مشاهده: اگر عامل به کل محیط دسترسی داشته باشد و بتواند آن را حس کند میگوییم محیط قابل مشاهده است، در غیر این صورت آن را غیر قابل مشاهده یا تا حدودی قابل مشاهده می نامیم. مثلاً در محیط عامل شطرنج باز کل محیط قابل مشاهده است. طبیعی است که یک مسئله با محیط قابل مشاهده برای طراحان عاملها مطلوب تر میباشد.
قطعی و غیر قطعی: اگر بتوان حالت بعدی را از حالت فعلی، عمل فعلی و کنشهایی که تاکنون انجام شده به دست بیاوریم، میگوییم که محیط قطعی است. بازهم میتوان از بازی شطرنج برای محیط قطعی مثال زد، چون با محیط فعلی و حرکت فعلی میشود حالت بعدی را به صورت دقیق یافت. قابل توجه است که بدانیم اگر محیط کاملاً قابل مشاهده نباشد آنگاه قطعی نخواهد بود. اما اگر با یک حرکت ممکن باشد به چندین حالت برویم محیط غیر قطعی است.
دوره‌ای یا غیر دوره ای: اگر هر دوره از دوره‌های دیگر مستقل باشد میگوییم محیط دوره‌ای است. مانند دوره‌های مختلف در مذاکرات چند عامله. محیط‌های غیر دوره‌ای به عنوان محیط‌های ترتیبی نیز یاد میشوند.
ایستا و پویا: اگر محیط در زمان تصمیم‌گیری عامل تغییر کند آنگاه محیط پویا است. و در غیر آن صورت محیط ایستا است. اما اگر محیط در زمان تصمیم‌گیری ثابت بماند اما زمان، کارایی عامل را کاهش دهد، محیط را نیمه پویا مینامیم.
گسسته و پیوسته: اگر مشاهدات و کنش‌های مختلف مجزا و تعریف شده باشند، محیط پیوسته است. مانند شطرنج. اما یک عامل بهینه ساز معادلات در محیط پیوسته کار میکند.
ساختار عامل های هوشمند
تا کنون در مورد محیط‌ها و کلیات مربوط به عاملها صحبت کردیم. حال نوبت بررسی ساختارهای مختلف عاملها است. مهمترین وظیفه ما طراحی برنامه عامل است. برنامه عامل تابعی است که ادراکات را به یک عمل‌ها نگاشت میکند. معماری عامل ساختاری است که برنامه محاسباتی عامل تر روی آن پیاده‌سازی میشود. پس در کل معماری از طریق حسگرها ورودی را میگیرد، توسط برنامه تصمیم میگیرد و در نهایت با عملگرها عمل میکند و روی محیط تأثیر میگذارد.
عامل های واکنشی ساده
در این گونه عاملها سعی بر این است که به ازای هر حالت ممکن در دنیا یک عمل مناسب انجام دهیم. برای این کار میتوانیم حالت محیط را در ستون اول یک جدول قرار دهیم و عمل مربوط به آن را در ستون دوم نکه داری کنیم. به چنین عاملی وابسته به جدول نیز میگویند. و به این جدول، جدول حالت-قانون نیز میگویند. در همان ابتدا مشخص میشود که برای طراحی چنین عاملی محیط باید کاملاً قابل مشاهده باشد. مهمترین مشکلی که در راه طراحی این عامل به وجود می‌آید این است در مسائل دنیای واقعی پر کردن چنین جدولی غیرممکن است. مثلاً برای شطرنج 35100 حالت مختلف برای محیط وجود دارد. حال اگر فرض کنیم توانایی پر کردن جدول را داشته باشیم، آنگاه اولا حافظه لازم را نخواهیم داشت و ثانیا جستجو جهت یافتن جواب زمان زیادی خواهد گرفت. ساختار این عامل در شکل زیر دیده میشود.
به هر موجودیت که از طریق گیرنده ها و سنسورهایش محیط اطراف خود را مشاهده نموده و از طریق اندام های خود در آن محیط عمل مینماید (بر روی آن محیط تاثیر میگذارد) عامل (Agent) میگویند. برای مثال انسان به عنوان یک عامل از گوش ها، چشم ها و دیگر اندام های خود جهت دریافت اطلاعات از محیط استفاده کرده و از طریق دست و پا و زبان برای عمل نمودن در همان محیط استفاده مینماید. به همین ترتیب یک عامل رباتیک نیز از سنسورهای خود به عنوان دریافت کننده و از بازو های خود به عنوان عمل کننده، در محیط اطراف استفاده مینماید.
هر موجودیت که نسبت به مشاهدات خود از محیط اطراف واکنش نشان میدهد را عامل مینامند.
عامل هوشمند (Rational Agent)
عاملی است که در محیط خود کار صحیح را انجام میدهد. قطعا انجام کار صحیح بهتر از انجام کار اشتباه است! اما سوالی که پیش می آید این است که براستی تعریف کار صحیح چیست؟
در حال حاضر میتوان بطور تقریبی اینگونه به این سوال پاسخ داد که کار صحیح کاریست که باعث کسب موفقیت توسط عامل هوشمند میشود. با این حال توجه داشته باشید که همین تعریف تقریبی هم ما را با دو سوال چگونه و چه زمان در ابهام باقی میگذار. اگر اینگونه تفسیر نمایید که چگونه به موفقیت برسیم؟ و چه زمان به موفقیت رسیده ایم؟ این ابهام برای شما ملموس تر خواهد شد.
برای رفع ابهام در مورد موفقیت عامل هوشمند، مفهومی با عنوان اندازه گیری عملکرد یا performance measure تعریف میشود. اندازه گیری عملکرد در واقع مجموعه ای از قوانین هستند که ما به عنوان طراحان یا شاهدان عملکرد عامل هشومند، وضع مینماییم تا بتوانیم عامل هوشمند خود را مورد سنجش قرار دهیم.
فرض کنید که ما بعنوان سازنده، عامل هوشمندی ساخته ایم که در واقع یک ربات نظافت گر خودکار میباشد. برای مثال یک معیار اندازه گیری عملکرد برای این ربات میتواند میزان جمع آوری گرد غبار در طول مدت یک شیفت کاری باشد. یا مثلا برای توانمند تر ساختن ربات میتوان مقدار انرژی الکتریکی مصرف شده و سر و صدای تولید شده توسط آن را به مجموعه معیار های اندازه گیری اضافه نمود. برای مثال میتوانیم بگوئیم اگر ربات ما در طول یک ساعت حداقل x لیتر غبار جمع آوری و کمتر از y انرژی مصرف نمود، کار خود به درستی انجام داده است.
تفاوت ِعقلانیت و علم لایتناهی
نکته ای که از اهمیت بسیاری برخوردا است، تمیز دادن بین دو مفهوم عقلانیت و علم لایتناهی میباشد. یک عامل با علم لایتناهی نتیجه خروجی تمامی اعمال خود را میداند که بسیار هم عالی و خوب است! اما در دنیای واقعی عملا همچین عاملی وجود نخواهد داشت! به مثالی که در ادامه آماده توجه فرمایید.
شما در یک منطقه دورافتاده و بی آب و علف هستید که ناگهان یک دختر بسیار زیبا را در طرف دیگر خیابان مشاهده مینمایید. هیچ ماشینی در حال تردد در خیابان نیست و شما نیز مجرد و تنها هستید! بنظر میرسد که با توجه به شرایط اطراف عاقلانه ترین کار این است که از عرض خیابان رد شده، به سراغ دختر زیبا بروید و او را به صرف یک نوشیدنی دعوت نمایید. در همین لحظه در ارتفاع 33000 پایی یک هواپیمای بار بری در حال عبور از منطقه شماست که ناگهان درب هواپیما کنده شده و به سمت زمین پرتاب میشود و با شما برخورد میکند. نتیجتا قبل از اینکه شما به طرف دیگر برسید مانند گوجه فرنگی در کف خیابان له خواهید شد!
سوالی که پیش می آید این است که تصمیم شما برای عبور از خیابان یک تصمیم اشتباه و غیر هوشمندانه بوده است؟ آیا از عمل شما به عنوان یک عمل غیر عقلانی یاد خواهد شد؟
اینجاست که باید بگوییم که در واقع، عقلانیت، با موفقیتی که ناشی از مجموعه مشاهدات عامل است تعریف میشود. (در مثال بالا، شخص عبور کننده توانایی دیدن درب هواپیما را نداشته برای همین تصمیم به عبور از خیابان گرفته است) به زبان دیگر ما نمیتوانیم یک عامل را که به خاطر عدم توانایی در مشاهده تمام محیط اطراف، شکست خورده است، سرزنش نماییم. نتیجه این بحث میتواند این باشد که در شرایط واقعی نمیتوان همیشه از عامل هوشمند خود انتظار داشت که کار صحیح را انجام دهد.
بطور خلاصه میتوان گفت که هوشمند بودن یک موجودیت به چهار عامل بستگی دارد.
اندازه گیری عملکرد که درجات موفقیت را مشخص مینماید.
هر آن چیز که عامل اخیرا مشاهده و یا در یافت نموده است.توالی مشاهدات.
هر آنچه که عامل از مورد محیط خود میداند.
مجموعه عمل هایی که عامل میتواند در محیط انجام دهد.
عامل هوشمند ایده آل
مجموعه تعاریف و مطالب فوق، ما را به سمت تعرف مفوهم عامل هوشمند ایده آل هدایت مینماید. عامل هوشمند ایده آل، عاملی است که برای هر مجموعه از توالی مشاهدات، با توجه به شواهد موجود در محیط و دانش پیش ساخته خود، آن عملِ مورد انتظاری را انجام دهد که باعث افزایش اندازه عملکرد و یا همان performance measure بشود.
توجه داشته باشید در نگاه اول ممکن است بنظر برسد که این تعریف باعث ساخت عامل های هوشمندانه ای خواهد شد که خود را در شرایطی که به انجام عمل غیر عقلانی ختم میشود قرار خواهد داد. در واقع ممکن است عامل هوشمند به خیال خود در حال افزایش اندازه عملکرد باشد در حالی که برای این افزایش آن از بسیاری از مسائل چشم پوشی نماید.
برای مثال اگر عامل برای عبور از خیابان به طرفین نگاه نکند (در حالی که هدفش عبور از خیابان است) توالی مشاهداتش او را از خطر تصادف با یک کامیون که با سرعت به طرف او می آید آگاه نخواهد کرد. در نتیجه طبق تعریف، عبور از خیابان برای عامل، عملی هوشمندانه به حساب آمده و او به راه خود ادامه خواهد. در صورتی که چنین تفسیری به دو دلیل اشتباه میباشد. اول آنکه بطور کلی ریسک عبور از خیابان بدون نگاه بطرفین بسیار بالا میباشد. دوم آنکه در صورت نتیجه گیری صحیح از تعریف عامل هوشمند ایده آل، چنین عاملی برای افزایش اندازه عملکرد خود باید به طرفین نگاه کند.
نگاشت ایده آل، از توالی مشاهدات به عمل
با توجه به مطالب فوق میتوان نتیجه گیری کرد از آنجا که رفتار عامل ما بر اساس توالی مشاهداتش میباشد، میتوان برای عامل ها با رسم جدول، مشاهده و عمل را به یکدیگر نگاشت نمود. با این حال باید توجه داشت که برای تمامی عامل ها چنین جدولی بسیار طولانی و یا دارای بی نهایت سطر میباشد مگر آنکه محدودیتی در طول مشاهدات، از طرف طراح برای آن جدول تعیین شده باشد.
به چنین جدولی، جدول “نگاشت مشاهدات به عمل” میگویند. در اصول میتوان با تست اینکه چه عملی برای مشاهدات مناسب است این جدول را تکمیل نمود. باید توجه نمود که اگر میتوانیم از روی نگاشت، عامل هوشمند داشته باشیم از روی نگاشت ایده آل نیز میتوان به عامل هوشمند ایده آل رسید.
البته معنی توضیحات بالا این نیست که ما باید همیشه و بطور ضمنی و دقیق جدولی تهیه نماییم. در واقع در بسیاری از موارد به جای یک جدول ضمنی میتوان از یک تعریف مشخص که خود تولید کننده سطرهای جدول میباشد استفاده نماییم. برای مثال فرض کنید که ما یک عامل هوشمند بسیار ساده داریم که قرار است توان اعداد را محاسبه نمایید. برای طراحی چنین عاملی احتیاجی به ایجاد یک جدول واقعی نخواهیم داشت و عملا میتوان سطرهای این جدول را با فرمول توان یک عدد به عدد دیگر محاسبه نمود.
![خوشه‌بندی k-میانگین روش‌‌ها و الگوریتمهای متعددی برای تبدیل اشیاء به گروه‌های همشکل یا مشابه وجود دارد. الگوریتم k-میانگین یکی از ساده‌ترین و محبوب‌ترین الگوریتم‌هایی است که در «داده‌کاوی» (Data Mining) بخصوص در حوزه «یادگیری نظارت نشده» (Unsupervised Learning) به کار می‌رود. معمولا در حالت چند متغیره، باید از ویژگی‌های مختلف اشیا به منظور طبقه‌بندی و خوشه کردن آنها استفاده کرد. به این ترتیب با داده‌های چند بعدی سروکار داریم که معمولا به هر بعد از آن، ویژگی یا خصوصیت گفته میشود. با توجه به این موضوع، استفاده از توابع فاصله مختلف در این جا مطرح میشود. ممکن است بعضی از ویژگی‌های اشیا کمی و بعضی دیگر کیفی باشند. به هر حال آنچه اهمیت دارد روشی برای اندازه‌گیری میزان شباهت یا عدم شباهت بین اشیاء است که باید در روشهای خوشه‌بندی لحاظ شود. الگوریتم خوشه‌بندی k-میانگین از گروه روشهای خوشه‌بندی تفکیکی (Partitioning Clustering) محسوب میشود و درجه پیچیدگی محاسباتی آن برابر با O ( n d k + 1 ) است، به شرطی که n تعداد اشیاء، d بعد ویژگی‌ها و k تعداد خوشه‌ها باشد. همچنین پیچیدگی زمانی برای این الگوریتم برابر با O ( n k d i ) است، که البته منظور از i تعداد تکرارهای الگوریتم برای رسیدن به جواب بهینه است. در خوشه‌بندی k-میانگین از بهینه‌سازی یک تابع هدف (Object Function) استفاده میشود. پاسخ‌های حاصل از خوشه‌بندی در این روش، ممکن است به کمک کمینه‌سازی (Minimization) یا بیشینه‌سازی (Maximization) تابع هدف صورت گیرد. به این معنی که اگر ملاک «میزان فاصله» (Distance Measure) بین اشیاء باشد، تابع هدف براساس کمینه‌سازی خواهد بود پاسخ عملیات خوشه‌بندی، پیدا کردن خوشه‌هایی است که فاصله بین اشیاء هر خوشه کمینه باشد. در مقابل، اگر از تابع مشابهت (Dissimilarity Function) برای اندازه‌گیری مشابهت اشیاء استفاده شود، تابع هدف را طوری انتخاب می‌کنند که پاسخ خوشه‌بندی مقدار آن را در هر خوشه بیشینه کند. معمولا زمانی که هدف کمینه‌سازی باشد، تابع هدف را «تابع هزینه» (Cost Function) نیز مینامند. روش خوشه بندی k-میانگین، توسط «مک‌کوئین» (McQueen) جامعه شناس و ریاضیدان در سال ۱۹۶۵ ابداع و توسط دیگر دانشمندان توسعه و بهینه شد. برای مثال در سال 1957 نسخه دیگری از این الگوریتم به عنوان الگوریتم استاندارد خوشه‌بندی k-میانگین، توسط «لوید» (Lloyd) در آزمایشگاه‌های بل (Bell Labs) برای کدگذاری پالس‌ها ایجاد شد که بعدها در سال 1982 منتشر گردید. این نسخه از الگوریتم خوشه‌بندی، امروزه در بیشتر نرم‌افزارهای رایانه‌ای که عمل خوشه‌بندی k-میانگین را انجام می‌دهند به صورت استاندارد اجرا میشود. در سال 1956 «فورجی» (W.Forgy) به طور مستقل همین روش را ارائه کرد و به همین علت گاهی این الگوریتم را با نام لوید-فورجی می‌شناسند. همچنین روش هارتیگان- ونگ (Hartigan-Wong) که در سال ۱۹۷۹ معرفی شد یکی از روش‌هایی است که در تحقیقات و بررسی‌های داده‌کاوی مورد استفاده قرار میگیرد. تفاوت در این الگوریتم‌ها در مرحله آغازین و شرط همگرایی الگوریتم‌ها است ولی در بقیه مراحل و محاسبات مانند یکدیگر عمل می‌کنند. به همین علت همگی را الگوریتمهای خوشه‌بندی k-میانگین مینامند. روش خوشه‌بندی k-میانگین فرض کنید مشاهدات ( x 1 , x 2 , … , x n ) که دارای d بعد هستند را باید به k بخش یا خوشه تقسیم کنیم. این بخش‌ها یا خوشه‌ها را با مجموعه‌ای به نام S = { S 1 , S 2 , … , S k } می‌شناسیم. اعضای خوشه‌ها باید به شکلی از مشاهدات انتخاب شوند که تابع «مجموع مربعات درون خوشه‌ها» (within-cluster sum of squares- WCSS) که در حالت یک بعدی شبیه واریانس است، کمینه شود. بنابراین، تابع هدف در این الگوریتم به صورت زیر نوشته میشود. a r g m i n S k ∑ i = 1 ∑ x ∈ S i ∥ x − μ i ∥ 2 = a r g m i n S k ∑ i = 1 | S i | Var S i در اینجا منظور از μ i میانگین خوشه S i و | S i | تعداد اعضای خوشه iام است. البته میتوان نشان داد که کمینه کردن این مقدار به معنی بیشینه‌سازی میانگین مربعات فاصله بین نقاط در خوشه‌های مختلف (between-Cluster sum of Squares- BCSS) است زیرا طبق قانون واریانس کل، با کم شدن مقدار WCSS، مقدار BCSS افزایش مییابد، زیرا واریانس کل ثابت است. در ادامه به بررسی روش خوشه بندی k-میانگین به روش لوید-فورجی (استاندارد) و هارتیگان-ونگ می‌پردازیم. خوشه‌بندی k-میانگین با الگوریتم لوید (Lloyd’s Algorithm) به عنوان یک الگوریتم استاندارد برای خوشه‌بندی k-میانگین از الگوریتم لوید بخصوص در زمینه علوم کامپیوتر، استفاده میشود. ابتدا به علائمی که در این رابطه به کار می‌رود، اشاره می‌کنیم. m ( i ) j : میانگین مقدارهای مربوط به خوشه jام در تکرار iام از الگوریتم را با این نماد نشان می‌دهیم. S ( i ) j : مجموعه اعضای خوشه jام در تکرار iام الگوریتم. الگوریتم لوید را با توجه به نمادهای بالا میتوان به دو بخش تفکیک کرد. ۱- بخش مقدار دهی ( A s s i g n m e n t S t e p )، ۲- بخش به روز رسانی (Update Step). حال به بررسی مراحل اجرای این الگوریتم می‌پردازیم. در اینجا فرض بر این است که نقاط مرکزی اولیه یعنی m ( 1 ) 1 , m ( 1 ) 2 , ⋯ , m ( 1 ) k داده شده‌اند. بخش مقدار دهی: هر مشاهده یا شی را به نزدیکترین خوشه نسبت می‌دهیم. به این معنی که فاصله اقلیدسی هر مشاهده از مراکز، اندازه گرفته شده سپس آن مشاهده عضو خوشه‌ای خواهد شد که کمترین فاصله اقلیدسی را با مرکز آن خوشه دارد. این قانون را به زبان ریاضی به صورت S ( t ) i = { x p : ∥ ∥ x p − m ( t ) i ∥ ∥ 2 ≤ ∥ ∥ x p − m ( t ) j ∥ ∥ 2 ∀ j , 1 ≤ j ≤ k } می‌نویسیم. بخش به روز رسانی: میانگین خوشه‌های جدید محاسبه میشود. در این حالت داریم: m ( t + 1 ) i = 1 | S ( t ) i | ∑ x j ∈ S ( t ) i x j توجه داشته باشید که منظور از | S ( t ) i | تعداد اعضای خوشه iام است. الگوریتم زمانی متوقف میشود که مقدار برچسب عضویت مشاهدات تغییری نکند. البته در چنین حالتی هیچ تضمینی برای رسیدن به جواب بهینه (با کمترین مقدار برای تابع هزینه) وجود ندارد. کاملا مشخص است که در رابطه بالا، فاصله اقلیدسی بین هر نقطه و مرکز خوشه ملاک قرار گرفته است. از این جهت از میانگین و فاصله اقلیدسی استفاده شده که مجموع فاصله اقلیدسی نقاط از میانگینشان کمترین مقدار ممکن نسبت به هر نقطه دیگر است. نکته: ممکن است فاصله اقلیدسی یک مشاهده از دو مرکز یا بیشتر، برابر باشد ولی در این حالت آن شئ فقط به یکی از این خوشه‌ها تعلق خواهد گرفت. تصویر زیر یک مثال برای همگرایی الگوریتم لوید محسوب میشود که مراحل اجرا در آن دیده میشود. همانطور که مشخص است الگوریتم با طی ۱۴ مرحله به همگرایی میرسد و دیگر میانگین خوشه‌ها تغییری نمی‌یابد. البته ممکن است که این نقاط نتیجه تابع هزینه را بطور کلی (Global) کمینه نکنند زیرا روش k-میانگین بهینه‌سازی محلی (Local Optimization) را به کمک مشتق‌گیری و محاسبه نقاط اکستریمم اجرا میکند. K-means_convergence همگرایی الگوریتم k-میانگین نکته: به نقاط مرکزی هر خوشه مرکز (Centroid) گفته میشود. ممکن است این نقطه یکی از مشاهدات یا غیر از آنها باشد. مشخص است که در الگوریتم لوید، k مشاهده به عنوان مرکز خوشه‌ها (Centroids) در مرحله اول انتخاب شده‌اند ولی در مراحل بعدی، مقدار میانگین هر خوشه نقش مرکز را بازی میکند. خوشه‌بندی k-میانگین با الگوریتم هارتیگان-ونگ (Hartigan-Wong) یکی از روشهای پیشرفته و البته با هزینه محاسباتی زیاد در خوشه‌بندی k-میانگین، الگوریتم هارتیگان-ونگ است. برای آشنایی با این الگوریتم بهتر است ابتدا در مورد نمادهایی که در ادامه خواهید دید توضیحی ارائه شود. ϕ ( S j ) : از این نماد برای نمایش «تابع هزینه» برای خوشه S j استفاده می‌کنیم. این تابع در خوشه‌بندی k-میانگین برابر است با: ϕ ( S i ) = ∑ x ∈ S j ( x − μ j ) 2 S j : از آنجایی که هدف از این الگوریتم، تفکیک اشیاء به k گروه مختلف است، گروه‌ها یا خوشه‌ها در مجموعه‌ای با نام S قرار دارند و داریم، S = { S 1 , S 2 , ⋯ , S k } . μ j : برای نمایش میانگین خوشهjام از این نماد استفاده میشود. بنابراین خواهیم داشت: μ j = ∑ x ∈ S j x n j n j : این نماد تعداد اعضای خوشه jام را نشان میدهد. بطوری که j = { 1 , 2 , ⋯ , k } است. البته مشخص است که در اینجا تعداد خوشه‌ها را با k نشان داده‌ایم. مراحل اجرای الگوریتم در خوشه‌بندی k-میانگین با الگوریتم هارتیگان میتوان مراحل اجرا را به سه بخش تقسیم کرد: ۱- بخش مقدار دهی اولیه ( A s s i g n m e n t S t e p ) ، ۲- بخش به روز رسانی ( U p d a t e S t e p )، ۳- بخش نهایی (Termination). در ادامه به بررسی این بخش‌ها پرداخته میشود. بخش مقدار دهی اولیه: در الگوریتم هارتیگان-ونگ، ابتدا مشاهدات و یا اشیاء به طور تصادفی به k گروه یا خوشه تقسیم میشوند. به این کار مجموعه S با اعضایی به صورت { S j } j ∈ { i , ⋯ , k } مشخص میشود. بخش به روز رسانی: فرض کنید که مقدارهای n و m از اعداد ۱ تا k انتخاب شده باشد. مشاهده یا شیئ از خوشه nام را در نظر بگیرید که تابع Δ ( m , n , x ) = ϕ ( S n ) + ϕ ( S m ) − Φ ( S n ∖ { x } ) − ϕ ( S m ∪ { x } ) را کمینه سازد، در چنین حالتی مقدار x از خوشه nام به خوشه mام منتقل میشود. به این ترتیب شی مورد نظر در S m قرار گرفته و خواهیم داشت x ∈ S m . بخش نهایی: زمانی که به ازای همه n,m,x مقدار Δ ( m , n , x ) بزرگتر از صفر باشد، الگوریتم خاتمه مییابد. نکته: منظور از نماد ϕ ( S n ∖ { x } ) محاسبه تابع هزینه در زمانی است که مشاهده x از مجموعه S n خارج شده باشد. همچنین نماد ϕ ( S m ∪ { x } ) به معنی محاسبه تابع هزینه در زمانی است که مشاهده x به خوشه S m اضافه شده باشد. در تصویر زیر مراحل اجرای الگوریتم هارتیگان به خوبی نمایش داده شده است. هر تصویر بیانگر یک مرحله از اجرای الگوریتم است. نقاط رنگی نمایش داده شده، همان مشاهدات هستند. هر رنگ نیز بیانگر یک خوشه است. در تصویر اول مشخص است که در بخش اول از الگوریتم به طور تصادفی خوشه‌بندی صورت پذیرفته. ولی در مراحل بعدی خوشه‌ها اصلاح شده و در انتها به نظر میرسد که بهترین تفکیک برای مشاهدات رسیده‌ایم. در تصویر آخر نیز مشخص است که مراکز خوشه‌ها، محاسبه و ثابت شده و دیگر بهینه‌سازی صورت نخواهد گرفت. به این ترتیب پاسخ‌های الگوریتم با طی تکرار ۵ مرحله به همگرایی میرسد. hartigan algorithm الگوریتم هارتیگان بخش مقدار دهی اولیه hartigan algorithm الگوریتم هارتیگان تکرار ۱ hartigan algorithm الگوریتم هارتیگان تکرار ۲ hartigan algorithm الگوریتم هارتیگان تکرار ۳ hartigan algorithm الگوریتم هارتیگان تکرار ۴ hartigan algorithm الگورییتم هارتیگان تکرار ۵ اجرای این الگوریتم‌ها با استفاده از دستورات زبان برنامه‌نویسی R برای استفاده از دستورات و فرمان‌های مربوط به خوشه‌بندی k-میانگین، باید بسته یا Package مربوط به خوشه‌بندی kmeans به اسم stats را در R نصب کرده باشد. البته از آنجایی این بسته بسیار پرکاربرد است، معمولا به طور خودکار فراخوانی شده است. کدهای زیر نشانگر استفاده از الگوریتم خوشه‌بندی توسط روشهای مختلف آن است. library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") k=3 kresults1=kmeans(data,k,algorithm = method[1]) kresults2=kmeans(data,k,algorithm=method[2]) kresults3=kmeans(data,k,algorithm=method[3]) kresults1 kresults2 kresults3 1 2 3 4 5 6 7 8 9 10 11 12 library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") k=3 kresults1=kmeans(data,k,algorithm = method[1]) kresults2=kmeans(data,k,algorithm=method[2]) kresults3=kmeans(data,k,algorithm=method[3]) kresults1 kresults2 kresults3 با توجه به داده‌های iris که مربوط به اندازه و ابعاد کاسبرگ و گلبرگ سه نوع گل مختلف است، خوشه‌بندی به سه دسته انجام شده است. اطلاعات مربوط به ۱۰ سطر اول این مجموعه داده، به صورت زیر است. با اجرای کدهای نوشته شده، خوشه‌بندی انجام شده و نتابج تولید میشوند. به عنوان مثال میتوان خروجی را برای kresult1 که انجام خوشه بندی توسط الگوریتم هارتیگان است به صورت زیر مشاهده کرد: iris clustering همانطور که دیده میشود، در سطر اول تعداد اعضای هر خوشه، نمایش داده شده است. در بخش دوم که با سطر ۱ و ۲ و ۳ مشخص شده، مراکز هر سه خوشه برحسب ویژگی‌های (طول و عرض کاسبرگ و طول و عرض گلبرگ) محاسبه شده و در قسمت Cluster Vector نیز برچسب خوشه هر کدام از مشاهدات دیده میشود. در انتها نیز مجموع مربعات فاصله درون خوشه‌ای (مجموع فاصله هر مشاهده از مرکز خوشه) استخراج شده و درصد یا شاخص ارزیابی خوشه‌بندی بر اساس نسبت مربعات بین خوشه‌ها به مربعات کل دیده میشود. این مقدار برای این حالت برابر ۸۸.۴٪ است که نشان میدهد بیشتر پراکندگی (total_ss) توسط پراکندگی بین خوشه‌ها (between_ss) بیان شده است. پس به نظر خوشه‌بندی مناسب خواهد بود. پس اختلاف بین گروه‌ها ناشی از خوشه‌های است که مشاهدات را به دسته‌‌های جداگانه تفکیک کرده. همچنین در کدها مشخص است که تعداد خوشه‌های در متغیر k ثبت و به کار رفته است. در شکل دیگری از دستور kmeans میتوان به جای معرفی تعداد خوشه‌ها از مراکز دلخواه که با تعداد خوشه‌ها مطابقت دارد، استفاده کرد. برای مثال اگر برنامه به صورت زیر نوشته شود، الگوریتم ابتدا نقاط معرفی شده را به عنوان نقاط مرکزی (Centroids) به کار گرفته و سپس مراحل بهینه سازی را دنبال میکند. از آنجا که سه نقطه مبنا قرار گرفته، الگوریتم متوجه میشود که باید مشاهدات به سه خوشه تفکیک شود. library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") c1=c(6,4,5,3) c2=c(5,3,1,0) c3=c(6,2,4,2) centers=rbind(c1,c2,c3) kresults1=kmeans(x = data,centers = centers,algorithm = method[1]) kresults2=kmeans(x = data,centers = centers,algorithm=method[2]) kresults3=kmeans(x = data,centers = centers,algorithm=method[3]) kresults1 kresults2 kresults3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") c1=c(6,4,5,3) c2=c(5,3,1,0) c3=c(6,2,4,2) centers=rbind(c1,c2,c3) kresults1=kmeans(x = data,centers = centers,algorithm = method[1]) kresults2=kmeans(x = data,centers = centers,algorithm=method[2]) kresults3=kmeans(x = data,centers = centers,algorithm=method[3]) kresults1 kresults2 kresults3 در تصویر زیر نتیجه خوشه بندی k-میانگین را برای داده‌های iris توسط یک نمودار مشاهده می‌کنید. البته باید توجه داشت که این نمودار دو بعدی است در حالیکه داده‌ها، دارای چهار ویژگی هستند. به کمک روشهای آماری مانند تجزیه به مولفه‌های اصلی (PCA) ابعاد مسئله کاهش یافته تا در سه بعد روی نمودار نمایش داده شود. سمت راست تصویر گروه‌های واقعی و سمت چپ نتیجه خوشه‌بندی دیده میشود. نقاطی که در خوشه‌ها به درستی تشخیص داده نشده‌اند، باعث افزایش خطای خوشه‌بندی خواهند شد. کاربردها از الگوریتم خوشه‌بندی k-میانگین در «بخش‌بندی بازار کسب و کار» (market Segmentation)، «دسته‌بندی مشتریان» (Customer Segmentation)، «بینایی رایانه‌ای» (Computer Vision) و «زمین‌آمار (Geostatistics) استفاده می شود. برای مثال در تشخیص تعداد رنگ و یا فشرده سازی تصاویر برحسب رنگ‌ها میتوان از این الگوریتم‌ها استفاده کرد. در تصویر بالا گل رز زرد رنگی دیده میشود که در یک محیط سبز قرار گرفته است. با استفاده از الگوریتمهای خوشه‌بندی میتوان تعداد رنگ‌ها را کاهش داده و از حجم تصاویر کاست. در تصویر زیر دسته بندی رنگ‌های گل رز دیده میشود. در این تصویر، هر طیف رنگ براساس میزان رنگ قرمز و سبز، بوسیله «سلول‌های ورونوی» (Voronoi Cell) تقسیم‌بندی شده است. این تقسیم‌بندی میتواند توسط الگوریتم‌ها خوشه‌بندی k-میانگین صورت گرفته باشد. در کل تصویر نیز، طیف رنگ‌های مختلف برای تصویر گل رز در یک «نمودار ورونوی» (Voronoi diagram) نمایش داده شده است که خوشه‌ها را بیان میکند. معایب و مزایای خوشه‌بندی k-میانگین از آنجایی که در این روش خوشه‌بندی، محاسبه فاصله بین نقاط توسط تابع فاصله اقلیدسی انجام میشود، از این الگوریتم‌ها به صورت استاندارد، فقط برای مقدارهای عددی (و نه ویژگی‌های کیفی) میتوان استفاده کرد. از طرف دیگر با توجه به محاسبات ساده و سریع آنها، پرکاربرد و موثر است. از طرف دیگر نسخه‌های تعمیم یافته از روش خوشه بندی k-میانگین نیز وجود دارد که با توابع فاصله دیگر مانند فاصله منهتن و یا فاصله‌هایی که برای داده‌های باینری قابل استفاده است، مراحل خوشه‌بندی را انجام میدهد. به منظور ارزیابی نتایج خوشه‌بندی از معیارهای متفاوتی کمک گرفته میشود. ممکن است از قبل برچسب خوشه‌ها مشخص باشد و بخواهیم کارایی الگوریتم را با توجه به مقایسه برچسب‌های واقعی و حاصل از خوشه‌بندی، اندازه‌گیری کنیم. در این حالت، شاخص‌های ارزیابی بیرونی، بهترین راهنما و معیار برای سنجش صحت نتایج خوشه‌بندی محسوب میشوند. معمولا به این برچسبها، استاندارد طلایی (Golden Standard) و در کل چنین عملی را ارزیابی Benchmark میگویند. برای مثال شاخص رَند (Rand Index) یکی از این معیارها و شاخص‌های بیرونی است که از محبوبیت خاصی نیز برخوردار است. از طرف دیگر اگر هیچ اطلاعات اولیه از ساختار و دسته‌بندی مشاهدات وجود نداشته باشد، فقط ملاک ارزیابی، میتواند اندازه‌هایی باشد که میزان شباهت درون خوشه‌ها و یا عدم شباهت یا فاصله بین خوشه‌ها را اندازه می‌گیرند. بنابراین برای انتخاب بهتر و موثرترین روش خوشه‌بندی از میزان شباهت درون خوشه‌ها و شباهت بین خوشه‌ها استفاده میشود. روشی که دارای میزان شباهت بین خوشه‌ای کم و شباهت درون خوشه‌ای زیاد باشد مناسب‌ترین روش خواهد بود. این معیارها را به نام شاخص‌های ارزیابی درونی می‌شناسیم. به عنوان مثال شاخص نیم‌رخ (silhouette) یکی از این معیارها است که شاخصی برای سنجش مناسب بودن تعلق هر مشاهده به خوشه‌اش ارائه میدهد. به این ترتیب معیاری برای اندازه‌گیری کارایی الگوریتم خوشه‌بندی بدست می‌آید. اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد میشوند: مجموعه آموزش‌های یادگیری ماشین و بازشناسی الگو مجموعه آموزش‌های آمار، احتمالات و داده‌کاوی آموزش خوشه بندی K میانگین (K-Means) با نرم افزار SPSS آموزش خوشه بندی تفکیکی با نرم افزار R آموزش خوشه بندی سلسله مراتبی با SPSS آشنایی با خوشه‌بندی (Clustering) و شیوه‌های مختلف آن روش های ارزیابی نتایج خوشه بندی (Clustering Performance) — معیارهای درونی (Internal Index) روش های ارزیابی نتایج خوشه بندی (Clustering Performance) — معیارهای بیرونی (External Index) ^^ telegram twitter به اشتراک بگذارید: منبع وبلاگ فرادرسWikipedia بر اساس رای 1 نفر آیا این مطلب برای شما مفید بود؟ بلیخیر نظر شما چیست؟ نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند * متن نظر * نام شما * ایمیل شما * پایتخت ایران کدام شهر است؟ برچسبها clusterClusteringclustering algorithmcost functiondata miningforgy algorithmhartigan-wong algorithmk-meanslloyd algorithmmaximizationMcQueen algorithmminimizationpartitioning algorithmunsupervise learningتابع هدفتابع هزینهتعداد خوشهخوشه بندیخوشه بندی K میانگینخوشه بندی در آمارخوشه‌بندیخوشه‌بندی k-میانگینمربعات بین خوشهمربعات درون خوشهمعیارهای ارزیابی خوشه عضویت در خبرنامه ایمیل * آموزش برنامه نویسی آموزش متلب Matlab نرم‌افزارهای مهندسی برق نرم‌افزارهای مهندسی عمران نرم‌افزارهای مهندسی مکانیک نرم‌افزارهای مهندسی صنایع](https://blog.faradars.org/wp-content/uploads/2018/10/kmeans.jpg)
می‌نویسیم.
از این نماد برای نمایش «تابع هزینه» برای خوشه 
این نماد تعداد اعضای خوشه jام را نشان میدهد. بطوری که 
است. البته مشخص است که در اینجا تعداد خوشه‌ها را با k نشان داده‌ایم.
مشخص میشود.
را کمینه سازد، در چنین حالتی مقدار x از خوشه nام به خوشه mام منتقل میشود. به این ترتیب شی مورد نظر در 
قرار گرفته و خواهیم داشت 
.
بزرگتر از صفر باشد، الگوریتم خاتمه مییابد.
محاسبه تابع هزینه در زمانی است که مشاهده x از مجموعه 
خارج شده باشد. همچنین نماد 
به معنی محاسبه تابع هزینه در زمانی است که مشاهده x به خوشه 
