بایگانی برچسب برای: ai fknd

خوشه بندی k میانگین (k-means Clustering) قسمت 1

از مهم‌ترین تکنیک‌های عملی داده‌کاوی که کاربرد زیادی در علوم مختلف دارد، می توان به «خوشه بندی k-میانگین» (K-means Clustering)  اشاره کرد، که با توجه به بار محاسباتی زیاد آن، استفاده از کامپیوتر در انجام این فرآیند، کمک شایانی به کاربران می‌کند. در این راستا زبان برنامه‌نویسی و محاسباتی R قابلیت انجام این گونه محاسبات را دارد و به محققین در تحلیل خوشه‌بندی تفکیکی بر مبنای روش K-میانگین، کمک شایانی می‌کند. در این متن به بررسی روش خوشه‌بندی با استفاده از دستورات مربوط به این زبان برنامه‌نویسی می‌پردازیم و با البته با مفاهیم اولیه خوشه‌بندی k-میانگین نیز آشنا می‌شویم.

خوشه‌بندی k-میانگین

روش‌‌ها و الگوریتم‌های متعددی برای تبدیل اشیاء به گروه‌های همشکل یا مشابه وجود دارد. الگوریتم k-میانگین یکی از ساده‌ترین و محبوب‌ترین الگوریتم‌هایی است که در «داده‌کاوی» (Data Mining) بخصوص در حوزه «یادگیری نظارت نشده» (Unsupervised Learning) به کار می‌رود.

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

الگوریتم خوشه‌بندی k-میانگین از گروه روش‌های خوشه‌بندی تفکیکی (Partitioning Clustering) محسوب می‌شود و درجه پیچیدگی محاسباتی آن برابر با O(ndk+1) است، به شرطی که n تعداد اشیاء، d بعد ویژگی‌ها و k تعداد خوشه‌ها باشد. همچنین پیچیدگی زمانی برای این الگوریتم برابر با O(nkdi) است، که البته منظور از i‌ تعداد تکرارهای الگوریتم برای رسیدن به جواب بهینه است.

در خوشه‌بندی k-میانگین از بهینه‌سازی یک تابع هدف (Object Function) استفاده می‌شود. پاسخ‌های حاصل از خوشه‌بندی در این روش، ممکن است به کمک کمینه‌سازی (Minimization) یا بیشینه‌سازی (Maximization) تابع هدف صورت گیرد. به این معنی که اگر ملاک «میزان فاصله» (Distance Measure) بین اشیاء باشد، تابع هدف براساس کمینه‌سازی خواهد بود پاسخ عملیات خوشه‌بندی، پیدا کردن خوشه‌هایی است که فاصله بین اشیاء هر خوشه کمینه باشد. در مقابل، اگر از تابع مشابهت (Dissimilarity Function) برای اندازه‌گیری مشابهت اشیاء استفاده شود، تابع هدف را طوری انتخاب می‌کنند که پاسخ خوشه‌بندی مقدار آن را در هر خوشه بیشینه کند.

خوشه‌بندی 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 نرم‌افزارهای مهندسی برق نرم‌افزارهای مهندسی عمران نرم‌افزارهای مهندسی مکانیک نرم‌افزارهای مهندسی صنایع

 

معمولا زمانی که هدف کمینه‌سازی باشد، تابع هدف را «تابع هزینه» (Cost Function) نیز می‌نامند.

