درهم‌سازی میانی

در علوم کامپیوتر، درهم‌سازی میانی یک روش برای تخمین میزان مشابهت دو مجموعه به صورت سریع می‌باشد. این رویه توسط آندری برودر ابداع شد و ابتدا در موتور جستجو آلتاویستا برای پیدا کردن و حذف کردن صفحه‌های تکراری استفاده شد. همچنین در خیلی مسایل مربوط به دسته بندی کردن، مانند دسته بندی مدارک و اسناد با توجه به تشابه بین مجموعه کلمات آنها، استفاده شد.

تشابه و مقدار میانی در هم‌سازی ژاکار

ثابت تشابه ژاکار برای دو مجموعه $A$ و $B$ به صورت زیر تعریف می‌شود

J(A,B)={{|A\cap B|} \over {|A\cup B|}}.

که یک عدد بین ۰ و ۱ است؛ وقتی دو مجموعه کاملاً از هم جدا هستند مقدار ۰ و وقتی دو مجموعه برابر هستند مقدار ۱ را می‌پذیرد. در بقیه حالات به‌طور موکد بین ۰ و ۱ است. این ثابت یک نمایش رایج برای نشان دادن میزان تشابه بین دو مجموعه است: دو مجموعه بیشتر به هم شبیه هستند اگر ثابت ژاکار آن نزدیکتر به ۱ باشد، و به همین طریق وقتی ثابت ژاکار آن‌ها به ۰ نزدیکتر باشد، کمتر متشابه‌اند.

فرض کنید h یک تابع درهم‌سازی باشد که اعضای $A$ و $B$ را به اعداد صحیح متمایز نسبت می‌دهد، و برای هر مجموعه S تعریف می‌کنیم $h min (S)$ که عضو $x$ از $S$ است با مقدار میانی $h (x)$ . بنابراین $h min (A) = h min (B)$ دقیقاً زمانی که مقدار درهم سازی میانی اجتماع $A \cup B$ داخل تلاقی $A \cap B$ قرار گیرد. از همین رو،

Pr[h min (A) = h min (B)] = J (A, B).

به عبارتی دیگر، اگر $r$ یک متغیر تصادفی باشد که وقتی $h min (A) = h min (B)$ است برابر ۱ و در غیر این صورت ۰ باشد، آنگاه $r$ یک برآوردگر بی‌غرض از $J (A, B)$ است، با اینکه واریانس بالایی برای اینکه در نوع خود مفید باشد، دارد. هدف روش درهم‌سازی میانی برای کاهش واریانس، میانگین‌گیری از چندین متغیر است که به صورت یکسان تولید شده‌اند.

الگوریتم

گوناگونی با توابع درهم‌سازی زیاد

ساده‌ترین نسخه از روش درهم‌سازی میانی از $k$ تابع درهم‌سازی متفاوت استفاده می‌کند (که یک پارامتر عدد صحیح ثابت است) و نمایانگر هر مجموعه $S$ با $k$ مقدار از $h min (S)$ برای این $k$ تابع است.

برای تخمین زدن $J (A, B)$ با استفاده از این نسخهٔ این رویه، فرض کنید $y$ تعداد توابع درهم‌سازی باشد به صورتی که $h min (A) = h min (B)$ ، از $y / k$ به عنوان تخمین استفاده کنید. این تخمین حاصل میانگین $k$ متغیر تصادفی است که بین ۰-۱ هستند، که هر کدام وقتی $h min (A) = h min (B)$ است، برابر ۱ و در غیر اینصورت برابر ۰ هستند، و هرکدام از این‌ها یک ثابت مطلق ژاکار هستند. از این رو میانگین آن‌ها هم یک برآوردگر بی‌غرض است، و بر طبق کران‌های چرنوف استاندارد برای مجموع متغیرهای تصادفی ۰-۱ خطای مورد انتظار از $O(1/\sqrt k)$ می‌باشد.

از این رو، برای هر $ε> ۰$ ای یک ثابت $k = O(1/ε 2)$ وجود دارد به طوری که خطای مورد انتظار تخمین حداکثر برابر $ε$ است. برای مثال، ۴۰۰ تابع در هم‌سازی ملزوم تخمین $J (A, B)$ با خطای مورد انتظار کوچکتر یا مساوی ۰٫۰۵ است.

گوناگونی با تک تابع درهم‌سازی

