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

Я ищу способ реализовать кластерный алгоритм, который должен иметь возможность кластеризовать строковые массивы.

Предполагая, что такие входы:

string[][] input =
{
     new string[] { "A", "B", "C", "D", "F", "G"},
     new string[] { "D", "F", "G", "H"},
     new string[] { "A", "B", "C", "G"},
     new string[] { "B", "C", "Z", "A", "F"},
     new string[] { "O", "N", "P", "X"}
};

Алгоритм должен уметь определять, что элементы 0, 2 и 3 находятся в одном кластере. Но как я могу это сделать?

Что я пробовал? Я пытался использовать платформу Accord.net для создания кластера KMeans. Но я заметил, что Kmeans работает только с двойными числами (поэтому я конвертирую каждое значение в строке [] в число и пытаюсь снова). В качестве меры расстояния я реализовал расстояние Jaccard.

После этого я получаю сообщение об ошибке: «Матрица точек должна быть прямоугольной». Это имеет смысл, потому что мои входные данные не являются прямоугольной матрицей.

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

Пример кода:

double[][] inputs =
{
     new double [] { 0, 1, 2, 3, 4 },
     new double [] { 0, 1, 5, 2, 3, 4 },
     new double [] { 33, 0, 1, 5, 2, 4 },
     new double [] { 0, 1, 2, 6, 7,  8},
     new double [] { 0, 9, 1, 2, 6, 8 },
     new double [] { 0, 4, 10, 15, 11, 12, 13  },
     new double [] { 0, 4, 14, 15, 11, 12, 13, 16  },
     new double [] { 0, 17, 18, 11, 19, 12, 20},
     new double [] { 0, 17, 18, 11, 19, 12, 20, 15, 26},
     new double [] { 0, 4, 14, 15, 11, 12, 13, 16, 17, 18  },
     new double [] { 0, 21, 22, 23, 24, 26, 25},
     new double [] { 24, 26, 27, 21, 28, 29, 1},
     new double [] { 24, 243, 26, 30},
     new double [] { 31, 24, 22, 23, 0, 11, 26 }
     // Many others... 
};

var kmeans   = new KMeans(k: 3, distance: new JaccarDistanceDouble() );
var clusters = kmeans.Learn(inputs); // Throws the error.
int[] labels = clusters.Decide(inputs);

machine-learning c# cluster-analysis k-means accord.net
person lwb    schedule 22.07.2018    source источник
comment
Я никогда не работал с этими алгоритмами, но думаю, что на вход алгоритма кластеризации должна поступать матрица расстояний Жаккара. Причем последний будет прямоугольным и типа двойным.   -  person Olivier Jacot-Descombes    schedule 22.07.2018
comment
Я сделаю несколько тестов, но я думаю, что это не сработает, потому что KMeans должен вычислить расстояние от элемента [0] до каждого другого элемента, чтобы он мог вычислить K ближайших элементов для формирования кластера. Но я попробую ваше предложение. Спасибо @OlivierJacot-Descombes   -  person lwb    schedule 22.07.2018
comment
Или обработайте ввод как одномерную задачу, где ввод представляет собой массив наборов букв. Каждый набор букв будет рассматриваться как один объект, расстояние которого до других должно быть определено. Теперь входными данными для алгоритма кластеризации является вектор, а не матрица.   -  person Olivier Jacot-Descombes    schedule 22.07.2018
comment
@OlivierJacot-Descombes: нет, k-средним нужны координаты, а не расстояния. Имеет смысл использовать только с непрерывными переменными.   -  person Has QUIT--Anony-Mousse    schedule 29.07.2018

Ответы (3)


arrow_upward
1
arrow_downward

Метод K-средних требует непрерывных переменных.

Потому что ему нужно вычислить среднее. Отсюда и название.

Следовательно, вы не можете использовать k-средние для этих данных.

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

person Has QUIT--Anony-Mousse    schedule 29.07.2018

arrow_upward
1
arrow_downward

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

Поскольку вы имеете дело со строковыми или категориальными данными, можно применить алгоритм try k-modes. Хотя существует несколько других алгоритмов кластеризации категориальных данных, K-режим является расширением классического k-средних. Подробное обсуждение вы можете прочитать в этом статье. . Я не знаю, как это можно реализовать в C#, но для R вы можете увидеть это документация.

Кроме того, вы также можете сделать one-hot encoding, который представляет собой представление категориальных переменных в виде двоичных векторов, а затем применить k-средних. Но тогда вы можете столкнуться с проклятием размерности.

person mnm    schedule 29.07.2018

arrow_upward
-1
arrow_downward

Вы можете отсортировать каждый одномерный массив по отдельности, а затем заполнить их нулями для отсутствующих значений. В этот момент вы можете применить jaccard или cosine и т. д.

person WestCoastProjects    schedule 22.07.2018