روش خوشه بندی k-میانگین، توسط «مک‌کوئین» (McQueen) جامعه شناس و ریاضیدان در سال ۱۹۶۵ ابداع و توسط دیگر دانشمندان توسعه و بهینه شد. برای مثال در سال 1957 نسخه‌ دیگری از این الگوریتم به عنوان الگوریتم استاندارد خوشه‌بندی k-میانگین، توسط «لوید» (Lloyd) در آزمایشگاه‌های بل (Bell Labs) برای کدگذاری پالس‌ها ایجاد شد که بعدها در سال 1982 منتشر گردید. این نسخه از الگوریتم خوشه‌بندی، امروزه در بیشتر نرم‌افزارهای رایانه‌ای که عمل خوشه‌بندی k-میانگین را انجام می‌دهند به صورت استاندارد اجرا می‌شود. در سال 1956 «فورجی» (W.Forgy) به طور مستقل همین روش را ارائه کرد و به همین علت گاهی این الگوریتم را با نام لوید-فورجی می‌شناسند. همچنین روش هارتیگان- ونگ (Hartigan-Wong) که در سال ۱۹۷۹ معرفی شد یکی از روش‌هایی است که در تحقیقات و بررسی‌های داده‌کاوی مورد استفاده قرار می‌گیرد. تفاوت در این الگوریتم‌ها در مرحله آغازین و شرط همگرایی الگوریتم‌ها است ولی در بقیه مراحل و محاسبات مانند یکدیگر عمل می‌کنند. به همین علت همگی را الگوریتم‌های خوشه‌بندی k-میانگین می‌نامند.

روش خوشه‌بندی k-میانگین

فرض کنید مشاهدات  که دارای d بعد هستند را باید به k بخش یا خوشه تقسیم کنیم. این بخش‌ها یا خوشه‌ها را با مجموعه‌ای به نام  می‌شناسیم. اعضای خوشه‌ها باید به شکلی از مشاهدات انتخاب شوند که تابع «مجموع مربعات درون خوشه‌ها» (within-cluster sum of squares- WCSS) که در حالت یک بعدی شبیه واریانس است، کمینه شود.

بنابراین، تابع هدف در این الگوریتم به صورت زیر نوشته می‌شود.

الگوریتم K-means

در اینجا منظور از  میانگین خوشه  و   تعداد اعضای خوشه iام است. البته می‌توان نشان داد که کمینه کردن این مقدار به معنی بیشینه‌سازی میانگین مربعات فاصله بین نقاط در خوشه‌های مختلف (between-Cluster sum of Squares- BCSS) است زیرا طبق قانون واریانس کل، با کم شدن مقدار WCSS، مقدار BCSS افزایش می‌یابد، زیرا واریانس کل ثابت است.

در ادامه به بررسی روش خوشه بندی k-میانگین به روش لوید-فورجی (استاندارد) و هارتیگان-ونگ می‌پردازیم.

خوشه‌بندی k-میانگین با الگوریتم لوید (Lloyd’s Algorithm)

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

mj(i): میانگین مقدارهای مربوط به خوشه jام در تکرار iام از الگوریتم را با این نماد نشان می‌دهیم.

Sj(i): مجموعه اعضای خوشه jام در تکرار iام الگوریتم.

الگوریتم لوید را با توجه به نمادهای بالا می‌توان به دو بخش تفکیک کرد. ۱- بخش مقدار دهی ()، ۲- بخش به روز رسانی (Update Step). حال به بررسی مراحل اجرای این الگوریتم می‌پردازیم. در اینجا فرض بر این است که نقاط مرکزی اولیه یعنی  داده شده‌اند.

  1. بخش مقدار دهی: هر مشاهده یا شی را به نزدیکترین خوشه نسبت می‌دهیم. به این معنی که فاصله اقلیدسی هر مشاهده از مراکز، اندازه گرفته شده سپس آن مشاهده عضو خوشه‌ای خواهد شد که کمترین فاصله اقلیدسی را با مرکز آن خوشه دارد. این قانون را به زبان ریاضی به صورت  فرمول 2  می‌نویسیم.
  2. بخش به روز رسانی: میانگین خوشه‌های جدید محاسبه می‌شود. در این حالت داریم:  فرمول 3

