Кіріспе

Деректер қорындағы айнымалылар арасындағы қызықты қатынастарды табу әдісі

Қауымдастық ережелерді оқыту – үлкен деректер қорындағы айнымалылар арасындағы қызықты қатынастарды анықтауға арналған, ережелерге негізделген машиналық оқыту әдісі. Ол деректер базаларындағы қызығушылық өлшемдерін пайдаланып, анықталған берік ережелерді табуға бағытталған. Кез келген транзакцияда әртүрлі тауарлардың болуымен, қауымдастық ережелер нақты тауарлардың қалай немесе неге байланысты екенін анықтайтын ережелерді ашуға көмектеседі. Ракеш Агравал, Томаш Имилинский және Арун Свами берік ережелер концепциясына сүйене отырып, супермаркеттердегі сату нүктелері (POS) жүйелерімен тіркелген үлкен транзакциялық деректердегі өнімдер арасындағы реттеліліктерді анықтау үшін қауымдастық ережелерді енгізді. Мысалы, супермаркет сату деректеріндегі ереже көрсетуі мүмкін, егер клиент пияз бен картопты бірге сатып алса, ол гамбургер етін де сатып алуы мүмкін. Мұндай ақпарат маркетингтік шаралар туралы шешімдер қабылдауда, мысалы, акциялық бағалар немесе тауарларды орналастыру үшін негіз ретінде қолданылуы мүмкін. Нарықтық талдаудан басқа, қауымдастық ережелер бүгінде веб-қолдануды зерттеу, қатерлерді анықтау, үздіксіз өндіріс және биоинформатика сияқты көптеген салаларда қолданылады. Реттік талдаудан айырмашылығы, қауымдастық ережелерді оқыту әдетте транзакция ішінде немесе транзакциялар арасында тауарлардың ретін ескермейді. Қауымдастық ережелер алгоритмі әртүрлі параметрлерден тұрады, бұл деректерді өңдеуде тәжірибесі жоқ адамдар үшін оны орындауды қиын етуі мүмкін, сонымен қатар көптеген ережелерді түсіну қиын болуы мүмкін.

Пайдалы тұжырымдамалар

+ 2-кесте. 5 транзакция және 7 тауардан тұратын транзакция ID-мен үлгілік деректер базасы сүт нан сары май сыра бекіре жұмыртқа жеміс 1 1 1 0 0 0 0 1 2 0 0 1 0 0 1 1 3 0 0 0 1 1 0 0 4 1 1 1 0 0 1 1 5 0 1 0 0 0 0 0 0 Тұжырымдамаларды түсіндіру үшін супермаркет саласынан шағын мысал келтіреміз. 2-кестеде әрбір жазбада 1 саны тиісті транзакцияда тауардың бар екенін, ал 0 саны осы транзакцияда тауардың жоқ екенін көрсететін тауарларды қамтитын шағын деректер базасы көрсетілген. Супермаркет үшін мысал ретінде, егер сары май мен нан сатып алынса, клиенттер сүт те сатып алады деген ереже берілуі мүмкін. Барлық мүмкін ережелердің ішінде қызықты ережелерді таңдау үшін маңыздылық және қызығушылықтың әртүрлі өлшемдеріне шектеулер қолданылады. Ең белгілі шектеулер – қолдау мен сенімділіктің минималды деңгейлері. Егер itemsets, ассоциациялық ереже және T – берілген деректер базасының транзакциялар жиыны болса. Ескерту: бұл мысал өте шағын. Нақты қолданыста ереже статистикалық тұрғыдан маңызды деп есептелуі үшін жүздеген транзакцияның қолдауы қажет, ал деректер жиынтығында мыңдаған немесе миллиондаған транзакциялар болуы мүмкін.

Тарих

Қауымдастық ережелер ұғымы, әсіресе 1993 жылы Агравал және авторлар тобының GUHA туралы мақаласы арқылы танымал болды, бұл Петр Хайек және авторлар тобы әзірлеген жалпы деректерді талдау әдісі. Барлық қауымдастық ережелерді табу үшін ең төменгі қолдау мен сенімділікті пайдаланудың ерте (шамамен 1989 жылғы) мысалы – мүмкіндіктерге негізделген модельдеу аясы, ол пайдаланушы белгілеген шектеулерден артық қолдауға және сенімділікке ие барлық ережелерді анықтады.

Статистикалық тұрғыдан дұрыс байланыстар

