عنوان
يک روش بهبود يافته جديد براي کاوش مجموعه اقلام مکرر ماکسيمال مبتني بر تئوري گراف و درخت
نویسنده (گان)
سايباني,محمودرضا;نادي,فرزاد;حيدري,نسرين;گلزاري هرمزي,شهرام
چکیده مقاله
کاوش مجموعه اقلام نقش مهمي در تمام زمينه¬هاي تحقيقاتي داده کاوي مانند: قوانين انجمني، خوشه¬بندي و طبقه¬بندي ايفا مي¬کند. کاوش تمام مجموعه اقلام مکرر منجر به تعداد گسترده¬اي از اقلام مي¬گردد. اين مسئله مي¬تواند به مسئله يافتن مجموعه اقلام مکرر ماکسيمال (MFI) تبديل شود. در اين مقاله يک روش جديد براي کاوش تمام MFIها مبتني بر تئوري گراف و بهبود سرعت آن به وسيله تئوري درخت پيشنهاد شده است. در روش ارائه شده ابتدا يک ماتريس مربعي وابسته به عناصر تراکنش¬هاي پايگاه داده ساخته مي¬شود. سپس گراف ماتريس در نظر گرفته مي¬شود و زيرگراف¬هاي کامل ماکسيمال (کيليک بيشينه) که يک به يک متناظر با MFIها هستند پيدا مي¬شوند. در اين روش ابتدا فرض مي¬شود گراف اوليه کامل است و در هر مرحله گراف شکسته مي¬شود تا به تمامي زيرگراف¬هاي ماکسيمال برسيم. در اين بين هر زيرگرافي که شکسته مي¬شود در يک درخت نگهداري مي¬شود. اين درخت با مکانيزم خاصي براي بالابردن سرعت جستجو استفاده شده است. نتايج آزمايشات مزاياي روش پيشنهادي شامل راندمان، سادگي، دقت، و حافظه مصرفي را تاييد مي¬کند. علاوه بر اين روش پيشنهادي کارايي خوبي در پايگاه¬داده¬هاي بزرگ دارد.

متن کامل مقاله