অ্যাসোসিয়েশন রুলসঃ অ্যাপ্রিওরি অ্যালগরিদম

অ্যাসোসিয়েশন রুলস কি ?

অ্যাসোসিয়েশন রুলস হচ্ছে ডেটার ভেতর থেকে অদেখা ইনসাইটস বের করার চমৎকার একটি পদ্ধতি। অ্যাসোসিয়েশন রুলস বোঝানোর জন্য আমরা মূলত অ্যাপ্রিওরি অ্যালগরিদম নিয়েই আলোচনা করবো। অ্যাসোসিয়েশন রুলস শব্দটি থেকেই বোঝা যায় এর মানে হচ্ছে সম্পর্কের নিয়ম। ধরুন আপনি পুরান ঢাকায় গিয়েছেন কাচ্চি বিরিয়ানি খেতে। বিরিয়ানি খাওয়া শেষ হলে নিশ্চয়ই বোরহানি অর্ডার করবেন, সাধারনত বেশিরভাগ ক্ষেত্রে আমরা বিরিয়ানির সাথে বোরহানিও খেয়ে থাকি। সুতরাং বিরিয়ানির সাথে বোরহানির এই সম্পর্কটাই হচ্ছে অ্যাসোসিয়েশন রুলস। অ্যাসোসিয়েশন রুলসকে অনেকে " ব্রেড এন্ড বাটার " রুলস বলে থাকে, সাধারনত ব্রেড কিনলে তার সাথে বাটারও কিনতে হয় , বাটার দিয়ে ব্রেড খাওয়ার জন্য ( এই উদাহরনটি বাইরের দেশে বেশী প্রযোজ্য ) । অ্যাসোসিয়েশন রুলস এর মাধ্যমে যেটা করা হয় সেটা হচ্ছে মার্কেট বাস্কেট এনালাইসিস। বিভিন্ন পণ্যের ভেতরে একটির সাথে আরেকটির বিক্রি হবার সম্পর্কের প্রবাবিলিটি নির্ণয় করা হয়। তবে শুধু সুপারশপের পণ্য নয় বর্তমানে ই-কমার্সেও এরকমটি দেখতে পাবেন। ইউটিউবে একটি ভিডিও দেখলে সাথে সাথে ডজন খানেক ভিডিওর সাজেশন চলে আসে । আপনি হয়তো ইন্টারনেটে কিছু একটা সার্চ করেছিলেন অথবা অনলাইনে কোন একটা প্রডাক্ট দেখেছিলেন কোন ওয়েবসাইটে, তাহলে আপনার আর রক্ষা নেই, ফেসবুকে ঢুকলেই দেখবেন রিলেটেড ডজন ডজন প্রডাক্টের এড এসে হাজির আপনার সামনে। এরকম সবকিছুই করা হয় অ্যাসোসিয়েশন রুলস এর মাধ্যমে। অ্যাসোসিয়েশন রুলস ব্যবহার করে তৈরি করা হয় রিকমান্ডেশন ইঞ্জিন, যা আমাদের সামনে হাজির করে রিলেটেড শত শত বিষয় । আর আমাদের মনে হয় কম্পিউটার যেন আমাদের মনের কথা জানে !

ছবি - মার্কেট বাস্কেট এনালাইসিস ( সূত্র- ইন্টারনেট)

এখন প্রশ্ন হচ্ছে এই অ্যাসোসিয়েশন রুলস কি কাজে লাগে ? ধরুন আপনার বিরাট এক সুপারশপ রয়েছে, সেলফে সেলফে সাজানো শত শত পণ্য। একজন কাস্টমার এসেছে আপনার সুপারশপে টুথপেস্ট কিনতে। তিনি টুথপেস্ট যে সেলফে সাজানো আছে সেখান থেকে টুথপেস্ট কিনলেন। তিনি মনে মনে ভালো কোন টুথব্রাশও খুজছিলেন , কিন্তু আপনার দোকানে টুথব্রাশ ছিল দূরের অন্য কোন সেলফে রাখা । আপনার কাস্টমারের আশেপাশে কোন টুথব্রাশ চোখে না পরায় তিনি শুধু টুথপেস্ট কিনেই বাড়ি ফিরে গেলেন। আপনি যদি অ্যাসোসিয়েশন রুলসকে কাজে লাগিয়ে জানতেন টুথপেস্টের সাথে টুথব্রাশের বেচা-বিক্রি হবার সম্পর্ক আছে তাহলে এই দুটি প্রডাক্টকে পাশাপাশি রাখতে পারতেন, ফলে একটি বিক্রি হলে আরেকটি বিক্রি হবারও সম্ভাবনা বেড়ে যেত। এচাড়াও আপনি টুথপেস্ট কেনার সাথে টুথব্রাশ কিনলে তার জন্য কোন বিশেষ কোন অফার বা ডিসকাউন্ট দিতে পারতেন, তাহলেও আপনার সেলস বেড়ে যেত। এটাই হচ্ছে অ্যাসোসিয়েশন রুলসের বাস্তব উদাহরন।

