MINHASH_LSH

يعد إلغاء التكرار والبحث عن التشابه بكفاءة أمرًا بالغ الأهمية لمجموعات بيانات التعلم الآلي واسعة النطاق، خاصةً بالنسبة لمهام مثل تنظيف مجموعات التدريب لنماذج اللغات الكبيرة (LLMs). عند التعامل مع ملايين أو مليارات المستندات، تصبح المطابقة التامة التقليدية بطيئة ومكلفة للغاية.

يُتيح فهرس MINHASH_LSH في Milvus إمكانية إلغاء البيانات المكررة التقريبية السريعة والقابلة للتطوير والدقيقة من خلال الجمع بين تقنيتين قويتين:

• MinHash: يولد بسرعة توقيعات مضغوطة (أو "بصمات أصابع") لتقدير تشابه المستندات.

• التجزئة الحساسة للموقع (LSH): العثور بسرعة على مجموعات من المستندات المتشابهة بناءً على توقيعات MinHash الخاصة بها.

يرشدك هذا الدليل إلى المفاهيم والمتطلبات الأساسية والإعداد وأفضل الممارسات لاستخدام MINHASH_LSH في Milvus.

نظرة عامة

تشابه جاكارد

يقيس تشابه جاكارد التداخل بين مجموعتين (أ) و(ب)، ويُعرّف رسميًا على النحو التالي:

$$J(A, B) = \frac{|A \cap B|}{|A \cup B|}$$

حيث تتراوح قيمته من 0 (منفصلتان تمامًا) إلى 1 (متطابقتان).

ومع ذلك، فإن حساب تشابه جاكارد بالضبط بين جميع أزواج المستندات في مجموعات البيانات واسعة النطاق مكلف حسابيًا - O(n²) من حيث الوقت والذاكرة عندما يكون n كبيرًا. هذا يجعلها غير مجدية لحالات الاستخدام مثل تنظيف مجموعة تدريب LLM أو تحليل المستندات على نطاق الويب.

تواقيع MinHash: تشابه جاكارد التقريبي

MinHash هي تقنية احتمالية توفر طريقة فعالة لتقدير تشابه جاكارد. وهي تعمل عن طريق تحويل كل مجموعة إلى متجه توقيع مضغوط، مع الحفاظ على معلومات كافية لتقريب تشابه المجموعة بكفاءة.

الفكرة الأساسية:

كلما زاد تشابه المجموعتين، زادت احتمالية تطابق توقيعات MinHash الخاصة بهما في نفس المواضع. تمكّن هذه الخاصية MinHash من تقريب تشابه جاكارد بين المجموعتين.

تسمح هذه الخاصية ل MinHash بتقريب تشابه جاكارد بين المجموعتين دون الحاجة إلى مقارنة المجموعتين الكاملتين مباشرةً.

تتضمن عملية MinHash MinHash:

1. التجزئة: تحويل المستندات إلى مجموعات من التسلسلات الرمزية المتداخلة (التجزئة)

2. التجزئة: تطبيق دوال تجزئة مستقلة متعددة على كل تجزئة

3. التحديد الأدنى: بالنسبة لكل دالة تجزئة، قم بتسجيل الحد الأدنى لقيمة التجزئة عبر جميع التجزئات

يمكنك رؤية العملية بأكملها موضحة أدناه:

سير عمل التجزئة المصغرة

LSH ل MinHash

في حين أن توقيعات MinHash MinHash تقلل بشكل كبير من تكلفة حساب تشابه Jaccard الدقيق بين المستندات، إلا أن المقارنة الشاملة بين كل زوج من متجهات التوقيع لا تزال غير فعالة على نطاق واسع.

لحل هذه المشكلة، يتم استخدام LSH. يتيح LSH إمكانية البحث التقريبي السريع عن التشابه التقريبي من خلال ضمان تجزئة العناصر المتشابهة في نفس "الدلو" باحتمالية عالية - مما يجنب الحاجة إلى مقارنة كل زوج مباشرةً.

تتضمن العملية:

