!pip install recordlinkage
!pip install datasketch

Proszę zaimportować wymagane biblioteki

import numpy as np
import pandas as pd
import re
import time
from datasketch import MinHash, MinHashLSHForest
import recordlinkage
from recordlinkage.datasets import load_febrl1

Ten kod ładuje wbudowany zestaw danych (febrl1) przy użyciu funkcji load_febrl1() z modułu recordlinkage.datasets. Następnie łączy wszystkie kolumny zbioru danych w jedną kolumnę, z wyjątkiem kolumn określonych na liście exclude_columns. Na koniec scalona kolumna jest dodawana do oryginalnej DataFrame jako nowa kolumna o nazwie “text”.

# Loading and using the in-built dataset 
df = load_febrl1()
# Columns to exclude from merging
exclude_columns = []
# Merge all columns into a single column except for the excluded columns
merged_column = df.drop(columns=exclude_columns).apply(lambda x: ' '.join(x.astype(str)), axis=1)
# Add the merged column to the DataFrame
df["text"]=merged_column
df.head()

Ten kod tasuje DataFrame df przy użyciu funkcji sample() z ustalonym stanem losowym w celu zapewnienia powtarzalności (random_state=42). Następnie oblicza liczbę wierszy dla zestawów treningowych i testowych na podstawie określonych proporcji (99% dla treningu i 1% dla testów).

Następnie dzieli przetasowaną ramkę DataFrame na zestawy treningowe i testowe przy użyciu funkcji iloc aby wybrać wiersze do obliczonych indeksów dla zestawu treningowego (df_shuffled.iloc[:train_size]) i pozostałe wiersze dla zestawu testowego (df_shuffled.iloc[train_size:]).

Na koniec resetuje indeks zarówno dla ramek treningowych, jak i testowych DataFrame przy użyciu funkcji reset_index() za pomocą funkcji drop=True aby odrzucić stary indeks i zastąpić go nowym indeksem sekwencyjnym. Ten krok jest opcjonalny.

# Shuffle the DataFrame
df_shuffled = df.sample(frac=1, random_state=42)  # Shuffle with a fixed random state for reproducibility
# Calculate the number of rows for training and testing
train_size = int(0.99 * len(df))
test_size = len(df) - train_size
# Split the shuffled DataFrame into training and testing sets
df_train = df_shuffled.iloc[:train_size]
df_test = df_shuffled.iloc[train_size:]
# Reset index for both DataFrames if needed (Optional)
df_train.reset_index(drop=True, inplace=True)
df_test.reset_index(drop=True, inplace=True)

Poniższa funkcja tokenize_per_n_characters pobiera tekst wejściowy i tokenizuje go na n-znakowe fragmenty.

def tokenize_per_n_characters(text,n):
    tokens = []
    for i in range(len(text) - (n - 1)):
        tokens.append("'" + text[i:i+n] + "'")
    return tokens

To preprocess_text służy do wstępnego przetwarzania wprowadzonego tekstu.

• Lowercasing: Konwertuje cały tekst na małe litery przy użyciu funkcji lower() .
• Usunięcie interpunkcji,@‘ i kropek: Definiuje ona zmienną łańcuchową remove_chars zawierającą wszystkie symbole interpunkcyjne, ‘@‘ i kropki. Następnie używa on translate() metodę str.maketrans() aby usunąć te znaki z tekstu.
• Tokenizacja: Wywołuje tokenize_per_n_characters() funkcję tokenizującą wstępnie przetworzony tekst na tokeny o określonej długości n. tokenize_per_n_characters() zakłada się, że funkcja jest zdefiniowana w innym miejscu kodu.

import string
def preprocess_text(text):
    # Lowercasing
    text = str(text).lower()
    # Removing punctuation, @ symbols, and dots
    remove_chars = string.punctuation + '@.'
    text = text.translate(str.maketrans('', '', remove_chars))
    # Whitespace tokenization
    tokens = tokenize_per_n_characters(text,n)
    return tokens

