Дипломна работа на тема „ Откриване на зависимости в данни, променящи


с. 1



Софийски университет „Св. Кл. Охридски”

Факултет по математика и информатика



Катедра „Софтуерни технологии”



ДИПЛОМНА РАБОТА

на тема


Откриване на зависимости в данни, променящи се във времето. Подход базиран на Data Mining

Дипломант: Радостина Богданова Богданова

Специалност: Информатика

Направление: Софтуерни технологии

Факултетен номер: M22930

Научен ръководител:



ас. Милен Чечев
София, 2011 г.

Съдържание


1.Въведение 3

1.1.Актуалност на проблема и мотивация 3

1.2.Цел и задачи на дипломната работа 3

1.3.Очаквани ползи от реализацията 5

1.4.Структура на дипломната работа 5

2.Извличане на информация и откриване на знания (Data mining and knowledge discovery) 5

2.1.Въведение и основни дефиниции 6

2.1.1.Данни, информация и знание 7

2.1.2.Извличане на информация (data mining) 7

2.2.Основни етапи на процеса по извличането на знания 8

2.3.Основни задачи 12

2.4.Данни 16

2.5.Области на приложение 17

2.6.Няколко грешни разбирания за извличането на информация 18

3.Времеви серии (time series) 18

3.1.Въведение във времевите серии и времевите бази от данни 18

3.2.Дефиниции за разстояние и сходство между времеви серии 19

3.3.Начини за определяне на сходство и разстояние 20

3.3.1.Евклидово разстояние (Euclidean distance) 20

3.3.2.Манхатън (Manhattan distance) 21

3.3.3.Разстояние на Чебишев (Chebyshev distance) 22

3.3.4.Несходство Брей - Къртис (Bray Curtis Dissimilarity) 22

3.3.5.Разстияние Канбера (Canberra Distance) 22

3.3.6.Сходство косинус(Cosine Similarity) 22

3.3.7.Dynamic Time Warping (DTW) 23

3.3.8.Корелация на Пиърсън 24

3.3.9.Какво представлява шума в данните 26

3.3.10.Нормализация 26

3.4.Модели за откриване на сходство между времеви редове 27

4.Системи за препоръчване на музика (Recommendation Systems) 30

4.1.Популярност на системите за препоръчване в науката 31

32


4.2.Популярност системите за препоръчване в индустрията 32

4.3.Алгоритми за изготвяне на препоръка 33

4.4.Системи за препоръчване на музика 34

4.4.1.Подходът на Last.fm 34

4.4.2.Музикален лабиринт (Music Maze) 34

4.4.3.Подход 3 35

4.5.Нашият подход за препоръчване на музика 35

4.5.1.Данни 35

4.5.2.Изпълнители и контексти от изпълнители 38

4.5.3.Алгоритъм 42

4.5.4.Обработка на данните, съхраняващи история на потребителите 42

4.5.5.Текущ контекст 43

5.Заключение 44

Използвана литература 44





  1. Въведение

    1. Актуалност на проблема и мотивация


Нарастващото изобилие на данни в днешно време се дължи на наличието на все по-евтини сензори като камери, мобилни телефони, GPS устройства и др. и на повишения капацитет на устройства за съхранение на данни. Суровите данни са полезни само при наличие на методи за техния анализ, с цел извличане на информация и зависимости, които могат да се използват за изграждане на ефикасни приложения.

Много често суровите данни имат времева размерност, позволяваща анализа и автоматичното откриване на показатели, които се променят с времето. Към този тип данни спадат множество разнообразни индикатори в науката, инженерството и всекидневния живот. Извличането на зависимости от времеви данни играе основна роля в приложения за анализ на пазара, откриване на измами, контрол на производство, прогнозиране на продажби, бюджетен анализ, инвентаризация, обработка и контрол на качеството, наблюдение и прогноза на природни явления (като атмосфера, температура, вятър, земетресение), научни, инженерни и медицински експерименти.


    1. Цел и задачи на дипломната работа


Дипломната работа има за цел да изследва приложението на методите за анализ на времеви данни при препоръчване на музика. Това е основен проблем в литературата. Съществуват множество алгоритми, целящи да открият най-подходящия начин за отправяне на препоръка, на база анализи на поведението и навиците на потребители в конкретна област. Някои от тях взимат предвид различни демографски показатели, други разглеждат потребителското поведение в зависимост от конкретни периоди на деня (сутрин, обед, вечер), на седмицата (работни дни, почивни дни), на годината(пролет, лято, есен, зима) и т.н. Новият аспект в метода, разработен в дипломната работа е използването и анализа на времеви последователности от потребителската история, състояща се от слушания (наредено множество от музиканти, на всеки от които се съпоставя точен времеви период на слушане), с цел изготвяне на препоръка. Предложеният подход адресира няколко основни проблема:

  1. откриване подходящи данни, съдържащи история от слушания на достатъчно голям обем от потребители

  2. избор на подходяща метрика за сравняване както на изпълнители, така и на последователности от изпълнители

  3. индексиране на данните, с цел бързодействие, целящо изготвяне на препоръка в реално време.

За решаването на първият от гореспоменатите проблеми се използва цялостната историята на 1000 от съществуващите над 40 милиона активни потребители от 190 държави, притежаващи акаунт в музикалния сайт Last.fm (Фигура 1.2.1). Той дава възможност на музикалните любители да регистрират своите навици. Всеки път, когато слушат някоя песен, се изпраща автоматично информация за това до Last.fm сървърите.

Фигура 1.2.1. Потребителски профил в Last.fm [31].
Данните се пречистват и обработват предварително, извличат се кратки истории на слушания и се дефинира метод на намиране степен на подобие между изпълнители. Изборът на метрика за сравнение на времеви поредици от музиканти е резултат от изследване на различните техники, сфери на приложение, алгоритмична сложност, ефективност и точност при нарастващ обем и наличие на шум.
    1. Очаквани ползи от реализацията


Разработката на дипломната работа допринася за развитието на науката, давайки един нов щрих в частта от литературата, занимаваща се с извличане на информация и интересни зависимост от време-ориентирани данни. Поднася се интересен прототип и анализ на поведението на нов алгоритъм за препоръчване на музика, базиран на исторически сходни последователности от слушани артисти. С предложения подход се дава възможност за един по-различен поглед над системите за препоръчване.
    1. Структура на дипломната работа


Описанието на дипломната работа е разпределено в пет глави които следват логическата последователност на заложената в нея тематика.

Първа глава запознава читателите с целта и произлизащите от нея задачи, като и мотивацията да се изследват актуалните методите за анализ на времеви данни при препоръчване на музика.

Втора глава включва подробно описание на процеса по извличане на знания, като разглежда подпроцесите, които го изграждат. С цел въвеждане в проблематиката на работата се дават основни дефиниции, които са от голямо значение за по-нататъшното навлизане в спецификите на подхода. Описани са различните алгоритми и методи за изчисление на подобие между времеви данни, с цел откриване на интересни зависимости.

Трета глава е фокусирана върху характеристиките на време-ориентираните редици, начините за определяне на сходство и разстояние между тях, както и роля им в бизнеса и науката.

В четвърта глава се отделя специално внимание на системите за препоръчване и в частност - системите за препоръчване на музика. Разглежда се хронологическото развитие на този дял от литературата - извличане на знания, както в науката, така и в индустрията. Взимат се под внимание вече имплементирани системи за препоръчване, като се разглеждат подробно техните преимущества и недостатъци с цел приемственост на добрите практики и съответно предпазване от непрактични решения. Читателите се запознават с новия подход за препоръчване на музика, използваните данни, имплементирания алгоритъм и очакваните резултати.