Қауымдастықтарды табудың стандартты тәсілінің бір шектеуі – байланысты болып көрінетін элементтердің жиынтығын іздеу үшін көптеген мүмкін қауымдастықтарды қарастыру арқылы, көптеген жалған қауымдастықтарды табу қаупінің болуы. Бұл деректерде күтпеген жиілікпен кездесетін, бірақ тек кездейсоқ оқиғалардың нәтижесінде пайда болатын элементтердің жиынтығы. Мысалы, егер біз 10 000 элементтен тұратын жиынтықты қарастырып, сол жағында екі элемент, оң жағында бір элемент болатын ережелерді іздесек, онда шамамен 1,000,000,000,000 мұндай ереже болады. Егер тәуелсіздік үшін статистикалық тестті 0,05 маңыздылық деңгейімен қолдансақ, онда ешқандай қауымдастық болмаса, ереже қабылдану ықтималдығы 5% құрайды. Егер ешқандай қауымдастықтар жоқ деп есептесек, бәрібір 50,000,000,000 ереже табуға болады. Статистикалық тұрғыдан дұрыс қауымдастықтарды табу осы қауіпті бақылайды және көп жағдайларда кез келген жалған қауымдастықтарды табу тәуекелін пайдаланушы белгілеген маңыздылық деңгейіне дейін төмендетеді.

Алгоритмдер

Қауымдастық ережелерді жасау үшін көптеген алгоритмдер ұсынылған. Априори, Эклат және FP Growth сияқты белгілі алгоритмдер бар, бірақ олар жұмыстың жартысын ғана атқарады, себебі олар жиі кездесетін тауар жиынтықтарын табатын алгоритмдер. Дерекқорда табылған жиі тауар жиынтықтарынан ережелер жасау үшін одан әрі бір қадам қажет.

FP-өсу алгоритмі

FP – жиі кездесетін үлгі. Алғашқы қаралыста алгоритм транзакциялар жиынтығындағы элементтердің (атрибут мәні жұптарының) қайталануын есептейді және осы сандарды «бас кестеде» сақтайды. Екінші қаралыста ол транзакцияларды trie-ге енгізу арқылы FP ағашының құрылымын жасайды. Ағаштың жылдам өңделуін қамтамасыз ету үшін әрбір транзакциядағы элементтер деректер жиынтығындағы жиілігінің азаю ретімен сұрыпталуы керек. Әрбір транзакциядағы ең төменгі қолдау талабын қанағаттандырмайтын элементтер алынып тасталады. Егер көптеген транзакциялар ең көп кездесетін элементтерді ортақ пайдаланса, FP ағашы ағаш тамырына жақын жоғары сығылуды қамтамасыз етеді. Негізгі деректер жиынтығының осы сығылған нұсқасының рекурсивті өңдеуі кандидат элементтерді жасау және оларды бүкіл деректер базасына қарсы тексерудің (априори алгоритмі сияқты) орнына жиі элементтер жиынтығын тікелей өсіреді. Өсім бас кестедегі ең төменгі қолдауға ие элементті тауып, осы элементпен аяқталатын барлық сұрыпталған транзакцияларды анықтау арқылы жүзеге асырылады. Бұл элементті шақыру. Жаңа шартты ағаш құрылады, ол бастапқы FP ағашының проекциясы болып табылады. Проекцияланған ағаштағы барлық түйіндердің қолдауы қайта есептеледі, әр түйін өзінің балаларының санын алады. Ең төменгі қолдау деңгейіне жетпейтін түйіндер (және оларға байланысты тармақтар) қысқарылады. Рекурсивті өсім, егер шартты түрде жеке элементтер ең төменгі қолдау шегіне жетпесе, тоқтатылады. Түбірден бастап түбірге дейінгі жолдар жиі элементтер жиынтығын құрайды. Осы қадамнан кейін өңдеу бастапқы FP ағашының келесі ең аз қолдауға ие бас элементімен жалғасады. Рекурсивті процесс аяқталғаннан кейін барлық жиі кездесетін элементтер жиынтығы табылады және қауымдастыру ережелерін жасау басталады.

ASSOC

ASSOC процедурасы – GUHA әдісі, ол жылдам биттік операцияларды пайдаланып, жалпылама қауымдастық ережелерін табады. Осы әдіспен анықталған қауымдастық ережелері, мысалы, априори әдісімен алынған ережелерге қарағанда көбірек жалпылама болады, себебі "элементтер" конъюнкция және дизъюнкция арқылы байланыстырылуы мүмкін, сондай-ақ ереженің антецеденті мен консеквенты арасындағы қатынас априоридегідей минималды қолдау мен сенімділікпен шектелмейді: қолдау көрсетілген қызығушылық өлшемдерінің кез келген комбинациясын қолдануға болады.

OPUS іздеу

OPUS – ережелерді табуға арналған тиімді алгоритм. Көптеген басқа әдістерден айырмашылығы, ол минималды қолдау сияқты монотонды немесе антимонотонды шектеулерді қажет етпейді. Алғашқыда белгілі бір нәтижеге арналған ережелерді табу үшін қолданылған, кейіннен кез келген элементті нәтиже ретінде қолдануға болатын ережелерді табу үшін кеңейтілді. OPUS іздеуі – танымал Magnum Opus қауымдастықтарды табу жүйесінің негізгі технологиясы болып табылады.

Кітаптар

М. Хасслердің "Ассоциация ережелері бойынша түсіндірмелі библиографиясы"