الگوریتم CLASSIT؛ خوشه‌بندی مفهومی افزایشی برای داده‌های عددی:بخش اول

1.اهداف یادگیری

پس از مطالعه این فصل، خواننده باید بتواند:

• جایگاه CLASSIT را در میان روش‌های خوشه‌بندی مفهومی، سلسله‌مراتبی و افزایشی توضیح دهد.
• تفاوت CLASSIT با COBWEB و خوشه‌بندهای آماری مانند مدل مخلوط گاوسی را تحلیل کند.
• نمایش آماری هر گره، نقش آمار کافی و معیار مطلوبیت رده پیوسته را صورت‌بندی کند.
• چهار تصمیم محلی الگوریتم ــ افزودن، ایجاد، ادغام و شکافتن ــ را از نظر منطقی توضیح دهد.
• نقش دو پارامتر acuity و cutoff را در پایداری عددی و پیچیدگی ساختار تفسیر کند.
• حساسیت الگوریتم به ترتیب ورود، مقیاس ویژگی‌ها، داده پرت، ابعاد زیاد و همبستگی ویژگی‌ها را نقد کند.
• پیچیدگی زمانی و حافظه را با توجه به عمق، عامل شاخه‌بندی و تعداد ویژگی‌ها تحلیل کند.
• CLASSIT را با COBWEB، COBWEB/3، TRESTLE، GMM، BIRCH و روش‌های سلسله‌مراتبی متداول مقایسه کند.
• اعتبار و محدودیت نتایج تجربی کلاسیک الگوریتم را با معیارهای امروزی ارزیابی کند.

2.پیش‌نیازهای مفهومی

• تفاوت یادگیری نظارت‌شده و بدون نظارت؛
• مفهوم خوشه، رده، سلسله‌مراتب و درخت؛
• خوشه‌بندی تخت در برابر خوشه‌بندی سلسله‌مراتبی؛
• یادگیری افزایشی و پردازش نمونه‌به‌نمونه؛
• جست‌وجوی حریصانه و بهینه محلی.

پیش‌نیازهای آماری و ریاضی

• میانگین، واریانس و انحراف معیار؛
• توزیع نرمال تک‌متغیره و تابع چگالی احتمال؛
• احتمال پیشین و شرطی؛
• جمع، مجموع مربعات و آمار کافی؛
• انتگرال پایه و نمادگذاری مجموع؛
• تحلیل مرتبه زمانی با نماد (0)O.

پیش‌نیازهای محاسباتی

• ساختار داده درخت؛
• پیمایش بازگشتی؛
• به‌روزرسانی افزایشی آمار؛
• درک مقدماتی پایداری عددی محاسبه واریانس.

۳. چکیده

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

این فصل مبانی تاریخی و نظری CLASSIT، نمایش آماری گره‌ها، استخراج معیار تصمیم، مراحل اجرا، مثال‌های عددی، حساسیت به ترتیب و مقیاس، پیچیدگی، ابرپارامترها، مزایا، محدودیت‌ها و توسعه‌های آن را بررسی می‌کند. تأکید فصل بر این نکته است که CLASSIT از نظر تاریخی پلی میان خوشه‌بندی، یادگیری مفهوم و استنتاج احتمالاتی است، اما فرض نرمال محوری، جست‌وجوی محلی و نبود سازوکار فراموشی، استفاده مستقیم آن را در بسیاری از مسائل مدرن محدود می‌کند.

.

۴. بستر علمی و تعریف مسئله

۴.۱ از خوشه‌بندی عددی تا شکل‌گیری مفهوم

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

