кластерный анализ текста

[edvardoss]

добрый день.
спрашиваю на этом форуме как на самом активном в рунете по R .
Я специалист в другой области, но если абстрагироваться от отраслевой специфики, то есть надежда получить ответ мой на вопрос здесь. (на stackoverflow.com ничем не помогли)
есть вектор из неструктурированного и сильно замусоренного текста длиной в 15000 уникальных объектов - это названия алкогольной продукции от крупнейших федеральных розничных сетей РФ.
В этом векторе один и тот же продукт (семантически) может встречаться фактически до 50 раз в следующих вариациях (и в любой комбинации из этих вариаций):
- разный порядок слов в тексте
- разная степень сокращений одних и тех же слов
- разный язык написания одних и тех же слов (могут встречаться как английские так и русские вариации)
- разная интерпретация чисел (XXI век, 21 век, 21-й век, "двадцать первый век",...)
-разный разделитель целой и дробной части числа (0,5 , 0.5, 1/2л,...)
- в русских словах встречаются английские буквы идентичные по написанию с русскими( )

Проделал большую работу по созданию алгоритма, который принимает на входе этот ужас, парсит строку, разбивает ее на фрагменты, анализирует фрагменты, ищет аналогии по справочнику, проводит нормализацию по сокращениям слов, переводит слова на русский, переводит буквы на русский, чистит от мусорных символов,приводит числа к нормальному виду и оставляет релевантные фрагменты (я называя их "токенами").
Далее я решил по частоте встречаемости каждого нормализованного токена присвоить ему вес: от 10 баллов - для самого редковстречаемого токена до 1 балла для самых частых. Эти веса токенов планирую использовать для кластеризации текстов по их токенам.
Учитывая размерность вектора и ожидаемое количество токенов по нему, всю бизнес логику алгоритма реализовал процедурами в БД, в итоге получил 2 таблицы: таблица продукции t_prod : уникальный Id продукта и имя продукта=15000 записей, t_tokens : id продукта(ссылка на продукт в t_prod), имя полученного токена, вес токена в баллах=92000 записей
В итоге из 92000 получил 1700 уникальных токенов. Таким образом-если построить кросс таблицу (15000 объектов вниз, 1700 токенов вправо, и веса на пересечении)- то получится сильно разряженная большая матрица.
Писать алгоритм дальше нет смысла ибо это изобретение велосипеда учитывая количество итераций =15000^2-15000=225млн.
Собственно вопрос: как с помощью R разбить объекты на кластеры с учетом той структуры которую я получил, если число кластеров (семантически сходных продуктов) заранее не известно?

краткий пример приложил (там названия продуктов на английском т.к. пример затачивал под stackoverflow.com)

[gamm]

то, что описано, сильно напоминает типичную классификацию растительности. Токены - виды (species), продукты, объекты - sites (площадки сбора данных). Кластеризации подлежат как species, так и sites. Проблема - размер матрицы сходства 15000 х 15000 - долго, хотя в память влезет в нормальном компьютере (число токенов менее важно). Вторая проблема (по крайней мере для растительности) - возможно пропущенные токены (мы же хотим типичные сочетания выделить), и проблемы с вычислением сходства, если общих токенов нет (и проблемы, и возможные решения, описаны, например, в Beals E.W. Bray-Curtis-ordination: an effective strategy for analysis of multivariate ecological data / E.W.Beals // Adv. Ecol. Res. - 1984. - №14. - P.1-55.).

веса лучше убрать (оставить присутствие 0/1), анализ делается, в основном, в пакете vegan

Вариантов анализа несколько:

1) ординация (разложить объекты на плоскости, посмотреть, кто с кем рядом лежит, и, возможно, посмотреть на влияние разных внешних факторов) - MDS, NMDS, RDA, CA, CCA, DCA - позволяет оценить, ктос с кем лежит рядом, и прикинуть число классов

2) иерархический кластерный анализ hclust(), метод Варда, с разными матрицами сходства, вычисленными vegdist() - долго, но позволяет оценить число классов