1. تجزئة التواقيع:

   يتم تقسيم توقيع MinHash ذي الأبعاد n إلى نطاقات b. يحتوي كل نطاق على ص من قيم التجزئة المتتالية، وبالتالي فإن طول التوقيع الإجمالي يحقق: n = b × r.

   على سبيل المثال، إذا كان لديك توقيع MinHash ذو 128 بُعدًا(n = 128) وقسمته إلى 32 نطاقًا(b = 32)، فإن كل نطاق يحتوي على 4 قيم تجزئة(r = 4).

2. التجزئة على مستوى النطاق:

   بعد التجزئة، تتم معالجة كل نطاق بشكل مستقل باستخدام دالة تجزئة قياسية لتعيينه إلى دلو. إذا أنتج توقيعان نفس قيمة التجزئة داخل النطاق - أي أنهما يقعان في نفس الدلو - يتم اعتبارهما متطابقين محتملين.

3. اختيار المرشح:

   يتم اختيار الأزواج التي تتطابق في نطاق واحد على الأقل كمرشحين للتشابه.

ضع في اعتبارك ثلاثة مستندات بتوقيعات MinHash ذات 128 بُعدًا:

سير عمل Lsh 1

أولاً، يقسّم LSH التوقيع ذا الـ 128 بُعدًا إلى 32 نطاقًا كل منها 4 قيم متتالية:

سير عمل Lsh 2

بعد ذلك، يتم تجزئة كل نطاق إلى دلاء مختلفة باستخدام دالة تجزئة. يتم اختيار أزواج المستندات التي تشترك في دلاء كمرشحين للتشابه. في المثال أدناه، يتم اختيار المستند A والمستند B كمرشحين للتشابه حيث تتطابق نتائج التجزئة الخاصة بهما في النطاق 0:

سير عمل Lsh 3

MHJACCARD: مقارنة تواقيع MinHash الصغيرة

تقارب تواقيع MinHash توقيعات MinHash تشابه Jaccard بين المجموعات باستخدام متجهات ثنائية ذات طول ثابت. ومع ذلك، نظرًا لأن هذه التواقيع لا تحافظ على المجموعات الأصلية، لا يمكن تطبيق المقاييس القياسية مثل JACCARD أو L2 أو COSINE مباشرةً لمقارنتها.

لمعالجة هذه المشكلة، يقدم Milvus نوع مقياس متخصص يسمى MHJACCARD ، مصمم خصيصًا لمقارنة تواقيع MinHash.

عند استخدام MinHash في Milvus:

• يجب أن يكون الحقل المتجه من النوع BINARY_VECTOR

• يجب أن يكون index_type MINHASH_LSH (أو BIN_FLAT)

• يجب تعيين metric_type على MHJACCARD

سيكون استخدام مقاييس أخرى إما غير صالح أو سيؤدي إلى نتائج غير صحيحة.

لمزيد من المعلومات حول هذا النوع من المقاييس، راجع MHJACCARD.

سير عمل إلغاء التكرار

تسمح عملية إلغاء البيانات المكررة المدعومة من MinHash LSH لـ Milvus بتحديد وتصفية السجلات النصية أو السجلات المهيكلة شبه المكررة بكفاءة قبل إدراجها في المجموعة.

1. التجزئة والمعالجة المسبقة: تقسيم البيانات النصية الواردة أو البيانات المهيكلة (مثل السجلات والحقول) إلى أجزاء؛ وتطبيع النص (تصغير الحروف وإزالة علامات الترقيم) وإزالة الكلمات المتوقفة حسب الحاجة.

2. إنشاء الميزات: إنشاء مجموعة الرموز الرمزية المستخدمة في MinHash (على سبيل المثال، التجزئة من النص؛ رموز الحقول المتسلسلة للبيانات المهيكلة).

3. إنشاء توقيع MinHash: حساب تواقيع MinHash لكل جزء أو سجل.

4. تحويل المتجه الثنائي: تحويل التوقيع إلى متجه ثنائي متوافق مع Milvus.

