Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/2: Рейтинг темы: голосов - 2, средняя оценка - 5.00
Maxelf
6 / 0 / 2
Регистрация: 18.10.2012
Сообщений: 5
1

Кластеризация бинарных векторов

26.04.2017, 15:17. Просмотров 444. Ответов 6

Здравствуйте! Я тут недавно и пока что не знаю, как лучше задавать вопросы,но очень нужно разобраться как сделать задачку.
У меня есть массив бинарных векторов(каждый вектор состоит из нулей и единиц).
Число векторов и число элементов в векторе изменяется.
Стоит задача разделить исходный массив на кластеры (количество кластеров не имеет значения). Буду очень благодарен, если посоветуете конкретные алгоритмы.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.04.2017, 15:17
Ответы с готовыми решениями:

Перебов бинарных векторов веса от 1 до w
Нужен алгоритм, который позволит перебрать все вектора длинной n и веса 1 - w. Например, ввод:...

Кластеризация
Ребят,кто-нибудь может объяснить как найти расстояния смешанных данных? Я изучила метод к-средних...

Кластеризация данных
Собственно не как не могу понять какой алгоритм подойдёт для такой задачи. Очень желательно не...

Спектральная кластеризация
Кто знает где описан алгоритм спектральной кластеризации с примером. Желательно если вы знаете...

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

6
VTsaregorodtsev
580 / 533 / 77
Регистрация: 19.02.2010
Сообщений: 1,935
27.04.2017, 22:10 2
Цитата Сообщение от Maxelf Посмотреть сообщение
Число векторов и число элементов в векторе изменяется.
Надеюсь, изменяется у разных задач - а не в пределах одной задачи.
В пределах одной задачи длина векторов д.б. одинаковой. Иначе - задача абсолютно неправильно поставлена.

Ну и о кластеризации.
Я бы при работе с данными, лежащими в вершинах гиперкуба (не всех вершинах), построил бы соединяющий эти точки остовное дерево (минимальный связный подграф), а потом рвал бы n-1 самых длинных его рёбер, чтобы получить n кластеров (наборов точек, соединённых внутри образовавшихся фрагментов дерева). При условии, что длины этих самых длинных рёбер таки больше, чем длины следующих, оставшихся неразорванными. А то вдруг данные у Вас покрывают все вершины - и тогда все рёбра в остовном подграфе будут иметь единичную длину, и возможно будет любое разбиение, и будет оно одинаково надуманным.
0
Maxelf
6 / 0 / 2
Регистрация: 18.10.2012
Сообщений: 5
27.04.2017, 23:03  [ТС] 3
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Надеюсь, изменяется у разных задач - а не в пределах одной задачи.
В пределах одной задачи длина векторов д.б. одинаковой. Иначе - задача абсолютно неправильно поставлена.
есть например такая задачка
есть n книг(всегда появляются новые книги) и есть информация о том, какие из них читали отдельные люди(кол-во людей тоже меняется). Хочется этих людей разделить на схожие группы по тому какие книги они читают(вместо книг можно использовать любой другой объект).
Думал использовать кластеризацию и коллаборативную фильтрацию для рекомендации людям схожие объекты по интересам,но пока не понял какой алгоритм кластеризации тут лучше подойдёт.
0
Павел Легков
1 / 1 / 0
Регистрация: 18.04.2017
Сообщений: 10
28.04.2017, 14:06 4
А Вы попробуйте начать с самого простого – введите бинарную функцию «Близость интересов», аргументами которой являются два читателя, а результатом – количество одинаковых книг, которые они прочли) Если значение «Близости интересов» больше определённого числа (ну примем 3), значит можно советовать одному читателю, книги прочитанные другим). Ну только при этом стоит всё-таки ещё разделить книги по тематике – тогда схожие предпочтения очевидно легче выявляются) А то можно попасть на такую ситуацию – леди А нравятся детективы и кулинарные книги, а джентльмену В – детективы и книги про войну. Насчёт детективов их предпочтения сходятся, но бесполезно будет предлагать леди книги про войну, а джентльмену – книги про кулинарию)
0
VTsaregorodtsev
580 / 533 / 77
Регистрация: 19.02.2010
Сообщений: 1,935
30.04.2017, 21:38 5
Maxelf, повторяю, даже в задаче колл.фильтрации длина векторов является постоянной. После добавления новой книги - у всех читаталей появляется новый компонент вектора с пустым значением.
То, что данные могут храниться в виде векторов переменной длины (чтобы не хранить сильно разреженную матрицу всю целиком) - оно только для хранения данных. А при обработке - данные явно или неявно "распаковываются" до прямоугольной матрицы.
0
Maxelf
6 / 0 / 2
Регистрация: 18.10.2012
Сообщений: 5
02.05.2017, 16:57  [ТС] 6
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Ну и о кластеризации.
Я бы при работе с данными, лежащими в вершинах гиперкуба (не всех вершинах), построил бы соединяющий эти точки остовное дерево (минимальный связный подграф), а потом рвал бы n-1 самых длинных его рёбер, чтобы получить n кластеров (наборов точек, соединённых внутри образовавшихся фрагментов дерева). При условии, что длины этих самых длинных рёбер таки больше, чем длины следующих, оставшихся неразорванными. А то вдруг данные у Вас покрывают все вершины - и тогда все рёбра в остовном подграфе будут иметь единичную длину, и возможно будет любое разбиение, и будет оно одинаково надуманным.
Возник вопрос,как имея набор бинарных векторов построить остовное дерево?
0
VTsaregorodtsev
580 / 533 / 77
Регистрация: 19.02.2010
Сообщений: 1,935
03.05.2017, 22:03 7
Тем же способом, как и в случае, если компоненты векторов целочисленные или с десятичной точкой.
0
03.05.2017, 22:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2017, 22:03

Кластеризация с использованием карт Кохонена
Реализовывал ли кто-нибудь подобную программу? Буду благодарен за код. Или за совет.

Почему так(комбинации бинарных и не бинарных вводов и выводов)?
#include <string> #include <iostream> #include <fstream> #include <iomanip> using namespace...

Создать класс для обработки векторов разность векторов норму векторов
Создать класс для обработки векторов разность векторов норму векторов


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru