متداول ترین رابطه‏ی اندازه‏گیری متریک. حالت خاصی از رابطه‏ی Minkowski با n=2. تولید خوشه‏هایی با شکل کروی.

الگوریتم
K-Means [32].

شباهت کسینوسی^[۵۷]

عدم وابستگی به طول بردار.

متداول ترین معیار اندازه‏گیری در خوشه‏بندی اسناد^[۵۸] [۷۵].

فاصله‏ی همینگ^[۵۹]

if then 1
else 0

تعداد بیت هایی که نیاز به تغییر دارند تا یک بردار بیتی به دیگری تبدیل شود.

الگوریتم خوشه‏بندی توافقی IVC [57] و برخی از الگوریتم‏های خوشه‏بندی تقریبی [۲۲].

محاسبه‏ی مرکز خوشه‏ها در الگوریتم‏های بخش‏بندی به دو روش انجام می‏شود. در روش اول هر یک از صفات خاصه‏ی بردار مرکز خوشه، میانگین صفات خاصه‏ی متناظر، در اشیاء داده‏ی همان خوشه است. یکی از الگوریتم‏های مطرح که از این روش استفاده می‏کند الگوریتم K-Means است که در بخش ۲-۲-۳ به طور دقیق‏تری مورد بررسی قرار می‏گیرد. در روش دوم مرکز هر خوشه، یکی از اشیاء داده‏ی همان خوشه انتخاب می‏شود به طوری که شئ داده‏‏ی انتخاب شده، نزدیک‏ترین بردار به مرکز ثقل خوشه می‏باشد. به عنوان مثال، الگوریتم K-Mediods با بهره گرفتن از این روش مرکز خوشه‏ها را محاسبه می‏کند.

روش‏های سلسله مراتبی
در خوشه‏بندی سلسله مراتبی، خوشه‏های بدست آمده در یک ساختار درختی سازماندهی می‏شوند. به این صورت که مجموعه داده X به بخش‏های H={H₁, H₂, …, H_Q} تقسیم می‏شود (Q ≤ N). به طوری که [۷۲]:
این گروه از الگوریتم‏های خوشه‏بندی به دو زیر گروه عمده تقسیم می‏گردد. یک زیر گروه شامل الگوریتم‏های تقسیم کننده است، که به صورت بالا به پایین داده‏ها را به خوشه‏هایی کوچکتر تقسیم می‏کنند، تا زمانی که هر خوشه تنها شامل یک شئ داده شود. زیر گروه دیگر شامل الگوریتم‏های تجمیع کننده است، که به صورت پایین به بالا خوشه‏هایی که در ابتدا تنها شامل یک شئ داده‏ هستند را جهت تشکیل خوشه‏هایی بزرگتر در هم ادغام می‏کنند، تا زمانی که تمام داده‏ها در یک خوشه واحد قرار گیرند. نتایج حاصل از الگوریتم‏های تقسیم کننده و تجمیع کننده را می‏توان با بهره گرفتن از نمودار درختی^[۶۰] نشان داد. برخی از مزایای روش‏های خوشه‏بندی سلسله مراتبی عبارتند از: ۱) پایان پذیری سریع، ۲) عدم نیاز به تشخیص تعداد خوشه‏ها قبل از انجام خوشه‏بندی، ۳) محاسبه‏ی کامل سلسله مراتبی از خوشه‏ها، ۴) دیداری سازی^[۶۱] مناسب نتایج و ۵) بدست آوردن یک خوشه‏بندی مسطح با برش قسمتی از نمودار درختی [۴۵]. الگوریتم‏های ^[۶۲]BIRCH ، CURE^[63] و CHAMELEON نمونه‏هایی از الگوریتم‏های سلسله مراتبی می‏باشند.

الگوریتم خوشه‏بندی K-Means
ساختار الگوریتم پیشنهادی در این پایان نامه بر اساس الگوریتم K-Means می‏باشد. بنابراین در این بخش به بررسی این الگوریتم می‏پردازیم تا برخی از مقدمات لازم جهت ارائه‏ الگوریتم پیشنهادی فراهم گردد. الگوریتم K-Means در سال ۱۹۵۶ ارائه شد و یکی از قدیمی‏ترین و پرکاربردترین الگوریتم‏های خوشه‏بندی می‏باشد. تاکنون توسعه‏های زیادی از این الگوریتم بوجود آمده است [۵۰،۶۰،۱۱،۶۹،۵]. فهرست کاملی از مقالات مرتبط با الگوریتم خوشه‏بندی K-Means را می‏توانید در [۳۵] مشاهده نمایید. الگوریتم خوشه‏بندی K-Means و جنبه‏ه ای مختلف آن در [۵۸،۵۶] بطور کامل مورد بررسی قرار گرفته است. الگوریتمی که در این قسمت ارائه می‏گردد، الگوریتم ابتدایی K-Means می‏باشد.

در اجرای الگوریتم K-Means ابتدا باید K مرکز اولیه برای K خوشه انتخاب گردد، K (تعداد خوشه‏های مورد نظر) پارامتری است که به طور معمول توسط کاربر تعیین می‏شود. هر شئ داده به نزدیک‏ترین مرکز اختصاص می‏یابد و مجموعه داده‏های تخصیص یافته به یک مرکز، یک خوشه را تشکیل می‏دهند. سپس مرکز هر خوشه بر مبنای اشیاء داده موجود در آن بروز رسانی می‏شود. این تخصیص و بروز رسانی تا زمانی تکرار می‏گردد که هیچ داده‏ای باعث تغییر خوشه‏ها نشود و یا به عبارت دیگر مرکز خوشه‏ها تغییر نکند [۵۲]. شبه کد K-Means در الگوریتم ۲-۱ تشریح شده است.
شکل ۲-۲ نیز مراحل اجرای K-Means را در چهار گام با سه مرکز اولیه نشان می‏دهد. مرکز خوشه‏ها در شکل با نماد “+” مشخص شده‏اند؛ تمام اشیاء داده‏ی مربوط به یک خوشه، دارای شکل مشابهی هستند.

الگوریتم ۲-۱ الگوریتم K-Means [30]

Input:
K : the number of clusters
X : a data set containing N objects
Output: A set of K clusters.
Method:
(۱) arbitrarily choose k objects from X as the initial cluster centers
(۲) repeat
(۳) (re)assign each object to the cluster to which the object is the most similar,
based on the mean value of the objects in the cluster
(۴) update the cluster means, i.e., calculate the mean value of the objects for each
cluster
(۵) until clusters do not change