پیاده‌سازی الگوریتم COBWEB در پایتون با مطالعات موردی

۱. مقدمه

ر بخش نخست، مبانی نظری الگوریتم COBWEB، خوشه‌بندی مفهومی، یادگیری افزایشی و معیار Category Utility بررسی شد. در این بخش، همان مباحث به یک فرایند عملی تبدیل می‌شوند. تمام کدهای ارائه‌شده اجرا شده‌اند و خروجی‌های عددی، جدول‌ها و نمودارهای درج‌شده در فایل از اجرای واقعی همین کدها به دست آمده‌اند.

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

نکته روش‌شناختی: پیاده‌سازی حاضر یک نسخه آموزشی از منطق COBWEB برای تشکیل مفاهیم سطح اول است. تصمیم میان افزودن نمونه به مفهوم موجود و ایجاد مفهوم جدید با Category Utility انجام می‌شود. هدف، اجرای شفاف و قابل بازتولید مطالعات موردی است؛ نه بازسازی کامل تمام جزئیات نسخه کلاسیک شامل همه حالت‌های Merge و Split.

2. محیط اجرا و آماده‌سازی داده‌ها

۲.۱. کتابخانه های موردنیاز

کتابخانه	کاربرد
NumPy	محاسبات عددی و مدیریت برچسب‌ها
Pandas	ساخت جدول داده‌ها و نتایج
Matplotlib	رسم نمودار اندازه مفاهیم
Scikit-learn	محاسبه ARI و NMI
collections و copy	شمارش مقادیر و شبیه‌سازی تصمیم‌ها

from collections import Counter, defaultdict
from copy import deepcopy
import random
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score

۲.۲. قالب داده ورودی

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

sample = {
    "color": "red",
    "shape": "circle",
    "size": "small"
}

ویژگی‌های عددی، پیش از اجرا، باید به بازه‌های طبقه‌ای تبدیل شوند. برای نمونه، سن می‌تواند به گروه‌های کمتر از ۱۸، ۱۸ تا ۲۹، ۳۰ تا ۴۹ و ۵۰ سال یا بیشتر تبدیل شود.

۳. پیاده‌سازی الگوریتم COBWEB در پایتون

کد زیر نسخه اجرایی استفاده‌شده در تمام مطالعات موردی این فایل است. این کد آمار مقادیر ویژگی‌ها را نگهداری می‌کند، Category Utility را محاسبه می‌کند، داده‌ها را به‌صورت افزایشی می‌پذیرد و برای هر نمونه یک مفهوم سطح اول تعیین می‌کند.

from collections import Counter, defaultdict
from copy import deepcopy
from pathlib import Path
import random
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score

OUT=Path('/mnt/data/cobweb_assets'); OUT.mkdir(exist_ok=True)

class Concept:
    def __init__(self):
        self.n=0
        self.counts=defaultdict(Counter)
    def add(self,x):
        self.n+=1
        for a,v in x.items(): self.counts[a][v]+=1
    def p(self,a,v):
        return self.counts[a][v]/self.n if self.n else 0.0
    def sqsum(self, all_values):
        s=0.0
        for a,vals in all_values.items():
            for v in vals:
                p=self.p(a,v); s+=p*p
        return s