ভিনদেশী সুপারশপের গল্প

অ্যাসোসিয়েশন রুলস নিয়ে একটি চমৎকার বিদেশী গল্প প্রচলিত রয়েছে। এক ব্যক্তি হঠাৎ একদিন তার টিন এইজ মেয়ের মেইল বক্সে ' প্রেগন্যান্সি প্রডাক্টের অফার' নিয়ে একটি ইমেইল দেখলেন। তিনি ভাবলেন আমার টিন এইজ মেয়ের কাছে এই ইমেইল কেন ! যেই সুপারশপের পক্ষ থেকে মেইলটি এসেছিল তিনি ছুটে গিয়ে তার ম্যানেজারকে রীতিমত বকাঝকা শুরু করলেন। আমার মেয়ে তো মাত্র টিন এইজ তার কাছে প্রেগন্যান্ট মহিলাদের পণ্যের অফার নিয়ে মেইল যাবে কেন? গোবেচারা ম্যানেজার তখন কাচুমাচু হয়ে বললেন " স্যার এটা কম্পিউটার জেনেরেটেড মেইল তো, সফটওয়্যার নিজ থেকেই পাঠায়, আমরা ইচ্ছে করে পাঠাইনি , হয়তো ভুলে চলে গেছে, আমরা আন্তরিক ভাবে দুঃখিত"।

ম্যানেজারের কথায় বাড়িতে ফিরে এলেন লোকটি। কিছুদিন পরের ঘটনা। টিন এইজ মেয়ের বাবা হঠাৎ একদিন জানতে পেলেন তার মেয়ে প্রেগন্যান্ট ! ভদ্রলোকের মাথায় হাত ! পরে একদিন ছুটে গিয়ে ক্ষমা চেয়ে আসলেন সুপারশপের ম্যানেজারের কাছে। কম্পিউটার কিভাবে জানলো তার মেয়ে প্রেগন্যান্ট ছিল ? এটাই হচ্ছে বিহেভিয়ার প্যাটার্ন এনালাইসিস। অনেকেই প্রেগন্যান্সির আর্লি পিরিয়ডে নির্দিষ্ট কিছু প্রডাক্ট কিনে থাকে বা অনুসন্ধান করে থাকে। টিন এইজ মেয়েটিও এমনটি করেছিল, সেই থেকেই কম্পিউটার তাকে সম্ভাব্য প্রেগন্যান্ট হিসাবে ধরে নিয়েছি, আর একারনেই তার মেইলে এসেছিল প্রেগন্যান্সি প্রডাক্টের অফার !

এই গল্পটিই হচ্ছে অ্যাসোসিয়েশন রুলস এর বাস্তব উদাহরন। আপনার-আমার বিহেভিয়ার এনালিসিস করে আমাদের পছন্দ-অপছন্দ অনেক কিছুই আজকাল কম্পিউটারের কাছে অজানা নয়, বরং আমাদের সম্পর্কে কোন কোন ক্ষেত্রে আমাদের থেকেও ভালো জানে কম্পিউটার।

অ্যাসোসিয়েশন রুলস কিভাবে কাজ করে ?

অ্যাসোসিয়েশন রুলসকে বলা হয় IF-THEN বা যদি-তাহলে রুলস অর্থাৎ একটি প্রোডাক্ট কিনলে অন্য একটি প্রোডাক্ট কেনার সম্ভাবনা কত ? ধরুন ব্রেড বিক্রির সাথে বাটার বিক্রির অ্যাসোসিয়েশন রুলস জানতে চাচ্ছেন, সেক্ষেত্রে ব্রেড হচ্ছে Antecedent বা IF আর বাটার হচ্ছে Consequent বা THEN।

অ্যাসোসিয়েশন রুলসকে আমরা ব্যখ্যা করবো একটি গ্রোসারি শপের ডেটাসেটের মাধ্যমে। ধরুন গ্রোসারি শপের ছয়টি ট্রানজেকশনের ডেটা নিচে দেয়া রয়েছে। এই ডেটাসেট থেকে আমরা দেখতে পাচ্ছি কোন ট্রানজেকশনে কি কি পণ্য বিক্রি হয়েছিল সেই ডেটা দেয়া রয়েছে।