ممکن است از لحاظ محاسباتی، محاسبهٔ توابع گوناگون درهم‌سازی پرهزینه باشد ولی یک نسخه مربوط به روش درهم‌سازی میانه از این مشکل پرده برداری کرده‌است، تنها با استفاده از یک تک تابع درهم‌سازی و استفاده از آن برای انتخاب چند مقدار از هر مجموعه به جای انتخاب کردن تنها یک مقدار کمینه از تابع درهم‌سازی. فرض کنیم $h$ یک تابع درهم‌سازی باشد، و $k$ یک عدد صحیح ثابت. اگر $S$ هر مجموعه‌ای از $k$ یا مقادیر بیشتری در دامنه $h$ باشد، تعریف می‌کنیم $h (k) (S)$ یک زیر مجموعه از $k$ عنصر $S$ با کمترین مقدار $h$ است. این زیر مجموعه $h (k) (S)$ به عنوان یک مشخصه برای مجموعه $S$ است. که تشابه بین هر دو مجموعه از طریق مقایسه این مشخصه بدست می‌آید و تخمین زده می‌شود.

خصوصاً، فرض کنیم A و B دو مجموعه دلخواه باشند، آنگاه $X = h (k) (h (k) (A) \cup h (k) (B)) = h (k) (A \cup B)$ یک مجموعه k عضوی از $A \cup B$ است، و اگر h یک تابع تصادفی باشد، آنگاه هر زیر مجموعه از k عضو با احتمال برابر انتخاب می‌شوند؛ یعنی اینکه، $X$ یک نمونه تصادفی ساده از $A \cup B$ است، زیر مجموعه $Y = X \cap h (k) (A) \cap h (k) (B)$ یک مجموعه از اعضای $X$ است که متعلق به تلاقی $A \cap B$ است. از این رو | $Y$ |/ $k$ یک برآوردگر بی‌غرض $J (A, B)$ است. تفاوت این برآوردگر با برآوردگر تولید شده توسط توابع گوناگون درهم‌سازی این است که $X$ در هر صورتی دقیقاً $k$ عضو دارد، درحالیکه توابع گوناگون درهم‌سازی ممکن است به دلیل اینکه دو تابع متفاوت در هم‌سازی ممکن است مینیما برابر داشه باشند، منجر به اعضای کوچکتر از نمونه‌های ساده شده شود. به هر حال وقتی $k$ یک مقدار کوچکی نسبت به اندازهٔ مجموعه است این تفاوت قابل چشم پوشی است.

بر طبق کران‌های چرنوف استاندارد برای ساده‌سازی بدون جایگزینی، این برآوردگر دارای خطای مورد انتظار از $O(1/\sqrt k)$ ، در مقایسه با اجرای روش تابع درهم سازی چند گانه می‌باشد.

بررسی زمانی

برآوردگر $| Y |/ k$ در زمانی از $O(k)$ در هر کدام از روش‌ها، از طریق دو مشخصه دو مجموعه محاسبه می‌شود. از این رو، وقتی $ε$ و $k$ ثابت باشند، مدت زمان محاسبه تشابه تخمینی از مشخصه‌ها هم ثابت است. مشخصه هر مجموعه قابل محاسبه در زمان خطی (تابع خطی از زمان) روی اندازهٔ مجموعه است، بنابراین وقتی مقدار بسیاری تشابه زوج مانند قرار است که تخمین زده شود، این روش منجر به صرفه جویی قابل توجه زمان اجرا در مقایسه با، مقایسهٔ کامل تمام اعضای هر مجموعه است. خصوصاً، برای مجموعه‌ای با اندازه $n$ ، توابع گوناگون درهم‌سازی از $O(n k)$ زمان می‌گیرد. تک تابع درهم‌سازی به‌طور معمول سریعتر است، و ملزم به $O(n log k)$ زمان برای نگهداری لیست مرتب شده مینیما است.

جایگشت‌های مستقل نسبت به مقدار میانی

برای پیاده‌سازی رویهٔ درهم‌سازی میانه که در فوق مورد وصف قرار گرفت، به یک تابع درهم سازی $h$ نیاز است که یک جایگشت تصادفی روی $n$ عضو تعریف کند، به طوریکه $n$ مجموع اعداد اعضای متمایز از اجتماع تمام مجموعه‌هایی است که قرار است مقایسه شوند. اما به خاطر اینکه $n!$ جایگشت متفاوت وجود دارد، تنها برای مشخص کردن صحیح یک جایگشت تصادفی نیاز به $Ω(n log n)$ بیت دارد، که حتی برای مقادیر متوسط از $n$ ، به‌طور ناکارآمدی بزرگ است. به همین دلیل، همانند نظریه درهم‌سازی جهانی، تلاش قابل توجهی بر روی پیدا کردن خانواده‌ای از جایگشت‌ها که نسبت به مقدار میانی مستقل هستند صورت گرفت، به معنی آنکه برای هر زیر مجموعه بر روی دامنه، هر عضوی به احتمال برابر می‌تواند مینیمم باشد. این قضیه بنا شده‌است که یک خانواده از جایگشت‌های مستقل از مقدار میانی حداقل باید

 $lcm(1,2,...,n)\geq e^{n-o(n)}$