class EducationalCOBWEB:
    """آموزشی: مفاهیم سطح اول را با معیار Category Utility می‌سازد."""
    def __init__(self):
        self.root=Concept(); self.concepts=[]; self.all_values=defaultdict(set)
    def _refresh_values(self,x):
        for a,v in x.items(): self.all_values[a].add(v)
    def category_utility(self, concepts=None, root=None):
        concepts=self.concepts if concepts is None else concepts
        root=self.root if root is None else root
        k=len(concepts)
        if root.n==0 or k==0: return 0.0
        base=root.sqsum(self.all_values)
        total=0.0
        for c in concepts:
            total += (c.n/root.n)*(c.sqsum(self.all_values)-base)
        return total/k
    def _simulate_add(self, idx, x):
        root=deepcopy(self.root); root.add(x)
        concepts=deepcopy(self.concepts); concepts[idx].add(x)
        return self.category_utility(concepts,root)
    def _simulate_new(self,x):
        root=deepcopy(self.root); root.add(x)
        concepts=deepcopy(self.concepts); c=Concept(); c.add(x); concepts.append(c)
        return self.category_utility(concepts,root)
    def insert(self,x):
        self._refresh_values(x)
        if not self.concepts:
            self.root.add(x); c=Concept(); c.add(x); self.concepts.append(c); return 0
        scores=[self._simulate_add(i,x) for i in range(len(self.concepts))]
        new_score=self._simulate_new(x)
        # deterministic: new concept only if strictly better
        if new_score > max(scores)+1e-12:
            self.root.add(x); c=Concept(); c.add(x); self.concepts.append(c); return len(self.concepts)-1
        idx=int(np.argmax(scores)); self.root.add(x); self.concepts[idx].add(x); return idx
    def fit(self,data):
        for x in data: self.insert(x)
        return self
    def score_sample(self,c,x):
        return sum(c.p(a,v) for a,v in x.items())/max(len(x),1)
    def predict(self,data):
        return np.array([int(np.argmax([self.score_sample(c,x) for c in self.concepts])) for x in data])
    def summaries(self):
        rows=[]
        for i,c in enumerate(self.concepts):
            row={'concept':i,'samples':c.n}
            for a,ctr in c.counts.items():
                v,n=ctr.most_common(1)[0]; row[a]=v; row[a+'_p']=round(n/c.n,3)
            rows.append(row)
        return pd.DataFrame(rows)

۴. مثال آموزشی کوچک

۴.۱. تعریف داده

شش شیء با سه ویژگی رنگ، شکل و اندازه به الگوریتم داده شدند. دو الگوی واضح «قرمز، دایره، کوچک» و «آبی، مربع، بزرگ» وجود دارند و دو نمونه دیگر حالت مرزی دارند.

toy_data = [
    {"color":"red", "shape":"circle", "size":"small"},
    {"color":"red", "shape":"circle", "size":"small"},
    {"color":"blue", "shape":"square", "size":"large"},
    {"color":"blue", "shape":"square", "size":"large"},
    {"color":"red", "shape":"square", "size":"medium"},
    {"color":"blue", "shape":"circle", "size":"medium"}
]
model = EducationalCOBWEB().fit(toy_data)
labels = model.predict(toy_data)
print(labels)
print(model.category_utility())

۴.۲. خروجی واقعی اجرا

Number of concepts: 2
Category Utility: 0.4167

color	shape	size	concept
red	circle	small	0
red	circle	small	0
blue	square	large	1
blue	square	large	1
red	square	medium	0
blue	circle	medium	0

خروجی نشان داد که داده‌ها در دو مفهوم اصلی سازمان‌دهی شدند. مقدار Category Utility برابر با ۰٫۴۱۶۷ است. دو نمونه تکراری هر الگوی اصلی در یک گروه قرار گرفتند و نمونه‌های مرزی بر اساس ترکیب ویژگی‌ها به نزدیک‌ترین مفهوم تخصیص یافتند.

.

۵. مطالعه موردی اول: خوشه‌بندی قارچ‌ها با COBWEB

۵.۱. معرفی مسئله

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

۵.۲. کد اجرا

df = pd.DataFrame(mushroom_records)
X = df.drop(columns=["id", "class"]).to_dict("records")
model = EducationalCOBWEB().fit(X)
labels = model.predict(X)
ari = adjusted_rand_score(pd.Categorical(df["class"]).codes, labels)
nmi = normalized_mutual_info_score(pd.Categorical(df["class"]).codes, labels)

۵.۳. خروجی واقعی اجرا

Number of concepts: 4
Category Utility: 0.7222
Adjusted Rand Index: 0.653
Normalized Mutual Information: 0.733
Purity: 1.000

id	cap_shape	cap_color	cap_surface	odor	stem_shape	habitat	bruises	class	concept
M01	convex	brown	smooth	almond	thick	forest	yes	edible	0
M02	convex	white	smooth	almond	thick	grassland	yes	edible	1
M03	flat	brown	smooth	none	thick	forest	yes	edible	2
M04	bell	red	scaly	pungent	thin	moist	no	poisonous	3
M05	convex	red	scaly	foul	thin	forest	no	poisonous	3
M06	bell	white	scaly	pungent	thin	moist	no	poisonous	3
M07	flat	white	smooth	none	thick	grassland	yes	edible	1
M08	convex	brown	scaly	foul	thin	moist	no	poisonous	3
M09	flat	brown	smooth	almond	thick	forest	yes	edible	0
M10	bell	red	scaly	foul	thin	moist	no	poisonous	3
M11	convex	white	smooth	none	thick	grassland	yes	edible	1
M12	flat	red	scaly	pungent	thin	forest	no	poisonous	3