COBWEB این دیدگاه را برای ویژگی‌های اسمی و گسسته صورت‌بندی کرد. در هر گره، احتمال مقادیر اسمی ویژگی‌ها نگهداری می‌شد و ساختار درخت با معیاری به نام مطلوبیت رده ارزیابی می‌گردید (Fisher, 1987). محدودیت روشن آن برای بسیاری از داده‌های علمی، پیوسته‌بودن اندازه‌گیری‌ها بود. قد، وزن، فشار، دما یا غلظت را نمی‌توان بدون از دست‌دادن اطلاعات به مجموعه کوچکی از مقادیر اسمی تبدیل کرد. CLASSIT برای پاسخ به همین خلأ، نمایش احتمال‌های گسسته COBWEB را با توزیع‌های نرمال تک‌متغیره جایگزین کرد (گناری و همکاران، ۱۹۸۹).

۴.۲ صورت مسئله

فرض کنید جریان نمونه‌های عددی زیر دریافت می‌شود:

هر نمونه از  d ویژگی عددی تشکیل شده است. برچسب رده برای آموزش در اختیار الگوریتم قرار ندارد. خروجی مطلوب، درختی ریشه‌دار است که:

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

۴.۳ ورودی و خروجی

• ورودی اصلی: دنباله‌ای از بردارهای عددی، پارامتر اسکالر acuity، پارامتر cutoff و در نسخه ساخت‌یافته، توصیف مؤلفه‌های هر شیء.
• خروجی اصلی: درخت مفهوم که در هر گره آمار تعداد، مجموع، مجموع مربعات، میانگین و پراکندگی ویژگی‌ها ذخیره شده است.
• خروجی استنتاجی: انتساب نمونه جدید به یک مسیر درخت، توصیف احتمالاتی خوشه‌ها و پیش‌بینی ویژگی‌های مفقود.

۴.۴ جایگاه علمی

CLASSIT را می‌توان هم‌زمان در سه سنت علمی قرار داد:

1. خوشه‌بندی مفهومی: زیرا کیفیت یک خوشه فقط با فشردگی هندسی سنجیده نمی‌شود، بلکه با قابلیت پیش‌بینی ویژگی‌ها نیز ارتباط دارد.
2. یادگیری افزایشی: زیرا مدل بدون بازآموزی کامل با هر مشاهده به‌روزرسانی می‌شود.
3. مدل‌سازی شناختی: زیرا مقاله اصلی آن را مدلی برای شکل‌گیری و سازمان‌دهی مفهوم در یادگیرنده نیز تلقی می‌کند.

این جایگاه سه‌گانه سبب شده است CLASSIT در منابع داده‌کاوی گاه «خوشه‌بندی مدل‌مبنا» و در منابع علوم شناختی «مدل شکل‌گیری مفهوم» نامیده شود. اصطلاح مدل‌مبنا در اینجا نباید با مدل مخلوط گاوسی یکسان انگاشته شود؛ CLASSIT تابع درست‌نمایی سراسری یک مخلوط را با EM بهینه نمی‌کند، بلکه ساختار را با تصمیم‌های محلی مبتنی بر مطلوبیت رده تغییر می‌دهد.

.

۵. مفاهیم پایه و تعاریف ضروری

۵.۱ مفهوم و گره مفهومی

مفهوم در CLASSIT مجموعه‌ای از نمونه‌ها همراه با خلاصه احتمالاتی ویژگی‌های آن‌هاست. هر مفهوم با یک گره در درخت نمایش داده می‌شود. گره ریشه همه نمونه‌های مشاهده‌شده را در بر می‌گیرد؛ فرزندان آن زیرمفهوم‌های جزئی‌ترند.

۵.۲ افراز محلی

اگر گره والد C_p دارای Kفرزند باشد، مجموعه فرزندان

یک افراز محلی از نمونه‌های والد ایجاد می‌کند. معیار تصمیم CLASSIT کیفیت همین افراز محلی را می‌سنجد.

۵.۳ آمار کافی

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

۵.۴ مطلوبیت رده

مطلوبیت رده یا Category Utility معیاری است که می‌پرسد: دانستن اینکه نمونه متعلق به کدام فرزند است، تا چه اندازه پیش‌بینی ویژگی‌های آن را بهتر می‌کند؟ در CLASSIT، پیش‌بینی‌پذیری بیشتر با پراکندگی کمتر توزیع ویژگی در فرزند مرتبط می‌شود.

