Archiwa kategorii: Bez kategorii

Z epopei do punktu – wektoryzacja dokumentów

W poprzednim wpisie stwierdziłem, że klasteryzacja jest przeprowadzana na punktach, skądś jednak te punkty muszą się wziąć, tutaj wkracza proces wektoryzacji.

Jedną z popularniejszych technik wektoryzacji tekstu jest algorytm TF-IDF (Term Frequency – Inverted Document Frequency).

Jaka jest zasada jego działania?

Celem działania algorytmu jest przedstawienie dokumentu w formie liczbowej, wektora wag przedstawiającego wpływ konkretnych słów zawartych w dokumencie na jego znaczenie merytoryczne, semantyczne. Algorytm wyznacza wektor opisujący dokument na podstawie tekstu przy czym każde słowo w tekście ma swoją wagę, zależną od częstotliwości występowania słowa w dokumencie oraz liczbie dokumentów w zbiorze w jakiej znajduje się słowo. Sam algorytm to tak naprawdę połączenie dwóch metod.

Czytaj dalej Z epopei do punktu – wektoryzacja dokumentów

Documents Clustering

This is my first post (actually second, but it is only translation of first) where I’d like to introduce a theoretic basis of Documents Clustering or Clustering in general which topic is close to me recently.

What does Document Clustering is about?

So, to explain Document Clustering it is good idea to define what is Clustering in general before.

Human is a being that likes to join things like objects, facts persons into groups or categories (here let’s call their clusters) to better or easier understand a world around. Let’s get people as an example. Imagine that you go the street and describe people you pass by sentences like: old man, another old man, nice girl, not very nice girl etc. We could describe them by their age, height, hair colour, style of wearing etc. In short, we could find many informations their would be categorised by.

So, what is this Clustering?

By definition we could say, clustering is a process of assignment of objects into groups where object in group is more similar to objects in this group than to all other groups. Result of this process are object of upper class (of abstraction), groups in which objects should be homogeneous or at least similar to each others.

What does that definition tell us?

So, having a set that contais some undefined strictly number of people we want to cluster, result should be groups where in range of group people would be related by some attribute that was used to describe them. Did we describe people by their hobbys, here we are, the result going to be groups related to same or similar hobby.

How does it look in practice?

Clustering is operation on a points.

Clustering example
Graphics source

Exacly. Points are grouped by distance between them and that’s how they are assigned to clusters. In most cases there is estimated a center point of cluster, centroid and then points are assigning to the nearest centroids.

Coming back to our example with people. How could we „clusterize” people if clustering algorithms work on points, numbers?

The way to do that is called vectorization. It is a proccess that converts more abstract objects like documents (or people as in example) into form of numbers. Products of this process, vectors are matrices with one column (or row if matrix is transformed). Each element of vector is related to one property’s numeric representation. Value of element means a weight, a extent of related attribute with object.

Let’s say we want to describe some group of people with wectors. We get 3 properties describing them, the easiest properties to vectorize would be: age, height and weight as they are numbers.

So, vector looks like:

[age, height, weight]

For example: [18, 182, 85], [25, 164, 58], [35, 170, 89], [53, 179, 88].

We’ve got a point in 3D space that describes people by mentioned attributes then it should not be a problem to create groups with similarities of age, height or weight. Obviously 4 points are not enough to do this effectively, so we need it more.

But wait.

As we know, clustering bases on distances. Having unregular data like that, I mean, influence of height or weight would be much bigger than influence of age on distribution of points, distances between them. Good idea would be weighting of values. For instance a value of element would be a quotient of some maximum value or value’s probability from normal distribution.

How does it work with documents?

It is very similar way to clustering documents that present as example before. Documents are converted into vectors by weight of word inside, calculated from analysis whole set of documents. Next, the multidimensional points are assigned to clusters by distances from each others. Description of algorithms to create vectors from text and to clustering are topics for another post.

O klasteryzacji dokumentów

English version is here

Jest to mój pierwszy wpis w którym chciałbym przedstawić podstawy teoretyczne klasteryzacji dokumentów, tematu w ostatnim czasie mi bliskiemu.

Czym jest owa klasteryzacja dokumentów?  

Aby ją opisać, pierw należy zdefiniować czym jest sama klasteryzacja.

