оптимальная кластеризация больших данных Опции

[Де бин Анатолий]

Добрый день. Спасибо администрации за идею создания такого полезного форума. Мой вопрос не столь по медицине, сколь из области маркетинга. Я провожу одно исследование. Не вдаваясь в подробности, цель исследования это изучить какие запросы яндексом воспринимаются как семантически близкие. Как я стал это делать. Я сам программист больше, я написал парсер. Работает он так. Ввожу запрос N1, яндекс в ответ дает какие-то ответы
запрос?1
ответ?1
ответ?2
...
потом в роли ключевого выступают эти ответы.
ответ?1
ответN
ответN
ответN
получается примерно такое. Т.е. по сути все транспонируется.

Далее , я стал высчитывать расстояние. Обратите внимание от фразы ремонт компьютеров столбец A1 до фразы ремонт ноутбуков 1 шаг. А от фразы ремонт ноутбуков столбец d1 до фразы ремонт компьютеров тоже 1 шаг. вычитаем расстояние по модулю. 1-1=0 Но на самом деле 0 я равнял к единицы. Эти запросы стоят очень близко. вообще до 10 шагов это считается недалеко друг от друга запросы. Чтобы высчитать эти шаги, я написал макрос. Получаем такой результат. Типа квадратная матрица.
Решил спрограммировать граф, но там бешенная каша.

Хотелось бы попросить помощи, а именно как лучше мне кластеризовать мои данные . Любой макрос сам напишу.Но меня интересует мнение математиков-профессионалов о том, как лучше визуализировать -кластеризовать мои данные, чтобы не было такое каши. Чтобы была четкая наглядность какие понятие(запросы) близки друг к другу.
Буду благодарен за любую подсказку.

Прикрепленные файлы

 ответ.rar ( 69,8 килобайт ) Кол-во скачиваний: 243
 макрос.rar ( 171,79 килобайт ) Кол-во скачиваний: 248
 корр.граф.rar ( 614,35 килобайт ) Кол-во скачиваний: 241

 

[anserovtv]

Ваши функции не являются метриками.
В данном случае применяются совсем другие (и очень сложные!) методы - нечеткий поиск (нечеткая логика).
Используют специальные нейронные сети - сети Хэмминга и специальные метрики с кодировкой.
http://habrahabr.ru/post/114997/
Существуют несложные бесплатные программы типа FuzzySearch / приложение к аналитической платформе Deductor/, демонстрирующие на простых примерах идеи данного метода.
Программу FuzzySearch легко скачать и установить. Автоматически создаете словарь, т.е. открываете из программы текстовый файл Word нужного типа (обычный текст, расширение txt ) и выполняете нечеткий поиск нужного "слова" в словаре.
Программа работает и с буквами (русскими, латинскими) и с цифрами.
http://www.basegroup.ru/download/demoprg/hamming/
P.S. Почти уверен в том, что время написания и отладки программы с уровнем, сравнимым с уровнем программ , применяемых в поисковых системах , можно смело измерять в годах.

Сообщение отредактировал anserovtv - 17.08.2014 - 16:06

[nokh]

...Хотелось бы попросить помощи, а именно как лучше мне кластеризовать мои данные . Любой макрос сам напишу.Но меня интересует мнение математиков-профессионалов о том, как лучше визуализировать -кластеризовать мои данные, чтобы не было такое каши. Чтобы была четкая наглядность какие понятие(запросы) близки друг к другу.
Буду благодарен за любую подсказку.

1. Организация данных. Ваши исходные данные организованы таким образом, что никто из посещающих ресурс специалистов не сможет ими воспользоваться. Думаю, что если бы вы выложили кусочек своих данных устроенных иначе, то имели бы уже пару-тройку готовых вариантов решения или рецептов:). В столбцах должны быть атрибуты, которые вы хотите в итоге описать и кластеризовать (хотя кластеризовать можно и случаи по профилям совстречаемости атрибутов), а в строчках - случаи. Пока не совсем понял, что у вас является случаем, скорее всего это конкретные интернет-ресурсы, которые вы с программой мониторите на предмет поиска совстречаемости атрибутов. Такая матрица данных должна содержать только 0 (атрибут не встречается в данном случае) или 1 (встречается). Такую матрицу можно обработать большим числом уже готовых методов, имеющихся в разных статистических пакетах, выбрать наиболее удачные и запрограммировать их уже прицельно - если цель состоит в написании собственного макроса или программы. Если же это исследовательская работа, рациональнее заставить работать макрос только над сбором данных, а анализировать их каком-нибудь в профессиональном и уже давно отлаженном пакете.