۵.۴. خلاصه مفاهیم

concept	samples	cap_shape	cap_shape_p	cap_color	cap_color_p	cap_surface	cap_surface_p	odor	odor_p	stem_shape	stem_shape_p	habitat	habitat_p	bruises	bruises_p
0	2	convex	0.5	brown	1.0	smooth	1.0	almond	1.0	thick	1.0	forest	1.0	yes	1.0
1	3	convex	0.667	white	1.0	smooth	1.0	none	0.667	thick	1.0	grassland	1.0	yes	1.0
2	1	flat	1.0	brown	1.0	smooth	1.0	none	1.0	thick	1.0	forest	1.0	yes	1.0
3	6	bell	0.5	red	0.667	scaly	1.0	pungent	0.5	thin	1.0	moist	0.667	no	1.0

۵.۵. تحلیل نتایج

الگوریتم چهار مفهوم تشکیل داد. مقدار خلوص برابر ۱٫۰۰ بود؛ یعنی در هر مفهوم، برچسب غالب کاملاً یکدست بود. ARI برابر ۰٫۶۵۳ و NMI برابر ۰٫۷۳۳ نشان می‌دهند که ساختار مفهومی با تقسیم خوراکی/سمی ارتباط قابل توجهی دارد، هرچند چهار مفهوم به جای دو برچسب واقعی تشکیل شده است. این نتیجه طبیعی است، زیرا COBWEB می‌تواند زیرگروه‌های توصیفی بیشتری از برچسب نهایی کشف کند.

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

.

۶. مطالعه موردی دوم: شناسایی الگوهای یادگیری دانش‌آموزان

۶.۱. معرفی مسئله

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

۶.۲. کد اجرا

df = pd.DataFrame(student_records)
X = df.drop(columns=["id", "performance"]).to_dict("records")
model = EducationalCOBWEB().fit(X)
labels = model.predict(X)
ari = adjusted_rand_score(pd.Categorical(df["performance"]).codes, labels)
nmi = normalized_mutual_info_score(pd.Categorical(df["performance"]).codes, labels)

۶.۳. خروجی واقعی اجرا

Number of concepts: 4
Category Utility: 0.6222
Adjusted Rand Index: 0.674
Normalized Mutual Information: 0.778
Purity: 0.933

id	participation	homework	study_time	resource	help_seeking	attendance	performance	concept
S01	high	regular	high	interactive	medium	regular	strong	0
S02	high	regular	high	video	low	regular	strong	1
S03	medium	mostly_regular	medium	book	medium	regular	average	2
S04	low	irregular	low	video	low	poor	needs_support	3
S05	low	irregular	low	book	high	medium	needs_support	3
S06	medium	mostly_regular	medium	interactive	high	regular	average	2
S07	high	regular	high	book	low	regular	strong	1
S08	medium	mostly_regular	medium	video	medium	medium	average	2
S09	low	irregular	low	interactive	high	poor	needs_support	3
S10	high	mostly_regular	medium	interactive	medium	regular	strong	0
S11	medium	regular	medium	book	low	regular	average	1
S12	low	irregular	low	video	medium	poor	needs_support	3
S13	high	regular	high	interactive	low	regular	strong	1
S14	medium	mostly_regular	medium	video	high	medium	average	2
S15	low	irregular	low	book	high	poor	needs_support	3

۶.۴. خلاصه مفاهیم

concept	samples	participation	participation_p	homework	homework_p	study_time	study_time_p	resource	resource_p	help_seeking	help_seeking_p	attendance	attendance_p
0	2	high	1.0	regular	0.5	high	0.5	interactive	1.0	medium	1.0	regular	1.0
1	4	high	0.75	regular	1.0	high	0.75	book	0.5	low	1.0	regular	1.0
2	4	medium	1.0	mostly_regular	1.0	medium	1.0	video	0.5	medium	0.5	regular	0.5
3	5	low	1.0	irregular	1.0	low	1.0	video	0.4	high	0.6	poor	0.8

۶.۵. تحلیل نتایج