۵.۵ acuity

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

۵.۶ cutoff

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

۵.۷ عملگرهای بازسازمان‌دهی

• افزودن: قراردادن نمونه در یک فرزند موجود؛
• ایجاد: ساخت فرزند جدید برای نمونه؛
• ادغام: ترکیب دو فرزند در یک گره میانی؛
• شکافتن: حذف یک فرزند و ارتقای فرزندان آن به سطح فعلی.

۵.۸ نمادهای اصلی

• N : تعداد کل نمونه‌های پردازش‌شده؛
•  d: تعداد ویژگی‌ها؛
•  C: یک مفهوم یا گره؛
•  n_C: تعداد نمونه‌های گره C؛
•  x_ri: مقدار ویژگی i برای نمونه r؛
•  μ _i,C: میانگین ویژگی i در گره C؛
•  σ_i,C: انحراف معیار ویژگی i در گره C؛
• a : مقدار اسکالر acuity در صورت‌بندی اصلی؛
•  K: تعداد فرزندان یک گره؛
•  P(C_k ): نسبت نمونه‌های فرزند C_k به والد؛
• τ: مقدار آستانه cutoff؛
•  CU_max (C_p,x): بیشترین مطلوبیت رده میان ساختارهای کاندید در گره والد C_p هنگام درج نمونه x.

.

۶. ایده محوری و مبانی نظری ـ ریاضی

۶.۱ ایده محوری

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

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

۶.۲ نمایش آماری گره

برای گره C و ویژگی i، تعداد نمونه‌ها برابر است با:

مجموع مقادیر ویژگی و مجموع مربعات آن به‌ترتیب چنین تعریف می‌شوند:

میانگین ویژگی از رابطه زیر محاسبه می‌شود:

در صورت استفاده از واریانس جامعه، انحراف معیار گره برابر است با:

نقش این آمار آن است که با ورود نمونه جدید، پارامترهای توزیع بدون پیمایش دوباره همه اعضای گره به‌روزرسانی شوند. مقاله اصلی نگهداری شمارش، مجموع و مجموع مربعات را مبنای یادگیری افزایشی قرار می‌دهد (گناری و همکاران، ۱۹۸۹).

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

۶.۳ کف پراکندگی یا acuity

اگر گره فقط یک نمونه داشته باشد، انحراف معیار صفر می‌شود. از سوی دیگر، معیار مطلوبیت شامل معکوس انحراف معیار است. در صورت‌بندی اصلی CLASSIT، یک پارامتر اسکالر a>0 به‌عنوان حداقل انحراف معیار به کار می‌رود و انحراف معیار مؤثر چنین تعریف می‌شود:

به‌کارگیری a_i جداگانه برای هر ویژگی، تعمیم معقولی برای داده‌های دارای دقت اندازه‌گیری متفاوت است، اما جزئی از تعریف اصلی الگوریتم نیست. استفاده از یک  مشترک هنگامی قابل‌تفسیرتر است که ویژگی‌ها مقیاس‌های قابل‌مقایسه داشته باشند؛ در غیر این صورت، واحد اندازه‌گیری بر سهم 1بر σ ̃ و در نتیجه بر ساختار درخت اثر می‌گذارد.

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

۶.۴ مدل نرمال ویژگی‌ها

CLASSIT برای ویژگی   i در مفهوم C_k چگالی نرمال تک‌متغیره را فرض می‌کند:

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

۶.۵ از پیش‌بینی‌پذیری تا معکوس انحراف معیار

در نسخه گسسته COBWEB، احتمال درست حدس‌زدن مقدار ویژگی با مجموع مربع احتمال‌ها ارتباط دارد. برای متغیر پیوسته، احتمال یک مقدار دقیق صفر است؛ ازاین‌رو f^2∫ باید به‌عنوان همتای پیوسته و یک تابعیِ درجه دوم از چگالی تفسیر شود، نه احتمال لفظیِ حدس درست یک نقطه. برای توزیع نرمال داریم:

