شناسایی خودکار زیرفضاهای یک فضای داده با ابعاد بالا که امکان خوشه بندی بهتر از فضای اصلی را فراهم می کند . CLIQUE (Clustering in QUEst) اولین الگوریتم پیشنهادی بود برای خوشه بندی زیرفضای رشد ابعاد در فضای با ابعاد بالا از زیر فضاهای تک بعدی شروع کنید و به سمت فضاهای با ابعاد بالاتر رشد کنید . CLIQUE هر بعد را مانند یک ساختار شبکه ای پارتیشن بندی می کند و چگالی یک سلول را بر اساس تعداد نقاط آن تعیین می کند . CLIQUE ادغام روش های مبتنی بر شبکه و مبتنی بر چگالی است
فضای داده d بعدی را به واحدهای مستطیلی غیر همپوشانی تقسیم کنید (برای هر پارتیشن به صورت 1-D انجام می شود) واحدهای متراکم را شناسایی کنید . یک واحد متراکم است اگر کسری از کل نقاط داده موجود در آن از پارامتر مدل ورودی بیشتر شود.
فضاهای فرعی که مناطق متراکم را نشان می دهند برای تشکیل یک فضای جستجوی نامزدی که در آن واحدهای متراکم با ابعاد بالاتر ممکن است وجود داشته باشند، قطع می شوند.
📌 نقات قوت CLIQUE
- به طور خودکار فضاهای فرعی با بالاترین ابعاد را تا زمانی که خوشه‌های چگالی بالا در آن فضاهای فرعی
- به ترتیب رکوردها در ورودی حساس نیست و برخی از توزیع داده‌های متعارف را فرض نمی‌کند
- به صورت خطی با اندازه ورودی مقیاس می شود
- روش ساده و قابلیت تفسیر نتایج
- یک الگوریتم خوشه بندی زیر فضا است که از K-means، DBSCAN و Farthest First در زمان اجرا و دقت بهتر عمل می کند.
- می تواند خوشه هایی از هر شکل را پیدا کند و قادر به پیدا کردن هر تعداد خوشه در هر تعداد ابعاد است، جایی که تعداد توسط یک پارامتر از پیش تعیین نشده است.
- یکی از ساده ترین روش‌هاو تفسیر نتایج.
📌 نقات ضعف CLIQUE
- مانند همه رویکردهای خوشه بندی مبتنی بر شبکه، کیفیت نتایج به طور اساسی به انتخاب مناسب تعداد و عرض پارتیشن‌هاو سلول های شبکه
- نقطه ضعف اصلی الگوریتم CLIQUE این است که اگر اندازه سلول برای مجموعه ای از مقادیر بسیار بالا نامناسب باشد، تخمین بیش از حد انجام می شود و خوشه صحیح قادر به پیدا کردن نخواهد بود.
📌 عملکرد CLIQUE
الگوریتم CLIQUE از تراکم و تکنیک مبتنی بر شبکه یعنی الگوریتم خوشه بندی زیر فضا استفاده می کند و خوشه را با در نظر گرفتن استانه چگالی و تعدادی از شبکه ها به عنوان پارامترهای ورودی پیدا می کند. این به ویژه برای رسیدگی به مجموعه داده ها با تعداد زیادی از ابعاد طراحی شده است. الگوریتم CLIQUE با توجه به ارزش سوابق و تعدادی از ابعاد در مجموعه داده بسیار مقیاس پذیر است زیرا مبتنی بر شبکه است و از ویژگی Apriori به طور موثر استفاده می کند. رویکرد Apriori اظهار داشت که اگر یک واحد X بعدی متراکم باشد، تمام طرح های ان در فضای بعدی X-1 نیز متراکم هستند. این بدان معنی است که مناطق متراکم در یک زیرفضای داده شده باید مناطق متراکم را در هنگام پیش بینی به یک زیر فضای کم بعدی تولید کنند. CLIQUE جستجوی خود را برای سلول های متراکم با ابعاد بالا به تقاطع سلول های متراکم در زیر فضا محدود می کند زیرا CLIQUE از خواص apriori استفاده می کند. الگوریتم CLIQUE ابتدا فضای داده را به شبکه تقسیم می کند. این کار با تقسیم هر بعد به فواصل مساوی به نام واحد انجام می شود. پس از ان، واحدهای متراکم را شناسایی می کند. یک واحد متراکم است اگر نقاط داده در این بیش از مقدار استانه باشد. هنگامی که الگوریتم سلول های متراکم را در امتداد یک بعد پیدا می کند، الگوریتم تلاش می کند تا سلول های متراکم را در امتداد دو بعد پیدا کند و تا زمانی که تمام سلول های متراکم در کل بعد پیدا شوند، کار می کند. پس از پیدا کردن تمام سلول های متراکم در تمام ابعاد، الگوریتم برای پیدا کردن بزرگترین مجموعه (“خوشه“) سلول های متراکم متصل می شود. در نهایت، الگوریتم CLIQUE یک توصیف حداقل از خوشه تولید می کند. سپس خوشه ها از تمام زیر فضاهای متراکم با استفاده از رویکرد apriori تولید می شوند.
📌 مراحل پیاده سازی CLIQUE
- فضاهای فرعی که شامل خوشه ها هستند را شناسایی کنید
- فضای داده را پارتیشن بندی کنید و تعداد نقاطی را که در هر سلول پارتیشن قرار دارد بیابید
- با استفاده از اصل Apriori فضاهای فرعی که شامل خوشه هستند را شناسایی کنید
- خوشه‌هارا شناسایی کنید
- واحدهای متراکم را در همه زیرفضاهای علایق تعیین کنید
- واحدهای متراکم متصل را در همه زیرفضاهای علایق تعیین کنید
- حداقل توضیحات را برای خوشه‌هاایجاد کنید
- حداکثر مناطقی را تعیین کنید که یک خوشه از واحدهای متراکم متصل را برای هر خوشه پوشش می دهد.
- حداقل پوشش را برای هر خوشه تعیین کنید
💻کدنویسی
from pyclustering.cluster.clique import clique, clique_visualizer
from pyclustering.utils import read_sample
from pyclustering.samples.definitions import FCPS_SAMPLES
# read two-dimensional input data 'Target'
data = read_sample(FCPS_SAMPLES.SAMPLE_TARGET)
# create CLIQUE algorithm for processing
intervals = 10 # defines amount of cells in grid in each dimension
threshold = 0 # lets consider each point as non-outlier
clique_instance = clique(data, intervals, threshold)
# start clustering process and obtain results
clique_instance.process()
clusters = clique_instance.get_clusters() # allocated clusters
noise = clique_instance.get_noise() # points that are considered as outliers (in this example should be empty)
cells = clique_instance.get_cells() # CLIQUE blocks that forms grid
print("Amount of clusters:", len(clusters))
# visualize clustering results
clique_visualizer.show_grid(cells, data) # show grid that has been formed by the algorithm
clique_visualizer.show_clusters(data, clusters, noise) # show clustering results
intervals = 10
threshold = 3 # block that contains 3 or less points is considered as a outlier as well as its points
clique_instance = clique(data, intervals, threshold)