С последната глава се дава завършеност на дипломата работа като се обобщават разгледаните основни проблеми и се изясняват бъдещите планове за развитие и подобрение на предлагания подход.


  1. Извличане на информация и откриване на знания (Data mining and knowledge discovery)

    1. Въведение и основни дефиниции


Настоящата информационната ера се характеризира с изключителен растеж
на данни, които се генерират и съхраняват за всички видове човешки усилия. Последното десетилетие се свързва с революция в наличността и обмена на информация посредством Интернет. Уеб пространството нараства с бързи темпове и е далеч от достигане на конкретно нивото на насищане. Електронна търговия и други иновативни употреби на световния електронен обмен на информация са в своя вихър. Нови предизвикателства възникват за бизнеса и науката, свързани с откриване на консистентен начин за структуриране на информацията. Освен с цел отчитане и архивиране на дейностите на организация, тези данни понякога може да се окажат златна мина при осъществяване на стратегическо планиране. Все по-голям процент от тях започват да се записват под формата на компютърна база данни, така че да може да се осъществява лесен достъп до тях. Разпространението им в почти всички области на човешката дейност, създаде голямо търсене на нови, мощни инструменти за превръщане на данните в полезни, ориентирани към конкретни цели знания. В стремежа си да отговорят на тази нужда, изследователи правят проучване на идеи и методи, разработени в машинно обучение, разпознаване на образи, статистически анализ на данни, визуализация на данни, невронни мрежи и т.н. Тези усилия довеждат до появата на новo изследователско пространство, което често се нарича извличане на данни и откриване на нови знания. Целта на тези методи и алгоритми е да се извлекат полезни закономерности от големи количества данни, пряко под формата на "знание", дефинирано като връзки между интересни характеристики, или индиректно - като функции, които позволяват изготвяне на прогнози.

Откриването на мотиви, тенденции и аномалии в огромен обем от данни прави възможно създаването на модели, с безпрецедентна степен на сложност. За тази цел е необходимо е да бъдат разработени стабилни и ефективни алгоритми, които трябва за обработват големи бази от данни, с много размерности. Иновациите в областта също спомагат процеса по извличане на данни и откриване на нови знания. Потребителят с негово експертно мнение и интуиция относно домейна, участва в търсенето на нови структури в данните, като въвежда предварително знание, с цел насочване на стратегиите. Последната стъпка във веригата е осигуряване на достоверността на данните, което се осъществява с помощта на ​​специални техники за справяне с модели с голяма сложност [15].

Извличането на информация е начин за учене от миналото, за да се постигнат по-добри решения в бъдеще. Целта е да се избегнат два нежелани резултата:


  • да се вземат в предвид неща, които не са верни

  • да се вземат в предвид неща, които са верни, но не са полезни

Това са предизвикателства, пред които е изправен всеки изследовател. Допускането на първото от изброените по-горе нежелани резултата е по-критично, тъй като направените в последствие заключения ще се базират на некоректна входна информация. Резултатите от процеса по извличане на знания често изглеждат привидно правдоподобни, понеже първоизточникът са актуални, реални данни. Не винаги обаче данните са изчистени от некоректни и изкривени стойности, а понякога се случва така, че просто не са приложими за решаването на поставения проблем. В тези случаи направените трансформации водят до неправдоподобни резултати. Възприемане на изводи, които са верни, но безполезни не е толкова опасно, но е често срещано явление. Основната идея на процеса по извличане на информация е постигането на нови знания. Често се случва резултатите да достигнат до вече познати зависимости. Добра практика е тези случаи да се избягват, с изключение на моментите, когато се цели валидиране на някое извесно правило [32].
      1. Данни, информация и знание


Данните са всички факти, цифри или текст, който могат да се обработва от компютър.
Днес организациите са натрупали огромни и бързо нарастващи количества от данни, в различни формати, съхранявани върху различни платформи. Това включва: оперативни или още наричани транзакционни данни - продажби, разходи, инвентаризация, заплащане на труда и други. Неоперационните данни - продажбите на производството, прогнозни данни и макроикономически данни.

Модели, асоциации и връзки между всички тези данни, могат да предоставят информация. Така например, при осъществяване на анализа на данните за продажби на конкретно звено, може да бъде получена информация относно продуктите, които се продават, кога и защо се наблюдава голямо търсене.

Информацията може да се преобразува в знания за исторически модели и бъдещи тенденции. Например, в обобщена информация за продажби на супермаркет, може да се анализира поведението на потребителите, с цел подготвяне на печеливша реклама, на база на натрупаната от изследването информация. Така производител или търговец на дребно
може да определи кои продукти са най-податливи и са добри кандидати за участие в реклама.

      1. Извличане на информация (data mining)


Данните са основна форма на информация, която трябва да бъде управлявана, пресявана, тълкувана с цел достигане до знанието. Извличането на информация възниква в края на 1980 г., постига голям напредък по време на информационния век и продължава бързото си развитие в този все по-зависим от данните свят.

  • Извличането на данни е наблюдение и анализ на най-често големи количества от данни, с цел да се открият неподозирани връзки и да им се направи ново обобщение по един същевременно разбираем и полезен за собственика им начин [12].

  • Извличането на данни е интердисциплинарна област, обединяваща техники за
    машинно обучение, за откриване на мотиви, статистически похвати, бази данни и визуализация [14]

  • Според Гартнер [23], извличането на информация е процес на откриване нови и значими корелации, модели и тенденции в резултат от пресяване на големи количества от съхранявани в хранилища данни, с помощта на технологията за разпознаване на модели, както и много статистически и математически похвати [13].

Извличането на знания се свежда до намиране на скрити връзки, които присъстват в неявен вид и позволяват изготвянето прогнози. Използват се различни съвременни похвати, като класификация (decision trees, Bayes classifier, k-nearest neighbor, neural networks), групиране (k-means, hierarchical clustering, density-based clustering), асоциация (one-dimensional, multidimensional, multilevel association, constraint-based association). Многогодишната практика показва, че извличането на информация е процес и неговото успешно прилагане изисква предварителна манипулация с данните (намаляване на размерността, почистване, отстраняване на шум изключения) и обработка (осигуряване на разбираемост, обобщаване, визуализация), изискваща експертно познаване на домейна [15].

Ето един добър пример от реалния живот, който изяснява необходимостта от трансформирането на големи количества данни в полезни знания за конкретна област. Докато чакаме на опашка в някой голям супермаркет, ако се заслушаме, ще чуем един специфичен звуков сигнал, от скенерите, които четат бар кодове на хранителни продукти. Всеки сигнал показва нов ред в транзакционната базата от данни. Дори не можем да си представим, колко такива записа постъпват в минута, час, ден, седмица. Ясно е, че са много, въпросът обаче е какво можем да научим от всички тези данни? Какво ни носят те на пръв поглед? Не много. След задълбочен анализ и експертна оценка, от тях могат да се извлекат ценни наблюдения за потребителските навици.

Още през 1984 г., в книгата си „Megatrends”, Джон Найсбит отбелязва:


Ние се давим в информация, но сме жадни за знания”.
Проблемът днес, не е липсата на данни, в действителност сме затрупани с тях в повечето области, а по-скоро недостига на подготвени човешки анализатори, квалифицирани в превръщането на всички тези данни в знание [4].
    1. Основни етапи на процеса по извличането на знания