ثابت(2√π) / 1در همه افرازهای مقایسه‌شده یکسان است. بنابراین برای رتبه‌بندی گزینه‌ها می‌توان آن را حذف کرد. نتیجه مهم این است که سهم یک ویژگی در قابلیت پیش‌بینی، متناسب با 1بر σ ̃ می‌شود: هرچه توزیع باریک‌تر باشد، دانستن مفهوم مقدار ویژگی را دقیق‌تر محدود می‌کند.

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

فرض کنید گره والد C_p دارای K فرزند باشد. احتمال پیشین هر فرزند از نسبت تعداد اعضای آن به والد محاسبه می‌شود:

صورت منتشرشده معیار CLASSIT برای افراز محلی چنین است:

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

مقاله اصلی تصریح می‌کند که در پیاده‌سازی CLASSIT، مجموع سهم ویژگی‌ها بر تعداد ویژگی‌ها نیز تقسیم شده است تا مقایسه در حضور ویژگی‌های مفقود تعدیل شود. برای داده کامل با d ثابت، صورت میانگین‌گیری‌شده برابر است با:

در داده کامل، عامل ثابت 1بر d رتبه‌بندی کاندیدها را تغییر نمی‌دهد؛ بااین‌حال، مقیاس عددی CU و در نتیجه مقدار قابل‌مقایسه cutoff را تغییر می‌دهد. در داده ناقص باید مجموعه ویژگی‌های مشاهده‌شده و قاعده نرمال‌سازی به‌طور صریح تعریف شود، زیرا پیاده‌سازی‌ها الزاماً یک قرارداد واحد ندارند (گناری و همکاران، ۱۹۸۹).

۶.۷ چهار گزینه تصمیم

برای ورود نمونهx به گره جاری، CLASSIT ساختارهای کاندید زیر را ایجاد یا شبیه‌سازی می‌کند:

1. افزودن به بهترین فرزند: آمار هر فرزند به‌طور موقت با نمونه جدید به‌روزرسانی و مطلوبیت محاسبه می‌شود.
2. ایجاد فرزند جدید: نمونه به‌تنهایی یک مفهوم جدید تشکیل می‌دهد؛ acuity مانع برتری نامتناهی برگ تک‌نمونه‌ای می‌شود.
3. ادغام دو فرزند: دو فرزندی که مناسب‌ترند زیر یک گره میانی قرار می‌گیرند و نمونه به ساختار حاصل افزوده می‌شود.
4. شکافتن بهترین فرزند: این گزینه فقط هنگامی قابل ارزیابی است که بهترین فرزند خود دارای فرزند باشد. در این حالت، بهترین فرزند حذف و فرزندان آن به سطح جاری منتقل می‌شوند؛ سپس محل مناسب نمونه دوباره ارزیابی می‌گردد.

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

۶.۸ نقش cutoff

پس از ارزیابی ساختارهای مجاز، فرض کنید   CU _max (Cp,x)بیشترین مطلوبیت رده در گره جاری برای نمونه  باشد. منطق آستانه‌گذاری به‌صورت زیر بیان می‌شود:

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

بنابراین  آستانه خودِ مطلوبیت رده است، نه آستانه اختلاف میان دو مقدار CU. مستندات WEKA نیز cutoff را «حداقل مطلوبیت رده» تعریف می‌کنند؛ ازاین‌رو مقدارهای cutoff تنها وقتی قابل مقایسه‌اند که تعریف CU، از جمله عامل میانگین‌گیری بر ویژگی‌ها، یکسان باشد (دانشگاه وایکاتو، بی‌تا).

۶.۹ فرضیات پایه