To get_forest służy do budowania lasu LSH dla danego zbioru danych.

Parametry wejściowe

• dane: Zbiór danych zawierający tekst, który ma zostać zaszyfrowany. W tym przypadku będzie to df_train
• perms: Liczba permutacji dla MinHash. Kluczową ideą MinHash jest wykorzystanie permutacji elementów w zbiorze do tworzenia różnych funkcji skrótu. Każda permutacja definiuje unikalną funkcję skrótu. Liczba permutacji używanych w MinHash określa dokładność szacowania podobieństwa. Większa liczba permutacji generalnie prowadzi do lepszej dokładności, ale wymaga więcej zasobów obliczeniowych.
• zespoły: Liczba pasm, na które należy podzielić sygnaturę MinHash.
• rows_per_band: Liczba wierszy na pasmo dla LSH.

Proces

• Tokenizacja: Iteruje przez każdy tekst w zbiorze danych i wstępnie przetwarza go za pomocą funkcji preprocess_text.
• Hashing: Następnie generuje podpisy MinHash dla każdego tekstu przy użyciu określonej liczby permutacji (perms). Te podpisy MinHash są dodawane do listy.
• Budowanie lasu LSH: Inicjuje las LSH z określoną liczbą permutacji (perms). Następnie dodaje każdą sygnaturę MinHash do lasu LSH.
• Indeksowanie: Po dodaniu wszystkich podpisów MinHash indeksuje las LSH.
• Zapytanie o kandydujące pary: Odpytuje las LSH, aby znaleźć kandydujące pary podobnych tekstów. Dla każdej sygnatury MinHash pobiera określoną liczbę kandydujących wyników (num_results) z lasu LSH.
• Grupowanie kandydujących par w pasma: Grupuje pary kandydatów w pasma na podstawie ich wartości hash. Odbywa się to poprzez haszowanie pierwszych wartości pasma sygnatury MinHash.
• Drukowanie pasm z wieloma parami: Drukuje pasma wraz z parami podobnych tekstów znalezionych w każdym paśmie.

Wyjście

• Zwraca skonstruowany LSH Forest (forest) i słownik (bands_dict) zawierający pasma jako klucze i pary podobnych tekstów jako wartości.
• Dodatkowe uwagi: Indeksowanie w lesie LSH (Locality Sensitive Hashing) polega na organizowaniu danych w tabele haszujące na podstawie ich wartości haszujących. Każda tabela hashowa zawiera wiadra, a każde wiadro przechowuje odniesienia do punktów danych o podobnych wartościach hash. Ten proces indeksowania pozwala na efektywne pobieranie przybliżonych najbliższych sąsiadów podczas operacji zapytań. Kluczową ideą jest grupowanie podobnych punktów danych w oparciu o ich sygnatury hash, co umożliwia szybsze wyszukiwanie i pobieranie w porównaniu z metodami brute-force, zwłaszcza w przestrzeniach wielowymiarowych.

def get_forest(data, perms,bands, rows_per_band):
    start_time = time.time()
    minhash = []
    for text in data['text']:
        tokens = preprocess_text(text)
        m = MinHash(num_perm=perms)
        #print("value of m is ", str(m))
        for s in tokens:
            m.update(s.encode('utf8'))
        minhash.append(m)
    #for i,n in enumerate(minhash):
        #print("MinHash {}: hash values = {}".format(i+1, n.hashvalues))
        
    forest = MinHashLSHForest(num_perm=perms)
    
    for i,m in enumerate(minhash):
        forest.add(i,m)
        
    forest.index()
    # Query LSH Forest to find candidate pairs
    candidate_pairs = {}
    num_results=rows_per_band
    for i, m in enumerate(minhash):
        result = forest.query(m,num_results )
        for j in result:
            if i < j:  # Ensure no duplicate pairs
                candidate_pairs[(i, j)] = True
    
    # Group candidate pairs into bands based on their hash values
    bands_dict = {}
    for (row1, row2) in candidate_pairs.keys():
        band_hash = hash(tuple(sorted(minhash[row1].hashvalues[:bands])))
        if band_hash not in bands_dict:
            bands_dict[band_hash] = []
        bands_dict[band_hash].append((row1, row2))
    
    # Print bands with multiple pairs
    for band, pairs in bands_dict.items():
        if len(pairs) > 1:
            print("Band hash:", band)
            print("Pairs:", pairs)
    
    print('It took %s seconds to build forest.' %(time.time()-start_time))
    return forest,bands_dict

Przykładowy wynik: Band hash: -7380833634571281130 Pairs: [(9, 978), (402, 823)] Band hash: -1902129179255886798   Pairs: [(16, 727), (255, 788), (733, 879)]

• Band hash: Odnosi się do wartości skrótu obliczonej na podstawie sygnatury MinHash rekordów w określonym paśmie. Każde pasmo składa się z wielu wartości MinHash, a hash pasma jest obliczany przez hashowanie tych wartości. Pomaga to w efektywnym grupowaniu podobnych rekordów w zespoły.
• Pairs: Jest to lista krotek, gdzie każda krotka reprezentuje parę indeksów odnoszących się do rekordów w zbiorze danych. Indeksy te wskazują pozycje podobnych rekordów w oryginalnym zbiorze danych. Na przykład (9, 978) wskazuje, że rekordy na pozycjach 9 i 978 w zbiorze danych są podobne, a (402, 823) wskazuje, że rekordy na pozycjach 402 i 823 są podobne.

#Number of Permutations
permutations = 128
bands=2
rows_per_band=2
f,b=get_forest(df_train, permutations,bands, rows_per_band)

Następna funkcja iteruje po parach podobnych rekordów przechowywanych w zbiorze danych bands_dict słowniku, pobiera odpowiednie rekordy z DataFrame danych przy użyciu ich indeksów i dołącza je do listy podobnych rekordów. Na koniec zwraca listę podobnych rekordów w istniejącym zestawie danych szkoleniowych.

def check_similar_records(bands_dict, data):
    similar_records = []
    for pairs in bands_dict.values():
        for (row1, row2) in pairs:
            record1 = data.iloc[row1]
            record2 = data.iloc[row2]
            similar_records.append((record1, record2))
    return similar_records

# usage
similar_records = check_similar_records(b, df_train)

print(len(similar_records)) ####It has identified 491 similar records
print(similar_records[1])

Funkcja predict pozwala znaleźć podobne rekordy w bazie danych na podstawie podanego tekstu, efektywnie wykorzystując indeksowanie MinHash i LSH forest.

• Przetwarzanie wstępne: Przetwarza wstępnie tekst wejściowy, tokenizując go i generując obiekt MinHash na podstawie tokenów.
• Zapytanie do lasu LSH: Odpytuje las LSH za pomocą wygenerowanego obiektu MinHash, aby znaleźć podobne rekordy w bazie danych.
• Pobieranie wyników: Pobiera podobne rekordy z bazy danych na podstawie indeksów zwróconych przez zapytanie LSH forest.
• Dane wyjściowe: Zwraca podobne rekordy znalezione w bazie danych na podstawie wprowadzonego tekstu.

def predict(text, database, perms, num_results, forest):
    start_time = time.time()
    
    tokens = preprocess_text(text)
    m = MinHash(num_perm=perms)
    for s in tokens:
        m.update(s.encode('utf8'))
        
    idx_array = np.array(forest.query(m, num_results))
    if len(idx_array) == 0:
        return None # if your query is empty, return none
    
    result = database.iloc[idx_array]['text']
    
    #print('It took %s seconds to query forest.' %(time.time()-start_time))
    
    return result

rec: Jest to rzeczywisty tekst, dla którego znajdujemy pasujące rekordy w lesie (f) utworzonym przez df_train dataset. Wartość permutacji pozostanie taka sama.

#Number of Recommendations to return
num_recommendations = 1
df_test_small=df_test.head(5)
df_test_small["text"].head()
#rec="nichol prideaux 9 hicks street loccation 7229 bondi junction 5011 sa 19420429 1107619"
for rec in df_test_small["text"]:
    print("Actual records is ", rec , "\n")
    res=predict(rec, df_train, permutations, num_recommendations, f)
    print("Similar records is ", res)
    print("\n\n")

Actual records is  marianne rees 6 nerli place weeroona mansfield 3644 sa 19770628 4235561 

Similar records is  789    rees maribanne 6 nerli place weeroona mansfield 3644 sa 19770628 4235561
Name: text, dtype: object



Actual records is  isabella ayres 1075 arthur circle grevilla est glenwood 5112 qld 19531230 9208787 

Similar records is  390    isabella ayrse 1075 arthur circle grevilal est glewnood 5121 qld 19531230 9208787
Name: text, dtype: object



Actual records is  kirra brock 93 clarnette place backwoodlands orbost 2528 vic 19231209 5107876 

Similar records is  407    kirar brock 93 clarnette place nan orbost 2528 vic 19231209 5107876
Name: text, dtype: object



Actual records is  christina coleman 506 hall street rsde 817 wallace woolgoolga 3073 qld 19070811 6822993 

Similar records is  457    christina colemn 506 hall street rsde 817 wallace woolgoolga 3063 qld 19070811 6822993
Name: text, dtype: object



Actual records is  joshua rickett 1 burraly court malladup new farm 2439 act 19030121 4310453 

Similar records is  486    joshua rickett 1 burraly corut malladuo belleve hill 2439 act 19030121 4310453
Name: text, dtype: object

Poniższa funkcja umożliwia przyrostową aktualizację lasu LSH o nowe rekordy tekstowe i identyfikację wszelkich nowych pasm utworzonych przez te aktualizacje.

• Przetwarzanie wstępne: Przetwarza wstępnie nowy tekst poprzez tokenizację.
• Tworzenie MinHash: Generuje obiekt MinHash dla nowego tekstu na podstawie tokenów.
• Dodawanie MinHash do lasu: Dodaje nowy MinHash do lasu LSH.
• Odpytywanie lasu: Odpytuje las LSH w celu znalezienia par kandydujących dla nowego MinHash.
• Grupowanie w pasma: Grupuje kandydujące pary w pasma na podstawie ich wartości hash.
• Drukowanie nowych pasm: Jeśli nowy rekord tworzy zespół z wieloma parami, drukuje hash zespołu i pary.

def update_forest(forest, bands_dict, new_text, perms, bands, rows_per_band):
    
    # Preprocess the new text
    tokens = preprocess_text(new_text)
    
    # Create MinHash for the new text
    new_minhash = MinHash(num_perm=perms)
    for s in tokens:
        new_minhash.update(s.encode('utf8'))
    
    new_index = "m6"
    # Add the new MinHash to the forest
    forest.add(new_index, new_minhash)
    forest.index()
    
    
    # Query LSH Forest to find candidate pairs with the new MinHash
    num_results=rows_per_band
    result = forest.query(new_minhash, num_results)
    
    # Group candidate pairs into bands based on their hash values
    new_band_hash = hash(tuple(sorted(new_minhash.hashvalues[:bands])))
    if new_band_hash not in bands_dict:
        bands_dict[new_band_hash] = []
    bands_dict[new_band_hash].append(new_index)  # Append the index of the new record
    
    # Print the new bands with multiple pairs
    if len(result) > 1:
        print("New record created a band with multiple pairs:")
        print("Band hash:", new_band_hash)
        print("Pairs:", [(new_index, idx) for idx in result if idx < new_index])