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

У меня есть баллы с бинарными функциями:

id, feature 1, feature 2, ....
1, 0, 1, 0, 1, ...
2, 1, 1, 0, 1, ...

а размер матрицы порядка 20к * 200к, но она скудная. Я использую Mahout для кластеризации данных по алгоритму kmeans и имею следующие вопросы:

  1. Kmeans - хороший кандидат на двоичные функции?
  2. Есть ли способ уменьшить размеры, сохранив концепцию манхэттенской меры расстояния (мне нужен Манхэттен вместо Косинуса или Танимото)
  3. Использование памяти kmeans велико и требует 4 ГБ памяти для каждой задачи сопоставления / уменьшения (блоки 4 МБ в векторном файле размером 400 МБ для кластеров 3k). Учитывая, что объект Vector в Mahout использует двойные записи, есть ли способ использовать только логические записи для точек, но двойные записи для центров?

cluster-analysis k-means binary-data dimension-reduction mahout
person Masood_mj    schedule 11.07.2012    source источник

Ответы (2)


arrow_upward
2
arrow_downward

k-means - хороший кандидат, если у вас хороший показатель расстояния. Расстояние до Манхэттена могло быть вполне приемлемым; Мне нравится лог-вероятность.

Вы можете использовать любую технику уменьшения размеров, которая вам нравится. Мне нравится метод альтернативных наименьших квадратов; СВД тоже хорошо работает. Для матрицы такого размера вы можете легко сделать это в памяти с помощью Commons Math, а не возиться с Hadoop - это слишком много.

(См. Также http://myrrix.com - у меня есть очень быстрая реализация ALS, которую вы можете повторно использовать в ядре / онлайн-модулей. Он может обработать это за несколько секунд в куче десятков МБ.)

В матрице функций больше нет двоичных значений 0/1. В пространстве признаков должно работать косинусное расстояние (1 - cosineSimilarity). Танимото / Жаккар не подходит.

person Sean Owen    schedule 11.07.2012
comment
Я не уверен, что полностью понимаю проблему, но расстояние Жаккара подходит для оценки сходства между двумя объектами с двоичными атрибутами. - person Andres Felipe; 25.08.2013

arrow_upward
2
arrow_downward

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

  • Если среднее значение не уменьшает дисперсию, оно может не сходиться (арифметическое среднее является оптимальным для евклидова расстояния. Для Манхэттена медиана считается лучше. Для очень разных показателей я не знаю)
  • Среднее значение, вероятно, больше не будет таким редким
  • Среднее значение больше не будет двоичным вектором.

Более того, какие k вы хотите использовать, в частности, для больших наборов данных?

Вам действительно следует изучить другие меры расстояния. Размер ваших данных невелик; все равно должно хватить одного компьютера. Используя компактное векторное представление, он легко помещается в основную память. Просто не используйте сначала что-то, что вычисляет матрицу сходства n ^ 2. Может быть, попробовать что-нибудь с индексами для подобия бинарных векторов.

k-means довольно легко реализовать, особенно если вы не выполняете предварительный посев. Чтобы уменьшить использование памяти, просто реализуйте его самостоятельно для представления, оптимального для ваших данных. Это может быть битовый набор или отсортированный список ненулевых измерений. Затем расстояние до Манхэттена сводится к подсчету количества измерений, в которых векторы различаются!

person Has QUIT--Anony-Mousse    schedule 12.07.2012
comment
Как вы сказали, у centeriods нет двоичных значений, поэтому я не могу хранить для них двоичные значения. Кажется, что если я хочу обрабатывать центроиды и фактические данные по-разному, мне нужно иметь свою собственную реализацию. Кроме того, я не могу получить доступ к машине с десятками гигабайт памяти, поэтому мне кажется, что mahout - лучший вариант для меня, поскольку он может показать, что подход масштабируемый. Я должен попробовать метод Median, изменив реализацию mahout и посмотреть результат. - person Masood_mj; 12.07.2012
comment
да. И посмотрите на k-медианы. Средние значения снова являются двоичными, их легко вычислить для двоичных данных: они являются наиболее распространенным значением для кластера. Но это также риск: это значение, вероятно, всегда будет просто 0! На этом этапе вы выполняете лишь случайный выбор функций. Так что возьмите другой алгоритм, ничего из семейства k-средних. - person Has QUIT--Anony-Mousse; 12.07.2012
comment
@ Anony-Mousse, хотя я не согласен с вашими аргументами против k-means, также изложенными в этом другом вопрос об обмене стеком, мне любопытно, на чем вы их основываете, поскольку k-средние с помощью расстояния хамминга и компонентных медиан являются популярными выбор, когда доходит до использования k-средних для двоичных потоков, например Реализация Matlab k-means - person Andres Felipe; 25.08.2013
comment
k-медианы - это известный вариант, который является стабильным, поскольку медиана оптимизирует абсолютные отклонения. Однако для разреженных двоичных данных медиана в каждом измерении, скорее всего, будет равна 0. Не все, что используется, предлагается или популярно, является стабильным и математически обоснованным. - person Has QUIT--Anony-Mousse; 25.08.2013