3) гибрид ординации и кластерного анализа - пакет kohonen(), но предварительно желательно сглаживание по Beals. Строит классы и укладывает их на плоскости, это позволяет укладывать на плоскость новые объектв, отслеживать фазовое пространство (например, смотреть, как нечто, представленное несколькими объектами в разное время, двигалось по ординации), делать прогнозы - например, красить ординационную плоскость в соответствии с объемами продаж, и .д..

4) после оценки (на основе указанного выше) числа классов и примерного представления об их центрах, можно напустить обычный knn() с заданными начальными классами, но для практического применения (3) годится лучше.

как-то так

P.S. да, и вопросы нужно задавать не программерам на стэке (вопрос у вас не по программированию, а по статистике и машинному обучению), а статистикам на www.r-bloggers.com/, там и готовое можно найти, если покопаться

[bim2010]

levenshtein.damerau.distance
levenshtein.distance
http://cran.r-project.org/web/packages/vwr/vwr.pdf
http://cran.r-project.org/web/packages/ ... ngdist.pdf
https://en.wikibooks.org/wiki/R_Program ... Processing
http://www.bioconductor.org/packages/re ... rings.html
http://www.yimizhao.com/#!Compute-Leven ... f35a4a815d
Использование метрики Левенштейна для поиска аналогов названий
viewtopic.php?t=3841#p15812
Особенности алгоритмов нечёткого поиска

[gamm]

примерчик

[edvardoss]

добрый день.
bim2010, спасибо за ссылки, но метрики Левенштейна в этих данных будут плохо работать учитывая такое количество шума в данных, тем более что токенайзером я уже все по полочкам разложил и там же подсчитал меру сходимости с ближайшим объектом по расстоянию Жаккарда (к примеру: к продукту 1 ближе всего продукт 10001 со сходимостью 0,8) . Проблема как раз в другом- как теперь правильно разобрать все это по кластерам?


gamm, спасибо за развернутый ответ от 10 июл 2015, 12:15 - теперь только осталось найти время что бы уйти в этот лес алгоритмов.

Еще вопрос: Вы советовали нормализовать характеристики объектов в бинарный показатель элиминировав тем самым важность любой из характеристик (т.е. убрать рассчитанные веса токенов). Пытаюсь понять в моем конкретном случае-а правильно ли это?
К примеру сейчас в бд есть токен "ВОД" (присвоенный всем словам "водка" по самому короткому найденному сокращению) - самый популярный (13649 наблюдений, т.е. почти везде), и ему в противовес токен "ВЕДРОФФ" с 10 баллами и 2-мя наблюдениями.
Если эти 2 токена будут рассматриваться одинаково , то правильно ли я понял что в этом случае есть риск получить ложную близость 2-х продуктов? (т.к. по семантике важность каждого из них неодинакова)
К примеру, если элиминировать веса признаков,то продукт:
- "Ведрофф/водк.стек.бутыл-ка/0,5/40%(промо)" (токены: ВОД, ВЕДРОФФ, 0.5 , 40, СТЕК, БУТ, ПРОМО)
может стать ближе к
-"Водка Saimaa 0.5 40% стекл.бут. промонабор" (токены: ВОД, SAIMAA, 0.5 , 40, СТЕК, БУТ, ПРОМО)
чем к продукту:
"Ведрофф:(0,5)акция"
??????
за ссылку на карты Кохонена спасибо, начну читать.

[gamm]

Еще вопрос: Вы советовали нормализовать характеристики объектов в бинарный показатель элиминировав тем самым важность любой из характеристик (т.е. убрать рассчитанные веса токенов). Пытаюсь понять в моем конкретном случае-а правильно ли это?