Извличането на информация (data mining или на кратко DM) се свежда до откриване на знания (knowledge discovery) в големи количества от данни. В случаите, когато се търси точен термин за назоваване на процеса по обработване на голям обем от сурови данни и намиране на набор от ценни зависимости е по-правилна употребата на „извличане на знания от данни”. Това определение е дълго и по тази причина се е наложил терминът извличане на информация. Някои хора определят термина „откриването на знания в данни” (Knowledge Discovery from Data или KDD) като негов синоним. Други твърдят, че извличането на информация е стъпка от процеса KDD, който съдържа изобразените на Фигура 2.2.1. стъпки:

Фигура 2.2.1. Извличане информация като стъпка от процеса по откриване на знания [10].


  1. Пречистване на данните – отстранява се шума и неконсистентните данни

  2. Интеграция на данните – комбинират се различните източници на информация

  3. Избор на необходимите данни

  4. Трансформация на данните в подходяща форма

  5. Извличане на информация (data mining) - основен процес, при който се прилагат интелигентни методи, с цел откриване на интересни мотиви и зависимости

  6. Анализ и визуализация на получените резултати - идентифицира истински интересни модели, представляващи познание [10]

Всичко започва от една голяма купчина данни от различните източници на информация. Първите стъпки са свързана с подготовката им - те се почистват и интегрират, след което се подбират и трансформират по подходящ начин под ръководството на експерт в конкретния домейн. Тази фази изискват най-много време, като част от цялостния процес.

Всеки алгоритъм за извличане на знания, използва за обработка, подготвените в предишните стъпки данни, като ги компресира и трансформира по начин, който улеснява идентифицирането на скритите и ценни късове от информация. Различните техники, които се използват тук са асоциация, групиране, класификация, моделиране, откриване на мотиви от последователности и прогнозиране на времеви редове, те ще бъдат разгледани по-подробно в следващата глава.

Последният етап е известен като фазата за анализ на информацията, при която се оценява получения от алгоритъма резултат, с цел откриване на допълнителни знания за домейна и определяне значението на фактите, генерирани от използваната техника. Понякога резултатите са представени в „ако - то” форма, която улеснява разграничаването на ценните късове информация от безинтересните факти. В други случаи обаче е необходимо да бъдат анализирани визуално или чрез други инструменти за класифициране на полученото спрямо очакваните стойности. Във всички случаи, без да се взима предвид използвания алгоритъм за извличане на знания, резултатите трябва да се представят на потребителя. Успешно приложение за DM е онова, което включва преобразуване на суровите данни във форма, която е по-компактна, по-разбираема и в която взаимовръзките са точно специфицирани [15]


Процес по извличане на информация

Методологията по извличане на информация, може да бъде обяснена в 11 стъпки:



  • Разполагайки с описанието на глобалния проблем, се полагат усилия по привеждането му в data mining проблем.

  • Избира се подходящо множество от данни, като препоръчителни са реалните данни от някоя система, пред произволно генерираните такива.

  • Навлизане в спецификите на данните, разглеждане на възможните стойности за конкретните полета, с цел идентифициране в последствие на грешки и избягване на изключения в изследваното множество.

  • Избор на подмножество от данните, достатъчно за удовлетворяване на нуждите по решаването на конкретния проблем.

  • Премахване на грешни данни и изключения.

  • Трансформиране на данните до получаване на информация.

  • Изграждане на модели, базирайки се на получената от по-горната стъпка информация.

  • Тестване на модела и изчистване на несъответствия, идентифицирани в процеса на валидация.

  • Получаване на добър модел и неговото прилагане върху цялото множество от данни.

  • Изследване на резултатите и анализ новополучената информация.

Както се вижда от Фигура 2.2.2., процеса по извличане на данни се представя най-добре като набор от вложени линии, а не като една права линия. Стъпките, нямат естествен ред и дори не е необходимо да се завърши с някоя напълно преди да се започне друга. Научената в последствия информация в някой момент ще предизвика преразглеждане на полученото на предишна стъпка [32].



Фигура 2.2.2. Процес по извличане на информация [32].
Представянето от Фигура2.2.1. разглежда процеса по извличане на информация като подпроцес в KDD, но тъй като е изключително важна стъпка, придобива по-голяма популярност в индустрията и науката под името откриване на знания в данни. В следващите секции двата термина ще бъдат употребявани като синоними.

Базирайки се на Фигура2.2.1., архитектурата на система за извличане на информация притежава следните компоненти:





Фигура 2.2.3. Архитектура на система за извличане на информация.

    1. Основни задачи


Задачите по извличане на данни са много разнообразни, тъй като в огромна база данни могат да бъдат открити голяма разновидност от мотиви. Различни методи и техники са необходими за намирането на различни видове зависимости. Изборът на задачите зависи изцяло от поставените цели и конкретните насоки на изследванията. Като типове те могат да бъдат класифицирани в пет групи: обобщение, класификация, клъстеризация, асоциация и анализ на тенденции.

  • Обобщение

Това е процес, който цели постигане на обобщени данни. Резултантното множество е със значително малък обем. Обикновено информацията е агрегирана, за да се добие представа на едно по-високо и абстрактно ниво. Цели се генериране на компактно и характерно описание на даден набор от данни, представено по няколко възможни начина: статистически вид (очакване, средна стойност и т.н.), графичен вид (хистограми, различни типове графики) или правила от типа ако-то. Обобщението може да бъде на цялата база от данни или на специфично подмножество от нея [15]. Така представена информацията е подходяща за презентации пред мениджъри или потенциални клиенти за анализ.
С обобщението може да се постигнат различни нива на абстракция и данните да бъдат
разгледани от различни ъгли, визуализирайки закономерностите.

  • Класификация

Този проблем най-често се определя като контролирано обучение. Целта му е да намери взаимовръзка между входните атрибути на обект и изходния клас. Така придобитите знания правят възможно предвиждането на класа на нов, непознат обект. Тази техника се използва за класифициране на записи от данни, на няколко предварително дефинирани класове, на базата на определени критерии. Например, една верига ресторанти може обработвайки данните за продажби да определи кога са пиковите периоди с най-много клиенти и кой е най-често поръчвания продукт. Този тип анализ е особено подходящ при разкриване на измами и установяване на кредитен риск. Процесът по класификация започва с множество от предварително подготвени обекти (Фигура 2.3.1.), с вече известна принадлежност към някой клас. За да може да се разработи модел, който да се приложи върху цялата извадка от записи [15].

Представянето на един ново създаден модел може да се осъществи по няколко начина: класификационни (ако – то) правила, дървета за вземане на решение (decision trees), математически формули, невронни мрежи. Дърветата за вземане на решение са структура представляваща множество от възли. Всеки от тях тества стойността на някой от атрибутите на обекта, подлежащ на класификация, всяко ребро насочва към друг възел, в зависимост от получения резултат, а листата на дървото са класовете (Фигура 3.3.2(Б)). Този тип представяне лесно може да бъде конвертиран към класификационни правила (Фигура 3.3.2 (А)). Невронните мрежи представляват съвкупност от единици, представляващи невроните и претеглени връзки помежду им Фигура 3.3.2 (В).[10].





Фигура 2.3.1. Класификация[4].
(А)

Възрастова група? ( X, „Младежи” ) И Доходи ( X, „Високи” ) клас (X, „А”)

Възрастова група ( X, „Младежи” ) И Доходи ( X, „Ниски” ) клас (X, „Б”)

Възрастова група ( X, „Средна възраст” ) клас (X, „В”)

Възрастова група ( X, „Пенсионери” ) клас (X, „В”)
(Б)

(В)