2. Меры расстояния. Это очень серьёзно. Если два атрибута встречаются вместе (единицы в строке), то здесь всё более-менее понятно - это уже ассоциация. А если не встречаются (нули в строке)? Будем мы считать отсутствие совместной встречаемости за сходство и в какой степени? Или не будем? При использовании в качестве меры расстояния между атрибутами простой корреляции Пирсона (что вообще некорректно для качественных признаков) или даже ранговой корреляции отсутствие совместной встречаемости обрабатывается наравне с совстречаемостью. При использовании в качестве мер расстояния различных коэффициентов ассоциации, вычисляемых по таблицам сопряжённости (которые более уместны в вашем случае) - аналогично. Именно поэтому мне не нравятся результаты анализа соответствий, хотя именно этот анализ используется наиболее часто при редукции данных с обобщением для данных представленных 0 и 1. Часто получаются какие-то странные ассоциации, особенно в случае слабой насыщенности матрицы (больше нулей чем единиц). Дело в том, что какие-то атрибуты могут оказаться сходными не потому что они чаще встречаются вместе, а потому, что наоборот чаще не встречаются. А если для совстречаемости есть малое число поддающемуся осмыслению причин, то для остутствия совстречаемости их - бесчётное множество. Поэтому экологи в таких случаях используют другие меры расстояния, например, коэффициент или индекс сходства Жаккара: отношение числа случаев совместной встречаемости атрибутов к числу случаев, когда встречался хотя бы один из них. Получается, что в таком коэффициенте отсутствие совстречаемости просто не учитывается. Есть и другие меры, но Жаккара я бы посоветовал включить в набор мер расстояний обязательно.

3. Мерность пространства. Кластерный анализ - тупые процедуры, которые ничего не говорят о мерности пространства с которым мы работаем. Я имею в виду не математическую мерность, а смысловую, семантическую. Для семантического анализа более подходят другие методы обработки данных, типа анализа главных координат, многомерного шкалирования, ну или хотя бы тот же анализ соответствий. Каждое измерение нового редуцированного пространства имеет вполне поддающуюся осмыслению интерпретацию: одни атрибуты группируются вместе по одним причинам, другие - по другим... Кластерный анализ не удобен для осмысления, т.к. расстояния по всем семантическим размерностям усредняются и кластер на дендрограмме мы вольны трактовать в меру своей (не)компетенции. Именно поэтому я склоняюсь к использованию готовых пакетов для анализа данных, подобных вашим: зачем изобретать велосипед, когда уже есть весь арсенал транспорта?

4. Кластеризация случаев в редуцированном пространстве. Даже если специалист, интерпретирующий дендрограмму будет в высшей степени компетентен, сама процедура кластеризации располагает к ошибкам интерпретации или к неполноте последней. Дело в том, что может оказаться, например, что из 100 показателей 80 встречаются совместно по одной причине, 15 - по другой и 5 - по третьей. При кластеризации атрибутов мы эти 3 группы увидим. Но вот при кластеризации случаев эти 80 "забьют" оставшиеся 20, которые почти не дадут вклада в итоговое расстояние. Получится, что мы будем думать, что находим некие интегральные кластеры случаев по всем 100 показателям, хотя реально будем находить только те, которые навяжет причина совстречаемости 80-ти. Применительно к вашим данным, например, всё что связано с ремонтом "забьёт" все что связано с тюнингом, апгрейдом и т. д. Поэтому если такую кластеризацию и делать, то в редуцированном пространстве. Т.е. сначала свести 80 - к одной оси, 15 - к другой, и 5 - к третьей, интерпретировать, а уже далее провести кластеризацию случаев в новом трёхмерном пространстве.

5. Про алгоритмы кластеризации не пишу, их тоже куча + полезным может оказаться не один, а сразу несколько вариантов. Ещё один "+" в пользу готовых пакетов.