дело темное, тут много нюансов. Например, проблема четвертого угла - в вашем случае токены : ВОД, 40, СТЕК, БУТ для "Ведрофф:(0,5)акция" просто пропущены, хотя на самом деле они есть. Для их восполнения и существуют всякие методы, в том числе "сглаживание". Фактически, это Байесовская процедура, которая вместо присутствия/отсутствия (0/1) вставляет вероятности в каждый объект. В результате, у вас для подобных признаков всегда будет стоять вероятность, достаточно большая (около 1 для водки вместо нулей), и различие будет не таким страшным. Вы пытаетесь делать то же самое весами, так тоже делают, считают взвешенную разность. И есть еще подход - вместо вероятности сглаженные значения рассматривать как нечеткие числа (степень наличия токена), тогда можно использовать для вычисления сходства меру, близкую к Куртису, но с дополнением (пусть у нас 5 токенов, пример на R):

Код: Выделить всё

x=c(0.0, 0.3, 0.9, 1.0, 0.5); xc=c(x,1-x) # c(0.0, 0.3, 0.9, 1.0, 0.5,   1.0, 0.7, 0.1, 0.0, 0.5)
y=c(0.0, 0.8, 0.8, 0.3, 0.5); yc=c(y,1-y)  #c(0.0, 0.8, 0.8, 0.3, 0.5,   1.0, 0.2, 0.2, 0.7, 0.5) 
xy1=pmin(xc,yc)  #c(0.0, 0.3, 0.8, 0.3, 0.5, 1.0, 0.2, 0.1, 0.0, 0.5)
xy2=pmax(xc,yc)  #c(0.0, 0.8, 0.9, 1.0, 0.5, 1.0, 0.7, 0.2, 0.7, 0.5)
beta=0.01
xy.dist=sum(xy1)/(beta+sum(xy2))

0.5863708 - сходство, от 0 до 1, расстояние = 1-сходство

[edvardoss]

gamm, добрый день.
Почитал пример SOM по Вашей ссылке, кое что попробовал, очень смутил этот фрагмент:
# topologies are possible
som_grid <- somgrid(xdim = 20, ydim=20, topo="hexagonal")
Правильно ли я понял что в данном случае формируется 20*20 кластеров т.е. 400 желаемых?
Из этого следует что надо заранее знать их число- что для меня не годится (по той же причине ранее отмел k-means)

[gamm]

Правильно ли я понял что в данном случае формируется 20*20 кластеров т.е. 400 желаемых?

неправильно

сетка задает разрешение (granularity) для аппроксимации распределения, часть классов может вообще оказаться пустыми. Если к-средних стараются найти центры кластеров, то SOM - аппроксимировать плотность распределения. Т.е. если у вас есть обособленная группа, то к-средних воткнет туда единственный центр, а SOM - число классов, пропорциональное объему группы (опуская некоторые детали). Т.е. классы представляют плотность, и, самое главное, укладываются на плоскость для обозрения структуры совокупности. У Кохонена был когда-то проект про тексты - WebSOM, поройтесь в интернете, там есть отчеты на эту тему.

а когда распределение уложили на плоскости, нужно нарисовать границы ("собрать шарики" в тематические классы). Для этого сам Кохонен рисовал U-map, можно классы располагать так, что расстояние на плоскости пропорционально различию классов, а проще всего самому нарисовать размер классов пропорционально численности, а линии между классами - с толщиной, пропорциональной сходству. Тогда сразу видно, кого нужно объединять, и где сходства нет или классы маленькие.

[sergsh]

(по той же причине ранее отмел k-means)

Вообще то k-means можно использовать для поиска оптимального количества классов в данных.
Нужно сделать разбиение выборки на 2 класса, потом на 3, потом на N.
И для каждого разбиения на N классов оценить качество этого разбиения.
Тогда можно выбрать из всех разбиений наиболее оптимальное, если оно конечно есть ...

Трудность тут только в том, что для больших данных это требует Большого времени, или Большого компьютера.

[edvardoss]

sergsh, спасибо за ответ - однако подсказать алгоритму k-means - сколько из 15000 продуктов следует сделать реальных кластеров с наскока не сможет даже Павел Глоба. А у меня и без этого мазохизма на работе хватает...

gamm, испытываю непреодолимое желание поприветствовать Вас!
Благодарю за развернутые ответы, которые безусловно в какой-то части помогают, однако всю глубину отраженных мыслей не позволяет постичь гуманитарная подготовка экономиста геологоразведочного Вуза, полученная 10 лет назад (отсюда-перед вами пролетариат в DataMining'е).
Тем не менее, усердно насилуя rstudio пакетом kohonen получилось вернуть некоторый результат,приближенный к желаемому по своей структуре, однако не по содержанию.
Взял 12 выборочных продуктов из которых априорно заметны 3 устойчивых кластера {Веда, Сибирская классик, Дрова}, все остальное в контексте этого датасета - выбросы.

Код: Выделить всё

library("kohonen")
z<-read.csv('Vodka_Cluster_Test2.csv',sep = ';',header = T,row.names = 1)
# заменяем NA на  0
z[is.na(z)]<-0
z.sc<-scale(z)
z.som<-som(data = z.sc,grid = somgrid(4, 3, "hexagonal"))
plot(z.som)
z.res<-data.frame(nm=rownames(z),cl=z.som$unit.classif,ds=z.som$distances)
print(z.res[order(z.res$cl),])

------nm------------------------------------------------------------------------------------------------cl---ds
Спиртной напиток черная смородина 0.7л. 37.5% Finlandia Blackcurrant--- 1--0.08283657
"Veda BLACK ICE"ВОДКА 0.5Л40%------------------------------------------------------------- 3--5.93529503
Водка Веда Черный лед 40%0.5ст/бут----------------------------------------------------- 3--6.72416581
Водка ЗОЛОТОЙ РОДНИК 40%+сув.кор. 0.75л--------------------------------------------4--2.37317686
водк.СИБИР.CLASSIC 40% 0.5л (Россия):20----------------------------------------------- 7--9.16746898
Водка Класс.40% 0.5л ст/бут SIBIRSKAYA------------------------------------------------- 7--6.28015693
|ОДКА СЛОБОДА КЛАСС.0.25 40%---------------------------------------------------------- 9--32.88692514
Водка Дрова очищ.дубовым углем 40% 0.5л------------------------------------------- 9--19.06689627
ВОДКА"DROVA"ДУБ.УГОЛЬ 40%.0.5---------------------------------------------------------- 9--14.52597562
Водка “Мягков” Серебряная 40% 0.5л----------------------------------------------------10--0.96661634
Водка ПУТИНКА Классич мягк 2014 40% 0.7L---------------------------------------------12--16.24323075
Водка Ред Арми 0.7л сув/ящ+рюмки------------------------------------------------------12--26.32519403

То есть устойчивы кластеры 3 и 7, в 9 появились шумы в виде "|ОДКА СЛОБОДА КЛАСС.0.25 40% " а 12 кластера вообще не должно существовать (как минимум должен быть разбит на 12 и 13 кластер).
Отсюда стойкие подозрение что модель надо тюнинговать, однако мне бить в шаманский бубен почему-то не разрешили(а горловое пение не помогает). Прошу участников уважаемого форума помочь советом ибо уже начал опасливо озираться на DBSCAN.
dataset прикладываю.

[gamm]

не тем вы занимаетесь ...

есть три разные задачи, вы определитесь, какую вы решать собрались:

1) есть небольшая совокупность объектов, вы хотите выяснить их структуру с точки зрения сходства, и разбить на группы "похожих". Для этого придуман иерархический кластерный анализ разными способами под разные цели (крайние случаи - метод Варда, и метод одиночных связей), он же дает представление о потребном числе кластеров. В R это hclust() и ему подобное. Это как раз для вашего примера.

2) есть совокупность объектов, вы хотите представить ее оптимальным числом "эталонов" с минимальной ошибкой (vector quantization). Сюда относятся knn и прочие lvq. Скорее всего, не ваш случай - они генерирую кластеры шарообразной формы, поэтому группы, имеющие не такую форму (типа огурца) будут представлены несколькими классами. Если "огурцы" правильной формы, то помогает Гауссова смесь (есть соответствующие пакеты), если неправильной - то ничего не помогает (если нет перколяции, и памяти хватит, то может помочь (1) с методом одиночных связей).