Фигура2.3.2. Представяния на класификационния модел: (А) Ако-То правила, (Б) Дървета за вземане на решение, (В) Невронни мрежи [10].


  • Клъстеризация

Целта на клъстеризацията е да групира в един и същ клъстер множество от подобни обекти, споделящи голям брой общи признаци, като за разлика от класификацията, групите не са предварително известни. По тази причина алгоритъмът е известен като неконтролирано обучение. За разлика от класификацията, при този подход в тренировъчното множество, обектите нямат специфицирана група, към която принадлежат. Тя се определя по време на самия процес. Групите са направени така, че вътре-класовото сходство е голямо, докато приликите между обекти от различни класове са сведени до минимум (Фигура 2.3.3.). Това се постига след прилагането специални критерии, определени от атрибутите на обектите. Този подход се използва при извличането на информация с цел оценка на сходство между обекти, изграждане на представителни прототипи, анализ на корелациите между атрибутите и други. Основния проблем, адресиран от този алгоритъм е свързан със сегментирането. Записи с голям брой атрибути трябва да бъдат разпределени по сравнително малък брой клъстери (сегменти), чийто брой най-често е известен предварително. Това е един от най-използваните подходи в областта на извличане на информация. Той идентифицира групи от свързани елементи, което от своя страна дава свобода при изследването и откриването на нови интересни зависимости.



Фигура 2.3.3.Пример за визуализация на клъстерите след процеса по клъстеризация [10].


  • Асоциация

Асоциацията се използва при търсене на връзката между характеристики и атрибути. Търсенaтa зависимост се нарича асоциативно правило. Подобни взаимовръзки са полезни за маркетинг сферата, при търговските услуги, в рекламата и т.н. Например, в един магазин може да се забележи, че клиентите са склонни да купуват безалкохолни напитки и чипс заедно. Така в последствие магазина поставя двата продукта в близост един до друг с цел насърчаване на продажбата им. Други известни приложения в бизнеса и науката са:

  • Определяне на случаите , в които ново лекарство ще доведе до неприятни последствия.

  • Проучване дали изразителното четене на родителите влияе на развитието на детето им и прогреса, с който то се учи да чете.
    1. Данни


Съществуват няколко начина за съхраняване на данните, които се използват за извличане на информация. Те са:

  • релационни бази данни

  • хранилища за данни (data warehouse)

  • транзакционни бази данни

  • текстови файлове

  • потоци от данни

  • усъвършенствани системи за бази данни

    • обектни бази данни

    • бази данни, ориентирани към конкретно приложение

    • пространствени бази данни

    • времеви бази данни

    • данни, съдържащи текстови документи или мултимедия

През последните години релационните база данни са широко използвани в различни бизнес приложения. С напредъка на технологиите в тази област, започва и появата на съвременни видове информационни системи, които отговарят на изискванията на новите направления. Това са приложения обработващи пространствени данни (като например географски карти), данни, свързани с инженерния дизайн (като например проектиране на сгради, компоненти в конкретна система), мултимедийни данни (текстове, изображения, видео и аудио данни), времеви данни (исторически данни, съхранявани за конкретен домейн, данни за фондова борса), поток от данни (видео наблюдения, сензорни за данни) и др. Изискват ефективни структури данни и мащабируеми методи за тяхната обработка, с което се превръщат в благодатна почва за много интересни научни изследвания. Предизвикателствата и спектърът от приложими техники зависят от типа на хранилището [10].
    1. Области на приложение


(стр 28, (1))

-стр 8, Discovering Knowledge in Data, фазите от case study

-стр .35, The Role of Data Mining, Data Mining Techniques for Marketing Sales and Customer Support.pdf

-стр .48, Lessons Learned, Data Mining Techniques for Marketing Sales and Customer Support.pdf

-стр .51 -стр 56, Identify the Business Opportunity

-стр .44, The Role of Data Mining, Data Mining Techniques for Marketing Sales and Customer Support.pdf


    1. Няколко грешни разбирания за извличането на информация


- стр 10, Discovering Knowledge in Data, FALLACIES OF DATA MINING
  1. Времеви серии (time series)

    1. Въведение във времевите серии и времевите бази от данни


Времевите бази от данни се състоят от поредици (Time Series или TS) от стойности/събития, получени при регулярни измервания, направени в конкретен период от време (Фигура 3.1.1.):



Фигура 3.1.1. Времеви ред.
Нека си представим, че разполагаме с данни по месеци за конкретна фондова борса в рамките на една година. Анализирайки ги можем да идентифицираме тенденцията на развитие. Разполагайки с информация за повече от една фондова борса, бихме могли да търсим приликите и различите между тях (Фигура 2), което от своя страна дава възможност за откриване на интересни аномалии и изготвяне на прогнози, отнасящи се за следващи периоди във времето.

Фигура 2. Сравнение между фондовите борси на Google и Microsoft [26]
Стойностите във времевите серии обикновено са измерват на равни интервали (например, всеки час, ден, седмица, месец). Този тип бази данни играят ключова роля както в бизнеса, така и в науката. Финансови данни, биомедицински данни, машинни и сензорни данни, произхождащи от производствените системи, метеорологични данни, геоложки проучвания са популярни и широко разпространени примери за времеви данни С нарастващото изобилие на различни устройства за онлайн събиране на данни, в рамките на един ден или дори за минута (например от космически програми НАСА) се генерира голям обем от информация, от порядъка на десетки гигабайта. Голямо предизвикателство представлява намирането на интересни зависимости, прилики, повтарящи се мотиви, тенденции, резки промени и т.н. в реално време, анализирайки огромни времеви серии [10]. Подходите за решаването на проблем от този тип ще разгледаме в следващите секции.
    1. Дефиниции за разстояние и сходство между времеви серии


Възможността за определяне на сходство между времеви редове, позволява постигане на интересни резултати, например намиране на групи от компании с подобен модел на растеж през годините. Правилното разбиране на тези понятия е голямо значение при работата с подобни серии.

Как измерваме сходството между серии, променящи се във времето? Откриването на начин в отговор на горепосочения въпрос е основен момент от анализа на исторически последователности. Термините „прилика” и „разстояние” между обекти са тясно свързани. Сходството е характеристика, която измерва колко силна е връзката между два обекта и най-често се мени между 0 и 1. Две времеви серии са напълно еднакви при стойност 1 за сходство и абсолютно различни при 0. Разстояние в термините на времеви редици е синоним на различие, представлява степента на несъответствие между два обекта на базата на различни характеристики.

Анализаторите на данни определят метричното разстоянието като добър начин за измерване на сходство [4]. В математиката, под метрика се разбира функция задаваща разстоянието между елементите на дадено множество [29]. Една функция d се нарича метрика, ако чрез нея на всяка наредена двойка (x,y) от обекти x и y се съпоставя реалното число d(x,y) и за всеки три обекти x, y и z са в сила следните свойства:


  1. d(x, y) ≥ 0 и d(x, y) = 0 тогава и само тогава, когато x = y

  2. d(x, y) = d(y, x)

  3. d(x, z) ≤ d(x, y) + d(y, z)

Свойство 1. гласи, че разстоянието е винаги положително число и е равно на нула само когато обектите са еднакви. Свойство 2 показва, разстоянието е симетрично, така например, разстоянието от Ню Йорк до Лос Анджелис е същото като разстоянието от Лос Анджелис до Ню Йорк. Свойство 3 е правилото на триъгълника, което гласи, че въвеждането на трета точка не може да скъси разстоянието между други две точки [4]. Не всички от разгледаните в следващата секция функции за определяне на разстояние са метрични, но за леснота ще ги наричам метрики, като общо название на методи за сравнение на времеви редици.


    1. Начини за определяне на сходство и разстояние