Такое видение проблемы. Курсивом выделил термины, чтобы вы погуглили на эти темы.

Сообщение отредактировал nokh - 17.08.2014 - 19:39

[Де бин Анатолий]

anserovtv, спасибо Вам, статья полезная.
nokh

Код

Организация данных. Ваши исходные данные организованы таким образом, что никто из посещающих ресурс специалистов не сможет ими воспользоваться. Думаю, что если бы вы выложили кусочек своих данных устроенных иначе, то имели бы уже пару-тройку готовых вариантов решения или рецептов:). В столбцах должны быть атрибуты, которые вы хотите в итоге описать и кластеризовать (хотя кластеризовать можно и случаи по профилям совстречаемости атрибутов), а в строчках - случаи. Пока не совсем понял, что у вас является случаем, скорее всего это конкретные интернет-ресурсы, которые вы с программой мониторите на предмет поиска совстречаемости атрибутов. Такая матрица данных должна содержать только 0 (атрибут не встречается в данном случае) или 1 (встречается). Такую матрицу можно обработать большим числом уже готовых методов, имеющихся в разных статистических пакетах, выбрать наиболее удачные и запрограммировать их уже прицельно - если цель состоит в написании собственного макроса или программы. Если же это исследовательская работа, рациональнее заставить работать макрос только над сбором данных, а анализировать их каком-нибудь в профессиональном и уже давно отлаженном пакете.

Там по сути данные как для многомерного шкалирования.
может в картинках будет понятнее.
вот то что было напарсено
1. вы видите в столбце А какие-то фразы, а потом ,если присмотреться, эти фразы транспонированы. И уже каждая фраза стала сама запросом от которого идут ответы
Я думаю с этим ясно.
D1 ремонт ноутбуков, D4 компьютерная помощь 3 шага.
G1 компьютерная помощь G3 ремонт ноутбуков
3 шага- 2 шага =1 шаг. т.е. запросы стоят близко.

кашеобразный граф, наверное уже видели.


смотрим матрицу
типичный пример данных для КА или МШ

Согласен, что вся исследовательская работа на моих макросах, но какое уже отлаженное ПО сможет мне дать визуализацию. Визуализировать большое кол-во данных это непростая задача. Матрица тут 375х375


Плюс попутно решаю задачу и классификации текстов. У меня есть 6000 документов. в каждом запрос какой-то и к нему по 50 снипетов. Задача исходя из этих данных также посмотреть какие запросы похожи семантически. Можно ли эту задачу решить в среде statistica 10 или тут нужно отдельное ПО.

Сообщение отредактировал Де бин Анатолий - 17.08.2014 - 22:31

Эскизы прикрепленных изображений

 

[nokh]

Какие "фразы", какие "шаги"?! Вы меня не услышали. Вообще не услышали. Пока смысла обсуждать что-то далее не вижу. Ждите других.

[anserovtv]

Де бин Анатолий!
Вы не понимаете всю сложность поставленной перед вами задачи.
Чтобы использовать стандартное ПО, нужно иметь возможность автоматической специальной перекодировки текстовой информации в числовую.
Полагаю, что этот путь - тупиковый, а визуализация результатов в смысле МШ, КА неактуальна.
В настоящее время существует специальное ПО для анализа текстовой информации /Text Mining/:
SAS Text Analytics, IBM SPSS Modeler и др.
Это технологии ИАД - интеллектуального анализа данных.
SAS Text Analytics автоматически определяет ключевые слова и тематику сообщений, производит семантический разбор текста и анализирует контекст...
http://www.sas.com/ru_ru/software/analytic...---------------
http://www.dp.ru/a/2010/05/15/IBM_dobudet_dlja_korporaci/
Почти уверен в том, что при этом используются методы , о которых я писал выше в сообщении #2.
Я этим пока не занимался. Данное ПО стоит огромных денег и для его установки и работы нужны специальные технические условия.
P.S. Скорее всего ваша задача является стандартной в текстовой аналитике и давно уже решена и реализована в каком-нибудь пакете Text Mining
(и с совсем другой терминологией).

Сообщение отредактировал anserovtv - 19.08.2014 - 06:33

