در ابتدا، کدهای آماده با توجه به جملات فاصله دارکه آنها به اشتراک گذاشته اند گروه بندی می شوند. این پوشهها، برگ های سلسله مراتب ما را فراهم می نمایند و برچسبهای آنها، حاشیه نویسی های آنها را ارائه می دهند(برچسبهای اولیه). فرض می شود که کدهای آماده که جمله فاصله دار یکسان را به اشتراک گذاری می نمایند با موضوع مشابه سرو کار دارند و در نتیجه باید در همان پوشه قرار گیرند[۲۱].
به منظور بستن واستحکام پوشهها (برگ) برای ساخت سلسله مراتب، اسنکت هر پوشهC را با مجموعه ای از برچسبهای ثانویه تعریف شده به عنوان جملات فاصله دار غنی سازی می نمایند که در C٪ از کدهای آمادهC رخ میدهد (در حال حاضر c=80). برچسب اولیه شرح بهتری از C را فراهم میکند، برچسب ثانویه آن ارائه دهنده یک توصیف دقیق تر از کدهای آماده پوشه است. برای مدیریت موثر برچسبهای اولیه و ثانویه، آنها به یک رشته منحصر به فرد الحاق می شوند و از یک کاراکتر ویژه به صورت جدا استفاده می نمایند. این رشته، امضای پوشه C نامیده میشود که توسط sig © مشخص میشود[۳۵].
گام استقراء از روند ساخت سلسله مراتب از پایین به بالا شامل سه مرحله اصلی میشود:
-
- شکل گیری والدین
-
- رتبهبندی
-
- هرس
یک پوشه والدینP ، برای هر گروه C1، C2 ،. . . ، CJ از پوشهها ایجاد می شود که یک جمله فاصله دار در میان امضاهای آنها است (از این رو، برچسبهای اولیه و ثانویه به کار گرفته می شوند). این جمله مشترک برچسب اولیه P و در نتیجه برچسب یادداشت نویسی آنp1 را فراهم میکند. مجموعه برچسبهای ثانویه ازP توسط برچسبهای ثانویه از Ci تشکیل می شود که حداقل در c٪ از کدهای آمادهP رخ می دهد. sig(P)با الحاق p1با همه برچسبهای ثانویهP بهدستمی آید. محاسبات کارآمد جمله به اشتراک گذاشته p1 از طریق یک آرایه Suffix ساخته شده روی تمام امضاهای پوشه انجام میشود. از آنجا که p1 در میان جملات فاصله دار محاسبه می شود، یک جمله فاصله دار است و لزوما یک زیر رشتهC1،. . ، CJ نیست[۳۵].
پس از تشکیل تمام پوشههای والدین و برچسبهای آنها،اسنکت آنها را با بهرهبرداری از رتبه برچسبهای پوشههای فرزندان آنها رتبه بندی می نمایند. در واقع، رتبهP از رتبه برچسبهای Cis محاسبه می شود .سپس،اسنکت یک گراف دو قسمتی وزن دارG را ایجاد می کند که در آن رئوس مجموعه ها توسط پوشههای والدین (در حال حاضر ساخت) و پوشههای فرزندان آنها ارائه شدهاند، لبه نشان دهنده واسطه والدین-بچه، و وزن یک راس، رتبه پوشه مربوطه است[۲۱,۳۵].
این نمودار در مرحله هرس بعدی به کارگرفته می شود که هدف آن، پاک کردن سطح فعلی سلسله مراتب پوشه به منظور مطابقت با اهداف اعلام شده در ابتدای این بخش است. اسنکت دو قانون مختلف هرس را برای صرفه نظر کردن از برخی از پوشههای والدین که در حال حاضر شکل گرفتهاست اتخاذ می کند. هدف از قانون اول، صرفه نظر کردن از پوشههای والدین است که Wrt یک واسطه پوشش دهنده-گراف است اگر دو پوشه والدین (تقریبا) پوشههای کودکان یکسان را پوشش دهد، آنگاه اسنکت پوشه والدین که دارای بزرگترین رتبه است را نگه می دارد. هدف از این قانون دوم، صرفه نظر کردن از پوشههای والدین است که Wrt کنار گذاشته شده، یک واسطه نحوی-شباهت در میان برچسبها است. اگر دو پوشه والدین با تقریبا همان کلمات برچسبگذاری تشریح شوند، آنگاه اسنکت پوشه والدین دارای بزرگترین رتبه را نگه می دارد. این قانون دوم، اختصار ، دقت و تمایز برچسب را در نظر می گیرد. قوانین در گراف دو قسمتی وزن دار از طریق یک روش حریصانه اعمال می شوند .تعداد پوشههای کنار گذاشته شده قابل اغماض نیست و حذف آنها منجر به ایجاد سلسله مراتب کلی قابل درک و جمع و جورتر می شود. در اینجا از جملات فاصله دار به عنوان برچسبها استفاده می شود و واسطه نحوی شباهت را برای بهدستآوردن برچسبهای پوشه بهتر اعمال می کند[۳۵].
پس از هرس، پوشه باقی مانده والدین، سطح بعدی را فراهم می نماید که بر اساس آن روند پایین به بالا دوباره تکرار میشود. این روند در حال حاضر پس از آن که سه سطح ساخته شد متوقف می شود (یک سلسله مراتب عمیق تر مد نظر کاربر نخواهد بود). یک کد آماده ممکن است در بسیاری از پوشهها رخ میدهد، و این مطابق با این مشاهده است که یک صفحه وب میتواند موضوعات متعدد را پوشش دهد. علاوه بر این، مشاهده میشود که استفاده از جملات فاصله دار، به اسنکت اجازه میدهد تا دو کد آماده را با هم خوشه بندی نماید، حتی اگر برخی از شرایط از دست برود، و یا حتی در نظمی متفاوت درون آنها رخ دهد. برای مثال، کدهای آماده حاوی جملات ” “John fitzegerald kennedy”, “Kennedy John” and “John F. kennedy” با هم توسط اسنکت خوشه بندی میشوند[۲۱].
شکل ۳-۲ ، گزارش پیچیدگی زمانی اسنکت و پیچیدگی زمانی موتورهای دیگر است و آزمایش آن در تعداد کمی از کدهای آماده را نشان میدهد.اسنکت با برچسبهای استخراج شده به نتایج عالی میرسد[۲۱].
Time Complexity |
Hierarchical Clustering |
Time Complexity |
Flat Clustering |
O(n2 log n2) O(kn) O(n) O(n logn + mlog mp) |
LA IBM SHOC اسنکت |
O(nk) O(kn log n) O(n) O(n) O(n) |
Retriever Wang et al. Grouper Carrot Microsoft |
شکل۳-۲. گزارش پیچیدگی زمانی اسنکت و پیچیدگی زمانی موتورهای دیگر[۲۱]
در شکل۳-۲، n تعداد کدهای آماده پردازش شده، k تعداد پوشههای مورد نظر،m تعداد جملات / کلمات استخراج شده، p تعداد برچسبهای استخراج شده توسط اسنکت می باشند[۲۱].