Избирането на добра метрика за определяне на сходство между времеви серии е задача изпълнена с предизвикателства. За да подберем идеалната е необходимо да се запознаем с преимуществата и недостатъците на най-разпространените техники за определяне на сходство и разстояние между времеви редове. В следващите дефиниции на метрики с А и В ще означаваме времевите серии със следния вид:




      1. Евклидово разстояние (Euclidean distance)


Една от най-естествените и често използвани в литературата метрики е Евклидовото разстояние. То се определя с помощта на следната формула[1]:

Евклидовото разстояние постига добри резултати при сравняване на поредици в едни същи мерни единици и с еднакъв обхват. На Фигура 3 по-долу, отляво са показани две време-ориентираните серии, а отдясно е визуализирано графично разстоянието d(A, B) между тях:





Фигура3. Графично изображение на две поредици и Евклидовото разстояние между тях. [9]

Експериментално се наблюдават значителни отклонения в резултатите при анализa на различни показатели, например доход и температура. Под въздействие на шум и при големи отклонения в стойностите на данните се оказва, че Евклидовото разстояние не е достатъчно прецизно при изчисленията. Това са случаи, при които се достигат екстремални стойности, които се намират в близост до границите за обхват или са в противоречие на тенденцията за развитие на данните. Локализирането им е много важно, защото има вероятност те да представляват грешки в данните. Дори и да са валидни стойности, оказват влияние върху някои чувствителни към присъствието им методи и в последствие водят до нестабилни резултати. При увеличаване размера на данните, Евклидовото разстояние отново показва затруднения при прецизното изчисляване на резултатите. В ситуациите, когато се изследват данни с колебания в показателите за дълъг период от време, не се препоръчва прилагането на тази метрика върху реални сурови данни. В тези случаи подходите са два: използване на Евклидово разстояние, като се намали размерът на данните или избор на друга метрика за определяне на сходство [4].


      1. Манхатън (Manhattan distance)


При p=1 от формулата на Минковски (4), се получава формулата на разстоянието Манхатън (Manhattan distance или city block distance):

      1. Разстояние на Чебишев (Chebyshev distance)


В граничния случай, когато се получава формулата за разстоянието на Чебишев или още известно като Chessboard distance:

Общото между първите три метрики за разстояние е, че са от семейството на Хърман Минковски от ред p [2]. Манхатън е известна още като , Евклидово разстояние като , а разстоянието на Чебишев се получава в крайния случай, когато p достигне безкрайност. Общата формула на разстоянията от семейството на Минковски е:




      1. Несходство Брей - Къртис (Bray Curtis Dissimilarity)


В своя публикация от 1957 г. Роджър Брей и Джон Къртис представят тази метрика за изчисляване на разстояние, като използват нормализирани и неотрицателни данни при сравнението. Когато данните са положителни на стойностите на Брей-Къртис се менят в диапазона от 0 до 1. Стойност 0 показва пълно съвпадение на две серии от данни, а 1 означава, че са тотално различни. Брей-Къртис не е метрично разстояние в математическия му смисъл, тъй като то не удовлетворява Свойство 3 от дефиницията (3.2) – неравенството на триъгълника. Това е формулата, по която се изчислява:

      1. Разстияние Канбера (Canberra Distance)


Разстоянието Канбера e въведено от Ланс и Уилямс в края на шейсетте [1] и е известно катое претеглена версия на класическата метрика L1( разстояние Манхатън) [16].


      1. Сходство косинус(Cosine Similarity)


Сходство косинус е мярка за определяне на прилика между два вектора, чрез измерване косинуса на ъгъла между тях. В резултатът от функцията е равен на 1, когато ъгълът е 0 и е по-малко от 1, за всеки друг, ненулев ъгъл. Иначе казано, косинуса определя дали два вектора са насочени, в приблизително една и съща посока. Този метод най-често се използва за сравняване на документи [30].


      1. Dynamic Time Warping (DTW)


Друг, по-гъвкав от горепосочените начин за измерване на сходство между време - ориентирани редици A = {, , …, } и B = {, , …, }, n N е динамичното свиване (деформиране) във времето (DTW). Бернд и Клифърд (Berndt и Clifford) през 1996, представят тази техниката пред общността, занимаваща се с извличане на информация от данни. DTW е първата метрика използвана за откриване на сигнали при разпознаването на реч. Прилага се също с цел откриване на сходство върху видео и графични данни - всъщност, всякакъв тип данни, които могат да бъдат линейно представени. Пространството от различни, сравними редици ще означаваме с F , като , ∈ F, i ∈ N са точки от по-горе дефинираните серии A и B. За да се сравнят тези поредици е необходимо да се дефинира локална метрика за определяне на разстояние – d (, ), която приема малки стойности, когато a e близко до b, a големи - в противен случай. Най-често d (, ) се дефинира като абсолютната стойност на разликата на a и b. Попълва матрица N x N за всяка двойка координати от двете поредици. Това се осъществява много ефективно на базата на динамично програмиране, като стойността на текущата клетка в матрицата c(i, j) се изчислява по следния начин:
c(i, j) = d (,) + min { c(i-1, j-1), c(i -1, j) , c(i, j-1) }
Деформиран път (warping path) е поредица от двойки координати p = (, . . . , ), = ( , ) [1 , N ] × [1 , N ] за всяко [1 , L ], която удовлетворява следните ограничения:


  1. Гранично условие: = (1,) и = (N, )

  2. Монотонност: . . . и . . . .

  3. Стъпка напред: - {(1, 0), (0, 1), (1, 1)} за всяко [1 , L-1 ].


Фигура 3 визуализира четири опита за откриване на деформиран път между две време-ориентирани серии. Графика (а) показва приемлив път, удовлетворяващ и трите условия от дадената по-горе дефиниция. На графика (b) неправилно откритият път е следствие от нарушеното граничното условие. От графика (c) ясно се забелязва неспазването на ограничението за монотонност и при графика (d) се наблюдава неправилна стъпка напред, не е изпълнено условие 3) от дефиницията за деформиран път.


Фигура 3. Деформиран път.[7, стр. 71]

С откриването на деформиран път, минимален път, при който са изпълнени всички ограничения, се намира начина за подравняване на двете редици, при който се наблюдава най-голямо сходство между тях. Подравняването представлява свързване на точка от едната редица с една или повече точки от другата, като задължително първите и последните координати на редиците са свързани (следствие от граничното условие) [7]. От примера на Фигура 4 ясно се вижда, че двете време-ориентирани серии имат приблизително един и същ размер и подобна форма, но покритието им по абсцисата не е пълно. В този случай динамичното времево деформиране (DTW) е най - ефективната техниката за откриване на степен на сходство между тях.





Фигура 4. Подравняване на две време-ориентирани серии. [8, стр. 1]

      1. Корелация на Пиърсън


Корелация е техника за разследване на връзката между две количествени, непрекъснато променливи характеристики, например, възраст и кръвно налягане. Коефициентът на Пиърсън е известен като най-добрият метод за измерване на корелация, тъй като се базира на метода на ковариация. Той дава информация за степента на съответствието, както и посоката на връзката. Корелацията е число между -1 и +1, което измерва степента на връзка между две серии, менящи се във времето. Положителната й стойност означава положителна връзка, т.е стойностите на едната редица нарастват, когато нарастват и стойностите на другата, и обратно. Колкото по-голяма е корелацията, толкова по-силна е връзката. Случаите, когато резултатът е равен на 0 се интерпретират като независимост на двете поредици, няма връзка между тях. Отрицателна й стойност предполага негативна или обратна връзка - нарастващи стойности на едната поредица, когато при другата стойностите намаляват и . Формулата, по която се изчислява коефициентът на Пиърсън е:

където N е дължината на A и B, и са средните стойности съответно в редиците А и B, a са съответните им стандартни отклонения.

Първата стъпка от изучаването на връзката между две редици изменящи се във времето е да се визуализират всички точки от представянето им в графика(scatter plot):

Фигура. Позитивна корелация на графиката отляво и негативна корелация на графиката отдясно [10, стр. 60].untitled.jpg

Колкото по-сгъстени са точките до права линия, толкова по-силна е връзката между наблюдаваните променливите(Фигура).




Фигура. Три различни случая на корелация със стойност 0 между две серии [10, стр. 60].
Тази фигура показва три случая, при които няма корелация между двете поредици във всички множества от данни.

      1. Какво представлява шума в данните


Шумът е случайна грешка или разминаване в измерената стойност на някоя променлива. Нека разгледаме числения атрибут „цена”. Как бихме могли да "изгладим" данните, така че да премахне шума? Нека да разгледаме следните техники за изглаждане на данни :[10, стр. 63].
      1. Нормализация


При измерване на разстояние се забелязва, че някои показатели имат големи стойности (пример: доход) и могат да влияят на други атрибути, които се измерват в по-малък мащаб (пример: години трудов стаж). За да се избегне това, анализаторите на данни трябва да подложат стойностите на атрибутите на нормализация, с цел мащабирането им, така че да попадат в рамките на определен малък обхват, като например 0.0 до 1.0. За методи свързани с намирането на разстояние между редици, нормализирането помага, като не допуска атрибути с първоначално голям обхват влияят върху такива с първоначално по-малък обхват [10]. Известни са няколко техники за нормализация. Три от най-широко разпространените методи за постоянно променящи се показатели са Мин.-Макс. нормализация и Z-score стандартизация и нормализиране, чрез десетично мащабиране (Decimal scaling). Нека с X означаваме първоначалната стойност, а с - тази след нормализация.

  • Min-Max нормализация

При този вид нормализация новата стойност се получава като съотношение между разликата на старата и минималната стойност (т.е колко по-голяма е старата от минималната стойност) и обхвата на поредицата.
Min–Max normalization:

Това означава, че стойности представляващи минимума в редицата ще имат нормализирана стойност 0, а новата стойност на тези, които са равни на максимума ще е 1.



  • Z-score стандартизация

Z-score стандартизация е много широко разпространено в света на статистическия анализ. Тук практиката е да се изчислява съотношението между разликата на старата и средната стойност и стандартното отклонение на стойностите от поредицата (2.2). Обхватът на й варира между -4 и 4, а средната стойност е 0 след Z-score стандартизация [4].

Z-score standardization:



  • Decimal scaling

Тази техника за нормализация е изключително интуитивна и лесна за изчисление. Да предположим, че записаните стойности в редица X варират в интервала от -986 до 917. Максималната абсолютна стойност X е 986. За да се постигне нормализация на X десетично мащабиране, е необходимо да разделим всяка стойност от редицата на 1000 (т.е. к = 3). Така обхватът от -986 до 917 се нормализира до -0.986 до 0.917 [10, стр. 72].

    1. Модели за откриване на сходство между времеви редове


-стр.489, Data Mining - Concepts and Techniques

Модели за откриване на сходство между времевиредове
-стр. 496, Data Mining - Concepts and Techniques

-глава 3, Lecture Notes in Data Mining.pdf


Изследване на поведението на метриките за разстояние между редици , променящи се във времето.
Изследване на поведението на метриките за разстояние между редици , променящи се във времето.


    1. Цел на експеримента

Този експеримент наблюдава поведението на няколко метрики за измерване на разстояние между време-ориентирани редици. Данните, използвани в него са синтетични, произволно генерирани. Изследването за сходство се извършва последователно по двойки, като в случаите, когато се добавя шум, множестото от данни изглежда по следния начин:





.



,

където:

  • N е броя на редиците, т.е обема на множеството от данни

  • е дължината на всяка от редиците

  • e четно число,,

  • е стандартното отклонение на редицата, където

  • е степента на зашумяване ,

  • е произволна реална стойност между -1 и 1.

В експеримента се променят 3 показателя: N, , за да се определи въздействието им върху точността на метриките и времето, което им е необходимо за извършване на изчисленията.

На графиките по-долу, различните метрики са означени за яснота по следния начин:

  • ED – Евклидово разстояние ()

  • MD Разстояние Манхатън ()

  • ChD Разстояние на Чебишев()

  • CD Разстояние Канбера

  • BCD Несходство Брей-Къртис

  • DTW Динамична деформация във времето

Очаквания:

  • С увеличаването на обема на тренировъчното множество от данни Евклидово разстояние става също толкова ефективно колкото и DTW, докато времето му за изчисление е все така малко.

  • Промяната на времето за изчисление на всяка една метрика, зависи от дължината l на сериите в извадката от данни

  • DTW расте с много по-бързи темпове, в сравнение с останалите метрики, поради квадратичната сложност на алгоритъма му за изчисление.

Експеримент с шум при разтеглияне?

1) оригинал: 1112223322 (размер 10)

2) разтегляне(по същият начин може и свиване): 111112233222 (размер по-голям от 10)

3) отрязване на същият размер като оригинала: 1111122332

4) ДТВ е по-добра от евклидово за сравнение на оригинала с резултатът от 3

N = 2000, = 2, = , първоначално генерираните стойности в редиците са между 0 и 10

N = 2000, = 2, = , първоначално генерираните стойности в редиците са между 0 и 10

N = , = 2, = 1.5, първоначално генерираните стойности в редиците са между 0 и 10

N = , = 2, = 1.5, първоначално генерираните стойности в редиците са между 0 и 10

N = 10, = , = 1.5, първоначално генерираните стойности в редиците са между 0 и 10

Времето за изчисляване на сходство за една двойка в зависимост от дължината на сериите в базата от данни.


  1. Системи за препоръчване на музика (Recommendation Systems)


Системите за препоръка са специфичен вид информационна филтрираща техника, която се опитва да се препоръча информационни елементи (филми, ТВ програми, видео, музика, книги, новини, снимки, уеб страници, научна литература, научни статии и т.н.), които могат да представляват интерес за потребителя. Практиката при този вид система е да изследват някои базовите характеристики от профила на потребителя, с цел да се предскаже дали конкретен елемент, неизвестен до сега би представлявал интерес за него. В зависимост от подходът, изследваните признаци могат да бъдат свързани с текущите предпочитания (content-based approach) или социалната среда на потребителя (collaborative filtering approach) [17].

Повечето системи за препоръчване разчитат на мнението на масата, при сформиране на предложение за музика. Оказва се обаче, че това не винаги дава добри резултати и е необходимо да се намерят други начини, по които да се определи каква музика би се харесала на конкретен човек. Различните потребители предполагат различен тип предложение, в зависимост от спецификата на личното им потребление [18]. Ето едно разделение на случайна извадка от хора, на възраст между 16 и 45 години, в зависимост от потреблението им на музика, изготвено от Oscar Celma и Paul Lamere :





Фигура. Типове потребители [18].

  • Авторите определят като експерти (savants) 7% от горепосочената извадка от хора. За тази група, всичко в живота е свързано с музика.

  • 21% от хората са любители – музиката е важна част от техния живот наред с останалите им интереси.

  • Като нормални слушатели са класифицирани 32% от извадката. За тях музиката е част от живота, но има далеч по важни неща.

  • Последната група авторите определят като незаинтересовани. Те няма да забележат, дори и ако музиката спре да съществува.
    1. Популярност на системите за препоръчване в науката


