Java — разбиение массива с плавающей точкой на аналогичные сегменты (кластеризация)
У меня есть массив с плавающей точкой, как это:
[1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200]
Теперь я хочу разделить массив следующим образом:
[[1.91, 2.87, 3.61] , [10.91, 11.91, 12.82] , [100.73, 100.71, 101.89] , [200]]
// [200] будет считаться выбросом из-за меньшей поддержки кластера
Я должен найти этот вид сегмента для нескольких массивов, и я не знаю, каким должен быть размер раздела. Я пытался сделать это с помощью иерархическая кластеризация (агломерация) и это дает удовлетворительные результаты для меня. Однако проблема в том, что мне предложили не использовать алгоритмы кластеризации для одномерной задачи, так как они не являются теоретическим обоснованием (как и для многомерных данных) для этого.
Я потратил много времени, чтобы найти решение. Тем не менее, предложения кажутся совершенно другими, как: этот а также этот VS. этот а также этот а также этот.
Я нашел другое предложение, а не кластеризацию, т.е. оптимизация естественных разрывов. Однако для этого также необходимо объявить номер раздела как K-означает (правильно?).
Это довольно запутанно (особенно потому, что я должен выполнить такую сегментацию на нескольких массивах, и невозможно определить оптимальный номер раздела).
Существуют ли способы найти разделы (таким образом, мы можем уменьшить дисперсию внутри разделов и максимизировать разницу между разделами) с некоторым теоретическим обоснованием?
Любые ссылки на статьи / статьи (если есть реализация на C / C ++ / Java) с некоторым теоретическим обоснованием будут для меня очень полезными.
Решение
Я думаю, что я бы отсортировал данные (если это еще не сделано), а затем взял бы смежные различия. Разделите различия на меньшие числа, это разница, чтобы получить процентное изменение. Установите порог, и когда изменение превысит этот порог, запустите новый «кластер».
Редактировать: Быстрый демонстрационный код в C ++:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <functional>
int main() {
std::vector<double> data{
1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200
};
// sort the input data
std::sort(data.begin(), data.end());
// find the difference between each number and its predecessor
std::vector<double> diffs;
std::adjacent_difference(data.begin(), data.end(), std::back_inserter(diffs));
// convert differences to percentage changes
std::transform(diffs.begin(), diffs.end(), data.begin(), diffs.begin(),
std::divides<double>());
// print out the results
for (int i = 0; i < data.size(); i++) {
// if a difference exceeds 40%, start a new group:
if (diffs[i] > 0.4)
std::cout << "\n";
// print out an item:
std::cout << data[i] << "\t";
}
return 0;
}
Результат:
1.91 2.87 3.61
10.91 11.91 12.82
100.71 100.73 101.89
200
Другие решения
Кластеризация обычно предполагает многомерный данные.
Если у вас есть одномерные данные, Сортировать это, а затем использовать либо оценку плотности ядра, либо просто сканировать для самых больших пробелов.
В 1-м измерении проблема существенно упрощается, потому что данные могут быть отсортированы. Если вы используете алгоритм кластеризации, он, к сожалению, не использовать это, так что используйте вместо этого одномерный метод!
Попробуйте найти самый большой разрыв в одномерных данных. Это тривиально: сортировка (n log n, но на практике настолько быстро, насколько это возможно), а затем поиск двух смежных значений для наибольшей разницы.
Теперь попробуйте определить «наибольший разрыв» в двух измерениях и эффективный алгоритм его определения …