Привет всем, это вторая и последняя часть этой серии. В этом посте мы конвертируем этот документ в код Python и таким образом достигнем практического понимания того, что такое имитация отжига и как ее можно использовать для кластеризации.

Часть 1 этой серии охватывает теоретическое объяснение имитации отжига (SA) с некоторыми примерами. Рекомендую прочитать. Однако, если вы хорошо осведомлены или знакомы с SA, я думаю, вы можете понять большую часть того, что собираетесь прочитать, но вы всегда можете перейти к Части 1 и прочитать ее, если что-то неуверенно для вас. Я не буду объяснять всю статью, только практическую часть.

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

Предположим, это товары, которые доступны на веб-сайте покупок, который вы посетили. Когда вы неоднократно просматривали несколько предметов, таких как обувь, рубашки, джинсы и часы, вы начинали получать все больше и больше разновидностей этих предметов, показываемых вам в качестве рекомендаций. Вы когда-нибудь замечали это? Теперь, как это происходит? Вот как это происходит. На веб-сайте будет указано количество просмотров продукта. На основе этого числа элементы группируются по категориям нравится и не нравится. Когда вы просматриваете какие-то продукты несколько раз, возможно, вы пытаетесь купить понравившиеся вам товары, которые похожи. Таким образом, веб-сайт помещает рубашки, обувь, джинсы и часы в кластер «нравится» (другими словами, помечает их как «Нравится»), а остальные товары с меньшим количеством просмотров помещает в группу «. не нравится ». Эти ярлыки - всего лишь примеры. Их можно назвать как «Можно покупать» или «Не покупать» в зависимости от разработчиков веб-сайта.

Извините за мои плохие навыки презентации, но я надеюсь, что идея вам понравится. Теперь другие веб-сайты могут использовать эту информацию и показывать вам рекламу обуви, рубашек и т. Д. Это очень простой пример. В реальной жизни на кластеры может влиять больше факторов (а не только количество просмотров).

Программно это будет выглядеть примерно так:

В зависимости от того, сколько раз вы просматривали элементы, они сгруппированы. На основе фактора, по которому происходит кластеризация, называется внутренний критерий кластеризации. Здесь критерий внутренней кластеризации - это количество раз, когда вы просматривали элемент. Еще один популярный пример критерия внутренней кластеризации - расстояние, которое используется в Кластеризация K-средних (см. Этот пост Мубарис Хассан для лучшего объяснения).

Теперь, когда вы разобрались с критериями кластеризации и внутренней кластеризации, Наша цель - выполнить кластеризацию с заранее определенным критерием внутренней кластеризации с использованием имитации отжига.

Приступим к реализации кода алгоритма, написанного в статье, на примере сценария. Предположим, есть 10 объектов (от 1 до 10) и 6 меток (от A до F) с начальным состоянием, как показано ниже:

initial_state = {1:’A’, 2: ‘B’, 3:’A’, 4:’B’, 5:’C’, 6:’B’, 7:’A’, 8:’None’, 9:’None’, 10:’None’ }

Здесь помечены объекты с 1 по 7, а с 8 по 9 - нет.

Поместим неиспользуемые метки в список

unused_labels = ['D', 'E', 'F']

Основные шаги алгоритма:

  1. Переменная под названием «начальная температура» имеет высокое значение и продолжает уменьшаться до тех пор, пока не будет достигнуто низкое значение, которое называется «конечная температура».
  2. Пока температура продолжает снижаться, «исходное состояние» принимается за «текущее состояние».
  3. Действие выполняется в текущем состоянии, и его энергия вычисляется на основе определенного критерия внутренней кластеризации. Если это «возмущенное состояние» (возмущенное состояние) отличается от текущего состояния, то оно выбирается как «следующее состояние».
  4. Вычисляется разница между энергиями следующего состояния и текущего состояния.
  5. Значение следующего состояния переводится в текущее состояние только в том случае, если разность энергий меньше нуля или если «коэффициент вероятности» (который зависит от текущей температуры) больше или равен случайному десятичное число от 0 до 1 (или случайное целое число от 0 до 10).
  6. Это заканчивается в зависимости от значения температуры и параметра, называемого «Максимальное количество итераций».

Существуют такие параметры, как «Среднее увеличение стоимости» над возмущениями, «Количество увеличений стоимости» в Макс. Итерациях случайных возмущений, «коэффициент приемлемости», «вероятность. epsilon » (не путайте его с коэффициентом вероятности, упомянутым выше) и « Beta » (0‹ beta ‹1), используя которые начальная и конечная температуры рассчитано.