5. البحث قبل الإدراج: استخدم فهرس MinHash MinHash LSH للبحث في المجموعة المستهدفة عن التكرارات القريبة من العنصر الوارد.

6. إدراج وتخزين: إدراج العناصر الفريدة فقط في المجموعة. تصبح قابلة للبحث في عمليات التحقق من التكرار في المستقبل.

المتطلبات الأساسية

قبل استخدام MinHash LSH في Milvus، يجب عليك أولاً إنشاء تواقيع MinHash. هذه التواقيع الثنائية المدمجة تقارب تشابه جاكارد بين المجموعات وهي مطلوبة للبحث المستند إلى MHJACCARD في Milvus.

اختر طريقة لتوليد تواقيع MinHash

اعتمادًا على عبء العمل الخاص بك، يمكنك اختيار:

• استخدام طريقة بايثون datasketch للتبسيط (موصى به للنماذج الأولية)

• استخدام الأدوات الموزعة (على سبيل المثال، Spark، Ray) لمجموعات البيانات واسعة النطاق

• تنفيذ منطق مخصص (NumPy، C++، إلخ) إذا كان ضبط الأداء أمرًا بالغ الأهمية

في هذا الدليل، نستخدم datasketch للتبسيط والتوافق مع تنسيق إدخال ميلفوس.

تثبيت المكتبات المطلوبة

قم بتثبيت الحزم اللازمة لهذا المثال:

pip install pymilvus datasketch numpy

توليد تواقيع MinHash

سننشئ تواقيع MinHash ذات 256 بُعدًا، مع تمثيل كل قيمة تجزئة كعدد صحيح 64 بت. يتوافق هذا مع تنسيق المتجه المتوقع لـ MINHASH_LSH.

from datasketch import MinHash
import numpy as np

MINHASH_DIM = 256
HASH_BIT_WIDTH = 64

def generate_minhash_signature(text, num_perm=MINHASH_DIM) -> bytes:
    m = MinHash(num_perm=num_perm)
    for token in text.lower().split():
        m.update(token.encode("utf8"))
    return m.hashvalues.astype('>u8').tobytes()  # Returns 2048 bytes

كل توقيع هو 256 × 64 بت = 2048 بايت. يمكن إدراج سلسلة البايت هذه مباشرة في حقل BINARY_VECTOR. لمزيد من المعلومات حول المتجهات الثنائية المستخدمة في ميلفوس، راجع المتجه الثنائي.

(اختياري) إعداد مجموعات الرموز الخام (للبحث المكرر)

بشكل افتراضي، يستخدم Milvus تواقيع MinHash وفهرس LSH فقط للعثور على الجيران التقريبي. هذا سريع ولكنه قد يُرجع نتائج إيجابية خاطئة أو قد يفوتك تطابق تقريبي.

إذا كنت تريد تشابه جاكارد دقيق، فإن ميلفوس يدعم البحث المنقح الذي يستخدم مجموعات الرموز الأصلية. لتمكينه

• تخزين مجموعات الرموز كحقل منفصل VARCHAR

• قم بتعيين "with_raw_data": True عند إنشاء معلمات الفهرس

• وتمكين "mh_search_with_jaccard": True عند إجراء بحث التشابه

مثال على استخراج مجموعة الرموز الرمزية:

def extract_token_set(text: str) -> str:
    tokens = set(text.lower().split())
    return " ".join(tokens)

استخدام MinHash LSH MinHash

بمجرد أن تصبح ناقلات MinHash ومجموعات الرموز الأصلية جاهزة، يمكنك تخزينها وفهرستها والبحث فيها باستخدام Milvus مع MINHASH_LSH.

اتصل بمجموعتك

from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530")  # Update if your URI is different

// java

// nodejs

// go

# restful

تعريف مخطط المجموعة

عرّف مخططًا بـ

• المفتاح الأساسي

• حقل BINARY_VECTOR لتوقيعات MinHash الصغيرة

• حقل VARCHAR لمجموعة الرموز الأصلية (إذا تم تمكين البحث المنقح)

