مقدمه
فرآیند کاوش الگو ممکن است هزاران الگو را از یک مجموعه داده مشخص کشف کند، که بسیاری از آنها ممکن است در نهایت بیارتباط یا بیعلاقه برای کاربران باشند. اغلب، کاربر درک خوبی از اینکه کدام «جهت» کاوش ممکن است به الگوهای جالب و «شکل» الگوها یا قوانینی که میخواهد پیدا کند، منجر شود، دارد. آنها همچنین ممکن است درک «شرایطی» برای قوانین داشته باشند که کشف قوانین خاصی را که میدانند مورد توجه نیستند، از بین میبرد. بنابراین، یک گزینه خوب این است که کاربران چنین شهود یا انتظاراتی را به عنوان محدودیت برای محدود کردن فضای جستجو یا انجام اصلاح محدودیت به صورت تعاملی بر اساس نتایج کاوش میانی مشخص کنند. این استراتژی به عنوان کاوش مبتنی بر محدودیت شناخته میشود. محدودیتها میتوانند شامل موارد زیر باشند:
• محدودیتهای نوع دانش: این محدودیتها نوع دانشی را که باید کاوش شود، مانند ارتباط، همبستگی، طبقهبندی یا خوشهبندی، مشخص میکنند.
• محدودیتهای داده: این محدودیتها مجموعه دادههای مرتبط با کار را مشخص میکنند.
• محدودیتهای ابعاد/سطح: این محدودیتها ابعاد (یا ویژگیهای) مطلوب دادهها، سطوح انتزاع یا سطح سلسله مراتب مفاهیم مورد استفاده در کاوش را مشخص میکنند.
• محدودیتهای جالب بودن: این محدودیتها آستانههایی را برای معیارهای آماری جالب بودن قانون مانند پشتیبانی، اطمینان و همبستگی مشخص میکنند.
• محدودیتهای قانون/الگو: این محدودیتها، شکل یا شرایط قوانین/الگوهایی را که باید کاوش شوند، مشخص میکنند. چنین محدودیتهایی ممکن است به صورت متارول (قالبهای قانون)، به عنوان حداکثر یا حداقل تعداد گزارههایی که میتوانند در مقدم یا تالی قانون رخ دهند، یا به عنوان روابط بین ویژگیها، مقادیر ویژگیها و/یا مجموعها بیان شوند.
این محدودیتها را میتوان با استفاده از یک زبان پرسوجوی دادهکاوی سطح بالا یا یک رابط کاربری گرافیکی مبتنی بر الگو مشخص کرد.
چهار نوع محدودیت اول قبلاً در کتاب مورد بررسی قرار گرفتهاند. در این بخش، ما در مورد استفاده از محدودیتهای قانون/الگو برای تمرکز بر وظیفه کاوش بحث میکنیم. این شکل از کاوش مبتنی بر محدودیت به کاربران اجازه میدهد تا قوانین یا الگوهایی را که میخواهند کشف کنند، توصیف کنند و در نتیجه فرآیند دادهکاوی را مؤثرتر سازند. در عین حال، میتوان از یک بهینهساز پرسوجوی کاوش پیشرفته برای بهرهبرداری از محدودیتهای مشخصشده توسط کاربر استفاده کرد و در نتیجه فرآیند کاوش را کارآمدتر ساخت.
در برخی موارد، کاربر ممکن است دوست داشته باشد برخی از شکلهای نحوی قوانین (که متارول نیز نامیده میشوند) را که به کاوش آنها علاقهمند است، مشخص کند. چنین شکلهای نحوی به کاربر کمک میکند تا انتظار خود را بیان کند و همچنین به سیستم کمک میکند تا فضای جستجو را محدود کرده و کارایی کاوش را بهبود بخشد. به عنوان مثال، یک متارول میتواند به شکل خرید (X,“iPad”) ⇒ P1(X,Y)∧P2(X,W)
که در آن P1 و P2 متغیرهای پیش بینی شده هستند که میتوانند در طول فرآیند کاوش، به ویژگیهای موجود در یک پایگاه داده داده شده نمونهسازی شوند، X متغیری است که نشاندهنده یک مشتری است و Y و W به ترتیب مقادیر ویژگیهای اختصاص داده شده به P1 و P2 را میگیرند. معمولاً، کاربر میتواند لیستی از ویژگیهایی را که برای نمونهسازی با P1 و P2 در نظر گرفته میشوند، مشخص کند. در غیر این صورت، ممکن است از یک مجموعه پیشفرض استفاده شود.
یک فراقاعده، فرضیهای را در مورد روابطی که کاربر علاقهمند به بررسی یا تأیید آنهاست، تشکیل میدهد. با پیروی از چنین الگویی، یک سیستم میتواند قوانین مشخصی را که با فراقاعده داده شده مطابقت دارند، کاوش کند. احتمالاً، قانون (5.12) که با فراقاعده (5.11) مطابقت دارد، به عنوان نتایج کاوش بازگردانده میشود.
تعداد خرید(X، “iPad”)⇒ سن (X,“20..29”)∧ درآمد (X,“41K..60K”)
برای تولید نتایج کاوش جالب و مفید، کاربران ممکن است روشهای متعددی برای تعیین محدودیتهای قانون/الگو داشته باشند. برای یک سیستم کاوش مطلوب است که از محدودیتهای قانون/الگو برای هرس کردن فضای جستجو استفاده کند، یعنی این محدودیتها را عمیقاً وارد فرآیند کاوش کند و در عین حال از کامل بودن پاسخ برگشتی برای یک پرسوجوی کاوش اطمینان حاصل کند. با این حال، این یک کار مهم نیست و مطالعه آن منجر به کاوش الگوی مبتنی بر محدودیت میشود.
برای مطالعه نحوه استفاده از محدودیتها در کاوش الگوهای مکرر یا قوانین انجمنی، مثال اجرایی زیر را بررسی میکنیم.
مثال ۵.۱۰. محدودیتهای کاوش تراکنشهای خرید. فرض کنید یک پایگاه داده تراکنش خرید چندبعدی شامل روابط مرتبط زیر باشد:
• item(item_ID, item_name, description, category, price)
• sales(transaction_ID, day, month, year, store_ID, city)
• trans_item(item_ID, transaction_ID)
در اینجا، جدول آیتم شامل ویژگیهای item_ID، item_name، description، category و price است؛ جدول thesales شامل ویژگیهای transaction_ID، day، month، year، store_ID و city است؛ و دو جدول از طریق ویژگیهای کلید خارجی، item_ID و transaction_ID، در جدول trans_item به هم مرتبط هستند.
یک پرسوجوی دادهکاوی ممکن است شامل چندین محدودیت باشد، به عنوان مثال، ممکن است یک پرسوجو داشته باشیم: “از فروش در شیکاگو در سال 2020، الگوهایی (یعنی مجموعههای آیتم) را پیدا کنید که کدام اقلام ارزان (که در آن مجموع قیمتها کمتر از 10 دلار است) در همان تراکنش با کدام اقلام گران (که در آن حداقل قیمت 50 دلار است) ظاهر میشوند (بنابراین ممکن است تبلیغ شوند).” این پرسوجو شامل چهار محدودیت زیر است: (1) sum(I.price) < $10، که در آن I نشان دهنده item_ID یک کالای ارزان است؛ (2) min(J.price)≥ $50، که در آن J نشان دهنده item_ID یک کالای گران است؛ (3) T.city= Chicago؛ و (4) T.year=2020، که در آن T نشان دهنده transaction_ID است.
در کاوش الگوی مبتنی بر محدودیت، فضای جستجو را میتوان در فرآیند کاوش با دو استراتژی هرس کرد: هرس فضای جستجوی الگو و هرس فضای جستجوی داده. اولی الگوهای کاندید را بررسی میکند و تصمیم میگیرد که آیا یک الگو باید از پردازش بیشتر حذف شود یا خیر. به عنوان مثال، اگر تمام ابرالگوی آن در فرآیند کاوش باقیمانده بیفایده باشد، مثلاً بر اساس ویژگی Apriori، ممکن است یک الگو را هرس کند. دومی مجموعه دادهها را بررسی میکند تا مشخص کند که آیا یک شیء داده خاص قادر به مشارکت در تولید بعدی الگوهای رضایتبخش در فرآیند کاوش باقیمانده نخواهد بود (از این رو شیء داده را با خیال راحت هرس میکند). این استراتژیهای هرس را در بخشهای بعدی بررسی میکنیم.
هرس فضای الگو با محدودیتهای هرس الگو
بر اساس اینکه چگونه یک محدودیت ممکن است با فرآیند کاوش الگو تعامل داشته باشد، محدودیتهای کاوش الگو را به چهار دسته تقسیم میکنیم: (1) ضدیکنواختی، (2) یکنواختی، (3) قابل تبدیل و (4) غیرقابل تبدیل. بیایید آنها را یکی یکی بررسی کنیم.
ضدیکنواختی الگو
گروه اول محدودیتها با ضدیکنواختی الگو مشخص میشوند. محدودیت C در صورتی ضدیکنواختی الگو است که ویژگی زیر را داشته باشد: اگر یک مجموعه اقلام، محدودیت C را برآورده نکند، هیچ یک از مجموعههای بالای آن، C را برآورده نخواهند کرد.
بیایید محدودیت “C1: مجموع(قیمت I) ≤ 100 دلار” را بررسی کنیم و ببینیم اگر محدودیت به جستجوی کاوش تراکنش خرید ما اضافه شود، چه اتفاقی ممکن است بیفتد. فرض کنید ما در حال کاوش مجموعه اقلام با اندازه k در kامین مرحله با استفاده از الگوریتم Apriori یا موارد مشابه هستیم. اگر مجموع قیمت اقلام در یک مجموعه اقلام کاندید S1 بیشتر از 100 دلار باشد، این مجموعه اقلام باید از فضای جستجو حذف شود، زیرا نه تنها مجموعه فعلی نمیتواند محدودیت را برآورده کند، بلکه اضافه کردن اقلام بیشتر به مجموعه (با فرض اینکه قیمت هر کالا کمتر از صفر نباشد) هرگز نمیتواند محدودیت را برآورده کند. توجه داشته باشید که حذف این الگو (مجموعه اقلام مکرر) برای محدودیت C1 محدود به چارچوب تولید و آزمایش کاندید Apriori نیست. به عنوان مثال، به همین دلیل، S1 باید در چارچوب رشد الگو حذف شود، زیرا الگوی S1 و رشد بیشتر از آن هرگز نمیتواند محدودیت C1 را برآورده کند. این ویژگی ضدیکنواختی نامیده میشود زیرا یکنواختی یک محدودیت معمولاً به این معنی است که اگر یک الگوی p محدودیت C را برآورده کند، گسترش بیشتر آن همیشه C را برآورده خواهد کرد. با این حال، در اینجا ادعا میکنیم که این محدودیت ممکن است رفتار معکوس داشته باشد: هنگامی که الگوی p1 محدودیت C1 را نقض کند، رشد (یا گسترش) بیشتر آن همیشه C1 را نقض خواهد کرد. هرس الگو با استفاده از خاصیت آنتیمانوتونیک میتواند در هر تکرار الگوریتمهای سبک Apriori اعمال شود تا به بهبود کارایی فرآیند کلی کاوش کمک کند و در عین حال کامل بودن وظیفه دادهکاوی را تضمین کند.
جالب است توجه داشته باشید که خود ویژگی بسیار اساسی Apriori (که بیان میکند همه زیرمجموعههای غیرتهی یک مجموعه اقلام مکرر نیز باید مکرر باشند) آنتیمانوتونیک است: اگر یک مجموعه اقلام حداقل آستانه پشتیبانی را برآورده نکند، هیچ یک از ابرمجموعههای آن نمیتوانند. این ویژگی در هر تکرار الگوریتم Apriori برای کاهش تعداد مجموعه اقلام کاندید برای بررسی استفاده شده است، در نتیجه فضای جستجو برای کاوش الگوهای مکرر کاهش مییابد.
محدودیتهای زیادی وجود دارند که آنتیمانوتونیک هستند. برای مثال، محدودیت «min(J.price)≥$50» و «count(I)≤10» ضدیکنواختی هستند. با این حال، محدودیتهای زیادی نیز وجود دارند که ضدیکنواختی نیستند. برای مثال، محدودیت «avg(I.price) ≤ $10» ضدیکنواختی نیست. دلیل این امر آن است که حتی برای یک مجموعه اقلام S که این محدودیت را برآورده نمیکند، یک ابرمجموعه ایجاد شده با اضافه کردن برخی اقلام (ارزان) ممکن است آن را با این محدودیت مطابقت دهد. از این رو، اعمال این محدودیت در فرآیند دادهکاوی، کامل بودن فرآیند دادهکاوی را تضمین نمیکند. فهرستی از محدودیتهای رایج در ستون اول جدول 5.3 ارائه شده است. ضدیکنواختی محدودیتها در ستون دوم نشان داده شده است. برای سادهسازی بحث، فقط عملگرهای وجود (مثلاً =,∈، اما نه =,/
عملگرهای مقایسه (یا مهار) با تساوی (مثلاً ≤,⊆) داده شدهاند.
یکنواختی الگو
∈ ودسته دوم محدودیتها، یکنواختی الگو است. محدودیت C یکنواختی الگو است اگردارای ویژگی زیر باشد: اگر یک مجموعه اقلام، محدودیت C را برآورده کند، همه ابرمجموعههای آن، C را برآورده خواهند کرد.
بیایید محدودیت دیگری به نام “C2: sum(I.price) ≥ $100” را بررسی کنیم و ببینیم اگر این محدودیت به پرسوجوی نمونه ما اضافه شود، چه اتفاقی ممکن است بیفتد. فرض کنید ما در حال کاوش مجموعه اقلام با اندازه k در تکرار kام با استفاده از الگوریتم Apriori یا موارد مشابه هستیم. اگر مجموع قیمت اقلام در یک مجموعه اقلام کاندید S1 کمتر از 100 دلار باشد، این مجموعه اقلام نباید از فضای جستجو حذف شود، زیرا اضافه کردن اقلام بیشتر به مجموعه فعلی ممکن است باعث شود که مجموعه اقلام محدودیت را برآورده کند. با این حال، هنگامی که مجموع قیمت اقلام در مجموعه اقلام S محدودیت C2 را برآورده کند، دیگر نیازی به بررسی این محدودیت برای S نیست زیرا اضافه کردن اقلام بیشتر مقدار مجموع را کاهش نمیدهد و همیشه محدودیت را برآورده میکند.
به عبارت دیگر، اگر یک مجموعه اقلام محدودیت را برآورده کند، تمام ابرمجموعههای آن نیز این کار را انجام میدهند. لطفاً توجه داشته باشید که این ویژگی مستقل از الگوریتمهای خاص دادهکاوی الگوی تکراری است. به عنوان مثال، همان روش هرس باید برای الگوریتمهای رشد الگو نیز اتخاذ شود.
در عمل محدودیتهای یکنواخت الگوی زیادی وجود دارد. به عنوان مثال، “min(I.price) ≤ $10” و “count(I) ≥ 10” از این قبیل محدودیتها هستند. الگوی یکنواختی فهرست محدودیتهای متداول در ستون سوم جدول 5.3 نشان داده شده است.
|
جدول ۵.۳ توصیف محدودیتهای هرس الگوی رایج. |
|||
|
محدودیت |
آنتیمونوتیک |
تکرنگ |
مختصر و مفید |
|
v ∈ S |
no |
yes |
yes |
|
S ⊇ V |
no |
yes |
yes |
|
S ⊆ V |
yes |
no |
yes |
|
min(S) ≤ v |
no |
yes |
yes |
|
min(S) ≥ v |
yes |
no |
yes |
|
max(S) ≤ v |
yes |
no |
yes |
|
max(S) ≥ v |
no |
yes |
yes |
|
count(S) ≤ v |
yes |
no |
no |
|
count(S) ≥ v |
no |
yes |
no |
|
sum(S) ≤ v (∀a ∈ S, a ≥ 0) |
yes |
no |
no |
|
sum(S) ≥ v (∀a ∈ S, a ≥ 0) |
no |
yes |
no |
|
range(S) ≤ v |
yes |
no |
no |
|
range(S) ≥ v |
no |
yes |
no |
|
avg(S) θ v, θ ∈ {≤, ≥} |
convertible |
convertible |
no |
|
support (S) ≥ ξ |
yes |
no |
no |
|
support (S) ≤ ξ |
no |
yes |
no |
|
all_conf idence(S) ≥ ξ |
yes |
no |
no |
|
all_conf idence(S) ≤ ξ |
no |
yes |
no |
محدودیتهای تبدیلپذیر: مرتبسازی دادهها در تراکنشها
محدودیتهایی وجود دارند که نه الگوی ضدیکنواخت هستند و نه الگوی یکنواخت. به عنوان مثال، اعمال مستقیم محدودیت “C3: میانگین(I.price)≤ $10” به عمق یک فرآیند کاوش تکراری دشوار است، زیرا مورد بعدی که به مجموعه اقلام فعلی اضافه میشود میتواند گرانتر یا ارزانتر از قیمت متوسط مجموعه اقلام محاسبه شده تاکنون باشد. در نگاه اول، بررسی محدودیتی که چنین محدودیتهایی را در کاوش الگو اعمال میکند، دشوار به نظر میرسد. با این حال، با توجه به اینکه اقلام موجود در یک تراکنش را میتوان به عنوان یک مجموعه در نظر گرفت، و بنابراین میتوان اقلام موجود در یک تراکنش را به هر ترتیب خاصی مرتب کرد، جالب توجه است که وقتی اقلام موجود در مجموعه اقلام به ترتیب صعودی یا نزولی قیمت مرتب میشوند، میتوان هرس کارآمد را در کاوش مجموعه اقلام مکرر مانند قبل بررسی کرد. در این زمینه، میتوان چنین نوع محدودیتهایی را به محدودیتهای یکنواخت یا ضدیکنواخت تبدیل کرد. از این رو، چنین محدودیتهایی را محدودیتهای تبدیلپذیر مینامیم. بیایید محدودیت C3 را دوباره بررسی کنیم. اگر اقلام موجود در تمام تراکنشها در فرآیند کاوش رشد الگو به ترتیب صعودی قیمت مرتب شوند (یا اقلام موجود در هر تراکنش به این ترتیب اضافه شوند)، محدودیت C3 ضدیکنواخت میشود، زیرا اگر یک مجموعه اقلام I این محدودیت را نقض کند (یعنی با قیمت متوسط بیشتر از 10 دلار)، افزودن بیشتر اقلام گرانتر به مجموعه اقلام هرگز آن را مطابق با محدودیت نمیکند. به طور مشابه، اگر اقلام موجود در تمام تراکنش به ترتیب نزولی قیمت مرتب شوند (یا به مجموعه اقلام در حال کاوش اضافه شوند)، یکنواخت میشود، زیرا اگر مجموعه اقلام این محدودیت را برآورده کند (یعنی با قیمت متوسط بیشتر از 10 دلار نباشد)، افزودن اقلام ارزانتر به مجموعه اقلام فعلی همچنان باعث میشود قیمت متوسط بیشتر از 10 دلار نباشد. آیا الگوریتم شبیه به Apriori از محدودیت قابل تبدیل برای هرس فضای جستجوی خود به خوبی استفاده خواهد کرد؟ متأسفانه، بررسی ارضای چنین محدودیتی را نمیتوان به راحتی با یک الگوریتم تولید و آزمایش کاندید شبیه به Apriori انجام داد، زیرا یک الگوریتم شبیه به Apriori مستلزم آن است که همه زیرمجموعههای {ab}، {bc}، {ac}) از یک کاندید {abc} باید مکرر باشند و محدودیت را برآورده کنند. با این حال، حتی خود {abc} میتواند یک مجموعه اقلام معتبر باشد (یعنی avg({abc}.price) ≤ $10)، زیرمجموعه {bc} ممکن است C3 را نقض کرده باشد، و ما هرگز قادر به تولید {abc} نخواهیم بود زیرا {bc} هرس شده است.
فرض کنید S مجموعهای از اقلام را نشان میدهد و مقدار آن price است. علاوه بر “avg(S)≤ c” و “avg(S)≥ c”، محدودیتهای قابل تبدیل دیگری نیز وجود دارد. به عنوان مثال، “variance(S) ≥ c”، “standard_deviation(S)≥ c” محدودیتهای قابل تبدیل هستند. با این حال، این بدان معنا نیست که هر محدودیت غیریکنواخت یا غیرآنتیمونوتیک قابل تبدیل است. به عنوان مثال، اگر تابع تجمیع برای مقادیر آیتمها در مجموعه رفتار نمونهگیری تصادفی داشته باشد، مرتب کردن آیتمها به ترتیب افزایشی یا کاهشی یکنواخت دشوار خواهد بود. بنابراین، هنوز دستهای از محدودیتها وجود دارند که غیرقابل تبدیل هستند. خبر خوب این است که اگرچه برخی محدودیتهای سخت وجود دارند که قابل تبدیل نیستند، اما سادهترین و پرکاربردترین محدودیتها متعلق به یکی از سه دستهای هستند که ما توضیح دادیم، آنتیمونوتیک، یکنواخت و قابل تبدیل، که میتوان روشهای کارآمد کاوش محدودیت را برای آنها اعمال کرد.
هرس کردن فضای داده با محدودیتهای هرس کردن داده
دومین روش هرس کردن فضای جستجو در کاوش الگوهای مکرر مبتنی بر محدودیت، هرس کردن فضای داده است. این استراتژی، قطعات داده را در صورتی که در تولید بعدی الگوهای رضایتبخش در فرآیند کاوش مشارکت نداشته باشند، هرس میکند. ما در این بخش، ناهمگنی دادهها را بررسی میکنیم.
جالب توجه است که بسیاری از محدودیتها، ناهمگنی داده هستند به این معنا که در طول فرآیند کاوش،اگر یک ورودی داده نتواند محدودیت ناهمگنی داده را بر اساس الگوی فعلی برآورده کند، میتوان آن را هرس کرد. ما آن را هرس میکنیم زیرا قادر به مشارکت در تولید هیچ ابرالگویی از الگوی فعلی در فرآیند کاوش باقیمانده نخواهد بود.
مثال ۵.۱۱. ناهمگنی دادهها. ما محدودیت C1 را بررسی میکنیم: sum(I.price)≥ $100، یعنی مجموع قیمت اقلام در الگوی کاوش شده نباید کمتر از ۱۰۰ دلار باشد. فرض کنید که مجموعه اقلام پرتکرار فعلی، S، محدودیت C1 را برآورده نمیکند (مثلاً به این دلیل که مجموع قیمت اقلام در S برابر با 50 دلار است). اگر اقلام پرتکرار باقیمانده در یک تراکنش Ti نتوانند S را وادار به برآورده کردن محدودیت کنند (مثلاً اقلام پرتکرار باقیمانده در Ti عبارتند از {i2.price = $5,i5.price = $10,i8.price = $20})، آنگاه Ti نمیتواند در الگوهایی که از S استخراج میشوند، مشارکت کند و میتواند از استخراج بیشتر حذف شود. توجه داشته باشید که چنین حذفی ممکن است با اعمال آن فقط در ابتدای فرآیند استخراج، مؤثر نباشد. دلیل این امر این است که ممکن است تراکنشهایی را که مجموع اقلام آنها محدودیت C1 را برآورده نمیکند، حذف کند. با این حال، ممکن است با موردی مواجه شویم که i3.price = $90 باشد، اما بعداً در فرآیند استخراج، i3 با S در مجموعه دادههای تراکنش، نادر میشود و در این مرحله، Ti باید حذف شود. بنابراین، چنین بررسی و هرس کردنی باید در هر تکرار برای کاهش فضای جستجوی داده اعمال شود.
توجه داشته باشید که محدودیت C1 یک محدودیت یکنواخت در رابطه با هرس فضای الگو است. همانطور که دیدهایم، این محدودیت یکنواخت الگو قدرت بسیار محدودی برای کاهش فضای جستجو در هرس الگو دارد. با این حال، همین محدودیت، ضدیکنواختی داده است و میتواند برای کاهش مؤثر فضای جستجوی داده استفاده شود.
برای یک محدودیت ضدیکنواختی الگو، مانند C2: sum(I.price) ≤ $100، میتوانیم هر دو فضای جستجوی الگو و داده را همزمان هرس کنیم. بر اساس مطالعه ما در مورد هرس الگو، ما از قبل میدانیم که اگر مجموع قیمتهای موجود در مجموعه اقلام فعلی بیش از 100 دلار باشد، میتوان آن را هرس کرد (زیرا گسترش بیشتر آن هرگز نمیتواند C2 را برآورده کند). در عین حال، میتوانیم هر مورد باقی مانده در تراکنش Ti را که نمیتواند محدودیت C2 را معتبر کند، هرس کنیم. برای مثال، اگر مجموع قیمت اقلام در مجموعه اقلام فعلی S برابر با ۹۰ دلار باشد، هر کالایی که قیمت آن بیش از ۱۰ دلار در اقلام پرتکرار باقیمانده در Ti باشد، میتواند هرس شود.
اگر هیچ یک از اقلام باقیمانده در Ti نتواند محدودیت را معتبر کند، کل تراکنش Ti باید هرس شود.
محدودیتهای الگویی را در نظر بگیرید که نه آنتیمانوتونیک هستند و نه مونوتونیک، مانند “C3: avg(I.price) ≤ 10”. این محدودیتها میتوانند آنتیمانوتونیک داده باشند، زیرا اگر اقلام باقیمانده در یک تراکنش Ti نتوانند محدودیت را معتبر کنند، آنگاه Ti نیز میتواند هرس شود. بنابراین، محدودیتهای آنتیمانوتونیک داده میتوانند برای هرس فضای داده مبتنی بر محدودیت بسیار مفید باشند.
توجه داشته باشید که هرس فضای جستجو توسط آنتیمانوتونیک داده فقط به یک الگوریتم دادهکاوی مبتنی بر رشد الگو محدود میشود، زیرا هرس یک ورودی داده بر اساس اینکه آیا میتواند به یک الگوی خاص کمک کند یا خیر، تعیین میشود. اگر از الگوریتم Apriori استفاده شود، نمیتوان از خاصیت ضدیکنواختی دادهها برای هرس کردن فضای داده استفاده کرد، زیرا دادهها با تمام الگوهای فعال فعلی مرتبط هستند. در هر تکرار، معمولاً الگوهای فعال زیادی وجود دارد. ورودی دادهای که نمیتواند در تشکیل ابرالگوهای یک الگوی مشخص نقش داشته باشد، ممکن است همچنان بتواند در ابرالگوهای سایر الگوهای فعال نقش داشته باشد. بنابراین، قدرت هرس کردن فضای داده میتواند برای الگوریتمهای مبتنی بر رشد غیرالگویی بسیار محدود باشد.
هرس فضای کاوش با محدودیتهای اختصار
برای کاوش الگو، دسته دیگری از محدودیتها به نام محدودیتهای اختصار وجود دارد. محدودیت c مختصر است اگر بتوان آن را با هرس مستقیم برخی از اشیاء داده از پایگاه داده یا با شمارش مستقیم همه و فقط آن مجموعههایی که تضمین میشود محدودیت را برآورده میکنند، اعمال کرد. مورد اول، داده مختصر نامیده میشود زیرا هرس مستقیم فضای داده را امکانپذیر میکند، در حالی که مورد دوم، الگو مختصر نامیده میشود زیرا تولید مستقیم الگو را با شروع از الگوهای اولیهای که محدودیت را برآورده میکنند، امکانپذیر میکند. بیایید چند مثال را بررسی کنیم.
ابتدا، محدودیت i ∈ S را بررسی میکنیم، یعنی الگو باید شامل آیتم i باشد. برای یافتن الگوهایی که شامل آیتم i هستند، میتوان فقط پایگاه داده i-projected را کاوش کرد زیرا یک تراکنش شامل i نیست و به الگوهای حاوی i کمکی نخواهد کرد و برای آنهایی که شامل i هستند، همه موارد باقی مانده میتوانند در بقیه فرآیند کاوش شرکت کنند. این امر هرس فضای داده را در ابتدا تسهیل میکند و بنابراین این محدودیت هم داده و هم الگو را مختصر میکند. از سوی دیگر، برای یافتن الگوهایی که شامل آیتم i نیستند (یعنی i/ ∈S)، میتوان آن را با کاوش در پایگاه داده تراکنش با حذف i کاوش کرد، زیرا i در یک تراکنش به الگو کمکی نخواهد کرد. این امر هرس فضای داده را در ابتدا تسهیل میکند و همچنین هرس فضای الگو را نیز تسهیل میکند (زیرا از استخراج هرگونه الگوی میانی حاوی i جلوگیری میکند، بنابراین
این محدودیت مختصر است و هم مختصر الگو و هم مختصر داده است.
به عنوان مثال دیگر، محدودیت “min(S.price) ≥ $50” مختصر داده است زیرا میتوانیم همه اقلامی را که قیمت آنها کمتر از 50 دلار است از تراکنشها حذف کنیم زیرا هر کالایی که قیمت آن کمتر از 50 دلار نباشد در فرآیند کاوش الگو مشارکت نخواهد کرد. به طور مشابه، min(S.Price) ≤ v مختصر الگو است زیرا میتوانیم فقط با اقلامی شروع کنیم که قیمت آنها بیشتر از v نباشد.
توجه داشته باشید که همه محدودیتها مختصر نیستند. به عنوان مثال، محدودیت sum(S.Price) ≥ v مختصر نیست زیرا نمیتوان از آن برای تسهیل هرس هر مورد از یک تراکنش در ابتدای فرآیند استفاده کرد زیرا مجموع قیمت یک مجموعه اقلام S به افزایش خود ادامه خواهد داد.
خلاصه بودن الگو در لیست محدودیتهای مبتنی بر مقادیر اولیه SQL در ستون چهارم جدول 5.3 نشان داده شده است.
از بحث بالا، میتوانیم ببینیم که یک محدودیت ممکن است به بیش از یک دسته تعلق داشته باشد. به عنوان مثال، محدودیت “min(I.price) ≤ $10” هم الگوی یکنواخت و هم داده مختصر است. در این حالت، میتوانیم از خلاصه بودن دادهها برای شروع فقط با اقلامی که قیمت آنها بیش از 10 دلار نیست استفاده کنیم.
با انجام این کار، به طور ضمنی خاصیت یکنواختی الگو را اعمال کردهایم، زیرا به محض اینکه محدودیت در نقطه شروع استفاده شود (یعنی برآورده شود)، دیگر نیازی به بررسی آن نخواهیم داشت. به عنوان مثال دیگر، محدودیت “c0: sum(I.price) ≥ $100” هم الگوی یکنواخت و هم داده غیر یکنواخت است، میتوانیم از داده غیر یکنواخت برای هرس کردن تراکنشهایی که قیمت اقلام باقیمانده آنها … است استفاده کنیم. جمع کردن نمیتواند به ۱۰۰ دلار برسد. در عین حال، وقتی یک الگو c0 را برآورده کند، نیازی به بررسی مجدد c0 در فرآیند کاوش نخواهیم داشت.
در برنامهها، کاربر ممکن است یک پرسوجوی کاوش ارائه دهد که ممکن است شامل چندین محدودیت باشد. در بسیاری از موارد، میتوان چندین محدودیت را با هم اعمال کرد تا فضای کاوش را به طور مشترک هرس کنند، که ممکن است منجر به پردازش کارآمدتر شود. با این حال، در برخی موارد، محدودیتهای مختلف ممکن است برای اجرای مؤثر محدودیت، به ویژه برای محدودیتهای قابل تبدیل، نیاز به ترتیب اقلام متفاوتی داشته باشند. به عنوان مثال، یک پرسوجو ممکن است شامل هر دو مورد c1: avg(S.profit)>20 و c2: avg(S.price)<50 باشد. متأسفانه، مرتبسازی بر اساس سود به ترتیب نزولی ارزش ممکن است منجر به ترتیب نزولی ارزش قیمت اقلام مرتبط با آنها نشود. در این حالت، بهتر است تخمین زده شود که کدام ترتیب ممکن است منجر به هرس مؤثرتر شود و کاوش پس از ترتیب هرس مؤثرتر منجر به پردازش کارآمدتر خواهد شد. فرض کنید یافتن الگوهایی که c1 را برآورده میکنند دشوار است اما یافتن الگویی که c1 را برآورده میکند آسان است. c2. سپس سیستم باید اقلام موجود در تراکنشها را به ترتیب نزولی سود مرتب کند. هنگامی که میانگین سود مجموعه اقلام فعلی به کمتر از 20 دلار کاهش یافت، میتوان مجموعه اقلام را دور انداخت (یعنی دیگر نیازی به استخراج با آن نیست) که منجر به پردازش کارآمد خواهد شد.