Transaction ID	Product
1	Candy, Chips, Bread, Butter
2	Candy, Bread, Butter
3	Bread, Butter
4	Chips
5	Candy, Chips, Bread, Butter
6	Candy, Chips, Butter

অ্যাসোসিয়েশন রুলস বের করার জন্য প্রথমেই আমাদের ডেটাসেটটিকে নিচের মত ফরম্যাটে নিয়ে আসতে হবে। আমরা দেখতে পাচ্ছি এখানে প্রতিটি প্রোডাক্টকে আলাদা আলাদা কলামে কনভার্ট করা হয়েছে এবং কোন ট্রানজেকশনে যেসকল প্রোডাক্ট বিক্রি হয়েছিল সেসব জায়গায় 1 দেয়া রয়েছে অন্যথায় 0 দেয়া রয়েছে।

Transaction ID	Candy	Chips	Bread	Butter
1	1	1	1	1
2	1	0	1	1
3	0	0	1	1
4	0	1	0	0
5	1	1	1	1
6	1	1	0	1

অ্যাসোসিয়েশন রুলস এর বিভিন্ন উপাদান

Support - Support হচ্ছে প্রোডাক্ট গুলোর জনপ্রিয়তার পরিমাপ। কোন প্রোডাক্ট কত বার বিক্রি হয়েছে সেই সংখ্যাকে মোট ট্রানজেকশন বা বিক্রির পরিমান দ্বারা ভাগ করলে যা পাওয়া যাবে সেটাই হচ্ছে Support । এই মান যত বেশী হবে বুঝতে হবে সেই পণ্যটি তত বেশী বিক্রি হয় বা ততো বেশী জনপ্রিয়। আমাদের ডেটাসেটের প্রোডাক্টগুলোর Support বের করলে তার মানগুলো নিচের টেবিলের মত হবে। আমরা চাইলে একসাথে দুই বা ততোধিক প্রোডাক্টেরও বের করতে Support পারি।

Confidence - কোন ক্রেতা একটি প্রোডাক্ট কিনলে আরেকটি নির্দিষ্ট প্রোডাক্টও কিনবে তার সম্ভাবনা নির্ণয় করা হয় Confidence এর মাধ্যমে। একাধিক প্রোডাক্টের ক্ষেত্রেও Confidence নির্ণয় করা যায়। ধরুন আমরা জানতে চাচ্ছি ক্যান্ডি এবং চিপস কেউ যদি কেনে তাহলে সে বাটারও কিনবে তার সম্ভাবনা কেমন ? নিচের উদাহরণের মাধ্যমে আমরা তা নির্ণয় করেছি, এক্ষেত্রে আমাদের ডেটাসেট অনুযায়ী ক্যান্ডি এবং চিপস কেউ যদি কেনে তাহলে সে বাটারও কিনবে তার সম্ভাবনা ১ ।

Lift - Lift এর মাধ্যমে রিলেশনশিপ কতখানি শক্তিশালী সেটা বোঝা যায়। Lift অনেকটা কোরিলেশনের মত কাজ করে।

• Lift =1 মানে কোন কোরিলেশন নেই

• Lift > 1 মানে পজিটিভ কোরিলেশন রয়েছে

• Lift < 1 মানে নেগেটিভ কোরিলেশন রয়েছে

Lift এর মান 1 এর যত বেশী হবে বুঝতে হবে রিলেশনশিপ তত বেশী শক্তিশালী। ক্যান্ডি এবং চিপস কেনার সাথে বাটার কেনার রিলেশনশিপ কতখানি শক্তিশালী সেটা আমরা Lift এর মাধ্যমে নিচে নির্ণয় করেছি,

Conviction - Conviction এর মান যত বেশী হবে অ্যাসোসিয়েশন রুলসটি বাস্তবায়নের সম্ভাবনা তত বেশী হবে। Conviction এর পারফেক্ট ভ্যালু হচ্ছে ইনফিনিটি।

অ্যাপ্রিওরি অ্যালগরিদমের কিছু বৈশিষ্ট্য

• প্রাপ্ত ফলাফলকে ইন্টারপ্রেট করা অত্যন্ত সহজ।

• বড় ডেটাসেটেও ব্যবহার করা যায়।

• অপেক্ষাকৃত ধীর গতির।

Walmart এর অ্যাসোসিয়েশন রুলস

অ্যাসোসিয়েশন রুলস বের করার জন্য আমরা Walmart এর একটি ডেটাসেট ব্যবহার করবো। এই ডেটাসেটে বিভিন্ন দেশের Walmart চেইন শপের ট্রানজেকশন ডেটা রয়েছে। প্রথমেই আমরা ইউসিআই মেশিন লার্নিং রিপোজেটরি থেকে ডেটাসেট লোড করে নেব এবং প্রয়োজনীয় লাইব্রেরী ইমপোর্ট করে নেব।

import pandas as pd
from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import association_rules

df = pd.read_excel('http://archive.ics.uci.edu/ml/machine-learning-databases/00352/Online%20Retail.xlsx')
df.head()

আমরা দেখতে পাচ্ছি আমাদের ডেটাসেটে ইনভয়েস নাম্বার অনুযায়ী কোন ক্রেতা কি কি পণ্য কিনেছে সেই ডেটা দেয়া রয়েছে।

এই ডেটাসেটে কতগুলো দেশের ডেটা রয়েছে আমরা চাইলে তা দেখে নিতে পারি,

df.Country.unique()

এবার ডেটাসেটের Description কলামে অতিরিক্ত স্পেস বাদ দেয়া, InvoiceNo না থাকলে সেই ট্রানজেকশন গুলো বাদ দেয়া এবং যেসব ট্রানজেকশন ক্রেডিট হয়েছে সেই ট্রানজেকশন সমূহ বাদ দেয়ার মাধ্যমে আমরা ডেটাসেটটি ক্লিন করে নেব।

# Stripping extra spaces in the description 
df['Description'] = df['Description'].str.strip() 
  
# Dropping the rows without any invoice number 
df.dropna(axis = 0, subset =['InvoiceNo'], inplace = True) 
df['InvoiceNo'] = df['InvoiceNo'].astype('str') 
  
# Dropping all transactions which were done on credit 
df = df[~df['InvoiceNo'].str.contains('C')] 

এবার ডেটাসেট থেকে আমরা শুধু ইতালির ডেটা আলাদা করে নেব, এখানে শুধু InvoiceNo, Description এবং Quantity এর অংশ থাকবে।

basket_Italy = (df[df['Country'] =="Italy"] 
          .groupby(['InvoiceNo', 'Description'])['Quantity'] 
          .sum().unstack().reset_index().fillna(0) 
          .set_index('InvoiceNo')) 

ইতালির জন্য আমাদের বাস্কেটটি দেখতে এরকম হবে,

এবার ইতালির বাস্কেটটি আরও খানিকটা প্রসেস করে নেব , এরফলে যেকল ট্রানজেকশনে কোন প্রোডাক্ট একাধিক বার বিক্রি হয়েছে সেখানে 1 দেয়া থাকবে অন্যথায় 0 থাকবে।

def hot_encode(x):
    if x <= 0:
        return 0
    if x >= 1:
        return 1

basket_encoded = basket_Italy.applymap(hot_encode) 
basket_Italy = basket_encoded 

এবার সেই কাঙ্ক্ষিত অ্যাসোসিয়েশন রুলস তৈরির পালা। সাপোর্টের মিনিমাম মান ০.০৫ বা ৫% ধরে আমরা রুলস তৈরি করবো, আপনি চাইলে আপনার প্রয়োজন অনুযায়ী এই মান নির্ধারণ করতে পারেন। বড় ডেটাসেটের ক্ষেত্রে এই মান পণ্যের সংখ্যা এবং ট্রানজেকশন এর সংখ্যা বেশী হলে সাধারনত এমনিতেই কম হয়।

frq_items = apriori(basket_Italy, min_support = 0.05, use_colnames = True) 
  
# Collecting the inferred rules in a dataframe 
rules = association_rules(frq_items, metric ="lift", min_threshold = 1) 
rules = rules.sort_values(['confidence', 'lift'], ascending =[False, False]
rules

উপরের ছবিতে আমরা দেখতে পাচ্ছি আমাদের অ্যাসোসিয়েশন রুলস , অর্থাৎ কোন প্রোডাক্ট বিক্রির সাথে কোন প্রোডাক্ট বিক্রির সম্পর্ক কেমন সেটাই এখানে বিস্তারিত ভাবে রয়েছে।

আমরা চাইলে এই রুলসকে আরও ফিল্টার করে নিতে পারি।

rules[ (rules['lift'] >= 3) &
       (rules['confidence'] >= 0.3) ]