Изследванията в сферата на препоръчване на музика започват през 2001 година, с едно единствено изключение, публикувано през 1994 г. За да покажете на нарастващия
интерес в тази област, Фигура 4.1 отразява броя на публикации от 2001 г. до 2009 г. Тази информация се базира на индексираните в Google Scholar документи. От 2004 г. насам се забелязва рязко увеличение на броя статии в тази област [22].


Фигура. Брой на индексираните в Google Scholar публикации, свързани с препоръчване на музика [22].

През годините този проблем става все по популярен и разпространен, хората са по- информирани, взима се под внимание тяхното отношение към музика – какво харесват, появява се база за изследвания на поведението им на слушане и потребление. В последните години се развива с усилени темпове онлайн пазаруването, което от своя страна дава информация, за най-търсените на пазара изпълнители.


    1. Популярност системите за препоръчване в индустрията


Системите за препоръчване играят важна роля в електронната търговия. Успешни примери за това са Amazon и Netflix, при които отправянето на добра препоръка е от критично значение за поддържане интереса на потребителите. Грег Линдън е човекът, който имплементира първото приложение за отправяне на предложения към клиентите на Амазон. Той твърди че продажбите, в резултат от направените препоръки са в пъти повече от тези, преди имплементацията на системата [22] и това лесно може да се види на Фигура.


Фигура. Растеж на фондовия пазар на Амазон [26].
От октомври 2006 г., тази област се радва на засилен интерес благодарение на постиженията и на Netflix в тази насока. Компанията организира конкурс, с награден фонд от $ 1,000,000 за този, които успее да подобри тяхната система за препоръчване на филми. За целите на състезанието Netflix предоставя най-големият до тогава, публично достъпен набор от данни, съдържащ над 100 милиона филмови рейтинга от анонимни потребители. Три години по-късно, през юли 2009 г. са обявени официално победителите – седем членен екип от статистици, експерти в машинно обучение и компютърни инженери от САЩ, Австрия, Канада и Израел. Многонационалният отбор, известен под името BellKor’s Pragmatic Chaos [27], постига резултати с 10% по-доби от тези на съществуващия до тогава алгоритъм, каквото е било и условието за успех в състезанието.
    1. Алгоритми за изготвяне на препоръка


  • Препоръка, базираща се на демографски показатели (Demographic Recommendation)

  • Content- Based Recommendation

  • Collaborative filtering

  • Hybrid aproaches
    1. Системи за препоръчване на музика


В днешна време имаме огромен набор от възможности за избор на музика, която да слушаме: музикални каталози, MySpace, iTunes и много други. Авторът на The Paradox of Choice - Б. Шварц твърди, че потребителите често изпадат в състояние на колебание когато са изправени пред по-голям набор от възможности [22]. Резултатите от проучване, направено между 5000 потребители на iPod през 2007 [18], доказват необходимостта от системи за препоръчване на музика. Оказва се, че 80% от слушаните песни се равняват само на 23% от наличната музиката, а в същото време 64% - никога не са били пускани.

През последните няколко години са предложени няколко подхода за препоръчване на музика, които прилагат съществуващи алгоритми като например collaborative filtering.


      1. Подходът на Last.fm


Last.fm е музикален сайт, създаден в Обединеното кралство през 2002 година.В момента в него съществуват над 40 милиона активни потребители от над 190 държави. На 30 май 2007 г., CBS Interactive, се сдобива с Last.fm срещу 140 милиона лири. [21]

Last.fm дава възможност на потребителите да регистрират своите музикални навици на слушане: всеки път, когато потребител слуша някоя песен, се изпраща автоматично информация за това до Last.fm сървърите. Въз основа на данните, събирани за по-дълъг период, Last.fm генерира списък на потребителите (съседи), които слушат подобни изпълнители и песни. Използвайки тази информация, Last.fm подготвя своите препоръки, адаптирайки алгоритъма collaborative filtering. Този подход работи изненадващо добре и дава много ценна информация за потребителите, които желаят да разширят своя музикален хоризонт. Ако двама потребители имат голяма група от общи изпълнители, то наистина е много вероятно, че те биха се насладили и на тази част от групата изпълнители на своя съсед , която не съвпада с тяхната. Last.fm също така позволява ръчно препоръчване на конкретни изпълнители, песни или албуми на хора, регистрирани в сайта и част от списък от приятели или групи принадлежат, при условие че препоръката въпрос е включен в базата данни Last.fm [19].


      1. Музикален лабиринт (Music Maze)



Това е приложение за препоръчване на подобни артисти предложено от Пол Ламере. Единственото, което трябва да направят неговите ползватели е да навигират между предлаганите сходни изпълнители, докато достигнат до някой, който им хареса. За осъществяването на това приложение, авторът визуализира данни, които извлича директно при поискване от уеб приложение известно под името Echo Nest API.


      1. Подход 3

    1. Нашият подход за препоръчване на музика


Потребителския вкус е непостоянен, зависи от обстановката, настроението, времето, популярните за момента изпълнители и много други фактори. Някои изследователи правят опити да представят профила на един любител на музика като съвкупност от различни микропрофили в зависимост от явленията, които му влияят. Нашето подход се базира на текущите предпочитания на потребителя, т.е изпълнителите, които слуша на в последно време и последователността на неговия избор.

Worry about the data first before you worry about the algorithm”



Peter Norvig

Director of Research at Google


      1. Данни



Данните, съхраняващи история на потребителите

Множеството от данни, с което работим представлява пълната история на 1000 потребителя, от създаването на акаунтите им до 05.05.2009. Записите се съхраняват във файл, със следната структура:


<потребител, дата и час, име на изпълнител, име на песен>


  • Статистики:

Извадката, която представлява нашата база от данни съдържа 19 150 868 записа. Броят на уникалните потребители в нея е 1000.

  • 15-те най-популярните изпълнители



Фигура. Извадка на 15-те най слушани изпълнители.
Данни, съхраняващи информация за потребителите

В друг файл се съдържа специфична информация за потребителите в следния вид:


<потребителски идентификатор, пол, възраст, държава, дата на създаване на профила>

Фигура. Извадка на 15-те държави с най-много потребители.
Извадката от потребители е разнообразна и това най ясно личи от Фигура.
Данни, съхраняващи информация за тагове на артисти

Това са набор от данни, представляващи етикети за изпълнители, събрани през пролетта на 2007 година от Пол Ламере, известен изследовател в областта на препоръчването на музика [25]. Те се съхраняват в следния формат:



< име на изпълнител, име на таг, брой срещания на тага>


  • Статистическа информация

Броят на уникалните артисти във файла е 20 907, а броят на уникалните тагове -100 784. На база на тази информация е изготвена извадка от 15-те най-популярни етикети и техните срещания (Фигура).


Фигура. Извадка на 15-те най-популярни етикети и броя на техните срещания.

      1. Изпълнители и контексти от изпълнители


Какво наричаме контекст? Кой е най-добрия начин за сравнение на два контекста с различна дължина? Как сравняваме музикални изпълнители? Следващите секции ще отговорят на всички тези въпроси.
Контекст