• بشكل اختياري، حقل document للنص الأصلي

from pymilvus import DataType

VECTOR_DIM = MINHASH_DIM * HASH_BIT_WIDTH  # 256 × 64 = 8192 bits

schema = client.create_schema(auto_id=False, enable_dynamic_field=False)
schema.add_field("doc_id", DataType.INT64, is_primary=True)
schema.add_field("minhash_signature", DataType.BINARY_VECTOR, dim=VECTOR_DIM)
schema.add_field("token_set", DataType.VARCHAR, max_length=1000)  # required for refinement
schema.add_field("document", DataType.VARCHAR, max_length=1000)

// java

// nodejs

// go

# restful

بناء معلمات الفهرس وإنشاء مجموعة

إنشاء فهرس MINHASH_LSH مع تمكين تنقيح جاكارد:

index_params = client.prepare_index_params()
index_params.add_index(
    field_name="minhash_signature",
    index_type="MINHASH_LSH",
    metric_type="MHJACCARD",
    params={
        "mh_element_bit_width": HASH_BIT_WIDTH,  # Must match signature bit width
        "mh_lsh_band": 16,                       # Band count (128/16 = 8 hashes per band)
        "with_raw_data": True                    # Required for Jaccard refinement
    }
)

client.create_collection("minhash_demo", schema=schema, index_params=index_params)

// java

// nodejs

// go

# restful

لمزيد من المعلومات حول معلمات بناء الفهرس، راجع بارامز بناء الفهرس.

إدراج البيانات

لكل مستند، قم بإعداد

• توقيع ثنائي MinHash ثنائي

• سلسلة مجموعة رموز متسلسلة

• (اختياريًا) النص الأصلي

documents = [
    "machine learning algorithms process data automatically",
    "deep learning uses neural networks to model patterns"
]

insert_data = []
for i, doc in enumerate(documents):
    sig = generate_minhash_signature(doc)
    token_str = extract_token_set(doc)
    insert_data.append({
        "doc_id": i,
        "minhash_signature": sig,
        "token_set": token_str,
        "document": doc
    })

client.insert("minhash_demo", insert_data)
client.flush("minhash_demo")

// java

// nodejs

// go

# restful

إجراء بحث التشابه

يدعم ميلفوس وضعين للبحث عن التشابه باستخدام MinHash LSH:

• البحث التقريبي - يستخدم فقط توقيعات MinHash و LSH للحصول على نتائج سريعة ولكن احتمالية.

• البحث المنقح - إعادة حساب تشابه جاكارد باستخدام مجموعات الرموز الأصلية لتحسين الدقة.

5.1 إعداد الاستعلام

لإجراء بحث تشابه، قم بإنشاء توقيع MinHash لمستند الاستعلام. يجب أن يتطابق هذا التوقيع مع نفس البعد وتنسيق الترميز المستخدم أثناء إدخال البيانات.

query_text = "neural networks model patterns in data"
query_sig = generate_minhash_signature(query_text)

// java

// nodejs

// go

# restful

5.2 البحث التقريبي (LSH فقط)

هذا سريع وقابل للتطوير ولكن قد يفوتك التطابقات القريبة أو يتضمن نتائج إيجابية خاطئة:

search_params={
    "metric_type": "MHJACCARD", 
    "params": {}
}

approx_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(approx_results[0]):
    sim = 1 - hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

// java

// nodejs

// go

# restful

5.3 البحث المنقح (موصى به للدقة):

يمكّن هذا من إجراء مقارنة دقيقة بين جاكارد باستخدام مجموعات الرموز الأصلية المخزنة في Milvus. إنه أبطأ قليلاً ولكن يوصى به للمهام الحساسة للجودة:

search_params = {
    "metric_type": "MHJACCARD",
    "params": {
        "mh_search_with_jaccard": True,  # Enable real Jaccard computation
        "refine_k": 5                    # Refine top 5 candidates
    }
}

refined_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(refined_results[0]):
    sim = 1 - hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

// java

// nodejs

// go

# restful

بارامترات الفهرس

يقدم هذا القسم نظرة عامة على المعلمات المستخدمة لبناء الفهرس وإجراء عمليات البحث على الفهرس.

معلمات بناء الفهرس

يسرد الجدول التالي المعلمات التي يمكن تكوينها في params عند إنشاء فهرس.

المعلمة	الوصف	نطاق القيمة	اقتراح الضبط
mh_element_bit_width	عرض البت لكل قيمة تجزئة في توقيع MinHash. يجب أن يكون قابلاً للقسمة على 8.	8, 16, 32, 64	استخدم 32 للحصول على أداء ودقة متوازنين. استخدم 64 للحصول على دقة أعلى مع مجموعات بيانات أكبر. استخدم 16 لحفظ الذاكرة مع خسارة مقبولة في الدقة.
mh_lsh_band	عدد النطاقات لتقسيم توقيع MinHash لـ LSH. يتحكم في المفاضلة بين الاستدعاء والأداء.	[1، طول_التوقيع]	للتوقيعات ذات 128 نطاقًا: ابدأ ب 32 نطاقًا (4 قيم/نطاق). قم بالزيادة إلى 64 لاستدعاء أعلى، وقلل إلى 16 لأداء أفضل. يجب تقسيم طول التوقيع بالتساوي.
mh_lsh_code_in_mem	ما إذا كان يجب تخزين رموز تجزئة LSH في ذاكرة مجهولة (true) أو استخدام تعيين الذاكرة (false).	صواب، خطأ	استخدم false لمجموعات البيانات الكبيرة (> 1 مليون مجموعة) لتقليل استخدام الذاكرة. استخدم true لمجموعات البيانات الأصغر التي تتطلب أقصى سرعة بحث.
with_raw_data	ما إذا كان سيتم تخزين توقيعات MinHash الأصلية إلى جانب رموز LSH للتنقيح.	صواب، خطأ	استخدم true عند الحاجة إلى دقة عالية وتكلفة تخزين مقبولة. استخدم false لتقليل نفقات التخزين الزائدة مع تقليل الدقة بشكل طفيف.
mh_lsh_bloom_false_positive_prob	الاحتمال الإيجابي الخاطئ لمرشح بلوم المستخدم في تحسين دلو LSH.	[0.001, 0.1]	استخدم 0.01 للحصول على استخدام متوازن للذاكرة والدقة. تقلل القيم المنخفضة (0.001) من النتائج الإيجابية الخاطئة ولكنها تزيد من الذاكرة. توفر القيم الأعلى (0.05) الذاكرة ولكنها قد تقلل من الدقة.

بارامترات البحث الخاصة بالفهرس

يسرد الجدول التالي المعلمات التي يمكن تكوينها في search_params.params عند البحث في الفهرس.

المعلمة	الوصف	نطاق القيمة	اقتراح الضبط
mh_search_with_jaccard	ما إذا كان يجب إجراء حساب تشابه جاكارد الدقيق على النتائج المرشحة للتنقية.	صواب، خطأ	استخدم true للتطبيقات التي تتطلب دقة عالية (على سبيل المثال، إلغاء التكرار). استخدم false للبحث التقريبي الأسرع عندما يكون فقدان الدقة الطفيف مقبولاً.
refine_k	عدد المرشحين المطلوب استرجاعهم قبل تنقيح جاكارد. فعال فقط عندما يكون mh_search_with_jaccard هو true.	[top_k, *top_k * 10*]	اضبطه على 2-5 أضعاف top_k المطلوب لتحقيق توازن جيد بين الاستدعاء والأداء. تعمل القيم الأعلى على تحسين الاستدعاء ولكنها تزيد من تكلفة الحساب.
mh_lsh_batch_search	ما إذا كان سيتم تمكين التحسين الدفعي للاستعلامات المتزامنة المتعددة.	صواب، خطأ	استخدم true عند البحث باستعلامات متعددة في وقت واحد لتحسين الإنتاجية. استخدم false لسيناريوهات الاستعلام الفردي لتقليل نفقات الذاكرة الزائدة.