بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
تصدیق مستقل از متن هویت گوینده با مدل آمیزههای گوسی تطبیق یافته ی ساختاری
چکیده :
در این مقاله، روش مدل آمیزه ی گوسی ساختار یافته (SGMM) که به منظور سرعت بخشی الگوریتم GMM-UBM در سیستم تصدیق هویت گوینده پیشنهاد شده است، مورد بررسی قرار می گیرد. تأثیر برخی پارامترها در ساخت مدل پس زمینه ی ساختاری (SBM) به تفصیل مورد بررسی و مقادیر بهینه در ساخت مدل مورد استفاده قرار می گیرد. همچنین برای پردازش امتیازهای خروجی ساختار SBM-SGMM ساختاری با عنوان شناسایی کننده ی GMM پیشنهاد می شود. شبیه سازیهای انجام یافته نشان می دهد، ساختار بهینه ی SBM در ترکیب با پردازنده ی امتیازهای پیشنهاد شده، عملکرد بهتری نسبت به سیستم پایه در ترکیب با شبکه ی عصبی دارد و این در حالتی است که پیچیدگی سیستم پیشنهاد شده، پایین تر از شبکه ی عصبی می باشد. با استفاده از سیستم پیشنهادی، نرخ سرعت بخشی برابر با ۲/۷ حاصل گردید و در عین حال عملکرد سیستم نیز نسبت به سیستم GMM-UBM بهبود نشان می دهد. در بهترین حالت می توان به نرخ خطای برابر معادل ۰/۳۵٪ دست یافت که نسبت به عملکرد سیستم GMM-UBM با نرخ خطای برابر ۱/۷۱٪ بهبود قابل ملاحظهای حاصل می شود.
۱- مقدمه
سیگنالها و معیارهای مختلفی برای سیستم های شناسایی افراد از روی مشخصه های حیاتی آنها تا به حال مورد مطالعه قرار گرفته اند. از این میان معروفترین مشخصهها، اثر انگشت، چهره و صدای افراد میباشد. با وجود این که هر کدام از این مشخصه ها مزایا و معایب خاص خود را با توجه به دقت و کاربرد دارد، عواملی وجود دارد که صدای افراد در هنگام صحبت را از این مشخصه ها متمایز می نماید. اول این که گفتار یک سیگنال طبیعی میباشد و تولید یک تکه گفتار مربوط به یک فرد برای افراد دیگر ممکن نیست. در بسیاری از کاربردها گفتار عمدهترین و یا تنها راه ممکن برای دسترسی به یک فرد می باشد (مانند ارتباطات تلفنی). دوم اینکه شبکهی تلفن یک شبکهی رایج و مطمئن برای به دست آوردن و تحویل سیگنال گفتار به شمار میرود و در کاربردهای مبتنی بر تلفن، هیچ نیازی به مبدلهای خاص سیگنال یا نصب یک شبکه ی ویژه در پایانه های دسترسی نمی باشد .علاوه بر این، به وسیله یک تلفن همراه، تقریباً همه جا میتوان به نمونه گفتار فرد دسترسی پیدا کرد. حتی در کاربردهایی غیر از کاربردهای مبتنی بر تلفن نیز، کارتهای صوتی و میکروفن ها ابزارهایی هستند که هم قیمت آن ها پایین است و هم بهراحتی در دسترس قرار دارند. سیگنال گفتار حامل مراتب مختلفی از اطلاعات است. ابتدا سیگنال گفتار حامل کلمات یا پیغام ادا شده است، اما در مرتبه ی بعدی سیگنال گفتار حامل اطلاعاتی راجع به هویت گوینده می باشد. تشخیص گوینده به دو مقولهای تعیین هویت گوینده و تصدیق هویت گوینده تقسیم می شود. در تصدیق هویت گوینده در مورد تأیید ادعای گوینده مبنی بر داشتن یک هویت، تصمیم گیری می شود. ولی در تعیین هویت گوینده، هویت از میان مجموعه ای از گویندهها تعیین میگردد. در تصدیق هویت گوینده ابتدا فرد، مدعی یک هویت می شود این امر به عنوان نمونه به وسیلهی وارد کردن یک شماره ی کارمندی یا وارد کردن یک کارت هوشمند صورت میپذیرد. سپس سیستم نمونههای گفتار فرد را گرفته و پس از پردازش آنها تصمیمی را مبنی بر قبول یا رد ادعای فرد اتخاذ کرده و یا اعلام می نماید که اطلاعات ورودی جهت تصمیم گیری کافی نمیباشد. تشخیص گوینده میتواند به صورت وابسته به متن یا مستقل از متن باشد. در سیستمهای وابسته به متن، عبارت مورد نظر برای سیستم شناخته شده است و می تواند به صورت یک جمله ی ثابت باشد و یا توسط سیستم به گوینده اعلان شود. اغلب، این عبارت به صورت رشتهی متوالی از اعداد میباشد که به عنوان رمز عبور شناخته می شود. ولی در سیستمهای مستقل از متن، محدودیتی روی محتوای متنی گفتار ادا شده وجود ندارد. از سیستمهای تصدیق هویت گوینده می توان در کنترل دسترسی به مکانهای امنیتی، کنترل دسترسی به کامپیوترها، معاملات تلفنی که با کارت اعتباری انجام می شوند و همچنین در معاملات انجام شده از طریق شبکهی اینترنت استفاده کرد. هر سیستم تصدیق هویت گوینده، دارای دو مرحله ی مجزا از هم می باشد، مرحله ی آموزش و فاز آزمون. هر کدام از این فرآیندها را می توان به عنوان یک بخش مجزا تصور کرد. در شکل (۱ الف) نمودار کلی جعبه ای فرآیند آموزش و در شکل ۱ (ب) نمودار کلی جعبه ای فرآیند آزمون نشان داده شده است. اولین قدم در فرآیند آموزش سیستم، همان گونه که در شکل (۱الف) مشاهده می شود استخراج پارامترهای مناسبی از سیگنال گفتار است که قابل استفاده برای مرحله ی مدل سازی آماری باشد. همان روالی که برای آموزش مدل یک گوینده به کار رفته است برای آموزش مدل پس زمینه نیز طی می شود. آنگونه که در شکل ۱ (ب) نشان داده شده است ورودیهای سیستم در مرحله ی آزمون شامل یک هویت ادعا شده و نمونههای گفتار یک فرد ناشناس میباشد، که مدعی آن هویت به خصوص شده است. هدف نمونه های گفتار رسیده به سیستم، متعلق به همان هویت ادعا شده است یا نه . برای انجام این کار ابتدا پارامترهای سیگنال گفتار، همانند روال مورد استفاده در مرحلهی آموزش، استخراج می شوند. سپس مدل گوینده ی مورد ادعا و نیز یک مدل پس زمینه که هر دو در مرحله ی آموزش محاسبه شدهاند از بانک اطلاعاتی سیستم استخراج می شود. در نهایت سیستم با استفاده از پارامترهای گفتار استخراج شده ی فرد مداغی و دو مدل آماری، امتیازهایی را محاسبه کرده، آنها را هنجارسازی نموده و تصمیمی مبنی بر قبول یا رد فرد مدعی اتخاذ می کند. در زمینه ی تشخیص گوینده در زبان فارسی کارهایی انجام شده است که به اختصار به آن می پردازیم. در سال ۱۳۷۳، آقایان مندولکانی و لطفی زاد [۱]، با استفاده از روش (DTW برای جمعیت ۱۰ نفری و به ازای ۱۰ جمله برای آموزش و ۱۰ جمله آزمون به کارآیی ۹۸٪ برای تعیین هویت گوینده وابسته به متن، دست یافته اند. بازهم در سال ۱۳۷۳ آقایان حدائق و لطفی زاد ۲، با استفاده از روش DTW و بر روی جمعیت ۱۰ نفری و به ازای ۱۰ تکرار جمله ی خاص برای آموزش و ۱۰ تکرار همان جمله برای آزمون به کارآیی ٪۱۰۰ برای تصدیق هویت گوینده وابسته به متن، دست یافته اند. در سال ۱۳۷۴، آقایان صیادیان و غفوریفرد ۳، با استفاده از کوانتیزاسیون برداری و بر روی جمعیت ۵۰ نفری گویندگان، به ازای ۱۰ جمله برای آموزش و یک جمله برای آزمون به کارآیی متوسط ۹۸/۰۳٪ برای تعیین هویت گوینده رسیدهاند. در همان سال، آقایان مقصودلو، نخعی و تبیانی [۴]، با استفاده از کوانتیزاسیون برداری و بر روی جمعیت ۱۰ نفری مردان، به ازای ۸ کد پنج رقمی برای آموزش و کدهای سه رقمی برای آزمون، جهت تصدیق هویت گوینده به کارآیی ۹۹/۸۳٪ رسیده اند. در بهمن ماه همین سال آقای شیخ زادگان ا۵ا تعیین هویت گوینده، بصورت مستقل از متن را به طور جدی مورد بررسی قرار دادند. در سال ۱۳۷۷، آقایان فیض آبادی و صدوقی [۶]، با استفاده از کوانتیزاسیون برداری و بر روی جمعیت ۳۰ نفری گویندگان و به ازای ۲۰ جمله و ۲۰ رقم برای آموزش و یک جمله برای آزمون به کارآیی ۱۰۰٪ برای تصدیق هویت گوینده رسیدهاند. در سال ۱۳۷۸، آقایان نجاری و همایونپور [۷]، با استفاده از دو روش شبکههای عصبی و الگوریتمهای ژنتیک و کوانتیزاسیون برداری بر روی جمعیت ۵۸ نفری (۳۶ مرد و ۲۲ زن)
گویندگان و به ازای ۵۰ رقم برای آموزش و ۷ رقم برای آزمایش در محیط تلفنی به کارآیی ۹۷/۸٪ رسیده اند.
شکل (۱): نمودار جعبه ای (الف) فاز آموزش و(ب) آزمون یک سیستم تصدیق هویت گوینده
در دیماه همان سال آقای نوری وند عملکرد شبکههای عصبی را بر روی گفتار تلفنی به منظور بازشناسی گوینده، مورد بررسی قرار دادهاند. در سال ۱۳۷۹، اقایان صیادیان، بدیع، حکاک و بیک زاده .با استفاده از مدل آمیزههای گوسی در سطح واج و یک مدل به ازای هر واج برای هر گوینده، بر روی جمعیت ۶۰ نفری (۴۰ مرد و ۲۰ زن) و به ازای ۱۰۰۰ جمله در دوره ی آموزش - که به صورت دستی واج نگاری می شود - و به ازای ۳ ثانیه گویش در دوره ی آزمون، به کارآیی ۱۰۰٪ برای تعیین هویت گوینده رسیده اند. در سال ۱۳۸۲، آقایان معین و بوستانی || ۱۰ ا، با استفاده از روش های ماشین بردار مرزی، "SVM، مدل آمیزه ی گوسی GMM, و مدل مارکف نهانی، "HMM بر روی جمعیت ۴۰ نفری گویندگان و رشته های صفر تا ۹ برای آموزش و آزمون به نرخ خطای برابر ۲٪، ۵٪ و ۸٪ به ترتیب روشهای ذکر شده دست یافتهاند. در سال ۱۳۸۳، آقایان همایونپور و کبودیان آ۱۱ ا، با استفاده از ترکیب روشهای GMM و HMM بر روی جمعیت ۱۰۰ نفری گویندگان (۶۱ مرد و ۳۹ زن) و بر روی پایگاه داده ی تلفنی FARSDIGITS1 به ازای دادههای آزمایشی، به کارآیی ٪۹۵/۵۱ در تعیین هویت گوینده و نرخ خطایی برابر ۰/۳۳٪در تصدیق هویت گوینده دست یافتهاند. در راستای آزمون الگوریتم های ارایه شده در این مقاله، ابتدا یک پایگاه اطلاعاتی گفتار متشکل از ۱۹۰ گوینده تهیه شده است که محدودیتی روی محتوای گفتار وجود نداشته است. هدف اصلی در تحقیق فعلی، شبیه سازی و بررسی عملکرد دو نوع سیستم تصدیق مستقل از متن هویت گوینده است که در طی چند سال اخیر توسعه یافته اند. این دو روش عبارتند از: مدل آمیزه ی گوسی تطبیق یافته" و مدل آمیزه ی گوسی ساختار یافته در ترکیب با شبکه ی عصبی، پایه و اساس این روش ها کار ارایه شده توسط رینولدز" است [۱۲] وی در تحقیق خود استفاده از مدل آمیزه ی گوسی را به منظور مدل سازی مدل آماری گویندگان در فضای مشخصهها در شناسایی مستقل از متن گوینده، را تشریح نمود. ما نیز در این مقاله بنای اصلی کار را بر اساس پروژه ی گزارش شده در مرجع [۱۲] قرار داده و کارهای انجام شده در آن را با دید یک سیستم تصدیق هویت گوینده شبیه سازی نمودیم. معرفی مدل آمیزه ی گوسی توسط رینولدز تحول شگرفی در عملکرد سیستمهای تصدیق هویت گوینده به وجود آورد که باعث شد روند اصلی تحقیقات در این زمینه بدین سو متمایل شود. تحقیقات انجام شده روی مدل آمیزه ی گوسی باعث بهبود عملکرد سیستمهای استفاده کننده از این مدل گردید که این بهبود هم از نظر نقطه ی کار و هم از نظر بار محاسباتی عملیات حاصل شد؛ تا این که بار دیگر رینولدز و همکاران، تغییری بنیادین را در مدل آمیزه ی گوسی مطرح کردند که باعث بهبود بیشتر کارآیی این مدل گردید [۱۳] این تغییر که هم مدلسازی مدل پس زمینه و هم در مدل سازی مدل گویندگان انجام شده بود و به نام سیستم GMM-UBM مشهور است، از آن زمان تاکنون جزء تفکیک ناپذیر بیشتر سیستمهای تشخیص گوینده به شمار میرود. کارهای مختلفی از سال ۲۰۰۰ به بعد در جهت بهبود عملکرد سیستمهای مبتنی بر GMM-UBM انجام شده است. در سال ۲۰۰۱، آکنتالر [۱۴]، تشریح کرد که ۹۰٪ وقت پردازش هر سیستم مبتنی بر GMMUBM صرف محاسبات امتیازدهی آمیزه های گوسی می شود. کار انجام شده در پروژه ی دکتری بینگ شیانگ که در سال ۲۰۰۳ میلادی در دانشگاه کرنل ایالات متحده امریکا انجام شده بود، به علت نتایج خوب و پس زمینه ی ریاضی قوی برای تسریع سیستم GMMUBM انتخاب گردید [۱۵] در این سیستم ابتدا یک ساختار درختی بر مبنای مدل UBM بنا می شود که SBM نام می گیرد و سپس یک مدل ساختاری برای گویندگان از روی SBM تطبیق داده می شود که SGMM نامیده می شود. هدف از ساخت مدل درختی، کاهش بار محاسباتی سیستم تأیید هویت گوینده است که به قیمت از دست دادن مقدار کمی از دقت تشخیص سیستم تمام می شود. برای جبران این کاهش دقت، از یک شبکهی عصبی برای ترکیب امتیازهای حاصله از لایه های مختلف ساختار درختی استفاده شده است. این سیستم ترکیبی، هم دارای دقت بیشتری نسبت به سیستم پایههای GMM-UBM و هم دارای بار محاسباتی کمتری نسبت به آن میباشد. در این مقاله، سیستم SBM-SGMM به همراه یک شبکه ی عصبی MLP به عنوان پردازشگر پسین شبیه سازی شده و با تغییر پارامترهای سیستم، عملکرد سیستم ترکیبی مورد بررسی قرار میگیرد. همچنین یک پردازشگر پسین جدید که نام آن را شناسایی کننده ی GMM گذاشته ایم، پیشنهاد می شود. این شناسایی کننده ی پیشنهادی از توزیع گوسی امتیازهای خروجی سیستم SBM-SGMM استفاده می کند. عملکرد شناسایی کنندهی GMM پیشنهادی توسط شبیه سازی کامپیوتری با عملکرد شبکه ی عصبی مقایسه می شود.
2 - مدلهای GMM
در این بخش، مدلهای GMM که با هدف بهبود کارآیی سیستم تصدیق هویت گوینده و کاهش بار محاسباتی سیستم، توسعه یافته اند، معرفی می شود. ابتدا مدل GMM-UBM که کارآیی آن در سال ۲۰۰۰ به اثبات رسید، شرح داده می شود [۱۲] و امتیازدهی سریع که از مزایای GMMUBM می باشد بحث میگردد. در ادامه، مدل SBM-SGMM که به منظور کاهش بار محاسباتی سیستم تصدیق هویت گوینده در سال ۲۰۰۳ معرفی شده است، تشریح میشود [۱۵]؛ سپس طریقه ی ساختن مدل SBM مورد بررسی قرار میگیرد. متناظر با کاهش بار محاسباتی سیستم، عملکرد سیستم تنزل مییابد که به خاطر جبران این تنزل عملکرد، از یک شبکهای عصبی استفاده شده است. با استفاده از فرض توزیع گوسی امتیازها که در هنجارسازی امتیازها استفاده می شود، سیستمی با عنوان شناسایی کننده ی GMM پیشنهاد شده است که به جای شبکهی عصبی قرار می گیرد.
۱-۲- مدل آمیزه های گوسی تطبیق یافته
یکی از راه کارهای به دست آوردن مدل پس زمینه، استفاده از یک مدل پسزمینه ی مستقل از گوینده، تحت عنوان UBM می باشد. در حقیقت UBM یک GMM است که برای بیان توزیع مستقل از گوینده ی مشخصهها به کار میرود. به طور خاص در ساخت UBM به دنبال انتخاب سیگنالهای گفتاری هستیم که مشخصات سیگنالهای گفتاری را که انتظار می رود در حین تشخیص گوینده با آنها برخورد شود، در شند. این مشخصات می تواند در قالب نوع و کیفیت گفتار و نیز ساختار مجموعه ی گویندگان باشد. در سیستم GMMUBM مدل گویندگان بوسیله ی تطبیق پارامترهای مدل UBM با استفاده از گفتارهای آموزشی گویندگان و شکلی از قاعدهٔ آموزشی بیز یا همان تخمین MAP ساخته می شود. برعکس راه کار قبلی، آموزش ML که در آن، مدل هر گوینده، مستقل از UBM ساخته می شد [۱۶ ]، ایده ی اصلی در اینجا تطبیق مدل گویندگان نسبت به مدل UBM به وسیلهی بهروزرسانی پارامترهای UBM می باشد. با انجام این کار ارتباط متقابل بین مدل گویندگان و مدل UBM برقرار می شود که نه تنها باعث بهبود عملکرد نسبت به مدل های آموزش دیده ی مستقل از هم می شود، بلکه همان گونه که در ادامه ذکر خواهد شد، این اجازه را میدهد تا از یک روش امتیازدهی سریع نیز استفاده کرد. ایدهٔ اصلی تخمین MAP برای GMM توسط گاوین " ولی " [۱۷] ارایه شد و سپس توسط لی، چن" و هو" [۱۸] تکمیل گردیده و بسط داده شد. معادلات مربوط به آموزش مدل UBM و چگونگی تطبیق مدل GMM از UBM به تفصیل در مراجع [۱۳ و ۱۶ ] بحث شده اند.
۲- ۲- محاسبه ی نسبت درست نمایی لگاریتمی در سیستمGMM-UBM
نسبت درست نمایی لگاریتمی، LLR، برای یک دنباله ی آزمون از بردارهای مشخصه ی X به صورت درست نمایی محاسبه میگردد که از این نسبت به عنوان امتیاز گوینده در سیستم تصدیق هویت گوینده استفاده می شود. در این رابطه مدل گوینده ی ادعا شده و مدل پس زمینه است. از این موضوع که مدل گویندگان، به وسیله ی تطبیق مدل UBM به دست آمده است، میتوان روش امتیازدهی سریعی را استفاده کرد که دیگر نیاز به مقداردهی کامل هر دو GMM نباشد [۱۳]. این راه کار بر پایه ی دو اثر مشاهده شده در آزمایش ها به شرح زیر میباشد: اول این که هنگامی که یک GMM بزرگ به ازای یک بردار مشخصه مقداردهی می شود، تعداد کمی از آمیزه ها سهم عمده ای در مقدار درست نمایی دارند، این امر بدین علت است که GMM نشان دهنده ی توزیعی در یک فضای بزرگ می باشد ولی یک بردار مشخصه تنها میتواند در نزدیکی تعداد کمی از اجزاء GMM واقع شود. بنابراین مقادیر درست نمایی را میتوان با استفاده از مقداردهی تعداد C آمیزهی جزء که بالاترین امتیاز را در بین بقیه ی اجزای GMM دارند به خوبی تقریب زد. دومین اثر مشاهده شده بدین قرار است که اجزای یک GMM تطبیق شده، تناظر خود را با آمیزه های UBM حفظ میکنند. به این معنی، بردارهایی که به یک آمیزه ی خاص در UBM نزدیک باشند، به آمیزه ی متناظر آن در مدل GMM گوینده نیز نزدیک خواهند بود. بدین ترتیب، راه کار امتیازدهی سریع را می توان به صورت زیر بیان کرد. برای هر بردار مشخصه، C آمیزه ی جزء را که بالاترین امتیاز را در UBM آوردهاند، پیدا کرده و مقدار درست نمایی مدل UBM به ازای بردار مشخصه ی داده شده را تنها با این C آمیزه محاسبه می کنند؛ سپس مقدار درست نمایی مدل GMM گوینده را نیز تنها به ازای C آمیزهی متناظر آن در مدل گوینده به دست میآورند. در این حالت اگر UBM حاوی M آمیزه باشد، این راه کار امتیازدهی تنها به M+C محاسبات گوسی برای تعیین LLR نیاز خواهد داشت. در صورتی که در راه کار اولیه ی 2M محاسبات گوسی مورد نیاز خواهد بود.
۳-۲- مدل آمیزههای گوسی ساختاری
در مرجع [۱۵] روشی به نام مدل آمیزههای گوسی ساختاری SGMM برای کاهش بار محاسباتی پیشنهاد گردید که این شیوه در تحقیق حاضر نیز استفاده شده است. در این راهکار ابتدا یک مدل پس زمینه ی ساختاری، SBM ، براساس یک UBM به صورت سلسله مراتبی، خوشه بندی می شود. با این کار فضای اکوستیکی به نواحی مختلف، با مراتب تفکیکپذیری متفاوت، تقسیم می شود. هر گره در ساختار درختی SBM توسط یک آمیزه ی گوسی نمایش داده میشود. برای هر گوینده یک SGMM توسط الگوریتم تطبیق MAP چند مرحلهای از SBM تولید می شود. در هنگام آزمون میتوان بار محاسباتی را به طرز مؤثری کاهش داد. این کار به وسیله ی جستجوی از بالا به پایین ساختار درختی SBM و ارزیابی تنها زیر مجموعه ی کوچکی از آمیزه های گوسی جزء در SBM و SGMM صورت میگیرد. در ادامه، طرز ساختن SBM به تفصیل مورد بررسی قرار گرفته است.
۲- ۴- نحوه ساختن SBM
نمودار جعبه ای آموزش SBM و SGMM در شکل (۲) نشان داده شده است. همانطور که در شکل (۳) دیده میشود، بر پایه ی UBM میتوان یک ساختار درختی SBM با L لایه را تولید کرد تا ساختار فضای آکوستیکی را مدل نمود. از طریق یک خوشه بندی سلسله مراتبی از بالا به پایین هر گره در L-I لایه ی بالایی نمایشگر خوشهای از آمیزه های گوسی جزء در UBM میباشد و خود توسط یک تابع چگالی احتمال گوسی مدل می شود. هر گره در لایه ی تحتانی مطابق با یک آمیزه ی گوسی جزء در UBM خواهد بود.
قبل از ساختن SBM، ابتدا باید یک معیار فاصله بین دو آمیزه ی گوسی را تعریف کرد. معیارهای فاصله ی مختلفی در مقالات مختلف مطرح شده است که معیارهای واگرایی KL [۱۹] معیار فاصله ای است که در این تحقیق استفاده شده است. ساخت SBM بدین گونه می باشد:
۱- ابتدا ساختار درخت طراحی و تعداد لایه ها و تعداد شاخه های منشعب از هر گره در هر لایه معین می شود. هیچ راه کار مشخصی برای طراحی خودکار ساختار درختی وجود ندارد؛ زیرا ساختار بهینه ممکن است با توجه به اندازهی مدل ها تغییر کند.
۲- گره ی ریشه را به عنوان گره ی kام و مجموعه G(که در مرحله ی اول تمام آمیزه های گوسی موجود در UBM میباشد.) را به عنوان به G تعیین می کنیم. تابع چگالی احتمال گره را با استفاده از کمینه کردن فاصله KL (معادلات مربوط به تخمین ML گره ی ریشه برای کمینه کردن معیار فاصله در مرجع [۱۵] موجود است) برای گره ی ریشه محاسبه می کنیم.
۳- اگر گره ی kام دارای هیچ گره ی انشعابی نباشد، خوشه بندی متوقف میشود؛ در غیر این صورت تابع چگالی احتمال اولیه ی هر گره ی انشعابی توسط روش minimax که در زیر توضیح داده می شود، برآورد میگردد. در اینجا تابع چگالی احتمال گره برای گره ی kام، Pk تعداد گره های انشعابی از گره ی kام و تابع چگالی احتمال گره ی انشعابی میباشد که
i از بین مجموعه ی Gnow آمیزه ی گوسی را به گونه ای انتخاب می کنیم که دارای بیشترین فاصله با باشد. این آمیزه ی گوسی را به عنوان تابع چگالی احتمال گره انشعابی در نظر میگیریم. یعنی
ii. آمیزه های گوسی برای cp از 2=p تا p=pk به طور متوالی به وسیله قاعده ی زیر انتخاب و به عنوان تابع چگالی احتمال گره ی انشعابی cp منظور می شوند:
