W ostatnim czasie miałem okazję zastanowić nad problemem klasyfikacji produktów w oparciu o ich jednozdaniowe opisy. Moim głównym celem było wykrycie nazw kolekcji lub serii produktów (np. dla butów marki Adidas są to m.in. copa, superstar). Podczas małego researchu udało mi się znaleźć kilka gotowych rozwiązań. Niestety jak w przypadku nazw produktów radziły sobie całkiem dobrze, tak w przypadku nazw kolekcji było przeciętnie. W dzisiejszym wpisie chciałem podzielić się własną koncepcją rozwiązania tego problemu, która nie wykorzystuje uczenia maszynowego.


Przykładowy kod do tego wpisu dostępny jest na moim GitHubie.

# Lista bibliotek z których korzystam:
  
import pandas as pd
import regex
import string
from nltk import word_tokenize, FreqDist
from nltk.corpus import stopwords

Niech \(n\) będzie liczbą sentencji \(S = \{s_1, s_2, s_3, ..., s_n\}\) (np. tytuły aukcji z serwisu Allegro). Moim celem jest znalezienie takiego zbioru słów \(X = \{x_1, x_2, x_3, ..., x_m\}\), które razem występują we wszystkich sentencjach, ale żadne dwa słowa nie występują w tej samej sentencji. Bardziej formalnie \(\forall s\in S\ \exists x\in X: słowo\ x\ jest\ fragmentem\ sentencji\ s\) i \(\forall i,j: x_i\ jest\ fragmentem\ sentencji\ s \wedge x_j\ jest\ fragmentem\ sentencji\ s \implies i=j\). Zbiorów spełniających te kryteria może być bardzo dużo (wszystko zależy od kategorii produktów, długości sentencji, liczby sentencji i wielu innych parametrów). Opracowanie algorytmu, który znajdzie zbiór \(X\) to jedno, a znalezienie właściwego zbioru (zawierającego wyłącznie nazwy producentów, albo nazwy kolekcji) to drugie.

W tym wpisie skupiam się głównie na pierwszej części problemu, a mianowicie znalezieniu zbioru spełniającego oba warunki. W praktyce dane nie są idealne (szczególnie, że mogą zawierać błędy), dlatego warunki mogą być nieco osłabione. Słowa ze zbioru \(X\) nie muszą występować we wszystkich sentencjach (wystarczy 90%-95% pokrycie). Dodatkowo dopuszczam możliwość współwystępowania słów ze sobą (np. maksymalnie pięć sentencji). Dla lepszego zrozumienia rozwiązania problemu pobrałem 6000 tytułów aukcji z serwisu Allegro, które dotyczyły butów sportowych (allegro-sports-shoes.csv) i na tych danych będę pracował w dalszej części wpisu.

df = pd.read_csv("allegro-sports-shoes.csv", sep=';', encoding='utf-8')
data = list(df.iloc[:, 0])
data[:3]
## ['Buty Nike air max 270 czerwone 43', 'Buty męskie Umbro Prime II UMMX218001', 'Buty męskie sportowe Adidas Galaxy 4 F36171']

Duża część znaków i słów może zostać usunięta z sentencji na samym początku. Z uwagi na optymalizację część kodu oczyszczającego (np. stopwords) przeniosłem do dalszej części.

def clean_data(data, filter=None):
    data = [x.lower() for x in data]
    data = [regex.sub('|\\'.join(string.punctuation), ' ', x) for x in data]
    data = [regex.sub(' ([0-9]+[^ ]{0,} )+', ' ', x) for x in data]
    data = [regex.sub('^[0-9]+[^ ]{0,} ', ' ', x) for x in data]
    data = [regex.sub(' [0-9]+[^ ]{0,}$', ' ', x) for x in data]
    if filter:
        data = [x for x in data if x.find(filter) > -1]
        
    return data

Oczyszczone sentencje konwertuję do tabeli częstości słów. Każda kolumna takiej tabeli reprezentuje słowa występujące w sentencjach. Wiersze reprezentują kolejne sentencje. W komórkach znajduje się informacja o liczbie słów w sentencji.

def prepare_freq_table(data):
    freq_table = [word_tokenize(x) for x in data]
    freq_table = [dict(FreqDist(x)) for x in freq_table]
    freq_table = pd.DataFrame.from_dict(freq_table)
    freq_table = freq_table.fillna(0)
    
    return freq_table

Powstała tabela posłuży do poszukiwania słów, które ze sobą nie występują. Z punktu widzenia algorytmu poszukuję wektorów (kolumn), których suma iloczynu jest zerowa (można na to patrzeć jak na prostopadłość wektorów).

Poniżej przykład słów, które ze sobą nie współwystępują (iloczyn wektorów puma i adidas jest wektorem zerowym).

##    puma adidas
## 1     0      0
## 2     0      1
## 3     0      0
## 4     1      0
## 5     0      0
## 6     0      0
## 7     0      0
## 8     0      1
## 9     0      1
## 10    0      1

Kolejny przykład dotyczy słów, które ze sobą współwystępują (iloczyn wektorów adidas i racer jest wektorem niezerowym)

##    adidas racer
## 1       0     0
## 2       0     0
## 3       0     0
## 4       1     0
## 5       1     1
## 6       0     0
## 7       1     0
## 8       1     1
## 9       0     0
## 10      1     1

Poniższa funkcja pozwala na porównanie ze sobą dwóch wektorów. Zakładam, że dane wejściowe nie są idealne i mogą zdarzyć się sytuacje, że słowa, których poszukuję mogą bardzo rzadko ze sobą występować. Na przykład aukcja, gdzie ktoś sprzedaje kilka par butów z różnych kolekcji.

def prepare_perp_summary(v1, v2, term1, term2, perp_threshold=5):
    iloc = sum(v1*v2)
    size = sum(v1) + sum(v2)
    
    return {'term1': term1,
            'term2': term2,
            'distance': iloc,
            'is_perp': iloc < perp_threshold,
            'size': size,
            'size_term1': sum(v1),
            'size_term2': sum(v2),
            'size_prop12': sum(v1)/sum(v2),
            'size_prop21': sum(v2)/sum(v1)}

Funkcja prepare_perp_table generuje porównania dla wszystkich par słów. Jest to aktualnie wąskie gardło algorytmu, dlatego przed generowaniem porównań usuwam krótkie słowa (jedno i dwuznakowe), usuwam stopwords oraz usuwam słowa, które występują prawie zawsze i prawie nigdy.

def prepare_perp_table(freq_table, sw='polish', rm_low_freq=5, rm_high_freq=5, perp_threshold=5):
    # remove short words
    data = freq_table.iloc[:, freq_table.columns.map(lambda x: len(x) > 2)]
    # remove polish stopwords
    data = data.iloc[:, ~data.columns.isin(stopwords.words(sw))]
    # remove words with low and hight frequency
    data = data.iloc[:, list(data.sum() > rm_low_freq)]
    data = data.iloc[:, list(data.sum() < data.shape[0] - rm_high_freq)]
    # convert positive numbers to 1
    for c in data.columns:
        data[c] = data[c].map(lambda x: 1 if x > 0 else 0)

    perp_table = []
    for i in range(data.shape[1]-1):
        for j in range(i+1, data.shape[1]):
            perp_table += [prepare_perp_summary(data[data.columns[i]],
                                                data[data.columns[j]],
                                                data.columns[i],
                                                data.columns[j],
                                                perp_threshold=perp_threshold)]
    perp_table = pd.DataFrame.from_dict(perp_table)
    perp_table = perp_table[perp_table.is_perp]
    
    return perp_table

Pozostaje już tylko algorytm, który wygeneruje zbiór słów spełniających założenia.

Funkcja find_perp_set działa w następujący sposób:
1. wybierz parę słów nie występujących wspólnie, które znajdują się w największej liczbie sentencji. Stosunek liczebności tych słów do siebie nie może przekraczać wartości parametru max_proportion.
2. znajdź wszystkie słowa, które nie występują z żadnym z poprzednio wybranych słów
3. spośród wybranych słów wybierz jedno, które występuje w największej liczbie sentencji (zachowaj proporcje max_proportion).
4. powtarzaj punkt 2 i 3 dopóki znalezione słowa nie będą obejmowały 90% sentencji (wartość domyślna parametrubp).

def find_perp_set(perp_table, input_data_len, max_proportion=3, bp=0.90):
    # find two perp words with the highest size
    curr_set = perp_table[(perp_table.size_prop12 < max_proportion) & \
                          (perp_table.size_prop21 < max_proportion)].sort_values(by=['size']).iloc[-1, :]
    curr_set = [curr_set.term1, curr_set.term2]

    p = perp_table[perp_table.term1.isin(curr_set) & perp_table.term2.isin(curr_set)]
    print('+{}: {}% size of set'.format(curr_set[0], round(p['size_term1'].sum()/(input_data_len) * 100, 2)))
    p = p['size'].sum() / (input_data_len)
    print('+{}: {}% size of set'.format(curr_set[1], round(p * 100, 2)))

    while p < bp:
        tmp_perp_table = perp_table[~(perp_table.term1.isin(curr_set) & perp_table.term2.isin(curr_set))]

        # find perp elements to curr_set
        tt = []
        for c in curr_set:
            t = tmp_perp_table[(tmp_perp_table.term1 == c) | (tmp_perp_table.term2 == c)]
            t = list(set(list(t.term1) + list(t.term2)))
            t.remove(c)
            tt += [t]

        # find perp elements to all words in curr_set
        perp_terms = tt[0]
        for i in range(1, len(tt)):
            perp_terms = list(set(perp_terms) & set(tt[i]))

        tmp_set = tmp_perp_table[((tmp_perp_table.term1.isin(perp_terms) & tmp_perp_table.term2.isin(curr_set)) |
                                  (tmp_perp_table.term1.isin(curr_set) & tmp_perp_table.term2.isin(perp_terms))) &
                                 ((tmp_perp_table.size_prop12 < max_proportion) &
                                  (tmp_perp_table.size_prop21 < max_proportion))].sort_values(by=['size'])
        if tmp_set.shape[0] > 0:
            tmp_set = tmp_set.iloc[-1, :]
            tmp_set = list(set(perp_terms) and set([tmp_set.term1, tmp_set.term2]))
            new_term = [x for x in tmp_set if x not in curr_set]

            # add this element to curr_set
            curr_set = list(set(curr_set + new_term))

            p = perp_table[perp_table.term1.isin(curr_set) & perp_table.term2.isin(curr_set)]['size'].sum()/((len(curr_set)-1)*input_data_len)
            print('+{}: {}% size of set'.format(new_term[0], round(p*100, 2)))
        else:
            print('early stoping - no more words')
            break
            
    return curr_set

Czas na testy.

df = pd.read_csv("allegro-sports-shoes.csv", sep=';')
data = list(df.iloc[:, 0])
data = clean_data(data, filter)
freq_table = prepare_freq_table(data)
perp_table = prepare_perp_table(freq_table)
perp_set_1 = find_perp_set(perp_table, input_data_len=len(data))
## +adidas: 29.15% size of set
## +nike: 49.17% size of set
## +puma: 58.37% size of set
## +balance: 67.17% size of set
## +reebok: 73.6% size of set
## +adidasy: 77.78% size of set
## +lacoste: 81.05% size of set
## +asics: 83.62% size of set
## +kappa: 85.2% size of set
## +under: 86.15% size of set
## +salomon: 86.9% size of set
## +timberland: 87.6% size of set
## +caterpillar: 88.25% size of set
## +timberland: 88.85% size of set
## +trapery: 89.37% size of set
## +vans: 89.83% size of set
## +big: 90.28% size of set

Pierwsza iteracja wypadła całkiem nieźle. Od razu widać kilka elementów, nad którymi trzeba będzie popracować. Pierwszy z nich to rozszerzenie o wyrażenia składające się z kilku słów (tutaj New Balance, Big Star). Kolejny problem to odmiany (tutaj adidasy).

Do rozważenia jest także zastosowanie rekurencji. Sprawdzam co się stanie na danych przefiltrowanych po słowie puma.

df = pd.read_csv("allegro-sports-shoes.csv", sep=';')
data = list(df.iloc[:, 0])
data = clean_data(data, filter='puma')
freq_table = prepare_freq_table(data)
perp_table = prepare_perp_table(freq_table)
perp_set_2 = find_perp_set(perp_table, input_data_len=len(data))
## +classic: 8.7% size of set
## +drift: 34.24% size of set
## +ignite: 41.85% size of set
## +smash: 48.37% size of set
## +runner: 52.36% size of set
## +rebound: 55.98% size of set
## +nrgy: 59.42% size of set
## +mid: 62.14% size of set
## +evospeed: 64.67% size of set
## +enzo: 66.49% size of set
## +turin: 68.3% size of set
## +court: 69.93% size of set
## +mesh: 71.56% size of set
## +knit: 73.19% size of set
## +jago: 74.64% size of set
## +miejskie: 76.09% size of set
## +whirlwind: 77.54% size of set
## +trainer: 78.99% size of set
## +tekstylne: 80.43% size of set
## +tsugi: 81.7% size of set
## +lite: 82.79% size of set
## +halowe: 83.88% size of set
## +desierto: 84.96% size of set
## +wyprzedaż: 86.05% size of set
## +evo: 87.14% size of set
## early stoping - no more words

Na kolejnym poziomie wyniki także są bardzo fajne. Jedyne do czego można się przyczepić to do takich słów jak wyprzedaż, ale to pozostaje w kwestii lepszego oczyszczenia danych wejściowych.

Podsumowując, wydaje mi się, że algorytm ma pewien potencjał, ale też wymaga jeszcze sporo pracy. Być może już w tej wersji może być to fajne narzędzie wspierające prace analityka.