documentation_crawling

Влечење на информации


Мојата платформа има преку 60 извори од кои влече содржини. Секоја страница има свој начин на структурирање на информациите и мојот 'crawler' треба
да се справи со сите ситуации и да ги извлече најбитните информации од секоја содржина:
- датум на објавување
- наслов на текстот
- содржина на текстот
- слика поврзана со текстот

Многумина од изворите ставаат во статички информации во крајот/почетокот на текстовите. Нашата платформа, кога ги обработува текстовите, потребно
е да ги игнорира овие информации поради две причини:
- не придонесуваат многу за објаснување на природата на текстот
- исти информации, доколу се многу, можат да влијаат негативно на алгоритмите за кластерирање такашто алгоритмот ќе
ги смести два текста во ист кластер, само поради тоа што имаат исти мета податоци.

Како решение на овој проблем, направив една табела која за секоја страница ни кажува кои параграфи треба да се игнорираат.
Со ова го влечеме само текстот, а ги игнорираме информациите кои не се директно поврзани со текстот.

Дополнителен проблем претставуваше влечењето на датумот на објавување на содржините. Различни страници во различен формат ги претставуваат времињата на објавување.
Потребно беше да се направи парсер кој ќе се справи со различните формати на датумите.


<Хиерархиско кластерирање>

Како што претходно беше наведено, со хиерархиско кластерирање се изврши групирањето на повлечените содржини.
После собирањето на содржините, претворање во векторски простор со помош на tf-idf векторизација, почнува кластерирањето.
На почеток, секој текст е претставен како точка во 100 000 димензионален простор и секој текст е посебен кластер.

1. Потоа, според одредена метрика, се бираат двата најблиски кластери.

    <Метрика за растојание>

        Метриката за блискост (сличност) помеѓу кластерите која ја користев беше косинусно растојание.
        Причината поради која се одлучив за ова растојание, а не на пример за Евклидово е следнава:
        Да претпоставиме дека имаме два текста, напишани од два различни автори. Да претпоставиме дека двата автори известуваат за иста тема, со тоа што
        едниот автор претпочита пишување на подолги текстови и почесто користење на едни те исти зборови. На пример, авторот А ги искористил зборовите:

        мачка: 3 пати
        убава: 6 пати
        природа:3 пати
        ..

        Додека авторот Б, кој е поскромен на зборови, ги искористил зборовите:
        мачка: 1
        убава: 2
        природа: 1
        ...

        Од приложеното, можеме да забележиме дека првиот автор користи два пати повеќе зборови од вториот автор, иако односот помеѓу
        нивната честота на користење останува иста.
        Доколку користиме косинусно растојание, наспроти Евклидово, ќе можеме да го "фатиме" случајот дека во суштина овие два текстови не се различни.
    </Метрика за растојание>

2. Сега, откако сме ги нашле двата најблиски кластери потребно е да направиме спојување на тие два кластери во еден кластер.
На почеток, откако сите кластери содржат само една вест, спојувањето оди така што се земаат сите точки од веста во првиот кластер и
во вториот кластер, збирот на тие точки се дели со два (вкупниот број на вести во новиот кластер, по спојувањето). Во првиот чекор и двата кластери
влијаат подеднакво во формирањето на новата репрезентативна точка, бидејќи и двата кластери имаат ист број на вести во себе - по една вест.
Потоа се враќаме на точка 1, се додека не надминеме некоја граница на сличност помеѓу кластерите. На пример, доколку сличноста помеѓу два кластери
е многу мала така што нема поента тие кластери да се спојуваат понатаму. Алтернативно, постапката се прекинува доколку сите кластери се спојат во еден кластер
и нема простор за понатамошно спојување.


<!!! ДЕТАЛНО ПРОУЧУВАЊЕ НА КОМПЛЕКСНОСТА !!!>
    Иницијалната комплексност на овој алгоритам беше O(N*N*N + N*K), каде што N - бројот на почетните вести, K - димензијата на кластерот.

    Во најлош случај, треба да ја направиме постапката под 2. N пати, и во секој чекор во квадратно време треба да ги најдеме најблиските кластери.
</!!! ДЕТАЛНО ПРОУЧУВАЊЕ НА КОМПЛЕКСНОСТА !!!>

</Хиерархиско кластерирање>