چهار مفهوم تشکیل شد. خلوص ۰٫۹۳۳، ARI برابر ۰٫۶۷۴ و NMI برابر ۰٫۷۷۸ نشان می‌دهند که الگوهای رفتاری شناسایی‌شده با سطح عملکرد ارتباط زیادی دارند. یکی از مفاهیم عمدتاً شامل دانش‌آموزان با مشارکت زیاد، تکالیف منظم، مطالعه زیاد و حضور منظم بود. مفهوم دیگری بیشتر دانش‌آموزان با مشارکت کم، تکالیف نامنظم، مطالعه کم و حضور ضعیف را در بر گرفت.

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

.

۷. مطالعه موردی سوم: گروه‌بندی درخواست‌های پشتیبانی نرم‌افزار

۷.۱. معرفی مسئله

در این مطالعه، درخواست‌های پشتیبانی بر اساس بخش نرم‌افزار، شدت، تکرارپذیری، دستگاه، مرحله وقوع، پیام خطا و نوع کاربر خوشه‌بندی شدند. متغیر «موضوع واقعی درخواست» در تشکیل مفاهیم وارد نشد و فقط برای ارزیابی خروجی نگهداری شد.

۷.۲. کد اجرا

df = pd.DataFrame(support_records)
X = df.drop(columns=["id", "topic"]).to_dict("records")
model = EducationalCOBWEB().fit(X)
labels = model.predict(X)
ari = adjusted_rand_score(pd.Categorical(df["topic"]).codes, labels)
nmi = normalized_mutual_info_score(pd.Categorical(df["topic"]).codes, labels)

۷.۳. خروجی واقعی اجرا

Number of concepts: 5
Category Utility: 0.5164
Adjusted Rand Index: 0.326
Normalized Mutual Information: 0.745
Purity: 0.667

id	module	severity	reproducibility	device	stage	error_message	user_type	topic	concept
T01	login	high	always	mobile	authentication	yes	regular	login_failure	1
T02	login	high	always	desktop	authentication	yes	regular	login_failure	1
T03	login	medium	sometimes	mobile	recovery	no	new	password_reset	2
T04	payment	critical	always	mobile	confirmation	yes	regular	payment_failure	0
T05	payment	critical	always	desktop	confirmation	yes	business	payment_failure	3
T06	payment	medium	sometimes	mobile	processing	no	regular	payment_delay	2
T07	report	medium	always	desktop	export	yes	business	report_export	3
T08	report	medium	always	desktop	export	yes	regular	report_export	3
T09	report	low	sometimes	desktop	generation	no	business	slow_report	4
T10	profile	low	sometimes	mobile	save	no	new	profile_update	2
T11	profile	low	one_time	tablet	save	no	regular	profile_update	4
T12	login	high	always	mobile	authentication	yes	business	account_lock	1
T13	payment	critical	always	tablet	confirmation	yes	business	payment_failure	0
T14	report	low	sometimes	desktop	generation	no	regular	slow_report	4
T15	profile	low	sometimes	mobile	save	no	regular	profile_update	2

۷.۴. خلاصه مفاهیم

concept	samples	module	module_p	severity	severity_p	reproducibility	reproducibility_p	device	device_p	stage	stage_p	error_message	error_message_p	user_type	user_type_p
0	3	payment	0.667	critical	0.667	always	1.0	mobile	0.667	confirmation	0.667	yes	1.0	regular	0.667
1	2	login	1.0	high	1.0	always	1.0	desktop	0.5	authentication	1.0	yes	1.0	regular	0.5
2	4	profile	0.5	medium	0.5	sometimes	1.0	mobile	1.0	save	0.5	no	1.0	new	0.5
3	3	report	0.667	medium	0.667	always	1.0	desktop	1.0	export	0.667	yes	1.0	business	0.667
4	3	report	0.667	low	1.0	sometimes	0.667	desktop	0.667	generation	0.667	no	1.0	regular	0.667

۷.۵. تحلیل نتایج

پنج مفهوم تشکیل شد. NMI برابر ۰٫۷۴۵ نشان می‌دهد که مفاهیم مقدار زیادی اطلاعات درباره موضوع واقعی درخواست‌ها دارند؛ اما ARI برابر ۰٫۳۲۶ و خلوص ۰٫۶۶۷ بیان می‌کنند که تطابق یک‌به‌یک با موضوع‌ها متوسط است. دلیل اصلی آن است که برخی موضوع‌ها از نظر ویژگی‌های عملیاتی مشابه‌اند؛ برای مثال خطای ورود و قفل حساب هر دو در بخش ورود، مرحله احراز هویت و با شدت زیاد رخ می‌دهند.

