خوارزمية Min Value: كيف نقدّر عدد القيم المختلفة
تناولنا في المقالة السابقة عن خوارزمية Linear Counting الخوارزميات الأساسية لحساب عدد القيم المختلفة في مجموعة بيانات وتقديره. وتنتظرنا اليوم خوارزمية احتمالية أخرى تمكّننا من تقدير عدد القيم المختلفة بدقة مقبولة ومتطلبات قليلة من الذاكرة.
خوارزمية 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 بالصيغة البسيطة:
حيث m هو ذلك العنصر الأصغر.
ونعود إلى التجزئة…
حسناً، لكن كيف نستفيد من ذلك إذا كانت في المدخلات سلاسل نصية أو قيم أخرى لا تحقق شرط التوزيع المنتظم في فترة الوحدة؟ نستعين مرة أخرى بدالة التجزئة القديمة الطيبة التي يمكن أن تعيد لأي مدخل عدداً نسبياً من فترة الوحدة. ومن السهل إنشاء دالة تجزئة كهذه.
بذلك نحصل من البيانات على أعداد نسبية، لكن كيف نجعل هذه الأعداد موزّعة بانتظام؟ هذا لم يعد ممكناً، لكن يمكننا أن نستعين بطريقة أخرى. فدالة التجزئة تتصرف من وجهة نظرنا بصورة «عشوائية» إلى حد كبير. فللكلمات المتشابهة جداً مثل «hello» و»hellp» و»hellq» تعيد دالة التجزئة على الأرجح مجاميع اختبارية مختلفة جداً. بعبارة أخرى: إذا جزّأنا ألف قيمة مختلفة إلى فترة الوحدة، فمن المستبعد جداً أن تكون الغالبية العظمى من الأعداد مثلاً أصغر من النصف. بل من المرجح جداً أن تكون هذه الأعداد موزّعة بانتظام تقريباً. وكلما جزّأنا بيانات أكثر، صار التوزيع أكثر انتظاماً.
ومن هذه الفكرة نحصل على خوارزمية بسيطة: نمرّ على بيانات المدخلات، ونجزّئ كل عنصر إلى فترة الوحدة، ونحفظ أصغر عنصر. ثم نقدّر عدد العناصر المختلفة بالصيغة السابقة. التطبيق في Python:
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
هذا ليس سيئاً، أليس كذلك؟ وإذا جرّبنا أيضاً مئة ألف قيمة مختلفة، مع أول محرفين و n = 24، حصلنا على النتائج الآتية:
103936
110080
102656
101120
101376
108288
97536
97024
107776
92416
نتيجة مقبولة إلى حد ما. لكن لا داعي للقلق، فما زالت توجد خوارزميات أفضل.
وما متطلبات الذاكرة؟ علينا أن نحتفظ بالقيمة الصغرى لكل مجموعة، لا أكثر. فإذا كانت المعرّفات بالصيغة الست عشرية، فمعنى ذلك أننا نحتاج إلى حفظ 16x قيمة صغرى على الأكثر، حيث x عدد المحارف التي نكوّن منها مفتاح المجموعة. والقيمة الصغرى الواحدة عدد نسبي واحد، أي متغير من النوع double أو float.
ملاحظة أخيرة: سمحنا لأنفسنا بتقسيم المدخلات إلى عدة مجموعات لأنّ المدخلات كانت معرّفات تتصرف كسلاسل نصية عشوائية. ولو لم تكن في المدخلات سلاسل عشوائية، بل بيانات بصيغة معيّنة، لكان علينا أن نقسمها بطريقة أخرى. فلو بدأ كل معرّف مثلاً بالبادئة userid-، لما نجح على الأرجح التقسيم إلى مجموعات بحسب المحرف الأول.
المحتويات: خوارزمية Linear counting: كيف نقدّر عدد القيم المختلفة, خوارزمية Min Value: كيف نقدّر عدد القيم المختلفة, خوارزمية LogLog: كيف نقدّر عدد القيم المختلفة, خوارزمية HyperLogLog: كيف نقدّر عدد القيم المختلفة بدقة عالية