پایان نامه در مورد : تشخیص پلاگاریسم به کمک گراف در ... |
- روش ارائه متن: این روش امکاناتی را فراهم می کند که ویژگیهای ساختاری و معنایی متمایز کننده متن را استخراج کرده و بتوان از آنها به عنوان شاخص های متمایزکنندهی متن و به اصلاح اثرانگشت متن استفاده کرد. هر چقدر ویژگیهای متمایز کننده متن در این مرحله بتوانند به طور کامل و درست استخراج شوند، تشخیص پلاگاریسم دقیقتر و حقیقیتر خواهد شد.
-
-
- روش مقایسه متن ارائه شده در قالب روش ارائه شده در مرحله قبل: بعد از اینکه مطمئن شدیم متن در قالبی کارآمد ارائه شد، که علاوه بر حذف کردن بخشهای زائد و تکراری متن که تنها منجر به سربار حافظهای و محاسباتی میشوند اطلاعات متمایز کننده را استخراج و بارز نموده است، نیاز به ارائه راهبردی برای مقایسه متون در این قالب کارآمد داریم. روش مقایسه باید بتواند با کمترین هزینه محاسباتی بیشترین بهره را از اطلاعات استخراج شده ببرد و قدرت تشخیص سیستم را در حد ممکن بالا ببرد.
( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
-
هدف اصلی این فصل معرفی مفاهیم مورد نیاز در زمینه تشخیص پلاگاریسم و محاسبه فاصله ویرایش گراف است.
۳-۱ تشخیص پلاگاریسم
به منظور تشخیص پلاگاریسم، تکنیکهای بازیابی اطلاعات متعددی به کار برده شده اند. این بخش تکنیکهایی را معرفی می کند که برای تطبیق متون مورد نیاز هستند.
۳-۱-۱ تطبیق n گرام
یک nگرام زیرمجموعهای از n جز یک متن است. هر جز در شکل پایهای آن توسط یک کلمه بیان می شود[۱۷]. n اندازه زیردنباله است. یک nگرام با اندازه ۱ یونیگرام نامیده می شود، با سایز ۲ ، بایگرام و با سایز ۳ ، ترایگرام. nگرامهای سایز بالاتر توسط اعدادشان مشخص میشوند. اجزای nگرام اجزای دیگر را بیان می کنند، از قبیل کاراکتر در کلمه، که کاربردهای دیگری دارند. تمرکز این پایان نامه روی تطبیق سطح جمله است، بنابراین تنها nگرامهای سطح کلمه در نظر گرفته میشوند.
تطبیق nگرام یک روش کاملا معمول در زمینه طبقه بندی متن است. مفهوم پایهای پشت تطبیق nگرام شامل شمارش تعداد تطبیقهای nگرامها در دو متن است. یک روش معمول شامل ترکیب تطبیقهای nگرامها با سایزهای مختلف است. کاربردهای مختلف از سایزهای مختلف nگرامها بهره میبرند و بهترین اندازه وابسته به مسئله و مجموعه داده های آن است.
۳-۱-۲ وزندهی عبارت
در طی بازیابی اطلاعات، اهمیت هر عبارت می تواند توسط یک وزن مشخص شود. هر عبارت بر اساس اینکه چقدر در حل یک مسئله تاثیر می گذارد، وزندهی می شود. زیربخشهایی که در ادامه میآیند روشهای معمول در وزندهی عبارات را ارائه می کنند، که در عین حال برای مسئله تشخیص پلاگاریسم قابل استفاده هستند.
حذف stop-wordها
Stop-wordها عباراتی هستند که در تمام متون وجود دارند همانند: مثل، از، به، ولی و غیره. این قبیل عبارات مستقل از محتوای متن هستند و اطلاعات معنایی کمی راجع به متن فراهم می کنند[۱۸]. حذف کننده stop-word برای این استفاده می شود که معنی یک متن بهتر استخراج شود، زیرا عبارات stop-word در تشخیص مفهوم متن تاثیر کمتری میگذارند.
فرکانس عبارت- وزندهی فرکانسی داکیومنت معکوس
پیشرفتهترین تکنیک وزندهی، وزندهی فرکانس عبارت-فرکانس داکیومنت معکوس (TF-IDF) است[۱۹]. تکنیک تعداد رخدادهای عبارات را در یک داکیومنت داده شده و تعداد آنها در کل داکیومنتها را با هم محاسبه می کند. به این ترتیب، عباراتی که کمتر تکرار شده اند و خاصتر هستند دارای مقدار بزرگتری نسبت به عبارات تکراریتر میشوند. فرمولهای متعددی در این زمینه وجود دارند، اما یکی از مهمترین آنها به صورت زیر است (t عبارت، d داکیومنت و D مجموعه داکیومنتها است):
که تکرار عبارت t در داکیومنت d است. معمولا تکرار عبارت با محاسبه تعداد رخدادهای عبارت تقسیم بر تعداد عبارات در داکیومنت محاسبه می شود. فرکانس داکیومنت معکوس است و معمولا با محاسبهی لگاریتم تعداد داکیومنتها تقسیم بر تعداد داکیومنتهایی که عبارت t را دارند محاسبه می شود.
قدرت وزندهی TF-IDF توانایی آن در وزندهی همه عبارات است. عبارات منحصر به فرد دارای بالاترین وزن میشوند، در حالی که عبارات تکراری کمترین وزن را به خود اختصاص می دهند. وزندهی TF-IDF نیاز به جستجوی دیکشنری دارند، بنابراین این روش مستقل از زبان است. با این حال پیدا کردن مقادیر IDF برای هر عبارت نیاز به محاسبه دارد.
۳-۱-۳ تعمیم عبارت
زیربخشهایی که در ادامه آمدهاند تکنیکهایی را توصیف می کنند که به ما امکان بیان عبارات را در فرم عمومیتری فراهم می کنند.
ریشهیابی
ریشهیابی فرایند بیان انواع شکلهای یک کلمه به صورت عمومیتر است، که ریشه نامیده می شود. به عنوان نمونه، کلمه بود شامل فرمهای بودم، بودی، بودند، بودهایم و غیره است. با ارائه فرمهای مختلف آن توسط کلمهی بود، تطبیق کلمات خیلی پایدارتر می شود.
با این حال، بیان کلمات توسطِ ریشههایشان، در حالاتی که دو کلمهی متفاوت دارای یک ریشه هستند، می تواند منجر به اشتباه شود. کلمات خرید در دو جمله “او به خرید میرود” و “او یک کتاب خرید” دارای ریشه مشترک خرید هستند که در یکی اسم و دیگری فعل است. هر دو کلمه دارای یک ریشه هستند و اگر فقط ریشه در نظر گرفته شود ممکن است یکسان در نظر گرفته شوند.
۳-۲ </st rong>گرافهای وابستگی
یک گراف وابستگی یک ارائه ساختیافته از یک جمله است. به منظور ایجاد گرافهای وابستگی، یک جمله توسط یک پارسر وابستگی پردازش می شود، که مبتنی بر یافتههای تئوریکی گرامر وابستگی است. گرامر وابستگی به صورت یک خانواده از تئوریها است که تعدادی فرضیه پایهای را درباره ساختار گرامری به اشتراک میگذارند [۲۰].
ساختارهای گرامری میتوانند خیلی پیچیده باشند و اغلب ورژنهای گراف وابستگی ساده شده ساختارهای وابستگی تئوری هستند. گرافهای وابستگی پیچیده نیاز به الگوریتمهایِ پیچیده دارند. گرافهای ساده وضوح کمتری دارند، ولی کار با آنها راحتتر است، به خصوص اگر هدف تجزیهی وابستگی خودکار باشد. لبهها نمایانگر وابستگی بین نودها هستند. برچسب لبه نوع وابستگی را مشخص می کند. این ویژگیها با جزئیات کامل در بخش بعد توضیح داده خواهند شد.
۳-۲-۱ وابستگیها
یک وابستگی بین دو عبارت، شامل یک هدر و وابستگی است. به عبارت دیگر، وابستگیها جهتدار هستند و گراف وابستگی را به گراف جهتدار تبدیل می کنند. اغلب نیاز است که بین روابط وابستگی متعدد تمایز قائل شویم. برچسبهای لبه، روابط بین هدر و وابستهها را مشخص می کنند. روابط بین توپ و شوت شد را در شکل ۱-۱ در نظر بگیرید. در اینجا رابطه بین توپ و شوت شد، مفعول است، یعنی توپ مفعول فعل شوت شد است. به طور کلی، این وابستگی شامل یک رابطه بین عمل (شوت کردن) و موجودیتی (توپ) است که به طور مستقیم توسط این عمل تحت تاثیر واقع شده است.
۳-۳ فاصله ویرایش گراف
فاصلهی ویرایش گراف معیاری برای سنجش اختلاف دو گراف است، که با محاسبهی مینیمم تعداد عملیاتی که لازم است در یک گراف انجام داده شود تا مشابه گراف دیگر شود، بدست می آید[۱]. یک عمل ویرایش می تواند روی نود یا لبه صورت گیرد، تعریف ۱ را دنبال کنید.
تعریف۱- عملیات ویرایش بین دو گراف و شامل یکی از سه عمل جایگزینی ، اضافه کردن یا حذف کردن است، که نودی در و نودی در است.
عمل جایگزینی در تعریف ۲ توضیح داده شده است.
تعریف۲- عمل جایگزینی شامل یک عمل اضافه کردن و یک عمل حذف کردن است.
۳-۳-۱ عملیات ویرایش
عملیات ویرایش نیاز به تبدیل گراف مبدا به گراف مقصد دارد، که یک مسیر ویرایش را شکل میدهد. شکل ۳-۱ مسیر ویرایش مورد نیاز برای تبدیل جمله “کودک توسط مادر در آغوش گرفته شد"، به جمله “مادر کودک را در آغوش گرفت” را نشان میدهد [۲۱].
شکل ۳- ۱ : مثال عملیات ویرایش برای دو گراف
هر عمل ویرایش دارای هزینه مربوط به خود است، که با عنوان تابع هزینه مشخص می شود. یک تابع هزینه برچسب نودها را با هم منطبق می کند و در عین حال اختلافها را برطرف مینماید. تابع هزینه ممکن است از یک کاربرد به کاربرد دیگر متفاوت باشد.
۳-۳-۲ مسئله انتساب
پیچیدگی زمانی برای تطبیقِ n نود به m نود، که n و m نودهای دو گراف هستند، برابر است، در نتیجه مسئله دارای پیچیدگی توانی روی تعداد نودها است. در نتیجه نیاز داریم از یک روش جایگزین استفاده نماییم.
یک راه حل سریع و نیمهبهینه توسطِ [۲۱] معرفی شده است. راه حلِ آنها مبتنی بر مسئله انتساب است، که n عامل را به m شغل منتسب می کند، که هر عامل دستمزد مختصِ خود را برای پذیرش یک شغل دارد. هدف پیدا کردن ارزانترین انتساب است و هزینه های عملیات ویرایش در اینجا نقش هزینه های کارهایِ مختلف را بازی می کند.
شکل ۳- ۲ : مسئله انتساب
شکل ۳-۲ مسئله انتساب را برای دو جمله شکل ۳-۱ نشان میدهد. از آنجایی که دو جمله دارای تعداد نابرابری کلمه هستند، دو عمل حذف و دو عمل اضافه انجام می شود. هزینه ویرایش معادل کل هزینه ویرایش است.
۳-۳-۳ ماتریس هزینه
زمانی که فاصله ویرایش را برای دو گراف محاسبه میکنیم، یک ماتریس هزینه دوبعدی میتوان تشکیل داد که هزینه را برای هر کدام از عملیات ویرایش برای هر نود در خود دارد. با ایجاد این ماتریس هزینه، مسئله فاصلهی ویرایش به یک مسئله انتساب تقلیل مییابد، که سادهتر میتوان آن را حل کرد.
کمترین هزینه ویرایش برابر با فاصله ویرایش تقریبی محاسبه شده برای دو گراف است. تابع هزینه به صورت زیر ایجاد می شود:
ماتریس دارای سایز است، که و نشاندهنده تعداد نودها در هر گراف هستند. هر سلول هزینه عملیات ویرایش را بین نودهای و نشان میدهد. هر نود تنها حق دارد یک عمل ویرایش انجام دهد. ناحیهی سمت چپ بالای ماتریس هزینه های جایگزینی نودها را مشخص می کند، در حالیکه ناحیهی سمت چپ پایین هزینه اضافه کردن نود را مشخص می کند. ناحیهی سمت راست بالا هزینه حذف نود و ناحیه پایین سمت راست هزینه جایگزینیهایی به فرم است که هیچ هزینهای ندارد.
۳-۳-۴ الگوریتمهای انتساب
الگوریتمهای متعددی وجود دارند که مسئله انتساب را حل می کنند، که از لحاظ سرعت عملیات متفاوت هستند. Fankhauser سه الگوریتم را برای حل مسئله انتساب معرفی کرده است[۱]. الگوریتم دورهگرد، الگوریتم مانکرس و الگوریتم Volgenant-Jonker. او در مقاله خود نشان داد که الگوریتم Volgenant-Jonker از همه سریعتر است و دارای پیچیدگی زمانی است.
فصل چهارم
روش پیشنهادی و پیادهسازی
فرم در حال بارگذاری ...
[پنجشنبه 1400-09-25] [ 09:03:00 ق.ظ ]
|