Człowiek z natury ma skłonność do grupowania pewnych obiektów, rzeczy, faktów a także ludzi w większe klasy, grupy, kategorie lub zgodnie z tytułem nazwijmy je klastrami. Niech przykładem w tym artykule będą ludzie. Idąc ulicą i opisując kolejnych ludzi których mijamy moglibyśmy rzucać stwierdzeniami typu: starszy pan, następny starszy pan, ładna kobieta, brzydka kobieta, kuc i tak dalej. Moglibyśmy opisywać ich według ich wieku, wzrostu, koloru włosów, typu ubrania. Słowem znaleźlibyśmy wiele dziedzin w jakich moglibyśmy skatalogować ludzi.

Czym jest więc klasteryzacja?

Jeśliby przedstawić jej definicję, można stwierdzić, że klasteryzacja to proces takiego przydziału obiektów do grup do których skatalogowany obiekt należy do klastra do którego należy w większym stopniu niż do pozostałych. Wynikiem procesu klasteryzacji są obiekty wyższego rzędu, grupy, skupiające wewnątrz jednorodne grupy obiektów.

Co nam mówi ta definicja?

Cóż, mając zestaw zawierający pewną liczbę osób, którą chcemy poddać klasteryzacji, wynikiem byłyby grupy osób, które w ramach grupy łączyłaby wspólna cecha, taka która zostałaby użyta do oceny konkretnej osoby. Czy osoby opisane są poprzez zainteresowania? Proszę bardzo, wynikiem  będą grupy ludzi o tych samych / podobnych zainteresowaniach.

Jak to wygląda w praktyce?

Klasteryzacja jest działaniem na punktach.

Obrazowy przykład klasteryzacji
Źródło grafiki

Dokładnie. Punkty grupowane są według odległości od siebie i według odległości przypisywane do klastrów. Przeważnie wyznaczany jest pewien punkt środkowy klastra, tzw. centroid, i wszystkie punkty przypisywane są do najbliższych centroidów, stąd każdy punkt w klastrze jest bliżej środka własnego klastra niż pozostałych środków.

Wróćmy do naszego przykładu z ludźmi. Jak niby mamy „sklasteryzować” ludzi, jeśli klasteryzacja działa tylko na punktach.

Da się ich jakoś zamienić?

Oczywiście, że się da. I ludzi i dokumenty tekstowe, które też punktami nie są a klasteryzowalne są. Proces odpowiedzialny za zamianę bardziej abstrakcyjnych na formę liczbową nazywany jest wektoryzacją. Wektory, czyli produkty tego procesu są macierzami o jednej kolumnie (a po transformacji o jednym wierszu). Każdy wiersz, czy może ściślej, każdy element wektora przyporządkowany jest jednej cesze. Wartość wektora w danym miejscu odpowiada zwyczajnie wadze, stopniu przynależności do tych cech.

Posłużę się znów moimi obiektami doświadczalnymi.

Załóżmy, że chcemy zamienić cechy określonej grupy ludzi na wektory. Niech będą to 3 cechy, które łatwo można określić liczbami, przyjmijmy, że pierwszy element wektora będzie oznaczał wiek, drugi wzrost, trzeci wagę.

[wiek, wzrost, waga]

I stwórzmy przykładowe wektory ludzi:

[18, 182, 85], [25, 164, 58], [35, 170, 89], [53, 179, 88].

Tak więc mamy punkty określające ludzi, a przynajmniej pewne ich cechy. Mając takich wektorów więcej można przeprowadzić klasteryzację wektorów i pogrupować ludzi według ich wagi, wzrostu i wieku.

Ale ale, nie tak szybko.

Wiedząc, że klasteryzacja działa w oparciu o odległości pomiędzy punktami, mając tak nieregularne dane, wpływ wzrostu lub wagi może mieć większy wpływ na wygląd zbioru niż wieku. Stąd dobrym  pomysłem jest wpisywanie konkretnych wag do wektorów zamiast konkretnych wartości. Przykładowo mogą to być ilorazy wartości i predefiniowanej maksymalnej wartości. Innym pomysłem mogłoby być prawdopodobieństwo wynikające z rozkładu normalnego dla danej wartości.

Jak to wygląda w przypadku dokumentów?

Bardzo podobnie. Dokumenty zamieniane są na wektory a wartościami wektorów są konkretne wagi dla słów (i/lub) zwrotów znajdujących się w dokumencie wyliczanych na podstawie analizy całego zbioru dokumentów. Następnie tak utworzone wielowymiarowe punkty są klasteryzowane według odległości punktów od siebie. Opis algorytmów tworzących wektory dokumentów i klasteryzacji to już temat na inny wpis.