Идея состоит в том, чтобы итеративно разделить ваше облако точек на 2 части.Другими словами, вы строите случайное двоичное дерево, в котором каждое разбиение (узел с двумя дочерними элементами) соответствует разбиению точек вашего облака на 2.
Вы начинаете с облака точек.
Вычислить его центроид (барицентр) w
Выбрать произвольную точку cL среди точек облака
Построить точку cR как симметричную точку cL по сравнению с w (сегмент cL-> w такой же, как w-> cR)
Разделить точки вашего облака на двете, которые ближе всего к cR, относятся к подоболочку R, а те, которые ближе всего к cL, принадлежат к подколу L
Повторяем для подоблаков R и L
Примечания:
Вы можете сбросить случайные точки, как только вы их использовали.Тем не менее, сохраняйте центроиды всех подгрупп.
Остановитесь, когда ваши подоблаки содержат ровно одну точку.
Если вы хотите k кластеров, просто возьмите k центроидов, чтобы они содержали все точкиначальное облако.Вы можете делать гораздо более сложные вещи, если хотите (сведение к минимуму дисперсии облаков и т. Д.). Предположим, вам нужно 4 кластера (степень два для удобства). Затем вам нужно только разрезать облако на две части, а затем разрезать каждоеПодоблаки надвое.Если вы хотите 8 кластеров, то снова разрежьте эти подколы один раз в два.И снова для 16 кластеров.
Если вы хотите, чтобы K кластеров с K не степенью 2 (скажем, 24), то посмотрите на ближайшую младшую степень двух.Это 16. Вам по-прежнему не хватает 8 кластеров.Каждый "кластер 16-го уровня" является центром тяжести "суб-облака 16-го уровня".Что вы будете делать, это взять 8 «кластеров уровня 16» (например, наугад) и заменить их каждым из двух «дочерних» «кластеров уровня 32».(Эти два дочерних «уровня-32-кластера» соответствуют двум «уровням-32-субоблакам», которые составляют родительский «уровень-16-суб-облака»)