✖

Min Value: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়

Linear Counting নিয়ে আগের প্রবন্ধে আমরা কোনো ডেটাসেটে ভিন্ন ভিন্ন মানের সংখ্যা গোনা ও আনুমানিক নির্ণয়ের মৌলিক অ্যালগরিদমগুলো দেখেছি। আজ দেখব আরেকটি সম্ভাবনাভিত্তিক অ্যালগরিদম (probabilistic algorithm), যা দিয়ে মোটামুটি ভালো নির্ভুলতায় এবং কম মেমোরিতে অনন্য মানের সংখ্যা আনুমানিক নির্ণয় করা যায়।

Min Value

এই প্রবন্ধে আমরা কাজ করব শুধু একক ব্যবধি (0, 1) এর বাস্তব সংখ্যা নিয়ে। এই ব্যবধির সংখ্যার এমন একটি সেট কল্পনা কর, যার সংখ্যাগুলো সমানভাবে ছড়ানো, যেমন সংখ্যার সেট {0.25, 0.5, 0.75}। পাশাপাশি সংখ্যাগুলো পরস্পর থেকে (এবং শূন্য ও এক থেকে) সবসময় 0.25 দূরে। ভিন্ন ভিন্ন উপাদানের সংখ্যা গুনতে এটি কীভাবে সাহায্য করবে?

যদি বলি, একক ব্যবধির সংখ্যার এমন একটি সমানভাবে ছড়ানো সেট আছে, আর সংখ্যাগুলোর পারস্পরিক দূরত্ব 0.2, তাহলে কি তুমি বলতে পারবে, এমন সেটে কয়টি উপাদান আছে? অবশ্যই, এটি সেট {0.2, 0.4, 0.6, 0.8}, যার কার্ডিনালিটি চার। ইনপুটে একক ব্যবধির সমানভাবে ছড়ানো সংখ্যা থাকলে এবং পাশাপাশি সংখ্যাগুলোর দূরত্ব জানা থাকলে আমরা সহজেই উপাদানের সংখ্যা নির্ণয় করতে পারি।

আর পাশাপাশি সংখ্যাগুলোর দূরত্ব সেটের ক্ষুদ্রতম উপাদানের সমান: সেট {0.25, 0.5, 0.75} এর পাশাপাশি উপাদানগুলোর দূরত্ব 0.25, ইত্যাদি। সমানভাবে ছড়ানো সংখ্যার উপাদান সংখ্যা নির্ণয় করতে আমাদের শুধু কোনোভাবে ক্ষুদ্রতম উপাদানটি জানলেই চলে। তখন উপাদানের সংখ্যা p নির্ণয় করা যায় এই সহজ সূত্রে:

p=1m−1

যেখানে m হলো সেই ক্ষুদ্রতম উপাদান।

আবার হ্যাশ করব…

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

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

এই ভাবনা থেকে পাই একটি সহজ অ্যালগরিদম: ইনপুট ডেটা একে একে দেখি, প্রত্যেক উপাদানকে একক ব্যবধিতে হ্যাশ করি এবং ক্ষুদ্রতম উপাদানটি মনে রাখি। আগের সূত্র অনুযায়ী অনন্য উপাদানের সংখ্যা আনুমানিক নির্ণয় করি। পাইথনে বাস্তবায়ন:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

ফাংশন unit_interval_hash আমাদের দেয় ব্যবধি (0, 1] এর একটি দশমিক সংখ্যা। ফাংশন count_unique_using_minimum প্রথমে সব ইনপুট মানকে এই সংখ্যায় রূপান্তর করে, ক্ষুদ্রতম মানটি খুঁজে বের করে এবং দেয় 1 / minimum - 1। লক্ষ কর, ডেটাসেটে কতগুলো মান একই, তাতে কিছুই আসে যায় না: দুইটি একই মানের জন্য হ্যাশ ফাংশন একই মূলদ সংখ্যা দেয়, যা প্রাপ্ত ক্ষুদ্রতম মানকে কোনোভাবে প্রভাবিত করে না। এ কারণেই এই অ্যালগরিদম দিয়ে আমরা অনন্য উপাদানের সংখ্যা গুনি।

ফল কেমন? (প্রত্যেক লাইনে আছে আনুমানিক কার্ডিনালিটি, অথচ সঠিক কার্ডিনালিটি 10,000।)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

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

উন্নত রূপ

দেখতে পাচ্ছি, অ্যালগরিদমের প্রধান সমস্যা অস্থিরতা: একবার দেয় বেশ ভালো অনুমান (9362), আরেকবার দেয় একেবারে ভুল অনুমান (65536)। উপায় কী? ইনপুট ডেটাকে কয়েকটি অংশে ভাগ করে প্রত্যেক অংশের অনন্য উপাদানের সংখ্যা নির্ণয় করতে পারি, তারপর সব কিছুর সুন্দরভাবে গড় নিতে পারি। ভাগ করা যেত আমাদের আইডির প্রথম অক্ষর অনুযায়ী। তাই আলাদাভাবে অনন্য মানের সংখ্যা নির্ণয় করি বর্ণ “a” দিয়ে শুরু হওয়া আইডির জন্য, তারপর বর্ণ “b” দিয়ে শুরু হওয়া আইডির জন্য, ইত্যাদি। কোড:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

পরিবর্তন আছে ফাংশন count_unique_using_minimum এ। চলক min_values এ আমরা প্রত্যেক গুচ্ছের ক্ষুদ্রতম মান রাখি। শেষে সব ক্ষুদ্রতম মান যোগ করে রাখা মানগুলোর মোট সংখ্যা দিয়ে ভাগ করি, এতে পাই গড় ক্ষুদ্রতম মান। রাশি 1/average_minimum থেকে জানি, প্রত্যেক গুচ্ছে গড়ে কতগুলো অনন্য মান আছে। এই মানকে গুচ্ছের সংখ্যা দিয়ে গুণ করলে পাই প্রদত্ত ডেটাসেটে অনন্য মানের আনুমানিক সংখ্যা। আর এই পরিবর্তিত পদ্ধতি কেমন কাজ করে?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

এখনো ভালো নয়, তবে অবশ্যই আগের চেয়ে ভালো। অ্যালগরিদমটি এখন বেশি স্থির। ফাংশনটি এমনভাবে বদলে দেখা যায়, যেন গুচ্ছগুলো প্রথম অক্ষর অনুযায়ী না হয়ে, ধরা যাক আইডির প্রথম দুইটি অক্ষর অনুযায়ী তৈরি হয়, অর্থাৎ এভাবে:

first_char = str(item)[0:2] # ToDo: choose better name for variable

তখন ফল হতো এমন:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

এবার কিন্তু খুব একটা খারাপ নয়, তাই না? যদি আরও চেষ্টা করি 1 লাখ অনন্য মান, প্রথম দুইটি অক্ষর এবং n = 24 দিয়ে, তাহলে পাই এই ফল:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

মোটামুটি চলে। তবে চিন্তার কিছু নেই, এর চেয়ে ভালো অ্যালগরিদমও আছে।

আর মেমোরির চাহিদা কত? প্রত্যেক গুচ্ছের জন্য একটি ক্ষুদ্রতম মান রাখতে হয়, এর বেশি কিছু নয়। আইডিগুলো hex আকারে থাকলে তার মানে আমাদের মনে রাখতে হবে সর্বোচ্চ 16x টি ক্ষুদ্রতম মান, যেখানে x হলো যতগুলো অক্ষর দিয়ে আমরা গুচ্ছের কী (key) বানাই তার সংখ্যা। একটি ক্ষুদ্রতম মান মানে একটি মূলদ সংখ্যা, অর্থাৎ double বা float ধরনের কিছু।

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

সূচিপত্র: Linear counting: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়, Min Value: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়, LogLog: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়, HyperLogLog: ভিন্ন ভিন্ন মানের সংখ্যা খুব নির্ভুলভাবে কীভাবে আনুমানিক নির্ণয় করা যায়