Контекст е времева серия, чийто елементи са артисти. На всеки музикант в поредицата се съпоставя timestamp – момента на слушане. Всяка разлика между времената на слушане на два последователни изпълнителя, която е по-голяма от 30 минути се възприема като граничен случай при разделяне на потребителските истории на отделни контексти. По тази причина е много вероятно получените поредиците да са с различна дължина. В този случай DTW (виж 2.3.7) е най-подходящо средство за измерване на разстояние между времеви редове. След като се приложи за всеки един контекст от клъстера, ще се търси онзи, който е най-сходен на търсения, т.е с най-малка стойност, изчислена от DTW. За да постигнем това обаче се нуждаем от подход за сравнение на изпълнители. Коя е най-подходящата функция за определяне на сходство между двама музиканти?

Какво представлява d(artist1, artist2) ? Как търсим сходство/несходство между двама изпълнители?

d(,)=?

Last.fm притежава функционалност, която позволява поставянето на етикет на артисти, албуми и песни, посредством които в последствие те могат да бъдат намерени. Това маркиране може да бъде по жанр, настроение, спрямо характеристика на изпълнителя или всяка друга форма, дефинирани от потребителя [21]. В данните, с които разполагаме, разпределението на типовете етикети е изобразено в Таблица.




Тип

Честота на използване

Примери

Жанр

68%

рок, поп, хип-хоп

Място

12%

българска, Сиатъл

Настроение

5%

парти, релаксираща

Мнение

4%

обичам, любима

Инструменти

4%

пияно,

Стил

3%

политически, хумористичен

Разни

3%

композитор, разтоварващ

Лични

1%

виждан на живо, супер е


Таблица. Типове етикети [18].
Изпълнител

Изпълнителите ще бъдат разглеждани като множество от етикети, на всеки от които се съпоставя броя на случаите, в които е бил използван от потребители, за маркиране на конкретния певец или музикална група (Фигура).




Фигура: Етикети, поставяни за Джон Ленън

Зависимостта, която се заложена тук е, че големината на шрифта на конкретен етикет е съпоставима с броя на употребите му. От примера на Фигура става ясно, че музиката на Джон Ленън най-често се определя от потребителите като класически рок. Нека разгледаме етикетите, дадени за Queen:




Фигура: Етикети, поставяни за Queen

На пръв поглед изглеждат подобни, но за да определим колко точно, е необходимо да подберем най-подходящата техника за откриване на сходство в този случай. Нека си представим N-мерното пространство, където N е броят на уникалните етикети.


Всеки от двата изпълнителя могат да се третират като вектор в това така дефинираното N-мерното пространство от етикети (Фигура). Разстоянието между тях е показател за сходство. Косинуса на ъгъла между два вектора е най-честата мярка разстояние в този случай (виж 2.3.6).



Фигура. Примерна визуализация на двама изпълнители, представени като два вектора в 3 мерното пространство.

Нека се върнем на търсената степен на сходство между музиката на Джон Ленън и Куийн.



Етикети





classic rock

2866

732

rock

2572

555

pop

330

178

singer-songwriter

21

458

80s

791

21

british

326

257

alternative

232

59

70s

168

89



...




Таблица.

След известен брой изчисления (виж 2.3.6) се получава следния резултат:



0,84

Обхватът на стойностите на косинус подхода в този случай е между 0 и 1 и тъй като се характеризира като техника за откриване на прилика, а не на разстояние, този резултат се интерпретира като много добра степен на сходство.



      1. Алгоритъм


#за обработване на заявка за препоръка на изпълнител

  1. Намира се разстоянията от текущия контекст до центровете на клъстерите. Избира се най-подходящия клъстер .

  2. От контекстите, намиращи се в, се избира онзи , който е с най-висока степен на сходство с търсения от нас текущ контекст :


Similarity (, context) ≥ Similarity (, context),

, N – брой контексти в .


  1. Намира се потребителя, към чиято история принадлежи и следващия изпълнител в историята му.

  2. Откритият изпълнител се препоръчва на потребителят, отправил искането.


      1. Обработка на данните, съхраняващи история на потребителите


Съхранявани локално, тези данни се подлагат на клъстеризация, като по този начин се групират сходни контексти в един и същ клъстер, независимо от това на кой потребител принадлежат. За да се подобри времето за изпълнение се планира индексиране на данните чрез клъстериране на сходни последователности от изпълнители.


      1. Текущ контекст


Текущ контекст на потребител наричаме поредица от слушани до момента изпълнители, запазени в акаунта му в Last.fm. Ето как изглежда частта от профила с най-скоро пусканите песни на случаен потребител:



Как определяме началото и края на текущия контекст?

В случая изпълнителят Idan Raichel е край на текущия контекст, а за начало се счита Katharine McPhee, тъй като предишната в списъка песен на Katy Perry е проследена 12 часа по-рано. Ако в този момент потребителят пожелае препоръка за следваща песен, той изпраща искане към системата.



  1. Заключение




Използвана литература





  1. Разстояние http://bg.wikipedia.org/wiki/Разстояние

  2. Minkowski distance http://en.wikipedia.org/wiki/Minkowski_distance

  3. M. Gavrilov, D. Anguelov, P. Indyk, and R. Motwani. “Mining the Stock Market: Which Measure is Best?”

  4. Discovering knowledge in data”

  5. Data Mining In Time Series Databases

  6. Lecture Notes in Data Mining

  7. Information retrieval for music and motion,  Meinard Müller

  8. Derivative Dynamic TimeWarping, Eamonn J. Keogh and Michael J. Pazzani

  9. MINING TIME SERIES DATA, Chotirat Ann Ratanamahatana, Jessica Lin, Dimitrios Gunopulos, Eamonn Keogh

  10. Data Mining – Concepts and Techniques

  11. Elliott R., Van der Hoek J., and Malcolm W.: Pairs trading. Quantitative Finance, pp. 271–276, 2005.

  12. David Hand, Heikki Mannila, and Padhraic Smyth, Principles of Data Mining, MIT Press,Cambridge, MA, 2001.

  13. The Gartner Group, www.gartner.com.

  14. Peter Cabena, Pablo Hadjinian, Rolf Stadler, JaapVerhees, and Alessandro Zanasi, Discovering Data Mining: From Concept to Implementation, Prentice Hall, Upper Saddle River,NJ, 1998.

  15. Introduction to Data Mining and its Applications

  16. G.N. Lance and W.T. Williams. Mixed-Data Classificatory Programs I - Agglomerative Systems. Aust.Comput. J., 1(1):15–20, 1967.

  17. http://en.wikipedia.org/wiki/Recommender_system

  18. Music Recommendation Tutorial, Oscar Celma, Paul Lamere, ISMIR 2007, September 23, 2007

  19. http://anthony.liekens.net/index.php/Computers/DataMining

  20. http://anthony.liekens.net/pub/scripts/last.fm/recommend.php

  21. http://en.wikipedia.org/wiki/Last.fm

  22. Music Recommendation and Discovery, O` scar Celma

  23. http://www.gartner.com/technology/research/it-glossary/

  24. http://www.dtic.upf.edu/~ocelma/MusicRecommendationDataset/lastfm-1K.html

  25. http://musicmachinery.com/2010/11/10/lastfm-artisttags2007/

  26. http://finance.yahoo.com

  27. http://bits.blogs.nytimes.com/2009/09/21/netflix-awards-1-million-prize-and-starts-a-new-contest/?8au&emc=au

  28. http://static.echonest.com/musicmaze/MusicMaze.html

  29. http://bg.wikipedia.org/wiki/Метрично_пространство

  30. http://en.wikipedia.org/wiki/Cosine_similarity

  31. http://last.fm

  32. Data Mining Techniques for Marketing Sales and Customer Support

с. 1

скачать файл