3) есть большая совокупность объектов, которая представляет собой выборку из бесконечной совокупности. Нужно выяснить и описать структуру этой совокупности. Для этого придуманы разные адаптивные методы (в том числе и SOM), число используемых классов при этом обычно сотни. Но роль у них совсем другая, нежели для (1) и (2).

И еще. При отсутствии данных вы ставите нули, хотя могут быть истинные нули, и просто пропущенные признаки (неполные описания). Чтобы результат правильно отображал генеральную совокупность, вместо нулей нужно ставить некоторые оценки, т.е. восполнять данные.

[edvardoss]

ответ - п.1, правда учитывая объем данных наверно лучше flashClust из той же области.
Пока бьюсь над тем как извлечь из hclust кластеры 1-го уровня (самые схожие объекты) в таблицу вида: номер кластера, название объекта.
в итоге родилось что то неудобоваримое через:

Код: Выделить всё

m2<- cutree(tree = m,h = floor(quantile(m$height,probs = .25)))

чуть более удобоваримое получилось через

Код: Выделить всё

rect.hclust(tree = m,h = floor(quantile(m$height,probs = .25)))->m2

[gamm]

в итоге родилось что то неудобоваримое через

обычно рисуют кривую агломерации (эти самые height из объекта - наверное, и рисовалка какая-нибудь есть), на ней хорошо видно, когда она пошла резко вверх. И на этой картинке отбивают height0 для выделения "естественных" классов. Но стоит и на дерево посмотреть, там обычно тоже видно, сколько нужно классов. Кстати, какой метод слияния вы использовали?

[edvardoss]

Кстати, какой метод слияния вы использовали?

Мои предыдущие сообщения основывались на "микровыборке" согласно вложению выше, соответственно что бы ответить на Ваш вопрос загрузил данные из БД в R целиком.
R висит на предпоследней строке расчета расстояний ибо для 15770 объектов получается 248млн итераций, сколько ждать с моими 8гб оперативки не понятно (подозреваю что вообще в итоге выкинет из сессии).
вес объекта z получился порядка 100 мегов.

Код: Выделить всё

# считываем и связываем 
pd<-read.csv('t_PrimaryData.csv',sep = ';',header = T,stringsAsFactors = F) 
t<-read.csv('t_Tokens.csv',sep = ';',header = T,,stringsAsFactors = F) 
tw<-read.csv('t_TokenWeights.csv',sep = ';',header = T,,stringsAsFactors = F) 
library(dplyr)  
inner_join(pd,t,by=c("id"="PrimaryData_id"))%>%
inner_join(tw,by=c("txt_TokenNormalized"="txt_Token"))%>%select(-id)->z
# разворачиваем в разряженную матрицу
library(reshape2)
m<-dcast(z,txt~txt_TokenNormalized,sum)
write.csv2(x = m,file = 'CrossTab_Tokens.csv',row.names = F,sep = ";")
# запускаемся 
# =========================================================
z<-read.csv('CrossTab_Tokens.csv',sep = ';',header = T,stringsAsFactors = F)
library(dplyr)  
library(tidyr)
# выборочный анализ исходных данных
sample_n(tbl = z,size = 5,replace = F)%>%gather(Token,vl,-txt)%>%filter(vl!=0)%>%arrange(txt)
# вызываем демонов
library(flashClust)
system.time(d<-dist(as.matrix(select(z,-txt))))
m<-flashClust(d,method = "average")

Поэтому к подбору алгоритма кластеризации пока приступить не могу.
PS Пока читаю эту ссылку но не уверен что это именно то что надо.

[edvardoss]

В итоге объект d класса dist оказался весом 1 гб, т.к. этот класс сохранить as is посредством R не получается то в результате конвертации его в матрицу для сохранения в csv прервал сессию , когда размер заливаемого файла в csv стал переваливать за 2,5 гигабайта. (((