جایگشت متفاوت داشته باشد، و به همین جهت که نیاز به $Ω(n)$ بیت برای مشخص کردن یک تک جایگشت دارد، باز هم به صورت ناکارآمدی بزرگ است.

به دلیل همین ناکارآمدی، دو تعریف گوناگون از استقلال نسبت به مقدار میانی معرفی شده‌است: خانواده‌های جایگشتی محدود (مستقل نسبت به مقدار میانی)، و خانواده‌های جایگشتی تقریبی (مستقل نسبت به مقدار میانی). نوع اول یعنی اینکه قسمت مستقل نسبت به مقدار میانی محدود به مجموعه‌هایی معین با اندازه (کاردینال) حداکثر $k$ است. نوع دوم حداکثر یک احتمال ثابت $ε$ متفاوت از استقلال کامل دارد.

کاربردها

کاربردهای اصلی برای درهم‌سازی میانی شامل دسته‌بندی و حذف قریب به شباهت متون (اینترنتی) می‌شود، که به عنوان مجموعه‌ای از کلمات که در متن حضور دارند معرفی می‌شود. تکنیک‌های مشابهی همچنین برای دسته‌بندی و حذف متون تکراری برای بقیه انواع داده‌ها استفاده شده‌است، مانند تصاویر: در موضوع داده‌های تصویری، یک تصویر می‌تواند به صورت یک سری از تصاویر بریده شده از ان معرفی شود، یا به عنوان یک سری ویژگی‌های تعریفی تصویری پیچیده، معرفی می‌شود.

در جمع‌آوری و استخراج داده، کوئن و همکاران از درهم‌سازی میانی به عنوان ابزاری برای یادگیری قانون ارتباط استفاده می‌کنند. با فرض اینکه یک پایگاه داده داریم که هر داده چند جنبه دارد (که به صورت ماتریسی از ۰ و ۱ است که به ازای هر پایگاه داده یک ردیف و به ازای هر جنبه یک ستون داریم). آن‌ها از تقریب‌های مبتنی بر درهم‌سازی میانه بر روی ثابت ژاکار انجام می‌دهند تا جفت هم جنبه مورد نظری که به صورت متداوم باهم رخ می‌دهند را محاسبه کنند، و سپس محاسبهٔ مقدار دقیق آن ثابت، فقط برای آن جفت‌ها، برای معین کردن آن‌هایی که تداوم با هم رخ دادنشان زیر یک بازه محدود داده شده باشد.

برای مشاهده

رویهٔ درهم‌سازی میانی ممکن است به عنوان نمونه‌ای از درهم سازی حساس به محل دیده شود، یک مجموعه‌ای از روش‌ها برای استفاده از توابع درهم‌سازی برای متناظر کردن مجموعه‌هایی بزرگ به مقادیر درهم‌سازی کوچکتر به طریقی که وقتی دو عضو فاصلهٔ کمی یک یکدیگر دارند، مقادیر در هم‌سازی آن‌ها احتمالاً با هم یکی است. در این نمونه، مشخصهٔ یک مجموعه ممکن است همان مقدار در هم‌سازی آن در نظر گرفته شود. دیگر روش‌های درهم‌سازی‌های حساس به محل برای فاصله همینگ بین دو مجموعه و فاصله کسینوسی بین دو بردار وجود دارد؛ درهم‌سازی حساس به محل در الگوریتم پیدا کردن نزدیک ترین همسایه، کاربردهای زیادی دارد. برای سیستم‌های توزیع شدهٔ بزرگتر و نگاشت‌کاهش خاص، یک سری نسخه‌های تغییر یافتهٔ درهم‌سازی میانی برای کمک به محاسبه تشابه بدون نیاز به بستگی در نقطه، وجود دارد.

ارزش‌ها و محک

یک ارزشگذاری در مقیاس بالا توسط گوگل از سال ۲۰۰۶ هدایت شد، تا اجرای الگوریتم درهم‌سازی میانی و شبه درهم‌سازی را با هم مقایسه کند. در سال ۲۰۰۷ گوگل خبر از استفاده از شبه درهم‌سازی برای پیدا کردن تکرار در مرور صفحات اینترنت، و استفاده از درهم‌سازی میانی و درهم‌سازی حساس به محل برای شخصی سازی قسمت خبری گوگل، داد.

برای مشاهده

پیوند به بیرون

منابع

مشارکت‌کنندگان ویکی‌پدیا. «MinHash». در دانشنامهٔ ویکی‌پدیای انگلیسی.