K-means++
Поделись знанием:
[Милый и бесценный друг. Ваше письмо от 13 го доставило мне большую радость. Вы всё еще меня любите, моя поэтическая Юлия. Разлука, о которой вы говорите так много дурного, видно, не имела на вас своего обычного влияния. Вы жалуетесь на разлуку, что же я должна была бы сказать, если бы смела, – я, лишенная всех тех, кто мне дорог? Ах, ежели бы не было у нас религии для утешения, жизнь была бы очень печальна. Почему приписываете вы мне строгий взгляд, когда говорите о вашей склонности к молодому человеку? В этом отношении я строга только к себе. Я понимаю эти чувства у других, и если не могу одобрять их, никогда не испытавши, то и не осуждаю их. Мне кажется только, что христианская любовь, любовь к ближнему, любовь к врагам, достойнее, слаще и лучше, чем те чувства, которые могут внушить прекрасные глаза молодого человека молодой девушке, поэтической и любящей, как вы.
Известие о смерти графа Безухова дошло до нас прежде вашего письма, и мой отец был очень тронут им. Он говорит, что это был предпоследний представитель великого века, и что теперь черед за ним, но что он сделает все, зависящее от него, чтобы черед этот пришел как можно позже. Избави нас Боже от этого несчастия.
Я не могу разделять вашего мнения о Пьере, которого знала еще ребенком. Мне казалось, что у него было всегда прекрасное сердце, а это то качество, которое я более всего ценю в людях. Что касается до его наследства и до роли, которую играл в этом князь Василий, то это очень печально для обоих. Ах, милый друг, слова нашего Божественного Спасителя, что легче верблюду пройти в иглиное ухо, чем богатому войти в царствие Божие, – эти слова страшно справедливы. Я жалею князя Василия и еще более Пьера. Такому молодому быть отягощенным таким огромным состоянием, – через сколько искушений надо будет пройти ему! Если б у меня спросили, чего я желаю более всего на свете, – я желаю быть беднее самого бедного из нищих. Благодарю вас тысячу раз, милый друг, за книгу, которую вы мне посылаете и которая делает столько шуму у вас. Впрочем, так как вы мне говорите, что в ней между многими хорошими вещами есть такие, которых не может постигнуть слабый ум человеческий, то мне кажется излишним заниматься непонятным чтением, которое по этому самому не могло бы принести никакой пользы. Я никогда не могла понять страсть, которую имеют некоторые особы, путать себе мысли, пристращаясь к мистическим книгам, которые возбуждают только сомнения в их умах, раздражают их воображение и дают им характер преувеличения, совершенно противный простоте христианской.
k-means++ — улучшенная версия алгоритма кластеризации k-means. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Оригинальный k-means не регламентирует то, как выполняется этот этап алгоритма, и поэтому является нестабильным. Алгоритм предложен в 2007 году Дэвидом Артуром и Сергеем Вассильвитским. Также есть другие похожие методы, открытые другими учёными независимо.
Инициализация
- Выбрать первый центроид случайным образом (среди всех точек)
- Для каждой точки найти значение квадрата расстояния до ближайшего центроида (из тех, которые уже выбраны) dx²
- Выбрать из этих точек следующий центроид так, чтобы вероятность выбора точки была пропорциональна вычисленному для неё квадрату расстояния
Это можно сделать следующим образом. На шаге 2 нужно параллельно с расчётом dx² подсчитывать сумму Sum(dx²). После накопления суммы найти значение Rnd=random(0.0,1.0)*Sum. Rnd случайным образом укажет на число из интервала [0; Sum), и нам остаётся только определить, какой точке это соответствует. Для этого нужно снова начать подсчитывать сумму S(dx²) до тех пор, пока сумма не превысит Rnd. Как только это случится, суммирование останавливается, и мы можем взять текущую точку в качестве центроида.
При выборе каждого следующего центроида специально следить за тем, чтобы он не совпал с одной из уже выбранных в качестве центроидов точек, не нужно, так как вероятность повторного выбора некоторой точки равна 0. - Повторять шаги 2 и 3 до тех пор, пока не будут найдены все необходимые центроиды.
Далее выполняется основной алгоритм K-Means.
Реализации
Реализация на языке Java включена в популярную библиотеку Apache[1].
Напишите отзыв о статье "K-means++"
Примечания
- ↑ [commons.apache.org/proper/commons-math/ Commons Math: The Apache Commons Mathematics Library]
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий K-means++
«Adieu, chere et bonne amie, que notre divin Sauveur et Sa tres Sainte Mere vous aient en Leur sainte et puissante garde. Marieie».[Милый и бесценный друг. Ваше письмо от 13 го доставило мне большую радость. Вы всё еще меня любите, моя поэтическая Юлия. Разлука, о которой вы говорите так много дурного, видно, не имела на вас своего обычного влияния. Вы жалуетесь на разлуку, что же я должна была бы сказать, если бы смела, – я, лишенная всех тех, кто мне дорог? Ах, ежели бы не было у нас религии для утешения, жизнь была бы очень печальна. Почему приписываете вы мне строгий взгляд, когда говорите о вашей склонности к молодому человеку? В этом отношении я строга только к себе. Я понимаю эти чувства у других, и если не могу одобрять их, никогда не испытавши, то и не осуждаю их. Мне кажется только, что христианская любовь, любовь к ближнему, любовь к врагам, достойнее, слаще и лучше, чем те чувства, которые могут внушить прекрасные глаза молодого человека молодой девушке, поэтической и любящей, как вы.
Известие о смерти графа Безухова дошло до нас прежде вашего письма, и мой отец был очень тронут им. Он говорит, что это был предпоследний представитель великого века, и что теперь черед за ним, но что он сделает все, зависящее от него, чтобы черед этот пришел как можно позже. Избави нас Боже от этого несчастия.
Я не могу разделять вашего мнения о Пьере, которого знала еще ребенком. Мне казалось, что у него было всегда прекрасное сердце, а это то качество, которое я более всего ценю в людях. Что касается до его наследства и до роли, которую играл в этом князь Василий, то это очень печально для обоих. Ах, милый друг, слова нашего Божественного Спасителя, что легче верблюду пройти в иглиное ухо, чем богатому войти в царствие Божие, – эти слова страшно справедливы. Я жалею князя Василия и еще более Пьера. Такому молодому быть отягощенным таким огромным состоянием, – через сколько искушений надо будет пройти ему! Если б у меня спросили, чего я желаю более всего на свете, – я желаю быть беднее самого бедного из нищих. Благодарю вас тысячу раз, милый друг, за книгу, которую вы мне посылаете и которая делает столько шуму у вас. Впрочем, так как вы мне говорите, что в ней между многими хорошими вещами есть такие, которых не может постигнуть слабый ум человеческий, то мне кажется излишним заниматься непонятным чтением, которое по этому самому не могло бы принести никакой пользы. Я никогда не могла понять страсть, которую имеют некоторые особы, путать себе мысли, пристращаясь к мистическим книгам, которые возбуждают только сомнения в их умах, раздражают их воображение и дают им характер преувеличения, совершенно противный простоте христианской.