[p2004r]

Ну и что "желтый цвет" должен "символизировать" в distance matrix?

[Де бин Анатолий]

на выходных подробнее отвечу. а касательно последнего вопроса. желтый цвет можно убрать, я его делал с целью типа постуя ячейка. совстречаемости между запросами нет. но потом оставил это идею.

[p2004r]

на выходных подробнее отвечу. а касательно последнего вопроса. желтый цвет можно убрать, я его делал с целью типа постуя ячейка. совстречаемости между запросами нет. но потом оставил это идею.

1) "стою на коленях и жду выходных"ТМ

2) Если это метрика, то в _каждой_ ячейке должно стоять число. Раз ничего нет, то расстояние равно бесконечности (или какому то разумно большому числу).

[Де бин Анатолий]

Выходные настали. Простите, что не мог на буднях ответить. Разрываюсь. Итак давайте начнем отвечать. Хотелось бы начать ответ пользователю Nokh, хоть он решил временно уйти в сторонку. Потому что не столь я Вас не услышал, сколь мы оба друг друга не услышали.
Я проанализировал Ваш пост.
Я понял вашу идею по поводу организации данных. Я Вас услышал

2. Меры расстояния. Это очень серьёзно. Если два атрибута встречаются вместе (единицы в строке), то здесь всё более-менее понятно - это уже ассоциация. А если не встречаются (нули в строке)?

эта фраза соприкасается с вопросом пользователя p2004r Желтым цветом в моем макросе обозначается как раз-таки отсутствии ассоциации или совстречаемости запросов. Т.е. на запрос X1 выдается ответ X2, Но когда Х2 становится сам запросом ответ X1 не появляется. это желтое. Я потом убрал строчку в макросе, чтобы не мозолила глаза, пусть просто будет пустая клетка

Будем мы считать отсутствие совместной встречаемости за сходство и в какой степени? Или не будем?

не будем

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

Тут задача из серии big data . На счет КА согласен тут он не уместен. Хотя бы потому что дендрограмма получится сверх огромной, её не проанализируешь. Может я плохо старался на мат.статистике, но помоему такие поп.пакеты как spss,statistica,sas не любят когда в них загружают много данных и речь я веду не о кейсах, их сколь угодно, я больше о переменных. атрибуты, как вы их называете.
Что это значит? А это значит, что я и подумал, что мне надо какой-то свой алгоритм разработать, но на базе известных! Мы программеры ленивый народ) Нам не хочется что-то редуцировать, нам хочется один раз сделать алгоритм и пользоваться, т.к. такие задачи будут часто! Пускай он и будет включать сам редуцирование. Т.е. мне надо понять,что в таких случаях делают, а потом уже писать код.

Ну и ещё по поводу организации данных. Всегда как нас учили необходимо сначала разбираться какая у нас шкала. С одной стороны, если принюхаться, то можно подумать, что мои данные в номинативной шкале. Но все-таки я думаю они в ранговой шкале. Я не смотрю на них как на качественные признаки. Я смотрю на них как удаленность друг от друга. Кто вообще стоит рядом, а кто-то очень далеко.
В плане вашего предположения по организации данных, мне тогда вообще всю методологию менять надо было. Но согласитесь интересно понять почему когда я вижу X1 и получаю ответ Y ,а когда ввожу Y не получаю Х1 ? Почему вдруг с обратной стороны яндекс не считает, что эти ответы чем то близки?
Единственное, где я Вас возможно и не услышал, так это то, как вы себе кейсы предствляете. Т.к. столбцы всегда будут такими как есть сейчас.

Вы не понимаете всю сложность поставленной перед вами задачи.

ещё как понимаю, иначе бы не просил помочь как такие задачи решаются

Полагаю, что этот путь - тупиковый, а визуализация результатов в смысле МШ, КА неактуальна.

и здесь не спорю

Чтобы использовать стандартное ПО, нужно иметь возможность автоматической специальной перекодировки текстовой информации в числовую.

так скажите как это делать.собственно для меня это и был начала поста этого. чаша Грааля так сказать. как кодировать то

P.S. Скорее всего ваша задача является стандартной в текстовой аналитике и давно уже решена и реализована в каком-нибудь пакете Text Mining