توجه داشته باشید که منظور از Si(t| تعداد اعضای خوشه iام است. الگوریتم زمانی متوقف می‌شود که مقدار برچسب عضویت مشاهدات تغییری نکند. البته در چنین حالتی هیچ تضمینی برای رسیدن به جواب بهینه (با کمترین مقدار برای تابع هزینه) وجود ندارد. کاملا مشخص است که در رابطه بالا،‌ فاصله اقلیدسی بین هر نقطه و مرکز خوشه ملاک قرار گرفته است. از این جهت از میانگین و فاصله اقلیدسی استفاده شده که مجموع فاصله اقلیدسی نقاط از میانگینشان کمترین مقدار ممکن نسبت به هر نقطه دیگر است.

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

تصویر زیر یک مثال برای همگرایی الگوریتم لوید محسوب می‌شود که مراحل اجرا در آن دیده می‌شود. همانطور که مشخص است الگوریتم با طی ۱۴ مرحله به همگرایی می‌رسد و دیگر میانگین خوشه‌ها تغییری نمی‌یابد. البته ممکن است که این نقاط نتیجه تابع هزینه را بطور کلی (Global) کمینه نکنند زیرا روش k-میانگین بهینه‌سازی محلی (Local Optimization) را به کمک مشتق‌گیری و محاسبه نقاط اکستریمم اجرا می‌کند.

 

K-means_convergence

همگرایی الگوریتم k-میانگین

 

نکته: به نقاط مرکزی هر خوشه مرکز (Centroid) گفته می‌شود. ممکن است این نقطه یکی از مشاهدات یا غیر از آن‌ها باشد. مشخص است که در الگوریتم لوید، k مشاهده به عنوان مرکز خوشه‌ها (Centroids) در مرحله اول انتخاب شده‌اند ولی در مراحل بعدی، مقدار میانگین هر خوشه نقش مرکز را بازی می‌کند.

خوشه‌بندی k-میانگین با الگوریتم هارتیگان-ونگ (Hartigan-Wong)

یکی از روش‌های پیشرفته و البته با هزینه محاسباتی زیاد در خوشه‌بندی k-میانگین، الگوریتم هارتیگان-ونگ است. برای آشنایی با این الگوریتم بهتر است ابتدا در مورد نمادهایی که در ادامه خواهید دید توضیحی ارائه شود.

فرمول 4  از این نماد برای نمایش «تابع هزینه» برای خوشه فرمول 5 استفاده می‌کنیم. این تابع در خوشه‌بندی k-میانگین برابر است با:

فرمول 6

 

فرمول 5 : از آنجایی که هدف از این الگوریتم، تفکیک اشیاء به k گروه مختلف است، گروه‌ها یا خوشه‌ها در مجموعه‌ای با نام S قرار دارند و داریم، فرمول 7

فرمول 8: برای نمایش میانگین خوشهjام از این نماد استفاده می‌شود. بنابراین خواهیم داشت:

فرمول 9

فرمول 11این نماد تعداد اعضای خوشه jام را نشان می‌دهد. بطوری که فرمول 10  است. البته مشخص است که در اینجا تعداد خوشه‌ها را با k‌ نشان داده‌ایم.

مراحل اجرای الگوریتم

در خوشه‌بندی k-میانگین با الگوریتم هارتیگان می‌توان مراحل اجرا را به سه بخش تقسیم کرد: ۱- بخش مقدار دهی اولیه (Assignment Step(   ،- ۲ بخش به روز رسانی (Update Step)، ۳- بخش نهایی (Termination). در ادامه به بررسی این بخش‌ها پرداخته می‌شود.

  1. بخش مقدار دهی اولیه: در الگوریتم هارتیگان-ونگ، ابتدا مشاهدات و یا اشیاء به طور تصادفی به k گروه یا خوشه تقسیم می‌شوند. به این کار مجموعه S با اعضایی به صورت فرمول 12  مشخص می‌شود.
  2. بخش به روز رسانی: فرض کنید که مقدارهای n و m از اعداد ۱ تا k انتخاب شده باشد. مشاهده یا شیئ از خوشه nام را در نظر بگیرید که تابع  فرمول 13 را کمینه سازد، در چنین حالتی مقدار x از خوشه nام به خوشه mام منتقل می‌شود. به این ترتیب شی مورد نظر در  فرمول 20 قرار گرفته و خواهیم داشت  فرمول 15 .
  3. بخش نهایی: زمانی که به ازای همه n,m,x مقدار  فرمول 16  بزرگتر از صفر باشد، الگوریتم خاتمه می‌یابد.

نکته: منظور از نماد  فرمول 17  محاسبه تابع هزینه در زمانی است که مشاهده x از مجموعه  فرمول 18  خارج شده باشد. همچنین نماد  فرمول 19 به معنی محاسبه تابع هزینه در زمانی است که مشاهده x به خوشه  فرمول 20  اضافه شده باشد.

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

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

در تصویر آخر نیز مشخص است که مراکز خوشه‌ها، محاسبه و ثابت شده و دیگر بهینه‌سازی صورت نخواهد گرفت. به این ترتیب پاسخ‌های الگوریتم با طی تکرار ۵ مرحله به همگرایی می‌رسد.

 

hartigan-step-1

الگوریتم هارتیگان بخش مقدار دهی اولیه

hartigan-step-2

الگوریتم هارتیگان تکرار 1

 

hartigan-step-3

الگوریتم هارتیگان تکرار 2

 

hartigan-step-5

الگوریتم هارتیگان تکرار 3

 

hartigan-step-4

الگوریتم هارتیگان تکرار 4

 

hartigan-step-6

الگوریتم هارتیگان تکرار 5

 

اجرای این الگوریتم‌ها با استفاده از دستورات زبان برنامه‌نویسی 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
با توجه به داده‌های 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
در تصویر زیر نتیجه خوشه بندی k-میانگین را برای داده‌های iris توسط یک نمودار مشاهده می‌کنید. البته باید توجه داشت که این نمودار دو بعدی است در حالیکه داده‌ها، دارای چهار ویژگی هستند. به کمک روش‌های آماری مانند تجزیه به مولفه‌های اصلی (PCA) ابعاد مسئله کاهش یافته تا در سه بعد روی نمودار نمایش داده شود. سمت راست تصویر گروه‌های واقعی و سمت چپ نتیجه خوشه‌بندی دیده می‌شود. نقاطی که در خوشه‌ها به درستی تشخیص داده نشده‌اند، باعث افزایش خطای خوشه‌بندی خواهند شد.

کاربردها

از الگوریتم خوشه‌بندی k-میانگین در «بخش‌بندی بازار کسب و کار» (market Segmentation)، «دسته‌بندی مشتریان» (Customer Segmentation)، «بینایی رایانه‌ای» (Computer Vision) و «زمین‌آمار (Geostatistics) استفاده می شود. برای مثال در تشخیص تعداد رنگ و یا فشرده سازی تصاویر برحسب رنگ‌ها می‌توان از این الگوریتم‌ها استفاده کرد.

 

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

 

 

در این تصویر، هر طیف رنگ براساس میزان رنگ قرمز و سبز، بوسیله «سلول‌های ورونوی» (Voronoi Cell) تقسیم‌بندی شده است. این تقسیم‌بندی می‌تواند توسط الگوریتم‌ها خوشه‌بندی k-میانگین صورت گرفته باشد. در کل تصویر نیز، طیف رنگ‌های مختلف برای تصویر گل رز در یک «نمودار ورونوی» (Voronoi diagram) نمایش داده شده است که خوشه‌ها را بیان می‌کند.

 

خوشه بندی k میانگین (k-means Clustering) قسمت 1
خوشه بندی k میانگین (k-means Clustering) قسمت 2

/0 دیدگاه /توسط

یادگیری ماشین قسمت 3

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

یادگیری ماشین چیست؟

تعریف عمومی از یادگیری ماشین  آن است که توسط دانشمند کامپیوتر آرتور ساموئل در سال ۱۹۵۹ داده شده است:

یک رشته علمی است که به کامپیوترها قابلیت یادگیری می دهد بدون آنکه مشخصا برای آن کار برنامه ریزی شده باشند.

این یک پاسخ مفهومی ساده است، اما بطور مشخص، فرآیند “یادگیری ماشین” چیست؟ خروجی آن چیست؟ و چگونه می توان آن را به داده های شما اعمال کرد؟ در این مقاله  تلاش خواهیم کرد تا به تمام این سوالات به طور ساده پاسخ دهیم، اما اولا، تعریف دقیق تر زیر را ارائه خواهیم کرد:

یادگیری ماشین فرآیند استفاده از داده ها  است  که به طور خودکار یک مدل می سازد ، که به عنوان ورودی از مجموعه ای از ویژگی های شناخته شده استفاده می کند  و به عنوان خروجی چیزی به عنوان  پیش بینی ارائه می دهد.

برخی اصطلاحات

مدل

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

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

معادله ای که به عنوان ورودی مقدار رنگ پیکسل های یک عکس را می گیرد و به عنوان خروجی شناسایی شیء موجود در عکس را می دهد.

معادله ای که به عنوان ورودی وضعیت کنونی هیئت مدیره Go را می دهد و به عنوان خروجی نشانگر حرکتی است که بهترین شانس برنده شدن در بازی را به ارمغان می آورد.

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

ویژگی ها

ویژگی های ورودی  مدل ماشین آموخته شده :

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

بیش برازش overfitting

برازش مدل شما به نوفه های تصادفی در  مجموعه داده های شماست. معمولا نتیجه یک مدل پیچیده؛ پیچیده خواهد شد؛ برای مثال، داشتن پارامترهای ورودی بیش از حد نسبت به تعداد مشاهدات نسبتا کم. چندین تکنیک برای جلوگیری از بیش برازش overfitting وجود دارد؛ یکی از روش های معمول برای این کار cross validation اعتبار سنجی متقابل است که در آن یک دوره جریمه های اضافی برای دادن اولویت به مدل هایی که از پارامترهای کمتری استفاده می کنند، گنجانده شده است.

طبقه بندی مشکلات یادگیری ماشین

سه طبقه بندی اصلی از وظایف یادگیری ماشین وجود دارد:

  • یادگیری تحت نظارت: مدل با استفاده از یک مجموعه شناخته شده “داده های آموزشی” ساخته شده است که شامل تمام ویژگی ها و همچنین مقادیر شناخته شده (“برچسب ها”) خروجی است که ما در حال تلاش برای مدل سازی آن هستیم. هدف از تکنیک های یادگیری تحت نظارت، رسیدن به یک مدل است که ویژگی های ورودی را برحسب برچسب ها نشان می دهد.
  • یادگیری بدون نظارت: خروجی این الگوریتم یادگیری،  برچسب ها  نیستند؛ هدف این روش کشف ساختار ناشناخته مانند خوشه ها clutsters و یا الگوهای دیگر است.
  • یادگیری تقویتی: الگوریتم پاداش و مجازات را بر اساس موفقیت آن در دستیابی به یک هدف خاص به ارمغان می آورد – به عنوان مثال، یک الگوریتم Go برای تغییرات در یک مدل که باعث افزایش نسبت زمان برنده شدن مدل و مجازات برای تغییراتی که قصد کاهش آن را دارد.این  الگوریتم قصد دارد پاداش را به حداکثر و مجازات را به حداقل برساند.

وظایف همچنین می تواند بر اساس خروجی مورد نظر از مدل یادگیری طبقه بندی شود. سه تا از رایج ترین ها عبارتند از:

طبقه بندی: داده ها به دو یا چند کلاس یا “برچسب ها” تقسیم می شوند (مثلا “hotdog” در مقابل “not hotdog “) و هدف عمل یادگیری این است که یک مدل تولید کند که ورودی ها را به یکی یا بیشتر از این برچسبها اختصاص دهد.

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

خوشه بندي: آنالوگ بدون نظارت برای طبقه بندي؛ ورودی ها باید به گروه ها تقسیم شوند، اما قبل از ساخت مدل، گروه ها شناخته نمی شوند.مثال کاربرد: پیش بینی قیمت خانه

منبع

آشنایی با الگوریتم های ضروری یادگیری ماشین

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

انواع الگوریتم های یادگیری ماشین

سه نوع اصلی الگوریتم های یادگیری ماشین از قرار زیرند :

  • یادگیری نظارت شده (هدایت شده – Supervised Learning) : در این نوع از الگوریتم ها که بار اصلی یادگیری ماشین را بر دوش می کشند (از لحاظ تعداد الگوریتم های این نوع)، با دو نوع از متغیرها سروکار داریم . نوع اول که متغیرهای مستقل نامیده میشوند، یک یا چند متغیر هستند که قرار است بر اساس مقادیر آنها، یک متغیر دیگر را پیش بینی کنیم. مثلا سن مشتری و تحصیلات و میزان درآمد و وضعیت تاهل برای پیش بینی خرید یک کالا توسط یک مشتری ، متغیرهای مستقل هستند. نوع دوم هم متغیرهای وابسته یا هدف یا خروجی هستند و قرار است مقادیر آنها را به کمک این الگوریتم ها پیش بینی کنیم . برای این منظور باید تابعی ایجاد کنیم که ورودیها (متغیرهای مستقل) را گرفته و خروجی موردنظر (متغیر وابسته یا هدف) را تولید کند.
  • فرآیند یافتن این تابع که در حقیقت کشف رابطه ای بین متغیرهای مستقل و متغیرهای وابسته است را فرآیند آموزش (Training Process) می گوئیم که روی داده های موجود (داده هایی که هم متغیرهای مستقل و هم متغیرهای وابسته آنها معلوم هستند مثلا خریدهای گذشته مشتریان یک فروشگاه) اعمال میشود و تا رسیدن به دقت لازم ادامه می یابد.  نمونه هایی از این الگوریتم ها عبارتند از رگرسیون، درختهای تصمیم ، جنگل های تصادفی، N نزدیک ترین همسایه، و رگرسیون لجستیک.
  • یادگیری بدون ناظر (unsupervised learning) : در این نوع از الگوریتم ها ، متغیر هدف نداریم و خروجی الگوریتم، نامشخص است. بهترین مثالی که برای این نوع از الگوریتم ها می توان زد، گروه بندی خودکار (خوشه بندی) یک جمعیت است مثلاً با داشتن اطلاعات شخصی و خریدهای مشتریان، به صورت خودکار آنها را به گروه های همسان و هم ارز تقسیم کنیم . الگوریتم Apriori و K-Means از این دسته هستند.
  • یادگیری تقویت شونده (Reinforcement Learning) : نوع سوم از الگوریتم ها که شاید بتوان آنها را در زمره الگوریتم های بدون ناظر هم دسته بندی کرد ، دسته ای هستند که از آنها با نام یادگیری تقویت شونده یاد میشود. در این نوع از الگوریتم ها، یک ماشین (در حقیقت برنامه کنترل کننده آن)، برای گرفتن یک تصمیم خاص ، آموزش داده می شود و ماشین بر اساس موقعیت فعلی (مجموعه متغیرهای موجود) و اکشن های مجاز (مثلا حرکت به جلو ، حرکت به عقب و …) ، یک تصمیم را می گیرد که در دفعات اول، این تصمیم می تواند کاملاً تصادفی باشد و به ازای هر اکشن یا رفتاری که بروز می دهد، سیستم یک فیدبک یا بازخورد یا امتیاز به او میدهد و از روی این فیدبک، ماشین متوجه میشود که تصمیم درست را اتخاذ کرده است یا نه که در دفعات بعد در آن موقعیت ، همان اکشن را تکرار کند یا اکشن و رفتار دیگری را امتحان کند.
  • با توجه به وابسته بودن حالت و رفتار فعلی به حالات و رفتارهای قبلی، فرآیند تصمیم گیری مارکوف ، یکی از مثالهای این گروه از الگوریتم ها می تواند باشد . الگوریتم های شبکه های عصبی هم می توانند ازین دسته به حساب آیند. منظور از کلمه تقویت شونده در نام گذاری این الگوریتم ها هم اشاره به مرحله فیدبک و بازخورد است که باعث تقویت و بهبود عملکرد برنامه و الگوریتم می شود

الگوریتم های اصلی و رایج یادگیری ماشین

  1. رگرسیون خطی
  2. رگرسیون لجستیک
  3. درخت تصمیم
  4. SVM
  5. Naive Bayes
  6. KNN
  7. K-Means
  8. جنگل تصادفی
  9. الگوریتم های کاهش ابعاد
  10. Gradient Boost & Ada Boost

منبع

یادگیری ماشین قسمت 1
یادگیری ماشین قسمت 2
یادگیری ماشین قسمت 3

/0 دیدگاه /توسط