initial_temperature = avg_cost_increase / math.log( num_cost_increases / ((num_cost_increases * acc_ratio) — (1-acc_ratio) * (max_iter — num_cost_increases)))
final_temperature = -beta * avg_cost_increase / math.log(prob_e)

«Альфа» определяется как скорость распада, при которой температура продолжает снижаться.

alpha = math.pow(final_temperature / initial_temperature , 1 / num_temp)

Значения Max Iertarions, Acceptance Ratio, Probability Epsilon, beta:

avg_cost_increase = 200
acc_ratio = 0.75 
prob_e = 0.00000000001
beta = 0.125
max_iter =  4 * num_objects

Все эти значения и формулы взяты из самого документа. Я не хочу объяснять здесь все параметры, потому что нам придется копать глубже, и я подумал, что это немного отклоняется от нашей реальной темы. Однако, если вас это сильно интересует, просмотрите ссылки в разделах статьи.

Это код, который мы использовали до сих пор. Давайте посмотрим на функцию Simulated Annealing:

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

Это самая важная часть кода. Нам нужно вычислить энергию состояния, и для этого нам нужно определить, когда состояние будет иметь высокую или низкую энергию. Давайте определим, что состояние будет иметь меньше энергии, когда есть больше объектов, помеченных как F, и с высокой энергией, когда меньше количество объектов, помеченных как F. Таким образом, алгоритм всегда будет стремиться иметь самую низкую энергию, возможную для состояния , поэтому он попытается поместить максимальное количество объектов в кластер F, другими словами, пометить максимальное количество объектов как F.

Итак, критерий внутренней кластеризации здесь должен иметь максимальное количество объектов, помеченных как F. Я взял здесь метку F. Вы можете попробовать с любым другим лейблом. Вы можете попробовать другой критерий внутренней кластеризации, например, количество объектов, помеченных как B, должно быть равно количеству объектов, помеченных как A, количество объектов, помеченных как A, должно составлять 1/3 от количества объектов, помеченных как C, и многие больше таких математических уравнений, включающих разные метки. Убедитесь, что вы поняли этот абзац, так как это ключевой момент для реализации этого кода в различных ситуациях.

Теперь давайте посмотрим на часть кода, которая выполняет действие в текущем состоянии для создания следующего состояния:

Мы инициализируем два списка L (используемые метки) и Lc (дополнение L - список неиспользуемых меток) и копируем текущее состояние в новую переменную, называемую Perturbated State. Выберите случайный объект и после входа в цикл выберите случайное целое число m между [0, | L |]. Если m = 0 и существует неиспользуемая метка кластера (т. е. | L | ‹k), то случайный объект, выбранный ранее, получит случайную метку из списка неиспользуемых меток. Если длина используемых меток и общее количество меток (k) равны, это означает, что неиспользуемых меток нет, и выбранный объект получит случайную метку из списка использованных меток.

Теперь нам нужно проверить, отличается ли возмущенное состояние от текущего состояния или нет. Возможен сценарий, при котором объекту присваивается та же метка, что и у него уже есть. Пример: объект 3 был выбран случайным образом, и одно из условий (m ›0 или длина l равняется k) выполняется, и метка A выбирается случайным образом из списка используемых меток. В этом случае возмущенное состояние будет таким же, как текущее состояние. Никаких изменений не будет. Таким образом, мы будем запускать этот цикл до тех пор, пока возмущенное состояние не станет равным текущему состоянию, и, наконец, не вернем возмущенное состояние.

Итак, мы принимаем возмущенное состояние как состояние nex, после чего мы вычисляем энергию следующего состояния через функцию значения. Мы помещаем значение следующего состояния в текущее состояние, если следующее состояние имеет меньше энергии, чем у текущего состояния, или если коэффициент вероятности больше или равен случайному целому числу от 0 до 10.

  1. Этот процесс продолжается (максимальное количество итераций, умноженное на разницу начальной и конечной температур) количество раз.

Вот окончательный код:

Вот результат:

Здесь у вас будут разные значения для «Энергии конечного состояния» каждый раз, потому что при каждом выполнении алгоритм выбирает множество значений случайным образом. Вы можете выполнить некоторую настройку параметров, чтобы увидеть, как это повлияет на результаты. При достаточно большом максимальном количестве итераций и достаточно малом (коэффициент принятия 1), бета-коэффициенте и эпсилон вероятности вы можете добиться лучших результатов.

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

Большое вам спасибо за ваше время. Хорошего дня!!