Существует ли алгоритм в виде дерева решений для неконтролируемой кластеризации?

20

У меня есть набор данных, состоящий из 5 функций: A, B, C, D, E. Все они являются числовыми значениями. Вместо кластеризации на основе плотности я хочу кластеризовать данные в виде дерева решений.

Подход, который я имею в виду, выглядит примерно так:

Алгоритм может делить данные на X исходных кластеров на основе признака C, то есть X кластеров могут иметь малые значения C, средний C, большие C и очень большие значения C и т. Д. Затем, под каждым из узлов X кластера, алгоритм дополнительно делит данные в кластеры Y основаны на функции A. Алгоритм продолжается до тех пор, пока не будут использованы все функции.

Алгоритм, который я описал выше, похож на алгоритм дерева решений. Но он мне нужен для неконтролируемой кластеризации, а не для контролируемой классификации.

Мои вопросы следующие:

  1. Такие алгоритмы уже существуют? Какое правильное название для такого алгоритма
  2. Существует ли пакет / библиотека R / python, в котором есть реализация алгоритмов такого рода?
бабушка
источник
3
But I need it for unsupervised clustering, instead of supervised classificationОдна только эта ключевая фраза слишком коротка и не дает четкого объяснения того, что вы хотите. Выше вы описали то, что мне кажется деревом решений. Можете ли вы сейчас дать аналогичный отрывок о желаемом алгоритме?
ttnphns
1
@ttnphns Привет, как вы знаете, дерево решений является контролируемым методом. Вы маркируете каждый вектор объектов как Class1 или Class2. Алгоритм определяет порог для каждого признака на основе известных меток. Однако я столкнулся с проблемой кластеризации. Я не знаю правильных меток для каждого векторного признака. Я хочу найти алгоритм, который автоматически определяет порог для каждой функции, чтобы построить дерево. Таким образом, результирующая кластеризация может быть легко интерпретирована как, например, кластер 1: высокий A-низкий B-средний C-высокий D-низкий E, кластер 2 как низкий A - высокий B-средний C-средний D - низкий E.
nan
Не совсем хорошо понимаю вас. Взять CHAID, к примеру, дерево. Вы должны выбрать зависимую переменную. Пусть это будет A. Алгоритм выбирает среди B, C, D, E переменную, наиболее коррелированную с A, и binns эту переменную (скажем, это, предиктор, быть D) на две или более категории «оптимально» - так, чтобы корреляция (между категорированной переменной D и переменной A максимально. Скажем, осталось 3 группы, D1, D2, D3. Далее, та же самая процедура повторяется внутри каждой категории (группы) D отдельно, и лучший предиктор среди B, C , E ищется под биннингом и т. Д. Что именно вам здесь не подходит?
ttnphns
2
@ttnphns Я только что нашел эту газету, думаю, они сделали то, что я имею в виду. ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/...
нан
1
@nan вы нашли какую-либо реализацию таких деревьев? Они не предоставляют ссылки на код в статье
Alleo

Ответы:

12

Вы можете рассмотреть следующий подход:

  • Используйте любой алгоритм кластеризации, подходящий для ваших данных
  • Предположим, что в результате кластер являются классами
  • Обучить дерево решений по кластерам

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

Аноним-Мусс-Восстановить Монику
источник
1
согласитесь, что это «уместно», но, конечно, нужно всегда иметь в виду, что создание метки из алгоритма кластеризации не является «реальной» особенностью наблюдения. В зависимости от качества и типа кластеризации, смещение будет существовать в большей или меньшей степени.
NiuBiBang
Можете ли вы указать мне статью, в которой обсуждается эта стратегия?
nCessity
2

Первая статья, которая приходит на ум, это: кластеризация посредством построения дерева решений https://pdfs.semanticscholar.org/8996/148e8f0b34308e2d22f78ff89bf1f038d1d6.pdf

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

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

1) Под надзором: это несколько похоже на статью (стоит прочитать). Создайте единую модель дерева решений, чтобы узнать какую-то цель (вы решаете, что имеет смысл). Цель может быть случайно сгенерированным столбцом (требуется повторение и оценка того, какая итерация была лучшей, см. Ниже). Определите каждый полный путь дерева как «кластер», поскольку точки, проходящие через этот ряд ветвей, технически схожи с целью. Это хорошо работает только для некоторых проблем, но эффективно в больших масштабах. Вы в конечном итоге с K кластеров (см. Ниже).

2) Полу-контролируемый (своего рода неконтролируемый, но механически контролируемый), используя # 1: вы можете попробовать построить деревья, чтобы предсказать столбцы в шаблоне «оставь один на один». то есть, если схема [A, B, C], создайте 3 модели [A, B] -> C, [A, C] -> B, [B, C] -> A. Вы получаете кластеры KN (см. Ниже). N = Len (схема). Если некоторые из этих функций не интересны или слишком несбалансированы (в случае категорий), не используйте их в качестве целей.

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

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

Минусы: не стандартные, должны быть написаны, наивный уклон, коллинеарность с целью приводит к плохим результатам, если 1000 одинаково важных функций не будут работать хорошо (KMeans с евклидовым расстоянием здесь лучше).

Сколько кластеров вы получаете? Вы должны, абсолютно должны ограничить модель DT, чтобы не расти слишком сильно. Например, установите минимальное количество выборок на лист, максимальное количество листовых узлов (предпочтительно) или максимальную глубину. При желании установите ограничения чистоты или энтропии. Вы должны проверить, сколько кластеров это вам дало, и оценить, лучше ли этот метод, чем реальная кластеризация.

Подходили ли вам методы и параметры? Что было лучше? Чтобы выяснить это, необходимо выполнить оценку кластера: показатели производительности для оценки обучения без учителя

ldmtwo
источник
2

То, что вы ищете, это алгоритм разделяющей кластеризации.

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

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

DIANA - единственный алгоритм разделения кластеризации, который я знаю, и я думаю, что он структурирован как дерево решений. Я был бы удивлен, если бы там не было других.

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

KirkD_CO
источник
0

Рассмотрим одну идею: предположим, у вас есть k особенностей и n баллов. Вы можете построить случайные деревья, используя (k-1) функцию и 1 функцию в качестве зависимой переменной. Y. Вы можете выбрать высоту h, после которой у вас будут точки данных в корнях. Вы можете принять участие в голосовании разных деревьев. Просто мысль.

Анкит Сварнар
источник