
\فصل{کارهای پیشین}

در فصل سوم پایان‌نامه، کارهای پیشین انجام‌شده روی مسئله به تفصیل توضیح داده می‌شود.
نمونه‌ای از فصل کارهای پیشین در زیر آمده است.\زیرنویس{
مطالب این فصل نمونه از پایان‌نامه‌ی آقای بهنام حاتمی گرفته شده است.}


\قسمت{مسائل خوشه‌بندی}

مسئله‌ی \مهم{خوشه‌بندی}\پاورقی{Clustering} یکی از مهم‌ترین مسائل در زمینه‌ی داده‌کاوی به حساب می‌آید.
در این مسئله، هدف دسته‌بندی تعدادی شیء به‌گونه‌ای است که اشیاء درون یک دسته (خوشه)، نسبت به یکدیگر در برابر دسته‌های دیگر شبیه‌تر باشند (معیارهای متفاوتی برای تشابه تعریف می‌گردد).
این مسئله در حوزه‌های مختلفی از علوم کامپیوتر از جمله داده‌کاوی، جست‌وجوی الگو\پاورقی{Pattern recognition}، پردازش تصویر\پاورقی{Image analysis}، بازیابی اطلاعات\پاورقی{Information retrieval} و رایانش زیستی\پاورقی{Bioinformatics} مورد استفاده قرار می‌گیرد~\مرجع{han2006}.

تا کنون راه‌حل‌های زیادی برای این مسئله ارائه شده است که از لحاظ معیار تشخیص خوشه‌ها و نحوه‌ی انتخاب یک خوشه، با یک‌دیگر تفاوت بسیاری دارند.
به همین خاطر مسئله‌ی خوشه‌بندی یک مسئله‌ی بهینه‌سازی چندهدفه\پاورقی{Multi-objective} محسوب می‌شود.


همان طور که در مرجع \مرجع{estivill2002so} ذکر شده است، خوشه در خوشه‌بندی تعریف واحدی ندارد و یکی از دلایل وجود الگوریتم‌های متفاوت، همین تفاوت تعریف‌ها از خوشه است.
بنابراین با توجه به مدلی که برای خوشه‌ها ارائه می‌شود، الگوریتم متفاوتی نیز ارائه می‌گردد.
در ادامه به بررسی تعدادی از معروف‌ترین مدل‌های مطرح می‌پردازیم:

\شروع{فقرات}

\فقره
\مهم{مدل‌های مرکزگرا}: در این مدل‌ها، هر دسته با یک مرکز نشان داده می‌شود.
از جمله معروف‌ترین روش‌های خوشه‌بندی بر اساس این مدل،  خوشه‌بندی $k$-مرکز، خوشه‌بندی $k$-میانگین\پاورقی{$k$-Means} و خوشه‌بندی $k$-میانه\پاورقی{$k$-Median} است.

\فقره
\مهم{مدل‌های مبتی بر توزیع نقاط}: در این مدل، دسته‌ها با فرض پیروی از یک توزیع احتمالی مشخص می‌شوند.
از جمله الگوریتم‌های معروف ارائه شده در این مدل، الگوریتم بیشینه‌سازی امید ریاضی\پاورقی{Expectation-maximization} است.

\فقره
\مهم{مدل‌های مبتنی بر تراکم نقاط}: در این مدل، خوشه‌ها متناسب با ناحیه‌های متراکم نقاط در مجموعه داده مورد استفاده قرار می‌گیرد.

\فقره
\مهم{مدل‌های مبتنی بر گراف}: در این مدل، هر خوشه به مجموعه از رئوس گفته می‌شود که تمام رئوس آن با یک‌دیگر همسایه باشند.
از جمله الگوریتم‌های معروف این مدل، الگوریتم خوشه‌بندی \لر{HCS}\پاورقی{Highly Connected Subgraphs} است.

\پایان{فقرات}

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

\شروع{فقرات}

\فقره
\مهم{تخصیص قطعی داده‌ها}: در این نوع خوشه‌بندی هر داده دقیقاً به یک خوشه اختصاص داده می‌شود.

\فقره
\مهم{تخصیص قطعی داده‌ها با داده‌ی پرت}: در این نوع خوشه‌بندی ممکن است بعضی از داده‌ها به هیچ خوشه‌ای اختصاص نیابد، اما بقیه داده‌ها هر کدام دقیقاً به یک خوشه اختصاص می‌یابد.

\فقره
\مهم{تخصیص قطعی داده}: در این نوع خوشه‌بندی هر داده دقیقاً به یک خوشه اختصاص داده می‌شود.

\فقره
\مهم{خوشه‌بندی هم‌پوشان}: در این نوع خوشه‌بندی هر داده می‌تواند به چند خوشه اختصاص داده شود.
در گونه‌ای از این مدل، می‌توان هر نقطه را با احتمالی به هر خوشه اختصاص می‌یابد.
به این گونه از خوشه‌بندی، خوشه‌بندی نرم\پاورقی{Soft clustering} گفته می‌شود.

\فقره
\مهم{خوشه‌بندی سلسه‌مراتبی}: در این نوع خوشه‌ها، داده‌ها به گونه‌ای به خوشه‌ها تخصیص داده می‌شود که دو خوشه یا اشتراک ندارند یا یکی به طور کامل دیگری را می‌پوشاند.
در واقع در بین خوشه‌ها، رابطه‌ی پدر فرزندی برقرار است.

\پایان{فقرات}

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

\قسمت{خوشه‌بندی $k$-مرکز}

\REM{
مسئله‌ی خوشه‌بندی، از‌ جمله مسائل مهم علوم کامپیوتر است که مورد توجه بسیاری از دانشمندان قرار گرفته است.
راه‌حل‌های الگوریتمی بسیار زیادی برای خوشه‌بندی ارائه شده است.
این الگوریتم‌ها را براساس رویکرد‌های مختلفی که به مسئله دارند، خوشه‌های متفاوتی به دست می‌آورند.
در عمل هیچ‌کدام از راه‌حل‌های ارائه شده به طور کلی بر دیگری ارجحیت ندارد و باید راه‌حل مدنظر را متناسب با کاربرد مطرح مورد استفاده قرار داد.
به طور مثال استفاده از الگوریتم‌های مرکزگرا، برای خوشه‌های غیر محدب به خوبی عمل نمی‌کند.
یکی از رویکردهای شناخته‌شده برای مسئله‌ی خوشه‌بندی، مسئله‌ی \مهم{$\boldsymbol{k}$-مرکز} است.
در این مسئله هدف، پیدا کردن $k$ نقطه به عنوان مرکز دسته‌ها است به‌طوری‌که شعاع دسته‌ها تا حد ممکن کمینه شود.
در نظریه‌ی گراف، مسئله‌ی $k$-مرکز متریک\پاورقی{Metric} یا مسئله‌ی مکان‌یابی تسهیلات متریک\پاورقی{Metric facility location} یک مسئله‌ی بهینه‌سازی ترکیبیاتی\پاورقی{Combinatorial optimization} است.
}



یکی از رویکردهای شناخته‌شده برای مسئله‌ی خوشه‌بندی، مسئله‌ی \مهم{$\boldsymbol{k}$-مرکز} است.
در این مسئله هدف، پیدا کردن $k$ نقطه به عنوان مرکز دسته‌ها است به‌طوری‌که شعاع دسته‌ها تا حد ممکن کمینه شود.
%فرض کنید که $n$ شهر و فاصله‌ی دوبه‌دوی آن‌ها، داده‌شده است.
%می‌خواهیم $k$ انبار در شهرهای مختلف بسازیم به‌طوری‌که حداکثر فاصله‌ی هر شهر از نزدیک‌ترین انبار به خود، کمینه گردد.
%در حالت نظریه‌ی گراف آن، این بدان معناست که مجموعه‌ای شامل $k$ رأس انتخاب کنیم به‌طوری‌که بیش‌ترین فاصله‌ی هر نقطه از نزدیک‌ترین نقطه‌اش داخل مجموعه‌ی $k$ عضوی کمینه گردد.
%توجه نمایید که فاصله‌ی بین رئوس باید در فضای متریک\پاورقی{Metric space} باشند و یا به زبان دیگر، یک گراف کامل داشته باشیم که فاصله‌ها در آن در رابطه‌ی مثلثی\پاورقی{Triangle equation} صدق می‌کنند.
مثالی از مسئله‌ی $2$-مرکز در شکل~\رجوع{شکل:دومرکز} نشان داده شده است.
در این پژوهش، مسئله‌ی $k$-مرکز با متریک‌های خاص و برای $k$های کوچک مورد بررسی قرار گرفته است و هر کدام از‌ 
تعریف رسمی مسئله‌ی $k$-مرکز در زیر آمده است:

\شروع{شکل}[t]
\centerimg{k-center}{8cm}
\vspace{1em}
\شرح{نمونه‌ای از ‌مسئله‌ی ۲-مرکز}
\برچسب{شکل:دومرکز}
\پایان{شکل}

\شروع{مسئله}
\مهم{($k$-مرکز)}  گراف کامل بدون جهت $G = (V, E)$ با تابع فاصله‌ی $d$، 
که از نامساوی مثلثی پیروی می‌کند داده ‌شده است.
زیرمجموعه‌ی $S \subseteq V$ با اندازه‌ی $k$ را به‌گونه‌ای انتخاب کنید که عبارت زیر را کمینه کند:
\شروع{equation}
\max_{v \in V} \{ \min_{s \in S} d(v, s) \}
\پایان{equation}
\پایان{مسئله}

گونه‌های مختلفی از مسئله‌ی $k$-مرکز با محدودیت‌های متفاوت توسط پژوهشگران مورد مطالعه قرار گرفته است.
از جمله‌ی این گونه‌ها، می‌توان به حالتی که در بین داده‌های ورودی، داده‌های پرت وجود دارد، اشاره کرد.
در واقع در این مسئله، قبل از خوشه‌بندی می‌توانیم تعدادی از نقاط ورودی را حذف نموده و سپس به خوشه‌بندی نقاط بپردازیم.
سختی این مسئله از آنجاست که نه تنها باید مسئله‌ی خوشه‌بندی را حل نمود، بلکه در ابتدا باید تصمیم گرفت که کدام یک از داده‌ها را به‌عنوان داده‌ی پرت در نظر گرفت که بهترین جواب در زمان خوشه‌بندی به دست آید.
در واقع اگر تعداد نقاط پرتی که مجاز به حذف است، برابر صفر باشد، مسئله به مسئله‌ی $k$-مرکز تبدیل می‌شود.
نمونه‌ای از مسئله‌ی $2$-مرکز با $7$ داده‌ی پرت را در شکل~\رجوع{شکل:دومرکزپرت} می‌توانید ببینید.
تعریف دقیق‌تر این مسئله در زیر آمده است:

\شروع{مسئله}
\مهم{($k$-مرکز با داده‌های پرت)} یک گراف کامل بدون جهت $G = (V, E)$ با تابع فاصله‌ی $d$، که از نامساوی مثلثی پیروی می‌کند داده‌شده است.
زیرمجموعه‌ی $Z \subseteq V$ با اندازه‌ی $z$ و  مجموعه‌ی $S \subseteq V - Z$ با اندازه‌ی $k$ را انتخاب کنید به‌ طوری ‌که عبارت زیر را کمینه کند:
\شروع{equation}
\max_{v \in V - Z} \{ \min_{s \in S} d(v, s) \}
\پایان{equation}
\پایان{مسئله}

\شروع{شکل}[t]
\centerimg{outlier}{8cm}
\شرح{نمونه‌ای از‌مسئله‌ی ۲-مرکز با داده‌های پرت}
\برچسب{شکل:دومرکزپرت}
\پایان{شکل}

گونه‌ی دیگری از مسئله‌ی $k$-مرکز که در سال‌های اخیر مورد توجه قرار گرفته است، حالت جویبار داده‌ی آن است.
در این‌گونه از مسئله‌ی $k$-مرکز، در ابتدا تمام نقاط در دسترس نیستند، بلکه به‌مرور زمان نقاط در دسترس قرار می‌گیرند.
محدودیت دومی که وجود دارد، محدودیت حافظه است، به‌طوری‌که نمی‌توان تمام نقاط را در حافظه نگه داشت و بعضاً حتی امکان نگه‌داری در حافظه‌ی جانبی نیز وجود ندارد و به‌طور معمول باید مرتبه‌ی حافظه‌ای کم‌تر از مرتبه حافظه‌ی \مهم{خطی}\پاورقی{Linear} متناسب با تعداد نقاط استفاده نمود.
از این به بعد به چنین مرتبه‌ای، مرتبه‌ی \مهم{زیرخطی}\پاورقی{sublinear} می‌گوییم.
مدلی که ما در این پژوهش بر روی آن تمرکز داریم مدل جویبار داده تک‌گذره\پاورقی{Single pass}~\مرجع{aggarwal2007data} است.
یعنی تنها یک بار می‌توان از ابتدا تا انتهای داده‌ها را بررسی کرد و پس از عبور از یک داده، اگر آن داده در حافظه ذخیره نشده باشد، دیگر به آن دسترسی وجود ندارد. علاوه بر این، در هر لحظه باید بتوان به پرسمان (برای تمام نقاطی از جویبار داده که تاکنون به آن دسترسی داشته‌ایم) پاسخ داد.

\REM{
یکی از دغدغه‌هایی که در مسائل جویبار داده وجود دارد، عدم امکان دسترسی به تمام نقاط است.
در واقع هم این مشکل وجود دارد که به تمام داده‌های قبلی دسترسی نداریم و هم این مشکل وجود دارد که هیچ اطلاعی از داده‌های آتی نداریم.
در نتیجه یکی از تبعات این‌گونه از مسئله‌ی $k$-مرکز، امکان انتخاب نقطه‌ای به عنوان مرکز برای یک دسته است به‌طوری‌که در بین نقاط ورودی نیست.
زیرا از نقاطی که تاکنون آمده‌اند به طور کامل اطلاع نداریم.
\شروع{تعریف}[متریک $L_p$]
به ازای دو نقطه‌ی $d$-بعدی $s(s_1, \cdots, s_d)$ و $q(q_1, \cdots, q_d)$، فاصله‌ی $p$ و $q$ در متریک $L_p$ برابر است با:
$$d(p, q) = \sqrt[p]{\sum_{i=1}^{d} (s_i - q_i) ^ p}$$
\پایان{تعریف}
این‌گونه از مسئله‌ی $k$-مرکز، معمولاً تنها برای $L_p$-متریک مطرح می‌شود یا حالتی که ما مجموعه‌ای از تمام نقاط فضا به انضمام فاصله‌هایشان را داشته باشیم.
زیرا مرکز دسته‌ها ممکن است در هر نقطه از فضا قرار بگیرد و ما نیاز داریم که فاصله‌ی آن را از تمام نقاط بدانیم.
نمونه‌ای از مسئله‌ی $2$-مرکز در حالت پیوسته، در شکل \رجوع{شکل:دومرکزپیوسته} نشان داده شده است.
تعریف دقیق گونه‌ی جویبار داده‌ی مسئله‌ی $k$‌-مرکز، در زیر آمده است:

\شروع{شکل}[t]
\centerimg{continious-k-center}{10cm}
\شرح{نمونه‌ای از ‌مسئله‌ی ۲-مرکز در حالت پیوسته}
\برچسب{شکل:دومرکزپیوسته}
\پایان{شکل}
}

\شروع{مسئله}
\مهم{($k$-مرکز در حالت جویبار داده)} مجموعه‌ای از نقاط در فضای $d$-بعدی به مرور زمان داده می‌شود.
در هر لحظه از زمان، به ازای مجموعه‌ی $U$ از نقاطی که تا کنون وارد شده‌اند،
زیرمجموعه‌ی $S \subseteq U$ با اندازه‌ی $k$ را انتخاب کنید به ‌طوری ‌که عبارت زیر کمینه شود:
\شروع{equation}
\max_{u \in U} \{ \min_{s \in S} d(u, s) \}
\پایان{equation}
\پایان{مسئله}

از آنجایی که گونه‌ی جویبار داده و داده پرت مسئله‌ی $k$-مرکز به علت به‌روز بودن مبحث داده‌های حجیم\پاورقی{Big data}، به تازگی مورد توجه قرار گرفته است.
در این تحقیق سعی شده است که تمرکز بر روی این‌گونه‌ی خاص از مسئله باشد.
همچنین در این پژوهش سعی می‌شود گونه‌های مسئله را برای انواع متریک‌ها و برای $k$های کوچک نیز مورد بررسی قرار داد. 

\قسمت{مدل جویبار داده}

همان‌طور که ذکر شد مسئله‌ی $k$-مرکز در حالت داده‌های پرت و جویبار داده، گونه‌های تعمیم‌یافته از مسئله‌ی $k$-مرکز هستند و در حالت‌های خاص به مسئله‌ی $k$-مرکز کاهش پیدا می‌کنند.
مسئله‌ی $k$-مرکز در حوزه‌ی مسائل ان‌پی-سخت\پاورقی{NP-hard} قرار می‌گیرد و با فرض $P \neq NP$ الگوریتم دقیق با زمان چندجمله‌ای برای آن وجود ندارد \مرجع{michael1979computers}.
بنابراین برای حل کارای\پاورقی{Efficient} این مسائل از الگوریتم‌های تقریبی\پاورقی{Approximation algorithm} استفاده می‌شود.