مزیت این خروجی، توصیف‌پذیری مفاهیم است. یک مفهوم می‌تواند با ویژگی‌هایی مانند «پرداخت، شدت بحرانی، وقوع در مرحله تأیید و وجود پیام خطا» مشخص شود و برای مسیردهی خودکار درخواست‌ها به تیم مناسب به کار رود.

.

۸. بررسی حساسیت به ترتیب ورود داده‌ها

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

Run 1 - Number of concepts: 3
Run 2 - Number of concepts: 4
Run 3 - Number of concepts: 2
ARI between run 1 and run 2: 0.824
ARI between run 1 and run 3: 0.750

تعداد مفاهیم در سه اجرا به‌ترتیب ۳، ۴ و ۲ بود. با وجود شباهت نسبتاً زیاد عضویت نمونه‌ها میان اجراها، ساختار نهایی کاملاً یکسان نشد. این نتیجه به صورت عملی حساسیت الگوریتم به ترتیب ورود نمونه‌ها را نشان می‌دهد.

.

۹. معیارهای ارزیابی

Category Utility معیار داخلی COBWEB است و افزایش پیش‌بینی‌پذیری ویژگی‌ها در اثر دانستن عضویت مفهومی را اندازه‌گیری می‌کند. برای مقایسه با برچسب‌های مرجع از Adjusted Rand Index، Normalized Mutual Information و خلوص استفاده شد.

مطالعه	تعداد مفاهیم	CU	ARI	NMI	خلوص
قارچ‌ها	4	0.7222	0.653	0.733	1.000
دانش‌آموزان	4	0.6222	0.674	0.778	0.933
پشتیبانی	5	0.5164	0.326	0.745	0.667

Silhouette Score در این فایل معیار اصلی نیست، زیرا معمولاً بر فاصله میان نمونه‌های عددی تکیه دارد؛ در حالی که COBWEB کلاسیک بر توزیع مقادیر طبقه‌ای و معیار Category Utility استوار است.

.

۱۰. محدودیت‌های پیاده‌سازی

پیاده‌سازی حاضر برای آموزش و بازتولید مطالعات موردی طراحی شده است و مفاهیم سطح اول را با تصمیم Create/Incorporate تشکیل می‌دهد. نسخه کامل کلاسیک COBWEB عملیات Merge و Split و جزئیات بیشتری برای بازآرایی درخت دارد. بنابراین، نتایج این فایل باید به عنوان خروجی یک پیاده‌سازی آموزشی و نه مرجع نرم‌افزاری کامل الگوریتم تفسیر شوند.

ویژگی‌های پیوسته باید گسسته‌سازی شوند. ترتیب ورود داده‌ها می‌تواند ساختار نهایی را تغییر دهد. نمونه‌های نویزی ممکن است مفاهیم کوچک ایجاد کنند و هزینه محاسبات با افزایش تعداد نمونه‌ها و ویژگی‌ها بیشتر می‌شود.

.

۱۱. نتیجه‌گیری

در این بخش، الگوریتم COBWEB به صورت عملی در پایتون اجرا شد. مثال آموزشی نشان داد که داده‌های طبقه‌ای بر اساس افزایش پیش‌بینی‌پذیری ویژگی‌ها به مفاهیم تقسیم می‌شوند. در مطالعه قارچ‌ها، زیرگروه‌های توصیفی با خلوص کامل نسبت به برچسب خوراکی/سمی شکل گرفتند. سپس در مطالعه دانش‌آموزان، الگوهای رفتاری با سطح عملکرد ارتباط زیادی داشتند. در مطالعه درخواست‌های پشتیبانی، مفاهیم عملیاتی قابل تفسیر شکل گرفتند، هرچند تطابق کامل با موضوع‌های دستی مشاهده نشد.

مهم‌ترین مزیت COBWEB در این مطالعات، افزایشی بودن و تفسیرپذیری خروجی است. مهم‌ترین محدودیت مشاهده‌شده نیز حساسیت به ترتیب ورود داده‌ها بود. تمام مقادیر عددی، جدول‌ها و نمودارهای این فایل مستقیماً از اجرای کدهای درج‌شده به دست آمده‌اند.