بخشی از مقاله
چکیده
صحت دادهها به عنوان یکی از مهمترین ابعاد کیفیت دادهها بهشمار میآید. تصحیح دادهها از دو فرایند تشخیص خطا و تصحیح خطای شناساییشده، تشکیلشدهاست. راهکارهای متعددی برای تصحیح ارائهشده، که برخی از این راهکارها خودکار و برخی دیگر متعامل هستند. راهکارهای تصحیح متعامل با کاربر، با توجه به حجم بالای منابع دادهای، روشهای مناسبی نمیباشد و لذا برای تصحیح دادهها نیاز به یک راهکار خودکار وجوددارد. در این مقاله راهکاری خودکار برای تصحیح خطا مبتنی بر یک روش ترکیبی از طبقهبندی بیز و k نزدیکترین همسایگی ارائهشدهاست. در این روش فرضشده، که رکوردهای حاوی خطا تشخیصدادهشدهاند، اما اینکه خطا در کدام فیلد رخدادهاست، مشخص نمیباشد.
لذا روش پیشنهادی از دو فرایند تشخیص فیلد خطادار و تصحیح آن تشکیلشدهاست. این روش توانایی تشخیص خطا را در انواع دادهای مختلف دارا میباشد.آزمایشات نشانمیدهد که به طور متوسط این روش میتواند %86 خطاهای موجود در دادهها را شناسایی و تصحیح نماید. همچنین روش پیشنهادی با یک روش تصحیح خطا مبتنی بر وابستگی تابعی، که همانند راهکار پیشنهادی روشی خودکار برای تشخیص خطاست مورد مقایسه قرارگرفتهاست. نتایج نشانمیدهد که روشپیشنهادی به طور متوسط %10 عملکرد بهتری در تصحیح خطا داشتهاست.
کلید واژه- تشخیص خطا، تصحیح خودکار، طبقهبند بیز، k نزدیکترین همسایه.
-1 مقدمه
با رشد روز افزون حجم منابع دادهای، تامین کیفیت دادهها1 به یک مشکل اساسی تبدیلشدهاست. کیفیت دادهها دارای ابعاد متنوعی از جمله یکپارچگی، دقت و صحت2 میباشد، که صحت در میان این ابعاد از اهمیت بالایی برخوردار است. علت اهمیت این بعد تاثیرگذاری بالای دادههای ناصحیح بر روی اطلاعات استخراجشده مبتنی بر این دادهها میباشد که سازمانها براساس این اطلاعات تصمیمگیری می-نمایند. از اینرو تصحیح دادهها به عنوان یک فعالیت مهم در سیستم-های اطلاعاتی محسوبمیشود بهگونهای که دادههای ناصحیح سازمانها را متحمل ضررهای اقتصادی و تصمیمگیریهای اشتباه می-نماید. [1]
فرایند تصحیح یک منبع داده اغلب زمانگیر میباشد اما در قبال هزینههایی که ممکن است سازمانها بر اثر دادههای ناصحیح باشکست متقبل شوند، قابل اغماض است.[2]دادههای ناصحیح ممکن است به دلایلی از قبیل، خطای انسانی در واردنمودن اطلاعات به سیستم و یا خطای سیستمی که در هنگام استخراج دادهها از منابع مختلف، بهوجودآیند. مشکلات متنوعی در دادهها ممکن است باعث بروز خطا در منابع دادهای گردد. ازجمله این مشکلات میتوان به ناقصبودن3، ناسازگاری4، مقادیر ازدست رفته5 و فرمت و دامنه ناهمگون6 اشارهنمود . تصحیح دادهها فرایندی شامل تشخیص دادههای ناقص، ناسازگار و نادرست و تصحیح آنها می-باشد.[3]
تاکنون روشهای متنوعی برای تصحیح دادهها مطرحشدهاست که میتوان این راهکارهای تصحیح دادهها را به دو رویکرد اساسی داده-کاوی و محدودیتهای یکپارچگی7 طبقهبندینمود .[4] روشهای مبتنی بر محدودیتهای یکپارچگی برای تصحیح از وابستگیهای تابعی[5] 8 و وابستگی تابعی شرطی9 استفادهکردهاند. روشهای مطرحشده در حوزه دادهکاوی از هستانشناسی [6]، طبقهبندهایی از قبیل درخت تصمیم [8,7]، شبکه عصبی [9] و قانون بیز [10]، قوانین [11,12] و یادگیری مرکب [9] برای تصحیح داده استفادهنمودهاند. در بعضی از روشها معایبی از جمله توانایی تصحیح در یک نوع دادهای خاص، تعامل با کاربر در حین تصحیح و عدم تفکیکپذیری فاز تشخیص و تصحیح مشاهدهمیشود.
در این مقاله روشی خودکار برای تصحیح خطا ارائهشدهاست. در این روش فرضشده که رکوردهای حاوی خطا از رکوردهای صحیح تشخیص دادهشدهاند، اما مشخص نیست کدام فیلد از رکوردها حاوی خطا میباشد . لذا راهکار پیشنهادی از دو فاز تشخیص فیلد حاوی خطا و تصحیح آن تشکیلشدهاست. در فاز تشخیص از یک روش ترکیبی مبتنی بر طبقهبند بیز و k نزدیکترین همسایگی10 استفادهشدهاست. در فاز تصحیح خطای شناساییشده در فاز اول به وسیله طبقهبند بیز اصلاحمیشود. این روش بدون نیاز به کاربر، به تشخیص و تصحیح خطا میپردازد. همچنین روشارائهشده قادراست خطا را در فیلدهایی با انواع دادهای متفاوت تصحیحنماید. نتایج آزمایشات حاکی از آن است که روش پیشنهادی به طور متوسط %86 از خطاها را شناسایی و تصحیح کردهاست. روش پیشنهادی با روشی که با استقاده از وابستگی تابعی به صورت خودکار به تشخیص میپردازد مورد مقایسه قرارگرفته-است.
مقایسات نشانمیدهد که روش پیشنهادی به طور متوسط %10عملکرد بهتری در تصحیح خطا داشتهاست.بخشهای بعدی این مقاله بدین شرح است. در بخش دوم ابتدا روشهای قبلی بررسی شدهاند. در بخش سوم روش پیشنهادی به طور کامل تشریحمیشود و در بخش چهارم نتایج آزمایشات بر روی یک مجموعه داده بیانشدهاست، که مجموعه داده شامل ویژگی های عددی11 و اسمی12 میباشد. علاوهبراین در بخش چهارم روش پیشنهادی با راهکار تصحیح خطا با استفاده از وابستگی تابعی [13] مقایسهمیگردد. در بخش پایانی خلاصه و نتیجهگیری از مقاله ارائه-میشود.
-2 پیشینه تحقیق
منابع دادهای سازمانها به دلیل خطاهای انسانی یا سیستمی دارای مشکلات کیفی از جمله عدم صحت میباشند. سازمانها جهت اتخاذ تصمیمهای درست باید کیفیت منابع داده خود را بهبود بخشند. راهکارهای متنوعی برای تصحیح دادهها ارائهشدهاست، که در این بخش بهطور خلاصه به برخی از آنها اشارهشدهاست.در [6] یک روش تشخیص و تصحیح خطا مبتنی بر هستان-شناسی و قوانین ارائهشدهاست. این روش در ابتدا به صورت نیمه خودکار عملمینماید و پس از چندین تصحیح تبدیل به یک روش خودکار میگردد. این راهکار برای شناسایی خطاها از هستانشناسی استفادهمینماید، اما برای تصحیح ابتدا تمام مقادیر معتبر موجود در هستانشناسی به ازای مقدار نامعتبر شناساییشده، را به کاربر نمایش-میدهد و کاربر مقدار صحیح را انتخابمیکند.
پس از چندین مرحله سیستم از رفتار کاربر قوانینی را برای تصحیح استخراج میکند و پس از آن سیستم به صورت خودکار به تصحیح میپردازد.روش DMI و SiMI بر پایه الگوریتم EM میباشند با این تفاوت که SiMI توسعهیافته الگوریتم DMI است.[7,8] این دو روش برای تصحیح مقادیر ازدسترفته ارائهشدهاست. در الگوریتم DMI به ازای هر ویژگی از روی مجموعه دادههای صحیح درخت تصمیم ساخته می-شود. سپس مقادیر از دسترفته در هر رکورد با استفاده از درخت متناظر آن تصحیح میگردد. در الگوریتم SiMI به جای درخت تصمیم از جنگل تصمیم استفادهنمودهاست. پس از ساخت جنگل به یافتن تقاطع برگهای درختان پرداخته و تقاطعها را با هدف بیشنه نمودن شباهت بین رکوردها ادغام مینماید.
سپس هر رکورد دارای مقدار از-دسترفته را به یک تقاطع نسبتمی دهد. این دو الگوریتم توانایی تصحیح ویژگیهای عددی و دستهای را دارا میباشند.در [10] الگوریتم SCARE با استفاده از الگوریتمهای یادگیرنده و likelihood برای تصحیح معرفیشدهاست. در این روش فرضشده که محل وقوع خطا مشخص میباشد و فقط به تصحیح آن پرداخته-است. در این راهکار به تعداد ویژگیهای موجود، طبقهبند ساختهمی-شود و طبقهبندها به وسیله دادههای صحیح آموزشدادهمیشوند. هرویژگی غلط به وسیله طبقهبندها پیشبینیمیگردد. سپس به وسیله رسم گراف بهترین مقدار برای هر رکورد انتخاب میشود.
در [11] الگوریتمی با استفاده از قوانینی که توسط کاربر تعیین میگردد، ارائهشدهاست. این قوانین دارای سه قسمت میباشند که قسمت اول بیانگر ویژگیهای مرتبط، قسمت دوم مقادیر ناصحیح ویژگیهای قسمت اول و قسمت آخر مقادیر صحیح برای آن ویژگیها میباشد. در این الگوریتم به جستجوی ویژگیهای قسمت اول و مقایسه مقدار آنها با بخش دوم میپردازد و در صورت یافتن تطابق مقدار ویژگی با قسمت سوم اصلاحمیگردد.راهکار دیگر برای تصحیح ناسازگاریهای موجود در دادهها، استفاده از قوانین ثابت است. در [12] روشی مبتنی بر این قوانین که متعامل با کاربر میباشد، ارائهشدهاست.
در این راهکار قوانین به همراه confidence آنها از منبع داده استخراجمیشود. هر رکورد ممکن است چندین قانون را نقضکند. براساس تعداد قوانینی که هر رکورد نقضمیکند، الگوریتم نمرهای به آن اختصاصمیدهد، که از مجموع confidence قوانین نقضشده به توان یک مقدار تجربی حاصلمی-گردد. هر رکورد به همراه نمره محاسبه شده توسط الگوریتم جهت تصمیمگیری به کاربر نشاندادهمیشود. کاربر بر اساس نمره هر رکورد راجب تصحیح آن تصمیمگیری میکند.استفاده از قوانین ثابت به تنهایی راهکار مناسبی برای تصحیح دادهها نمیباشد. در [4] با استفاده از بهبود قوانین ثابت به تشخیص خطا به صورت خودکار پرداختهشدهاست. این روش قوانینی با مقدار support بسیار پایین را استخراجمیکند. به ازای هر قانون، به جستجوی تعداد رکوردهایی که آن قانون را نقضمیکنند، میپردازد.
در صورتیکه تعداد رکوردهای متناقض با آن قانون از یک مقدار از پیش تعیینشده بیشتر باشد، آن قانون از مجموعه قوانین حذفمی-شود. پس از این مرحله در صورتیکه بتوان برای یک قانون، زیر مجموعههایی از قوانین یافت، برای کاهش افزونگی قوانین، زیر مجموعهها حذفمیشوند. سپس به ازای هر رکورد، تعداد قوانینی که با این رکورد تناقضدارند، محاسبه میگردد. چنانچه تعداد قوانین نقض-شده از یک حد آستانه بیشتر باشد، آن رکورد خطادار میباشد.دسته دیگری از مقالات از محدودیتهای یکپارچگی برای تصحیح دادهها استفادهمینمایند. در [5] روشی برای تصحیح خطا با وابستگی تابعی که یکی از محدودیتهای یکپارچگی میباشد، ارائه-شدهاست.
با توجه به اینکه تصحیحات متنوعی به ازای خطاهای شناساییشده به وسیله وابستگی تابعی قابل ارائهمیباشد، در این روش برای رسیدن به تصحیح بهینه از دو معیار هزینه و تنوع استفادهنموده-است. در واقع هدف کمینه نمودن هزینه تغییرات و بیشنه نمودن تنوع در تصحیحات میباشد.در [13] مدلی برای تصحیح دادهها مبتنی بر وابستگیهای تابعی معرفیشدهاست. در این راهکار وابستگیهای تابعی استخراجشده ثابت نیستند بلکه همزمان با تصحیح دادهها ممکن است وابستگیهای تابعی نیز تغییر نمایند. در ابتدا وابستگیهای تابعی بر اساس امتیازی که از میانگین دو پارامتر حاصلمیشود، در یک لیست به صورت نزولی مرتبمیگردند.
پارامتر اول درجه ناسازگاری هر وابستگی تابعی را با منبع داده مشخصمیکند و پارامتر دوم میزان تناقض وابستگیهای تابعی دیگر با وابستگی تابعی درنظرگرفتهشده را تعیینمیکند. وابستگیهای تابعی به ترتیب از لیست برداشتهمیشوند. این الگوریتم به صورت حریصانه عملمیکند. میزان هزینه تصحیح متناقض با وابستگی تابعی مورد نظر محاسبهمیشود؛ سپس هزینه تصحیح ناسازگاری وابستگی تابعی مورد نظر با وابستگیهای دیگر مورد محاسبه قرارمیگیرد. تصحیحی که کمترین هزینه را داشتهباشد، اعمال میشود و این روند برای وابستگی تابعی دیگر اجرا میشود.وابستگیهای تابعی ممکن است به دلیل دانش ناقص و یا منابع داده غلط در حین استخراج دچار خطا گردند. در [14] الگوریتمی ارائهشدهاست که به طور همزمان به تصحیح وابستگیهای تابعی و دادهها میپردازد.
هدف اصلی در این روش محدودنمودن حداکثر تعداد فیلدهایی که در منبع داده دچار تغییر میگردند و بهدستآوردن مجموعهای از وابستگیهای تابعی که به مجموعه اولیه وابستگی تابعی نزدیک و تناقضی با مجموعه دادهها نداشتهباشند است. این راهکار ابتدا به کمک گراف تناقض، مجموعه داده و وابستگیهای تابعی اولیه، به تصحیح وابستگیهای تابعی میپردازد. پس از اصلاح وابستگی تابعی، به ازای مجموعه جدید وابستگی تابعی و مجموعه دادهها، گراف تناقض رسممیشود و سپس هر تراکنش به صورت تصادفی انتخاب و جهت تصحیح مورد بررسی قرارمیگیرد.
در [15] نیز یک راهکار برای تصحیح ناسازگاریهای موجود در وابستگیهای تابعی و منابعداده معرفیشدهاست، با این تفاوت که این روش برای مجموعه دادههای پویا میباشد.
این روش برای تصحیح، هر بار از روند تصحیح قبلی استفادهمیکند. در این روش از یک طبقهبند برای تصحیح استفادهمیشود که نوع تصحیح را مشخصمیکند و از تصحیحات هر مرحله، آموزشدادهمیشود.برخی از راهکارهای تصحیح معرفیشده، دارای معایبی از قبیل نیمه خودکار بودن و عدم توانایی تشخیص خطا در انواع دادهای مختلف میباشند. هدف این مقاله معرفی راهکاری برای تشخیص فیلد حاوی خطا و تصحیح آن به صورت خودکار میباشد. این روش قادر است خطا را در انواع دادهای مختلف شناسایی و تصحیح نماید. در بخش بعدی جزئیات راهکار پیشنهادی بهطور کامل شرحدادهمیشوند.
-3 روش پیشنهادی
در این بخش به تفصیل به شرح راهکار پیشنهادی برای تصحیح خطا پرداختهشدهاست. در این راهکار فرضشده که رکوردهای صحیح از رکوردهای حاوی خطا تشخیص دادهشده اما محل وقوع خطا در هر رکورد مشخص نمیباشد. از این رو راهکار پیشنهادی از دو فاز تشخیص فیلد حاوی خطا و تصحیح خطا تشکیل شدهاست. در فازتشخیص خطا از k نزدیکترین همسایگی و طبقهبند بیز استفادهشده-است. در فاز تصحیح، خطاهای تشخیصدادهشده، با استفاده از طبقه-بند بیز اصلاحمیگردند. در زیر بخشهای 1-3 و 2-3 این دو فاز به-طور کامل توصیفمیگردد.
-1-3 مرحله اول. تشخیص خطا
قبل از شروع به عملیات تشخیص خطا ابتدا باید ویژگیهای عددی به ویژگی های دستهای تبدیل گردند. برای این کار میتوان از یکی از الگوریتمهای موجود استفادهنمود .[16] در ابتدا به ازای هر رکورد حاوی خطا، k نزدیکترین همسایه از میان رکوردهای صحیح انتخابمیشود. همچنین بیشترین مقدار تکرار شونده در هر فیلد از k نزدیکترین همسایگی هر رکورد در آرایه nearest ذخیرهمیگردد. بخشی از الگوریتم مرحله اول در شکل 1 ارائهشدهاست. خطوط 3-1در شکل 1 این بخش از الگوریتم را نشانمیدهد. فرضشده است که مجموعه داده خطادار، مجموعه داده صحیح و } { ویژگیهای این دو مجموعه داده میباشند.برای تشخیص ویژگی حاوی خطا روند بدین شرح است. ابتدا ویژگی جهت بررسی انتخابمیشود.
به ازای بقیه ویژگیها، هر بار یکی ازویژگیها حذفمیشود که در اولین مرحله برای ، ویژگی حذف-میشود. لذا مجموعه ویژگیها به صورت } { تغییرمی-یابد. طبقهبند بیز به ازای مجموعه رکوردهای صحیح آموزشدادهمی-شود. همچنین ویژگی به عنوان کلاس پیشبینی برای طبقهبند بیز قراردادهمیشود. سپس به وسیله طبقهبند مقدار ویژگی برای رکوردهای حاوی خطا پیشبینیمیگردد. این مقدار برای تمامی رکوردها ذخیرهمیگردد. به همین ترتیب ویژگیهای { } به ترتیب حذف و ویژگیی که در مرحله قبل حذفشده اضافهمیگردد و طبقهبند آموزشدادهمیشود. سپس مقداری به ازای ویژگی پیش-بینیمیکند. درواقع m-1 مقدار برای هر ویژگی پیشبینیمیگردد. به همین روش، m-1 مقدار برای هر یک از ویژگیهای { } پیشبینیمیشود. این مقادیر در آرایه bayse_predict ذخیرهمیشود. در شکل 1خطوط 17-5 مراحل این بخش از الگوریتم را نشانمیدهد.
پس از اینکه به ازای هر ویژگی مقداری پیشبینیگردید، باید براساس مقادیر پیشبینیشده و k نزدیکترین همسایه محل وقوع خطا در هر رکورد مشخصشود. شکل 2 شبه کد این بخش میباشد. به ازای هر رکورد حاوی خطا باید رویهای بدین شرح صورتپذیرد. چنانچه مقدار ویژگی در رکورد r را a بنامیم، تعداد دفعات تکرار a در bayse_predict - r, - و در k نزدیکترین همسایه r محاسبه به ترتیب در آرایه bayse_repeat و knearest_repeat ذخیرهمیشود. این روند به ازای تمام ویژگیهای r اجرامیشود.چنانچه صفرهای موجود در bayse_repeat کوچکتر از باشد، روند الگوریتم بدین شرح است. اگر - bayse_repeat - برابر صفر باشد، تعداد دفعات تکرار - nearest - r, در - bayse_predict - r, محاسبهمیگردد و در nearest_repeat