приведите пример этого пакета. Я знаю в статистика есть модуль текст майнинга.но он ограниченный . Кластеризовать тексты он не может
его исходные данные
это набор текстов и обязательно столбец, где указано относится текст к этой теме или нет. А что если мне не нужно обучать прогу, чтобы на базе текстов она потом могла определить будут ли следующие тексты относится к этой теме или нет.
пример тут, я читал, не подходит
http://statosphere.ru/blog/136-statistica-...-miner----.html
Моя задача это впихать мои 6000 файлов в программу и чтобы она исходя из запросов и снипетов к ним в каждом файле могла сама найти те запросы, которые семантически близки друг к другу.

Ну и что "желтый цвет" должен "символизировать" в distance matrix?

думаю вы получили ответ на этот вопрос.

Если это метрика, то в _каждой_ ячейке должно стоять число. Раз ничего нет, то расстояние равно бесконечности (или какому то разумно большому числу).

а вот на этот вопрос у меня нет ответа, т.к. если совстречаемости фраз нет, то ячейка пустая(желтая) и что делать тогда ? Как работать с пропущенными данными? Столбец удалять нельзя, там может быть много совстречаемости этой переменной с другой.,строчку тоже ну удалишь , т.к. там может быть тоже много совстречаемости со след.переменными.

[p2004r]

а вот на этот вопрос у меня нет ответа, т.к. если совстречаемости фраз нет, то ячейка пустая(желтая) и что делать тогда ? Как работать с пропущенными данными? Столбец удалять нельзя, там может быть много совстречаемости этой переменной с другой.,строчку тоже ну удалишь , т.к. там может быть тоже много совстречаемости со след.переменными.

думаю вы получили ответ на этот вопрос.

[anserovtv]

Эту ссылку с информацией о том, как примерно устроена автоматическая кодировка, я давно давал. http://www.basegroup.ru/download/demoprg/hamming/
Цитата Сети Хэмминга представляют собой одну из разновидностей нейронных сетей. Принцип работы сетей Хэмминга базируется на определении расстояния Хэмминга между объектами и нахождении наиболее близкого. Хэмминговым расстоянием называется число отличающихся битов в двух бинарных векторах. Для кодирования букв в цифры в нашем случае используется ASCII код, хотя можно использовать и другие методы кодирования. Более того, хорошо подобрав систему кодирования, можно значительно улучшить качество распознавания.
Для автоматической кодировки используются специальные программы, одной из которых (скорее всего самой простой) является программа FuzzySearch.
Почему бы вам не изучить возможности пакетов, о которых я писал: SAS Text Analytics, IBM SPSS Modeler? Эти пакеты гораздо сложнее (и дороже) разных STATISTICA. Я бы даже и не стал сравнивать.
Решение сложной задачи не может быть простым.
Существуют и другие программы и пакеты для текстовой аналитики / http://www.sworld.com.ua/simpoz3/3.pdf
Google Correlate, Intelligent Miner for Text (IBM) , TextAnalyst, WebAnalyst (Мегапьютер Интеллидженс) ,Text Miner (SAS) , SemioMap (Semio Corp.) , Oracle Text (Oracle) , Knowledge Server (Autonomy) , Galaktika-ZOOM (корпорация "Галактика") ,InfoStream (Информационный центр "ЭЛВИ)
Цитата
Типичные задачи Text Mining включают категоризацию, кластеризацию текстов, извлечение концептов и объектов, создание таксономий, смысловой анализ, обобщение документации и моделирование объектов, то есть установление связей между различными известными объектами.
P.S.Интересен пример применения Text Miner в медицине: в одной из американских национальных здравоохранительных организаций было собрано свыше 10 тыс. врачебных записей о заболеваниях сердца, собранных из клиник по всей стране. Анализируя эти данные с помощью Text Miner, специалисты обнаружили некоторые административные нарушения в отчетности, а также смогли определить взаимосвязь между сердечно-сосудистыми заболеваниями и другими недугами, которые не были определены традиционными методами.
http://www.sworld.com.ua/simpoz3/3.pdf

Сообщение отредактировал anserovtv - 10.09.2014 - 11:43