|
3. روش‌های پیشنهاد شده و مقایسه شده
این بخش روش‌های گوناگون پیشنهاد شده و مقایسه شده را در این مقاله تشریح می‌کند. روش‌های زیر بحث شده اند:
1. روش مبتنی بر N-gram
2. روش مدل فضای برداری (VSM)
3. روش مبتنی بر خوشه با استفاده از الگوریتم K-میانگین
4. K-میانگین با stemming
5. K-میانگین با ریشه یابی
6. K-میانگین با N-grams
7. K-میانگین با قطعه بندی
در آغاز برخی از پیش پردازش‌های سند متنی انجام می‌شوند. این پیش پردازش‌ها شامل tokenization، حذف نقطه گذاری و حذف کلمات اضافی ( کلماتی بدون معنا) است. یک لیست از 50 کلمه بیشتر استفاده شده در زبان انگلیسی توسط British National Corpus ارائه شده است که شامل 90 میلیون نشانه است که معمولا استفاده می‌شوند. در روشی که از قطعه بندی استفاده می‌شود، ابتدا چانک‌ها تشکیل می‌شوند و سپس کلمات اضافی حذف می‌شود. ابتدا روش مبتنی بر N-gram سنتی و روش VSM سنتی برای بازیابی کاندید استفاده می‌شود. روش مبتنی بر خوشه با استفاده از الگوریتم K-میانگین پیشنهادی پذیرفته شده است. تغییرات متفاوت تر K-میانگین صورت می‌گیرند و نتایج تحلیل و مقایسه می‌شود.
3.1 روش مبتنی بر N-gram
در اینجا پیش پردازش عمومی انجام می‌شود. سپس سند به N-gramها و N-shingles تقسیم می‌شود. این به دنباله ای از کلمات پی در پی با اندازه “N” اشاره دارد، در اینجا “N” کاربر مشخص شده است. هر دو سند مشکوک و سند منبع به پروفایل‌های N-gram خود تبدیل می‌شوند و تشابه با استفاده از ضریب Dice محاسبه می‌شود. این مشابه با ضریب جاکارد است اما اثر عبارات مشترک بین اسناد را کاهش می‌دهد. فرض کنید و مشخصه‌های N-gram مشکوک و منبع باشند، سپس ضریب Dice به شکل زیر تعریف می‌شود:
جمله انگلیسی زیر را در نظر بگیرید (E1):
“The people left their countries and sailed with Gilbert.”
بعد از پیش پردازش ابتدای، نشانه‌هایی بدست می‌آید (E1-tokens):
[‘people’, ‘left’, ‘countries’, ‘sailed’, ‘Gilbert’]
پس از تشکیل trigram ؛ N=3 ؛ (E1-3-gram) داریم:
[[‘people’, ‘left’, ‘countries’], [‘left’, ‘countries’, ‘sailed’], [‘countries’, ‘sailed’, ‘Gilbert’], [‘sailed’, ‘Gilbert’]]
بعد از تشکیل مشخصه‌های N-gram منبع و مشکوک، تشابه با استفاده از (1) محاسبه می‌شود. در عوض استفاده از مقدار آستانه برای انتخاب مجموعه کاندید صورت می‌گیرد، در اینجا تشابه بین هر منبع با همه موارد مشکوک محاسبه شده است. سپس اسناد مشکوک دارای حداکثر معیار ضریب جاکارد انتخاب شده به عنوان سند مربوطه است.
3.2 روش مدل فضای بردار (VSM)
مدل فضای برداری (VSM) یک مدل جبری است که نشان دهنده اطلاعات متنی به عنوان یک بردار است. در اینجا، بعد از پیش پردازش اولیه مورد نیاز، یک دیکشنری از عبارات (کلمات) از هر سند منبع استخراج می‌شود که با همه اسناد مشکوک مقایسه می‌شود. VSM اهمیت کلماتی که به صورت مکرر استفاده شده اند با متریک فراوانی سندی معکوس (tf-idf) نشان می‌دهد. فراوانی سندی معکوس idf(t) سپس محاسبه می‌شود که تاکید دارد که یک عبارت که تقریبا در کل مجموعه اسناد موجود است خوب نیست. در آخر، tf-idf محاسبه می‌شود و تشابه بین بردارهای سند با استفاده از شباهت کسینوسی محاسبه می‌شود. شباهت کسینوسی بین دو سند (مشکوک) و (منبع) به شکل زیر محاسبه می‌شود:
در اینجا و نمایش بردار سند مشکوک و منبع را به ترتیب نشان می‌دهند. صورت کسر در معادله (2) به ضرب نقطه ای سه بردار و مخرج کسر به ضرب نرم اقلیدسی آن‌ها اشاره دارد. بعد از محاسبه تشابه با استفاده از معادله (2)، اسناد کاندید توسط رویکرد مشابه با روش N-gram انتخاب می‌شود. بنابراین هر سند منبع با همه سندهای مشکوک مقایسه می‌شود و سند مشکوک با حداکثر شباهت کسینوسی انتخاب می‌شود. باید اشاره کنیم که مواردی وجود دارند که در آن یک سند منبع به هر سند مشکوکی بی ربط است، مانند زمانی که منبع کل وب است. اما رویکرد غیر آستانه ای در بازیابی کاندید کارامد است چرا که اینجا تحلیل دقیق تری برای تشخیص اسنادی که به واقع سرقت ادبی شده اند صورت می‌گیرد.
3.3 روش مبتنی بر خوشه با روش پیشنهادی الگوریتم K-میانگین
در این روش رویکرد خوشه بندی استفاده شده است، که در آن اسناد مشابه همراه هم به عنوان یک خوشه گروه بندی می‌شوند. در اینجا الگوریتم استفاده شده K-میانگین است که یک تکنیک خوشه بندی بخشی کارامد است. در الگوریتم خوشه بندی K-میانگین دو پارامتر اصلی تعداد خوشه‌ها (K) و مرکز خوشه اولیه/مرکزیت است. الگوریتم پایه به شرح زیر است:
1. انتخاب k و مرکزیت اولیه، در اینجا “K” تعداد مرکزیتی است که باید انتخاب شود.
2. انتساب هر شی به گروهی که با استفاده از معیار فاصله یا تشابه کمترین مرکزیت را دارد.
3. زمانی که همه شی‌ها تخصیص داده شدند، موقعیت‌های مرکز‌های “K” دوباره محاسبه شود.
4. تکرار مرحله 2 و 3 تا زمانی که مرکزیت دیگر تغییر نکند.
در اینج مسئله اصلی تصمیم گیری بر مقدار ‘K’ و مرکزیت اولیه است، چرا که این دو پارامترها کاملا نتایج الگوریتم را تنظیم می‌کنند. با در نظر گرفتن این محدودیت، رویکرد پیشنهادی این پارامترها مقادیر ثابتی را ارائه می‌دهند. در اینجا مفهوم استفاده شده این است که هر سند مشکوک به عنوان یک مرکزیت عمل می‌کند. سند منبع که به صورت کلی مشابه با سند مشکوک است برای خوشه‌هایی که شامل این سند مشکوک به عنوان مرکزیت هستند؛ گروه بندی می‌شود. بنابراین ‘K’ به عنوان مجموع تعداد اسناد مشکوک در نظر گرفته می‌شود، فرض کنید که مجموعه مشکوک (مجموعه PAN) داده شده باشد. با استفاده از این مفهوم، الگوریتم K-میانگین پایه برای وظیفه بازیابی کاندید به صورت زیر اصلاح می‌شود:
1. K= تعداد اسناد مشکوک
2. تنظیم مرکزیت K اولیه = هریک از K سند مشکوک.
3. تخصیص هر سند منبع به خوشه با نزدیک ترین مرکزیت با استفاده از شباهت کسینوسی
فرآیند با استفاده از یک پکیج Python اجرا می‌شود که خوشه بندی را تسهیل می‌کند و زمان در نظر گرفته شدن را برای بردارهای سند کاهش می‌دهد و تشابه آن‌ها را محاسبه می‌کند. سپس بر اساس معیار تشابه اسناد منبع آن‌ها بر اساس تناظر اسناد مشکوک گروه بندی می‌شوند. بنابراین هر خوشه متناظر با مجموعه کاندید از اسناد برای یک سند مشکوک خاص است. در الگوریتم پیشنهاد شده، زمانی که مرکزیت‌ها تثبیت شوند، تنها یک تکرار نیاز است. این از نظر پیچیدگی زمانی کارامد است.
3.4 تغییرات الگوریتم K-میانگین پیشنهادی
روش بازیابی کاندید K-میانگین بحث شده در زیر بخش 3.2، به عنوان رویکرد پایه استفاده شده است. سپس بسط مرکزیت بوجود می‌آیند و الگوریتم ارزیابی می‌شود. این روش‌ها در بخش‌های زیر بحث شده اند.
3.4.1 K-میانگین با Stemming (K-Stem)
در این روش، تنها تغییر این است که بعد از نشانه گذاری سند، stemming صورت می‌گیرد. ریشه یابی یک فرآیند اکتشافی از حذف وندها از کلمات است. مراحل باقی مانده مشابه با رویکرد پایه انجام شده است.
3.4.2 K-میانگین با ریشه یابی (K-Lem)
این روش از ریشه یابی به جای Stemming استفاده می‌کند. محدودیت فرم‌های پایه دیکشنری یک کلمه و موفولوژی را مورد استفاده قرار می‌دهد . این رابطه تنگاتنگی با ریشه یابی دارد اما ریشه یابی تنها در یک کلمه تکی اعمال می‌شود در حالی که محدودیت سازی بر کل متن اعمال می‌شود . این می‌تواند تبعیض قائل شدن بین کلماتی باشد که بسته به بخشی از گفتار دارای معانی متفاوت هستند.
3.4.3 K-میانگین با N-gram (K-Ng)
در اینجا روش K-میانگین با روش مبتنی بر N-gram ترکیب شده است. به جای اتخاذ کلمات منحصر N-grams ایجاد شده و پیش پردازش بیشتر از رویکرد پایه استفاده می‌شود.
3.4.4 K-میانگین با قطعه بندی (K-Chk)
روش از قطعه بندی برای تشکیل عبارات گرامری به جای مقابله با unigrams استفاده می‌کند. در ابتدا یک درخت تجزیه ساخته می‌شود. سپس اسم، فعل، صفت، قید از آن استخراج می‌شود چرا که این عبارات در معنا سازی یک جمله نقش دارد. الگوریتم با استفاده از مراحل پیش پردازش ارزیابی می‌شود، ریشه یابی و محدودیت در زیر بخش‌های 3.3.1 و 3.3.2 بحث شده اند؛ مانند K-Chk-Stem و K-Chk-Lem.
4. تنظیمات آزمایشی و تحلیل نتایج
4.1 آماره‌های داده
الگوریتم‌ها با استفاده از سه مجموعه از اسناد از مجموعه PAN-13 ارزیابی شدند. هر مجموعه دارای اسناد مشکوک و اسناد منبع متناظر هستند که در جدول 1 آورده شده است. سه مجموعه داده استفاده شده است:
•Set-1: بدون ابهام
• Set-2: ابهام تصادفی
• Set-3: ابهام در ترجمه
|