این مقاله بخش عملی آموزش الگوریتم ROCK است. اگر هنوز با مفاهیم شباهت Jaccard، گراف همسایگی، Link و تابع Goodness آشنا نیستید، ابتدا مقاله «الگوریتم ROCK چیست؟ راهنمای کامل خوشهبندی دادههای طبقهای» را مطالعه کنید.
در این بخش، مفاهیم نظری بخش اول را به کد پایتون تبدیل میکنیم؛ از آمادهسازی دادههای طبقهای و ساخت ماتریس شباهت تا تشکیل گراف همسایگی، محاسبه Link، خوشهبندی و ارزیابی خروجی.
1. مقدمه
پل زدن میان فرمولهای انتزاعی نظریه گراف و یک سیستم نرمافزاری کارآمد، نیازمند ترجمه مفاهیم ریاضی به ساختارهای داده بهینه است. الگوریتم ROCK (Robust Clustering using Links) برخلاف الگوریتمهای سنتی مبتنی بر فاصله (مانند K-Means یا K-Modes)، فرآیند تصمیمگیری خود را بر پایه یک مفهوم توپولوژیک به نام پیوند (Link) بنا میکند. در این الگوریتم، شباهت مستقیم میان دو نقطه داده (مانند شباهت جاکارد) به تنهایی برای خوشهبندی کافی نیست؛ بلکه تعداد همسایگان مشترک آنها در گراف شباهت، تعیینکننده اصلی انسجام است.
۱.۱. در این آموزش چه چیزی میسازیم؟
در پایان این آموزش، یک نسخه آموزشی از کلاس ROCKClustering در پایتون خواهیم داشت که میتواند دادههای باینری یا دادههای طبقهایِ تبدیلشده به one-hot را خوشهبندی کند. سپس آن را روی یک مثال کوچک قابلفهم و یک مطالعه موردی سبد خرید اجرا میکنیم.
روند عملی کار شامل محاسبه شباهت Jaccard، ساخت گراف همسایگی بر اساس آستانه θ، محاسبه Link میان نمونهها، ادغام سلسلهمراتبی خوشهها و تحلیل کیفیت خوشههای نهایی است.
از دیدگاه عملیاتی، پیادهسازی این الگوریتم شامل چهار گام کلیدی است:
- محاسبه ماتریس شباهت زوجی: معمولاً با استفاده از معیار جاکارد برای دادههای باینری/ردهای.
- اعمال آستانه شباهت (θ) برای تشکیل ماتریس مجاورت : این ماتریس یک گراف بدون جهت و بدون وزن را نشان میدهد که در آن یال بین دو نقطه وجود دارد اگر و تنها اگر شباهت آنها بزرگتر یا مساوی θ باشد.
- محاسبه ماتریس پیوند : با ضرب ماتریس مجاورت در خودش. در این ماتریس، مقدار درایه (i, j) نشاندهنده تعداد مسیرهای با طول ۲ بین گرههای i و j (همسایگان مشترک) است. قطر اصلی ماتریس مجاورت صفر در نظر گرفته میشود تا هر نمونه همسایه خودش محسوب نشود.
- ادغام سلسلهمراتبی تجمعی : ادغام سلسلهمراتبی تجمعی: استفاده از تابع Goodness برای ادغام گامبهگام خوشهها تا رسیدن به تعداد خوشه هدف K یا تا زمانی که ادغام معناداری باقی نماند.
۲. پیشنیازها و ساختار داده ورودی
2.1.کتابخانههای موردنیاز
pip install numpy scipy pandas scikit-learn matplotlibبعد توضیح کوتاه:
- :NumPy ساخت و پردازش ماتریسهای باینری
- :SciPy محاسبه فاصله و شباهت Jaccard
- :Pandas بارگذاری و آمادهسازی دادههای جدولی
- :scikit-learn کدگذاری one-hot و معیارهای ارزیابی
- Matplotlib : رسم نمودار حساسیت آستانه و تحلیل خروجی
2.2.داده ورودی ROCK باید چه ویژگیهایی داشته باشد؟
ورودی نهایی الگوریتم باید یک ماتریس دوبعدی باشد که هر سطر یک نمونه و هر ستون یک ویژگی را نشان دهد. مقادیر این ماتریس باید باینری، یعنی صفر و یک، باشند.
اگر دادهها طبقهای هستند، ابتدا باید با روش one-hot encoding به نمایش باینری تبدیل شوند. همچنین بهتر است ردیفهای کاملاً صفر، ستونهای بدون تغییر و مقادیر گمشده پیش از اجرای ROCK بررسی و مدیریت شوند.
بعد یک مثال کوتاه از pd.get_dummies() بگذار:
import pandas as pd
df_binary = pd.get_dummies(df, dummy_na=False).astype(int) X = df_binary.to_numpy()
۳. مثال آموزشی کوچک: از داده باینری تا Link Matrix
۳.۱. تعریف داده نمونه
پیش از اجرای ROCK روی دادههای بزرگ، بهتر است ابتدا رفتار الگوریتم را با یک مثال کوچک و قابل بررسی یاد بگیریم. در مثال زیر، شش نمونه داریم که هر کدام با شش ویژگی باینری توصیف شدهاند. مقدار ۱ نشاندهنده وجود یک ویژگی و مقدار ۰ نشاندهنده نبود آن است.
| نمونه | ویژگی ۱ | ویژگی ۲ | ویژگی ۳ | ویژگی ۴ | ویژگی ۵ | ویژگی ۶ |
| A | 1 | 1 | 1 | 0 | 0 | 0 |
| B | 1 | 1 | 0 | 0 | 0 | 0 |
| C | 1 | 0 | 1 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 1 | 1 | 1 |
| E | 0 | 0 | 0 | 1 | 1 | 0 |
| F | 0 | 0 | 0 | 1 | 0 | 1 |
کد پایتون:
import numpy as np
sample_names = ["A", "B", "C", "D", "E", "F"]
X_small = np.array([
[1, 1, 1, 0, 0, 0], # A
[1, 1, 0, 0, 0, 0], # B
[1, 0, 1, 0, 0, 0], # C
[0, 0, 0, 1, 1, 1], # D
[0, 0, 0, 1, 1, 0], # E
[0, 0, 0, 1, 0, 1] # F
], dtype=int)
theta = 0.5
۳.۲. چرا این مثال برای ROCK مناسب است؟
با آستانه θ برابر با ۰٫۵، نمونههای A و B شباهت مستقیم بالایی دارند. همچنین A و C نیز مشابهاند. اما B و C با وجود اینکه هر دو به A نزدیکاند، لزوماً همسایه مستقیم نیستند.
این دقیقاً همان وضعیتی است که مفهوم Link اهمیت پیدا میکند: B و C یک همسایه مشترک، یعنی A ، دارند. بنابراین ROCK فقط به شباهت مستقیم B و C اکتفا نمیکند و ارتباط ساختاری آنها را نیز در نظر میگیرد. همین الگو برای نمونههای D، E و F نیز تکرار میشود.
۳.۳. خروجی مورد انتظار این مثال
انتظار داریم گراف همسایگی دو ناحیه اصلی بسازد: گروه نخست شامل A، B و C و گروه دوم شامل D، E و F. در مرحله بعد، ماتریس شباهت Jaccard، ماتریس مجاورت و Link Matrix را از همین داده محاسبه میکنیم.
۳.۴. محاسبه ماتریس شباهت Jaccard
ابتدا شباهت Jaccard را برای تمام جفتهای نمونه محاسبه میکنیم. مقدار ۱ به معنای شباهت کامل و مقدار صفر به معنای نداشتن هیچ ویژگی مشترک است.
import numpy as np
import pandas as pd
from scipy.spatial.distance import pdist, squareform
# تبدیل فاصله Jaccard به شباهت Jaccard
jaccard_distance = squareform(pdist(X_small, metric="jaccard"))
similarity_matrix = 1 - jaccard_distance
# شباهت هر نمونه با خودش برابر ۱ است
np.fill_diagonal(similarity_matrix, 1.0)
similarity_df = pd.DataFrame(
similarity_matrix,
index=sample_names,
columns=sample_names
)
print("ماتریس شباهت Jaccard:")
print(similarity_df.round(2))
تفسیر:
برای نمونه، شباهت A و B برابر با ۰٫۶۷ است، زیرا دو ویژگی مشترک دارند و مجموع ویژگیهای فعال آنها سه مورد است. شباهت B و C برابر با ۰٫۳۳ است؛ بنابراین این دو نمونه از نظر مستقیم به اندازه کافی مشابه نیستند.
۳.۵. ساخت گراف همسایگی با آستانه θ
در این مثال، آستانه شباهت را برابر با ۰٫۵ در نظر گرفتهایم. اگر شباهت دو نمونه بزرگتر یا مساوی این مقدار باشد، میان آنها یک یال در گراف همسایگی ایجاد میشود.
theta = 0.5
adjacency_matrix = (similarity_matrix >= theta).astype(int)
# گراف بدون حلقه خودی است؛ هر نمونه به خودش متصل نیست
adjacency_df = pd.DataFrame(
adjacency_matrix,
index=sample_names,
columns=sample_names
)
print("ماتریس مجاورت:")
print(adjacency_df)
توضیح:
در ماتریس مجاورت، مقدار ۱ نشاندهنده وجود ارتباط همسایگی و مقدار ۰ نشاندهنده نبود آن است. در این مثال، A با B و C همسایه است؛ اما B و C با وجود ارتباط غیرمستقیم از طریق A، همسایه مستقیم محسوب نمیشوند.
۳.۶. محاسبه Link Matrix
اکنون با ضرب ماتریس مجاورت در خودش، تعداد همسایههای مشترک هر جفت نمونه را محاسبه میکنیم. این ماتریس، هسته اصلی تصمیمگیری در الگوریتم ROCK است.
link_matrix = adjacency_matrix @ adjacency_matrix
# مقدار قطر اصلی برای تحلیل پیوند میان نمونههای متفاوت صفر میشود
np.fill_diagonal(link_matrix, 0)
link_df = pd.DataFrame(
link_matrix,
index=sample_names,
columns=sample_names
)
print("ماتریس Link":)
print(link_df)
تفسیر :
مقدار Link(B, C) برابر با ۱ است، زیرا هر دو نمونه B و C یک همسایه مشترک، یعنی A، دارند. به همین شکل، مقدار Link(E, F) نیز برابر با ۱ است، زیرا هر دو به D متصلاند.
این مثال نشان میدهد که ROCK چگونه میتواند میان نمونههایی که شباهت مستقیم متوسطی دارند، اما در یک ساختار همسایگی مشترک قرار گرفتهاند، ارتباط معنادار پیدا کند.
۴. پیادهسازی آموزشی کلاس ROCKClustering
کد زیر یک پیادهسازی آموزشی از ROCK است و مراحل اصلی الگوریتم را بهصورت شفاف نشان میدهد: محاسبه Jaccard، تشکیل ماتریس همسایگی، محاسبه Link و ادغام سلسلهمراتبی خوشهها.
این نسخه برای دادههای کوچک و متوسط مناسب است، زیرا ماتریسهای جفتی میسازد. بنابراین نباید آن را بدون بهینهسازی روی دادههای بسیار بزرگ استفاده کرد.
import warnings
import numpy as np
from scipy.spatial.distance import pdist, squareform
class ROCKClustering:
def __init__(self, theta=0.5, n_clusters=2):
if not 0 < theta < 1:
raise ValueError(
"theta باید بزرگتر از ۰ و کوچکتر از ۱ باشد."
)
if not isinstance(n_clusters, int) or n_clusters < 1:
raise ValueError(
"n_clusters باید یک عدد صحیح مثبت باشد."
)
self.theta = theta
self.n_clusters = n_clusters
@staticmethod
def _validate_binary_matrix(X):
X = np.asarray(X)
if X.ndim != 2 or X.shape[0] < 2:
raise ValueError(
"X باید یک ماتریس دوبعدی با دستکم دو نمونه باشد."
)
if not np.isin(X, [0, 1]).all():
raise ValueError(
"مقادیر X باید فقط صفر و یک باشند."
)
return X.astype(np.int8)
def _goodness(self, link_count, size_i, size_j):
if link_count <= 0:
return 0.0
f_theta = (1 - self.theta) / (1 + self.theta)
exponent = 1 + 2 * f_theta
denominator = (
(size_i + size_j) ** exponent
- size_i ** exponent
- size_j ** exponent
)
return link_count / denominator if denominator > 0 else 0.0
def fit(self, X):
X = self._validate_binary_matrix(X)
n_samples = X.shape[0]
if self.n_clusters > n_samples:
raise ValueError(
"n_clusters نمیتواند از تعداد نمونهها بیشتر باشد."
)
self.X_fit_ = X
# ۱. محاسبه ماتریس شباهت Jaccard
self.similarity_matrix_ = 1 - squareform(
pdist(X, metric="jaccard")
)
np.fill_diagonal(self.similarity_matrix_, 1.0)
# ۲. ساخت ماتریس همسایگی
self.adjacency_matrix_ = (
self.similarity_matrix_ >= self.theta
).astype(np.int8)
# ۳. محاسبه Link Matrix
self.link_matrix_ = (
self.adjacency_matrix_ @ self.adjacency_matrix_
)
np.fill_diagonal(self.link_matrix_, 0)
# ۴. در ابتدا هر نمونه یک خوشه مستقل است
self.clusters_ = {
i: [i] for i in range(n_samples)
}
active_cluster_ids = list(self.clusters_.keys())
self.merge_history_ = []
# ۵. ادغام سلسلهمراتبی خوشهها
while len(active_cluster_ids) > self.n_clusters:
best_goodness = 0.0
best_pair = None
best_link_count = 0
for position, cluster_i in enumerate(active_cluster_ids):
members_i = self.clusters_[cluster_i]
for cluster_j in active_cluster_ids[position + 1:]:
members_j = self.clusters_[cluster_j]
link_count = int(
self.link_matrix_[
np.ix_(members_i, members_j)
].sum()
)
goodness = self._goodness(
link_count,
len(members_i),
len(members_j)
)
if goodness > best_goodness:
best_goodness = goodness
best_pair = (cluster_i, cluster_j)
best_link_count = link_count
# اگر ادغام معناداری باقی نمانده باشد
if best_pair is None:
warnings.warn(
"پیش از رسیدن به تعداد خوشه هدف، "
"دیگر ادغام معناداری باقی نماند.",
RuntimeWarning
)
break
cluster_i, cluster_j = best_pair
self.merge_history_.append({
"clusters": best_pair,
"link_count": best_link_count,
"goodness": best_goodness
})
self.clusters_[cluster_i].extend(
self.clusters_[cluster_j]
)
del self.clusters_[cluster_j]
active_cluster_ids.remove(cluster_j)
# ۶. ساخت برچسب نهایی برای هر نمونه
self.n_clusters_ = len(self.clusters_)
self.labels_ = np.empty(n_samples, dtype=int)
for label, members in enumerate(self.clusters_.values()):
self.labels_[members] = label
return self
def fit_predict(self, X):
return self.fit(X).labels_
ویژگی n_clusters_ تعداد واقعی خوشههای نهایی را نشان میدهد. اگر آستانه θ بیش از حد سختگیرانه باشد، ممکن است الگوریتم پیش از رسیدن به تعداد خوشه هدف متوقف شود. این موضوع خطای برنامه نیست، بلکه نشان میدهد در گراف همسایگی، Link معناداری برای ادغام بیشتر باقی نمانده است.
۴.۱. اجرای کلاس روی مثال آموزشی
rock = ROCKClustering(theta=0.5, n_clusters=2)
labels = rock.fit_predict(X_small)
print("برچسب نهایی هر نمونه:")
print(labels)
print("\nتعداد واقعی خوشهها:")
print(rock.n_clusters_)
for label in range(rock.n_clusters_):
member_indices = np.where(labels == label)[0]
members = [sample_names[i] for i in member_indices]
print(f"خوشه {label + 1}: {members}")
در این مثال، انتظار داریم نمونههای A، B و C در یک خوشه و نمونههای D، E و F در خوشه دیگر قرار بگیرند. خروجی اجرا نیز همین دو گروه را نشان میدهد.
متغیر merge_history_ نیز تاریخچه ادغامها، تعداد Link و مقدار Goodness هر ادغام را نگه میدارد و در بخش تحلیل خروجی از آن استفاده خواهیم کرد.
۵. مطالعه موردی اول: تحلیل توالیهای ژنتیکی
۵.۱. معرفی مطالعه موردی، شرح مسئله و چرایی انتخاب الگوریتم
در زیستشناسی محاسباتی، خوشهبندی توالیهای نوکلئوتیدی کوتاه DNA برای شناسایی خانوادههای ژنی، بررسی شباهت عملکردی و مطالعه روابط تکاملی اهمیت دارد. توالی DNA ذاتاً از نمادهای ردهای A، C، G و T تشکیل شده است؛ بنابراین استفاده مستقیم از روشهای مبتنی بر فاصله اقلیدسی یا میانگینگیری عددی، نمایش طبیعی و قابلتفسیری از این دادهها ارائه نمیکند.
در این مطالعه موردی، توالیها مستقیماً وارد الگوریتم نمیشوند؛ بلکه ابتدا به مجموعهای از ویژگیهای باینری مبتنی بر k-mer تبدیل میشوند. هر ویژگی نشان میدهد یک الگوی کوتاه ژنتیکی مشخص در یک توالی وجود دارد یا خیر. این تبدیل، داده را برای محاسبه شباهت Jaccard و اجرای ROCK مناسب میکند.
چالش اصلی، وجود تغییرات ژنتیکی مانند جانشینی، حذف یا اضافهشدن نوکلئوتیدها است. چنین تغییراتی ممکن است شباهت مستقیم میان دو توالی وابسته را کاهش دهد. ROCK با استفاده از Link و همسایگان مشترک، میتواند بخشی از ساختار ارتباطی غیرمستقیم میان توالیها را نیز در نظر بگیرد.
۵.۲. چرایی انتخاب الگوریتم ROCK
روشهایی مانند K-Means برای نمایش خام و ردهای توالی DNA انتخاب طبیعی نیستند، زیرا بر مفهوم میانگین یا مرکز عددی خوشه تکیه دارند. K-Modes برای دادههای ردهای مناسبتر است، اما تصمیمگیری آن عمدتاً بر شباهت مستقیم نمونهها استوار است.
ROCK علاوه بر شباهت مستقیم Jaccard، ساختار همسایگی را نیز وارد تصمیمگیری میکند. به بیان ساده، اگر دو توالی بهطور مستقیم شباهت متوسطی داشته باشند، اما با چند توالی واسطه مشابه در ارتباط باشند، Link میتواند شواهد بیشتری برای قرارگرفتن آنها در یک خوشه فراهم کند.
بنابراین، ROCK برای دادههای ژنتیکیِ تبدیلشده به ویژگیهای باینری، بهویژه در شرایطی که ساختار ارتباطی میان نمونهها اهمیت دارد، یک گزینه مناسب برای بررسی است.
۵.۳. تشریح دادهها
دادههای این مثال شبیهسازیشدهاند و شامل ۲۰ نمونه ژنی هستند. هر نمونه با ۱۰ ویژگی باینری توصیف میشود که نماینده وجود یا نبود ۱۰ k-mer منتخباند.
در این مثال، ۱۰ نمونه به یک خانواده ژنی اول و ۱۰ نمونه به خانواده ژنی دوم تعلق دارند. برچسب خانوادهها فقط برای ارزیابی نهایی نگه داشته میشود و بهعنوان ورودی به الگوریتم ROCK داده نمیشود.
۵.۴. آمادهسازی داده و ساخت مجموعه ژنی شبیهسازیشده
import numpy as np
import pandas as pd
# بازتولیدپذیری دادههای شبیهسازیشده
np.random.seed(42)
# خانواده اول:
# احتمال حضور k-merهای 1 تا 5 بالا و برای k-merهای 6 تا 10 پایین است
family_1 = np.random.binomial(
1, 0.8, size=(10, 10)
)
family_1[:, 5:] = np.random.binomial(
1, 0.1, size=(10, 5)
)
# خانواده دوم:
# احتمال حضور k-merهای 1 تا 5 پایین و برای k-merهای 6 تا 10 بالا است
family_2 = np.random.binomial(
1, 0.1, size=(10, 10)
)
family_2[:, 5:] = np.random.binomial(
1, 0.8, size=(10, 5)
)
# ساخت داده نهایی برای خوشهبندی
gene_data = np.vstack([family_1, family_2])
# این برچسبها فقط برای ارزیابیاند و به مدل داده نمیشوند
gene_labels_true = np.array(
["خانواده ۱"] * 10 + ["خانواده ۲"] * 10
)
gene_ids = [f"Gene_{i:02d}" for i in range(1, 21)]
feature_names = [f"k-mer_{i}" for i in range(1, 11)]
df_genes = pd.DataFrame(
gene_data,
index=gene_ids,
columns=feature_names
)
print("پنج نمونه اول از دادههای باینری ژنتیکی:")
print(df_genes.head())
خروجی:
مقدار ۱ به معنای وجود یک k-mer منتخب و مقدار ۰ به معنای نبود آن است. خانواده اول عمدتاً در ویژگیهای k-mer_1 تا k-mer_5 فعالتر است، در حالی که خانواده دوم الگوی فعالتری در k-mer_6 تا k-mer_10 دارد. مقدارهای احتمالی ۰٫۸ و ۰٫۱ نیز نویز کنترلشدهای ایجاد میکنند تا داده کاملاً بدون چالش نباشد.
۵.۵. پیادهسازی ROCK در پایتون
import warnings
from scipy.spatial.distance import pdist, squareform
class ROCKClustering:
def __init__(self, theta=0.5, n_clusters=2):
if not 0 < theta < 1:
raise ValueError(
"theta باید بزرگتر از ۰ و کوچکتر از ۱ باشد."
)
if not isinstance(n_clusters, int) or n_clusters < 1:
raise ValueError(
"n_clusters باید یک عدد صحیح مثبت باشد."
)
self.theta = theta
self.n_clusters = n_clusters
@staticmethod
def _validate_binary_matrix(X):
X = np.asarray(X)
if X.ndim != 2 or X.shape[0] < 2:
raise ValueError(
"X باید یک ماتریس دوبعدی با دستکم دو نمونه باشد."
)
if not np.isin(X, [0, 1]).all():
raise ValueError(
"مقادیر X باید فقط صفر و یک باشند."
)
return X.astype(np.int8)
def _goodness(self, link_count, size_i, size_j):
if link_count <= 0:
return 0.0
f_theta = (1 - self.theta) / (1 + self.theta)
exponent = 1 + 2 * f_theta
denominator = (
(size_i + size_j) ** exponent
- size_i ** exponent
- size_j ** exponent
)
return link_count / denominator if denominator > 0 else 0.0
def fit(self, X):
X = self._validate_binary_matrix(X)
n_samples = X.shape[0]
if self.n_clusters > n_samples:
raise ValueError(
"n_clusters نمیتواند از تعداد نمونهها بیشتر باشد."
)
self.X_fit_ = X
# محاسبه شباهت Jaccard
self.similarity_matrix_ = 1 - squareform(
pdist(X, metric="jaccard")
)
np.fill_diagonal(self.similarity_matrix_, 1.0)
# ساخت ماتریس همسایگی
self.adjacency_matrix_ = (
self.similarity_matrix_ >= self.theta
).astype(np.int8)
# محاسبه Link Matrix
self.link_matrix_ = (
self.adjacency_matrix_ @ self.adjacency_matrix_
)
np.fill_diagonal(self.link_matrix_, 0)
# در ابتدا، هر نمونه یک خوشه است
self.clusters_ = {
i: [i] for i in range(n_samples)
}
active_cluster_ids = list(self.clusters_.keys())
self.merge_history_ = []
# ادغام سلسلهمراتبی خوشهها
while len(active_cluster_ids) > self.n_clusters:
best_goodness = 0.0
best_pair = None
best_link_count = 0
for position, cluster_i in enumerate(active_cluster_ids):
members_i = self.clusters_[cluster_i]
for cluster_j in active_cluster_ids[position + 1:]:
members_j = self.clusters_[cluster_j]
link_count = int(
self.link_matrix_[
np.ix_(members_i, members_j)
].sum()
)
goodness = self._goodness(
link_count,
len(members_i),
len(members_j)
)
if goodness > best_goodness:
best_goodness = goodness
best_pair = (cluster_i, cluster_j)
best_link_count = link_count
if best_pair is None:
warnings.warn(
"پیش از رسیدن به تعداد خوشه هدف، "
"دیگر ادغام معناداری باقی نماند.",
RuntimeWarning
)
break
cluster_i, cluster_j = best_pair
self.merge_history_.append({
"clusters": best_pair,
"link_count": best_link_count,
"goodness": best_goodness
})
self.clusters_[cluster_i].extend(
self.clusters_[cluster_j]
)
del self.clusters_[cluster_j]
active_cluster_ids.remove(cluster_j)
self.n_clusters_ = len(self.clusters_)
self.labels_ = np.empty(n_samples, dtype=int)
for label, members in enumerate(self.clusters_.values()):
self.labels_[members] = label
return self
def fit_predict(self, X):
return self.fit(X).labels_
این نسخه برای دادههای کوچک و متوسط آموزشی مناسب است. در دادههای بسیار بزرگ، ساخت ماتریسهای جفتی Jaccard و Link هزینه محاسباتی و حافظهای بالایی خواهد داشت.
۵.۶. اجرای الگوریتم و ارزیابی خوشههای ژنی
نکته مهم: در داده فعلی، مقدار theta=0.45 مناسب نیست و الگوریتم را به سه خوشه میرساند. برای همین داده شبیهسازیشده، مقدار 0.15 بهدرستی دو خانواده ژنی را بازیابی میکند.
from sklearn.metrics import adjusted_rand_score
rock_gene = ROCKClustering(
theta=0.15,
n_clusters=2
)
gene_labels_pred = rock_gene.fit_predict(gene_data)
gene_results = pd.DataFrame({
"شناسه ژن": gene_ids,
"خانواده واقعی": gene_labels_true,
"خوشه پیشبینیشده": gene_labels_pred
})
print(gene_results)
print("\nتعداد واقعی خوشههای نهایی:")
print(rock_gene.n_clusters_)
ari_score = adjusted_rand_score(
gene_labels_true,
gene_labels_pred
)
print("\nAdjusted Rand Index:")
print(round(ari_score, 2))
خروجی:
حالا این کد را برای سنجش انسجام و جدایی خوشهها میگذاریم:
def mean_off_diagonal(matrix):
n = matrix.shape[0]
if n < 2:
return np.nan
mask = ~np.eye(n, dtype=bool)
return matrix[mask].mean()
gene_cluster_metrics = []
for cluster_id in sorted(np.unique(gene_labels_pred)):
member_indices = np.where(
gene_labels_pred == cluster_id
)[0]
similarity_submatrix = rock_gene.similarity_matrix_[
np.ix_(member_indices, member_indices)
]
gene_cluster_metrics.append({
"خوشه": cluster_id,
"تعداد ژن": len(member_indices),
"میانگین شباهت Jaccard درونخوشهای":
round(
mean_off_diagonal(similarity_submatrix),
2
)
})
gene_cluster_metrics_df = pd.DataFrame(
gene_cluster_metrics
)
print("\nمعیارهای درونخوشهای:")
print(gene_cluster_metrics_df)
cluster_0_indices = np.where(
gene_labels_pred == 0
)[0]
cluster_1_indices = np.where(
gene_labels_pred == 1
)[0]
between_cluster_similarity = rock_gene.similarity_matrix_[
np.ix_(cluster_0_indices, cluster_1_indices)
].mean()
print(
"\nمیانگین شباهت Jaccard بین دو خوشه:",
round(between_cluster_similarity, 2)
)
خروجی:
تفسیر نتیجه:
در این اجرا، الگوریتم ROCK دو خوشه ۱۰ عضوی ایجاد میکند که با دو خانواده ژنیِ تعریفشده در داده شبیهسازیشده منطبقاند. مقدار ARI برابر با ۱ است؛ یعنی خروجی خوشهبندی در این مثال دقیقاً با برچسبهای مرجع مصنوعی همراستا است.
میانگین شباهت Jaccard درون دو خوشه بهترتیب حدود ۰٫۵۱ و ۰٫۵۳ است، در حالی که میانگین شباهت بینخوشهای حدود ۰٫۱۲ است. این فاصله نشان میدهد توالیهای متعلق به یک خانواده، الگوی حضور k-mer مشابهتری نسبت به توالیهای خانواده دیگر دارند.
باید توجه داشت که ARI فقط به دلیل وجود برچسب مرجع در داده مصنوعی قابل محاسبه است. در دادههای واقعی و بدون برچسب، ارزیابی باید بر پایه انسجام درونخوشهای، جدایی بینخوشهای و تفسیر زیستی خوشهها انجام شود.
۵.۷. عیبیابی و نکات عملی در دادههای ژنتیکی
۱. قطعهقطعهشدن خوشهها در آستانههای بالا: اگر θ بیش از حد بزرگ انتخاب شود، فقط توالیهای بسیار مشابه همسایه محسوب میشوند. در نتیجه، گراف همسایگی تنک میشود و تعدادی خوشه تکعضوی یا کوچک شکل میگیرد. در این مثال، θ برابر با ۰٫۴۵ به سه خوشه منتهی میشود، در حالی که هدف دو خوشه است.
راهکار: چند مقدار θ را امتحان کن و علاوه بر تعداد خوشههای نهایی، معیارهایی مانند ARI، میانگین شباهت درونخوشهای و اندازه خوشهها را مقایسه کن.
۲. ادغام نادرست خوشهها در آستانههای پایین: اگر θ خیلی کوچک باشد، ارتباطهای ضعیف نیز بهعنوان همسایگی در نظر گرفته میشوند. این مسئله میتواند میان دو خانواده ژنی مستقل، پلهای کاذب ایجاد کند و خوشهها را بهاشتباه ادغام کند.
راهکار: توزیع شباهتهای Jaccard را بررسی کن و مقدار θ را در ناحیهای انتخاب کن که میان شباهتهای درونخانوادهای و بینخانوادهای تمایز ایجاد شود.
۳. ورود مستقیم توالی DNA به مدل: کلاس حاضر توالیهای متنی مانند ATCG… را نمیپذیرد و ورودی آن باید ماتریس باینری باشد.
راهکار: ابتدا توالیها را با استفاده از k-mer، one-hot encoding یا ویژگیهای حضور/نبود موتیفهای ژنتیکی به نمایش باینری تبدیل کن.
۴. ویژگیهای ژنتیکی کماطلاعات: k-merهایی که تقریباً در همه توالیها وجود دارند یا تقریباً در هیچ توالی دیده نمیشوند، قدرت تفکیک خوشهها را کاهش میدهند.
راهکار: پیش از خوشهبندی، فراوانی ویژگیها را بررسی کن و ویژگیهای کاملاً ثابت یا کماطلاعات را حذف کن.
۶. مطالعه موردی دوم: سیستم توصیهگر سبد خرید
۶.۱. هدف و شرح مسئله
هدف، خوشهبندی مشتریان بر اساس اقلام خریداریشده است تا فروشگاه بتواند برای هر گروه، تخفیف هدفمند و پیشنهاد خرید مناسب ارائه کند.
دادههای سبد خرید بهصورت یک ماتریس باینری نمایش داده میشوند؛ هر سطر یک مشتری، هر ستون یک محصول و مقدار یک نشاندهنده خرید محصول است. این دادهها معمولاً تنک هستند. الگوریتم ROCK با استفاده از شباهت جاکارد و تعداد همسایگان مشترک، مشتریانی را که الگوهای خرید مشابه دارند در یک خوشه قرار میدهد. متن زیر با ساختار و پیادهسازی آموزشی فایل هماهنگ شده است.
۶.۲. کد کامل پیادهسازی
import warnings
import numpy as np
from scipy.spatial.distance import pdist, squareform, cdist
class ROCKClustering:
def __init__(self, theta=0.3, n_clusters=3):
if not 0 < theta < 1:
raise ValueError("theta باید بین صفر و یک باشد.")
if not isinstance(n_clusters, int) or n_clusters < 1:
raise ValueError("n_clusters باید عدد صحیح مثبت باشد.")
self.theta = theta
self.n_clusters = n_clusters
@staticmethod
def _validate_data(X):
X = np.asarray(X)
if X.ndim != 2:
raise ValueError("ورودی باید یک ماتریس دوبعدی باشد.")
if not np.isin(X, [0, 1]).all():
raise ValueError("مقادیر ورودی باید فقط صفر و یک باشند.")
return X.astype(np.int8)
def _goodness(self, link_count, size_i, size_j):
if link_count <= 0:
return 0.0
f_theta = (1 - self.theta) / (1 + self.theta)
exponent = 1 + 2 * f_theta
denominator = (
(size_i + size_j) ** exponent
- size_i ** exponent
- size_j ** exponent
)
return link_count / (denominator + 1e-9)
def fit(self, X):
X = self._validate_data(X)
n_samples = X.shape[0]
if self.n_clusters > n_samples:
raise ValueError(
"تعداد خوشهها نمیتواند از تعداد مشتریان بیشتر باشد."
)
self.X_fit_ = X
# محاسبه شباهت جاکارد
self.similarity_matrix_ = 1 - squareform(
pdist(X, metric="jaccard")
)
self.similarity_matrix_ = np.nan_to_num(
self.similarity_matrix_,
nan=0.0
)
np.fill_diagonal(self.similarity_matrix_, 1.0)
# تشکیل گراف همسایگی
self.adjacency_matrix_ = (
self.similarity_matrix_ >= self.theta
).astype(np.int8)
# هر مشتری همسایه خودش محسوب نمیشود
np.fill_diagonal(self.adjacency_matrix_, 0)
# محاسبه تعداد همسایگان مشترک
self.link_matrix_ = (
self.adjacency_matrix_
@ self.adjacency_matrix_
)
np.fill_diagonal(self.link_matrix_, 0)
# ابتدا هر مشتری یک خوشه جداگانه است
self.clusters_ = {
i: [i] for i in range(n_samples)
}
active_clusters = list(self.clusters_.keys())
# ادغام خوشهها
while len(active_clusters) > self.n_clusters:
best_pair = None
best_goodness = 0.0
for position, cluster_i in enumerate(active_clusters):
members_i = self.clusters_[cluster_i]
for cluster_j in active_clusters[position + 1:]:
members_j = self.clusters_[cluster_j]
link_count = int(
self.link_matrix_[
np.ix_(members_i, members_j)
].sum()
)
goodness = self._goodness(
link_count,
len(members_i),
len(members_j)
)
if goodness > best_goodness:
best_goodness = goodness
best_pair = (cluster_i, cluster_j)
if best_pair is None:
warnings.warn(
"ادغام معناداری برای رسیدن به تعداد خوشه هدف باقی نماند.",
RuntimeWarning
)
break
cluster_i, cluster_j = best_pair
self.clusters_[cluster_i].extend(
self.clusters_[cluster_j]
)
del self.clusters_[cluster_j]
active_clusters.remove(cluster_j)
# تولید برچسب نهایی
self.labels_ = np.empty(n_samples, dtype=int)
for label, members in enumerate(
self.clusters_.values()
):
self.labels_[members] = label
self.n_clusters_ = len(self.clusters_)
return self
def fit_predict(self, X):
return self.fit(X).labels_
def predict(self, X_new):
X_new = self._validate_data(X_new)
if X_new.shape[1] != self.X_fit_.shape[1]:
raise ValueError(
"تعداد محصولات مشتری جدید با داده آموزشی برابر نیست."
)
similarities = 1 - cdist(
X_new,
self.X_fit_,
metric="jaccard"
)
similarities = np.nan_to_num(
similarities,
nan=0.0
)
predictions = []
for row in similarities:
cluster_scores = {}
for cluster_id in np.unique(self.labels_):
members = np.where(
self.labels_ == cluster_id
)[0]
cluster_scores[cluster_id] = row[members].mean()
predictions.append(
max(cluster_scores, key=cluster_scores.get)
)
return np.array(predictions)
# --------------------------------------------------
# شبیهسازی دادههای ۳۰ مشتری و ۱۵ محصول
# --------------------------------------------------
np.random.seed(24)
customer_data = np.zeros((30, 15), dtype=np.int8)
# مشتریان علاقهمند به الکترونیک
customer_data[:10, :5] = np.random.binomial(
1, 0.8, size=(10, 5)
)
customer_data[:10, 5:] = np.random.binomial(
1, 0.05, size=(10, 10)
)
# مشتریان علاقهمند به مواد غذایی
customer_data[10:20, 5:10] = np.random.binomial(
1, 0.8, size=(10, 5)
)
customer_data[10:20, np.r_[0:5, 10:15]] = np.random.binomial(
1, 0.05, size=(10, 10)
)
# مشتریان علاقهمند به پوشاک
customer_data[20:30, 10:15] = np.random.binomial(
1, 0.8, size=(10, 5)
)
customer_data[20:30, :10] = np.random.binomial(
1, 0.05, size=(10, 10)
)
# اجرای مدل
rock_market = ROCKClustering(
theta=0.3,
n_clusters=3
)
labels = rock_market.fit_predict(customer_data)
print("ابعاد داده:", customer_data.shape)
print("برچسب خوشه مشتریان:", labels)
print("اندازه خوشهها:", np.bincount(labels))
# پیشبینی مشتری جدید با گرایش الکترونیکی
new_customer = np.array([[
1, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0
]])
predicted_cluster = rock_market.predict(new_customer)[0]
print("خوشه مشتری جدید:", predicted_cluster)
# پیشنهاد سه محصول محبوب خوشه
product_names = [
"الکترونیک ۱", "الکترونیک ۲", "الکترونیک ۳",
"الکترونیک ۴", "الکترونیک ۵",
"مواد غذایی ۱", "مواد غذایی ۲", "مواد غذایی ۳",
"مواد غذایی ۴", "مواد غذایی ۵",
"پوشاک ۱", "پوشاک ۲", "پوشاک ۳",
"پوشاک ۴", "پوشاک ۵"
]
cluster_members = np.where(
labels == predicted_cluster
)[0]
product_popularity = customer_data[
cluster_members
].mean(axis=0)
recommended_indices = [
index
for index in np.argsort(product_popularity)[::-1]
if new_customer[0, index] == 0
][:3]
recommendations = [
product_names[index]
for index in recommended_indices
]
print("محصولات پیشنهادی:", recommendations)
خروجی:
۶.۳. عیبیابی و رفع مشکلات
- خطای ناسازگاری ابعاد: در گروه پوشاک فقط ۱۰ مشتری وجود دارد؛ بنابراین باید از size=(10, 5) استفاده شود، نه size=(20, 5).
- تشکیل خوشههای تکعضوی: مقدار theta بیش از حد بالا است. مقدارهایی مانند 0.2، 0.25 و 0.3 را آزمایش کنید.
- ادغام مشتریان نامرتبط: مقدار theta بیش از حد پایین است و ارتباطهای ضعیف را نیز وارد گراف میکند. آستانه را کمی افزایش دهید.
- اثر محصولات بسیار پرطرفدار: محصولاتی که تقریباً همه مشتریان خریدهاند باعث ایجاد ارتباطهای کاذب میشوند. این محصولات را پیش از خوشهبندی حذف کنید.
- وجود سبد خرید خالی: مشتریانی که هیچ خریدی ندارند، شباهت جاکارد معناداری تولید نمیکنند. آنها را حذف یا با روش جداگانهای مدیریت کنید.
- توقف مدل پیش از رسیدن به سه خوشه: گراف همسایگی بیش از حد تنک است. مقدار theta را کاهش دهید، محصولات بسیار نادر را حذف کنید یا بازه زمانی خرید مشتریان را افزایش دهید.
جمعبندی
در این فایل، الگوریتم ROCK از مفاهیم نظری تا پیادهسازی عملی در پایتون بررسی شد. برخلاف روشهای سنتی که تنها بر فاصله یا شباهت مستقیم تکیه دارند، ROCK با استفاده از شباهت جاکارد، گراف همسایگی و تعداد همسایگان مشترک یا Link، ساختار ارتباطی میان نمونهها را نیز در فرایند خوشهبندی در نظر میگیرد. این ویژگی، الگوریتم را برای دادههای باینری، طبقهای و تنک مناسب میسازد.
در بخش عملی، مراحل آمادهسازی داده، ساخت ماتریس شباهت و مجاورت، محاسبه ماتریس Link و ادغام سلسلهمراتبی خوشهها پیادهسازی شد. سپس عملکرد الگوریتم در دو مطالعه موردی تحلیل توالیهای ژنتیکی و سیستم توصیهگر سبد خرید بررسی شد. نتایج نشان دادند که ROCK میتواند الگوهایی را شناسایی کند که شباهت مستقیم آنها پایین است، اما از طریق همسایگان مشترک به یک ساختار یا رفتار کلی مشابه تعلق دارند.
بااینحال، کیفیت خروجی به انتخاب آستانه theta، نحوه باینریسازی دادهها و حذف ویژگیهای کماطلاعات یا بسیار پرتکرار وابسته است. آستانه بزرگ موجب تشکیل خوشههای کوچک و پراکنده میشود و آستانه بسیار پایین میتواند نمونههای نامرتبط را به یکدیگر متصل کند. همچنین، به دلیل تشکیل ماتریسهای زوجی، پیادهسازی آموزشی ROCK برای دادههای کوچک و متوسط مناسبتر است و برای دادههای بزرگ به روشهای بهینهسازی و ساختارهای تنک نیاز دارد.
در مجموع، ROCK روشی قابلتفسیر و مناسب برای خوشهبندی دادههای طبقهای است، بهویژه زمانی که روابط غیرمستقیم میان نمونهها اهمیت داشته باشد. موفقیت عملی آن نیز به آمادهسازی صحیح داده، تنظیم مناسب پارامترها و ارزیابی نتایج بر اساس معیارهای آماری و دانش حوزه کاربرد بستگی دارد.