• ویژگی‌ها عددی‌اند و در هر مفهوم با نرمال تک‌متغیره تقریب زده می‌شوند.
• سهم ویژگی‌ها جمع‌پذیر است و کوواریانس کامل مستقیماً وارد معیار نمی‌شود.
• کاهش پراکندگی درون‌مفهومی معیاری معتبر برای افزایش قابلیت پیش‌بینی است.
• داده در مقیاسی ارائه می‌شود که مقایسه 1بر σ میان ویژگی‌ها معنی‌دار باشد.
• تصمیم‌های حریصانه محلی برای ساخت یک سلسله‌مراتب مفید کافی تلقی می‌شوند.
• جریان داده در نسخه پایه سازوکار صریح فراموشی یا وزن‌دهی زمانی ندارد.

.

۷. مراحل گام‌به‌گام اجرای الگوریتم و منطق تصمیم‌گیری

۷.۱ مقداردهی اولیه

در آغاز، درخت یا خالی است یا فقط یک ریشه بدون فرزند دارد. نخستین نمونه، آمار ریشه را مقداردهی می‌کند و معمولاً یک برگ متناظر با خود می‌سازد. برای گره تک‌نمونه‌ای، میانگین هر ویژگی برابر مقدار نمونه است و پراکندگی مؤثر با acuity تعیین می‌شود.

۷.۲ ورود نمونه به ریشه

هر نمونه جدید ابتدا به ریشه ارائه می‌شود. آمار ریشه باید بازتاب‌دهنده همه نمونه‌های پردازش‌شده باشد؛ ازاین‌رو شمارش، مجموع و مجموع مربعات آن به‌روزرسانی می‌شود. اگر ریشه فرزندی نداشته باشد، فرزند جدید ساخته می‌شود. در غیر این صورت، ارزیابی ساختاری آغاز می‌گردد.

۷.۳ ارزیابی افزودن به فرزندان موجود

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

۷.۴ ارزیابی ایجاد یک مفهوم جدید

نمونه می‌تواند به‌عنوان فرزند جدید والد قرار گیرد. این گزینه هنگامی مناسب است که نمونه با هیچ مفهوم موجود سازگاری کافی نداشته باشد. چون برگ جدید پراکندگی تجربی صفر دارد، معیار از پراکندگی مؤثر برابر acuity استفاده می‌کند.

۷.۵ ارزیابی ادغام

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

۷.۶ ارزیابی شکافتن

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

۷.۷ انتخاب عمل و نزول در درخت

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

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

۷.۸ خروجی پس از هر نمونه

پس از پایان درج، درخت بلافاصله قابل استفاده است. هر گره آمار به‌روز دارد و می‌تواند:

• نمونه را در سطحی از سلسله‌مراتب توصیف کند؛
• مقدار یک ویژگی مفقود را با میانگین یا توزیع گره پیش‌بینی کند؛
• برای تحلیل مفهوم‌های کلی و جزئی بررسی شود؛
• نمونه بعدی را بدون بازآموزی دسته‌ای دریافت کند.

۷.۹ ابهام اجرایی

مقاله‌های تاریخی COBWEB و CLASSIT ترتیب دقیق برخی مقایسه‌ها و اولویت تساوی‌ها را کاملاً بی‌ابهام نمی‌کنند. مستندات WEKA ترتیب مشخصی برای میزبان، برگ جدید، ادغام و شکافتن اتخاذ کرده‌اند. بنابراین دو پیاده‌سازی که هر دو با توصیف کلی سازگارند، ممکن است درخت‌های متفاوت تولید کنند. برای بازتولید علمی باید ترتیب عملگرها، روش تساوی‌شکنی و زمان به‌روزرسانی آمار گزارش شود (دانشگاه وایکاتو، بی‌تا).

.

۸. شبه‌کد استاندارد

الگوریتم درج در CLASSIT
ورودی‌ها:
نمونه عددی جدید: x
گره جاری: C
پارامتر اسکالر acuity: a
آستانه حداقل مطلوبیت رده: τ
خروجی: درخت مفهوم به‌روزشده