برای مسئله‌ی $k$-مرکز، دو الگوریتم تقریبی معروف وجود دارد.
در الگوریتم اول، که به روش حریصانه\پاورقی{Greedy} عمل می‌کند، در هر مرحله بهترین مرکز ممکن را انتخاب می‌کند به طوری تا حد ممکن از مراکز قبلی دور باشد~\مرجع{megiddo1984complexity}.
این الگوریتم، الگوریتم تقریبی با ضریب تقریب 2 ارائه می‌دهد.
در الگوریتم دوم، با استفاده از مسئله‌ی مجموعه‌ی غالب کمینه\پاورقی{Dominating set}، الگوریتمی با ضریب تقریب ۲ ارائه می‌گردد \مرجع{vazirani2013approximation}.
همچنین ثابت شده است، که بهتر از این ضریب تقریب، الگوریتمی نمی‌توان ارائه داد مگر آن‌که $P = NP$ باشد.

برای مسئله‌ی $k$-مرکز در حالت جویبار داده برای ابعاد بالا، بهترین الگوریتم موجود ضریب تقریب $2 + \eps$ دارد \مرجع{mccutchen2008streaming, guha2009tight, ahn2014computing} و ثابت می‌شود الگوریتمی با ضریب تقریب بهتر از $2$ نمی‌توان ارائه داد. برای مسئله‌ی $k$-مرکز با داده‌ی پرت در حالت جویبار داده نیز، بهترین الگوریتم ارائه شده، الگوریتمی با ضریب تقریب $4 + \eps$ است که با کران پایین $3$ هنوز اختلاف قابل توجهی دارد \مرجع{charikar2001algorithms}. 

برای $k$های کوچک به خصوص، $k =1, 2$، الگوریتم‌های بهتری ارائه شده است. بهترین الگوریتم ارائه شده برای مسئله‌ی $1$-مرکز در حالت جویبار داده برای ابعاد بالا، دارای ضریب تقریب $1.22$ است و کران پایین $\frac{1 + \sqrt{2}}{2}$ نیز برای این مسئله اثبات شده است \مرجع{agarwal2010streaming, chan2014streaming}. برای مسئله $2$-مرکز در حالت جویبار داده برای ابعاد بالا، اخیرا راه‌حلی با ضریب تقریب $1.8 + \eps$ ارائه شده است \مرجع{kim2014improved}. برای مسئله‌ی $1$-مرکز با داده‌ی پرت، تنها الگوریتم موجود، الگوریتمی با ضریب تقریب $1.73$ است \مرجع{zarrabi2009streaming}.

\قسمت{تقریب‌پذیری}

یکی از راه‌کارهایی که برای کارآمد کردن راه‌حل ارائه شده برای یک مسئله وجود دارد، استفاده از الگوریتم‌های تقریبی برای حل آن مسئله است.
یکی از عمده‌ترین دغدغه‌های مطرح در الگوریتم‌های تقریبی کاهش ضریب تقریب است.
در بعضی از موارد حتی امکان ارائه‌ی الگوریتم تقریبی با ضریبی ثابت نیز وجود ندارد.
به طور مثال، الگوریتم تقریبی با ضریب تقریب کم‌تر از $2$، برای مسئله‌ی $k$-مرکز وجود ندارد مگر این‌که $P = NP$ باشد.
برای مسائل مختلف، معمولاً می‌توان کران پایینی برای میزان تقریب‌پذیری آن‌ها ارائه داد.
در واقع برای برخی مسائل ان‌پی-سخت، علاوه بر این که الگوریتم کارآمدی وجود ندارد، بعضاً الگوریتم تقریبی با ضریبی تقریب کم و نزدیک به یک نیز وجود ندارد.
در جدول \رجوع{جدول:تقریب‌پذیری}  میزان تقریب‌پذیری مسائل مختلفی که در این پایان‌نامه مورد استفاده قرار می‌گیرد را می‌بینید.



\شروع{لوح}[t]
\وسط‌چین
\شرح{نمونه‌هایی از کران پایین تقریب‌پذیری مسائل خوشه‌بندی}

\شروع{جدول}{|c|c|}
\خط‌پر
مسئله & کران پایین تقریب‌پذیری \\
\خط‌پر
\خط‌پر
$k$-مرکز & $2$ \مرجع{vazirani2013approximation} \\ 
$k$-مرکز در فضای اقلیدسی & $1.822$ \مرجع{bern1996approximation} \\
$1$-مرکز در حالت جویبار داده & $\frac{1 + \sqrt{2}}{2}$ \مرجع{agarwal2010streaming} \\
$k$-مرکز با نقاط پرت و نقاط اجباری & $3$ \مرجع{charikar2001algorithms}\\
\خط‌پر
\پایان{جدول}

\برچسب{جدول:تقریب‌پذیری}
\پایان{لوح}