۱. آمار گره جاری را با نمونه جدید به‌روز کن.
۲. اگر گره جاری فاقد فرزند است، یک برگ برای نمونه ایجاد کن و خاتمه بده.
۳. بدون تغییر دائمی درخت، امتیاز افزودن موقت نمونه به هر فرزند را محاسبه کن.
۴. بهترین و دومین فرزند را تعیین کن.
۵. امتیاز گزینه‌های مجاز را محاسبه کن:
   الف) افزودن نمونه به بهترین فرزند؛
   ب) ایجاد فرزند جدید برای نمونه؛
   ج) ادغام دو فرزند برتر و افزودن نمونه؛
   د) در صورت داشتن زیرساختار، شکافتن بهترین فرزند و ارزیابی ساختار بازشده.
۶. گزینه دارای بیشترین مطلوبیت رده را تعیین کن.
۷. اگر بهترین مطلوبیت رده کمتر از τ است، تغییرهای موقت را بازگردان و خاتمه بده.
۸. ساختار گزینه منتخب را تثبیت و سایر تغییرهای موقت را بازگردان.
۹. اگر گزینه منتخب میزبان نزول دارد، فرایند درج را در آن گره تکرار کن.
۱۰. در غیر این صورت خاتمه بده.

 

9. مثال‌های آموزشی

۹.۱ مثال شهودی: قد افراد

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

۹.۲ مثال عددی پایه: مقایسه دو افراز

مجموعه یک‌بعدی زیر را در نظر بگیرید:

افراز نخست چنین است:

میانگین و انحراف معیار جامعه هر فرزند برابرند با:

چون هر دو انحراف معیار با acuity برابرند، پراکندگی مؤثر نیز 0.5 است. میانگین والد برابر است با:

و انحراف معیار والد:

با توجه به اینکه احتمال هر فرزند 0.5 است، مطلوبیت افراز مناسب به‌صورت زیر به دست می‌آید:

اکنون افراز درهم‌آمیخته زیر را در نظر بگیرید:

برای این افراز داریم:

بنابراین:

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

۹.۳ مثال عددی متوسط: تصمیم میان افزودن و ایجاد

فرض کنید گره والد دارای دو فرزند است:

نمونه جدید x=3 وارد می‌شود. اگر نمونه به C₁ افزوده شود، فرزند نخست به مجموعه {0,1,2,3} تبدیل می‌شود. میانگین آن برابر است با:

انحراف معیار جامعه آن:

در مقابل، اگر برای x=3 یک برگ جدید ساخته شود، پراکندگی مؤثر برگ برابر acuity، یعنی 0.5، خواهد بود؛ ولی تعداد فرزندان از دو به سه افزایش می‌یابد و عامل 1بر K امتیاز را کاهش می‌دهد. نتیجه نهایی فقط با محاسبه کامل مطلوبیت والد تعیین می‌شود. این مثال نشان می‌دهد ایجاد برگ جدید صرفاً به دلیل پراکندگی کوچک، همیشه برنده نیست؛ جریمه تعداد فرزندان و تغییر احتمال‌های پیشین نیز مؤثرند.

برای تکمیل محاسبه، فرض کنید پس از ورود نمونه، پراکندگی والد برابر 3.897 باشد و پراکندگی فرزند دوم بدون تغییر حدود 0.816 باقی بماند. امتیاز تقریبی گزینه افزودن:

برای گزینه ایجاد، پراکندگی C₁ پیش از افزودن برابر حدود 0.816، پراکندگی C₂ نیز 0.816 و برگ جدید 0.5 است:

در این تنظیم، افزودن نمونه به C₁ اندکی مطلوب‌تر از ایجاد فرزند جدید است. این نتیجه به acuity، پراکندگی والد و اندازه فرزندان حساس است.

۹.۴ مثال پیشرفته: اثر مقیاس

دو ویژگی را در نظر بگیرید: قد بر حسب متر و وزن بر حسب گرم. اگر دو خوشه در قد انحراف معیار 0.05 متر و در وزن انحراف معیار 5000 گرم داشته باشند، سهم‌های معکوس پراکندگی به‌ترتیب برابرند با:

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

.