Способ и устройство для генерирования отсортированного списка элементов

Способ и устройство для генерирования отсортированного списка элементов

Иллюстрации

Показать все

Реферат

УРОВЕНЬ ТЕХНИКИ

Изобретение относится к автоматической сортировке элементов, таких как элементы, происходящие из запросов, или другие элементы, которые характеризуются параметрами, словами или атрибутами, которые можно сравнивать.

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

В последнее время, просмотр видеозаписей в режиме реального времени с, например, YouTube становится популярной альтернативой телевизионному просмотру. Это, однако, требует более активного отношения пользователя, так как ему обычно необходимо набирать текстовые запросы для поиска интересующих видеозаписей в таких хранилищах видеозаписей. Альтернативно, просматривание категорий или списка наиболее популярных видеозаписей может не требовать текстового ввода, но соответственно и не предоставляет персонализированных результатов.

Объединение практики просмотра телевидения «откинувшись в кресле» (интерактивного телевидения) с просматриванием интернет-видеозаписей в целом считается серьезной задачей, и данное изобретение относится к решению данной задачи.

Первый важный этап при реализации объединенного пространства, где пользователи могут наслаждаться как телепрограммами, так и интернет-видеозаписями, реализуется посредством предложения интернет-видеозаписей, которые связаны с телепрограммой, в личном канале. С этой целью, изобретатели разработали способ, который пытается найти интернет-видеозаписи, которые связаны с данной телепрограммой, посредством генерирования множества запросов. Эти запросы зависят от жанра телепрограммы. Например, если телепрограмма является фильмом, то запросы направлены на нахождение анонсных роликов, интервью с режиссером, интервью с главными актерами, удаленных сцен, и так далее. Для документального фильма запросы направлены на нахождение связанных видеозаписей об одном и том же объекте. Эти запросы генерируются с использованием информации, которая доступна в описании метаданных телепрограммы, таких как заголовок, жанр, состав актеров, и так далее. Затем запросы отправляются в хранилища видеозаписей в режиме реального времени. Далее результаты, которые возвращаются для различных запросов, объединяются в один список результатов, в котором желательно, чтобы видеозаписи, которые наиболее связаны с данной телепрограммой, находились в верхней части списка.

Для определения связанности между интернет-видеозаписями и телепрограммой, предполагается, что их описания должны использовать подобные слова. Прямой подход к определению связанности заключается в измерении степени наложения в используемых словах, где слова могут взвешиваться посредством использования так называемого подхода tf*idf [Salton & Buckley, 1987] (Солтон и Бакли, 1987). Прямой подход заключается в представлении каждого из телепрограммы p и интернет-видеозаписи v посредством вектора, где каждая запись в векторах соответствует слову, которое возможно появляется в описаниях соответствующих элементов, и где значение записи задается посредством весового коэффициента tf*idf. Затем связанность между p и v может быть количественно определена посредством косинуса между этими векторами. Более усовершенствованные подходы для количественного определения связанности также возможны, например, с использованием латентно-семантического анализа [Deerwester et al., 1990] (Дирвестер и др., 1990).

Прежде чем представить подробности настоящего изобретения, необходимо ввести некоторые начальные обозначения. Для заданного опорного (или порождающего) элемента, например телепрограммы p, и заданного дополнительного элемента, например интернет-видеозаписи v, пусть rel(v,p) ∈ [0,1] обозначает связанность между v и p. Кроме того, для заданного опорного элемента, например телепрограммы p, пусть Q(p) = {q₁, q₂, …, q_n} обозначает набор запросов, которые используются для нахождения связанных дополнительных элементов, например интернет-видеозаписей. Для запроса q_i ∈ Q(p), пусть R(q_i), = {r_i1, r_i2, …, r_im} обозначает набор результатов, которые возвращаются хранилищем элементов (хранилищем интернет-видеозаписей) по запросу q_i.

Теперь, можно просто соединить все результаты следующим образом R_total = R(q₁)∪R(q₂)∪ … ∪R(q_n), и упорядочить их по уменьшающейся связанности по отношению к программе p в окончательный список результатов: f₁, f₂..., f_N, при

rel(f_i,p) ≥ rel(f_i+1,p),

где i=1,..., N-1.

Целью изобретения является предоставление улучшенного автоматического генерирования отсортированного списка, в котором упорядочивание элементов должно помещать наиболее связанные или интересные элементы на первые места списка.

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

Таким образом, выбор элемента, который следует добавить к отсортированному списку, выполняется посредством устройства в два этапа: во-первых, выбирается кластер с самым высоким ранжированием (далее в данном описании называемым «оценкой») и внутри выбранного таким образом кластера выбирается элемент с самым высоким ранжированием. Кластер обладает ранжированием (отраженным его оценкой), то есть на основе функции связанности над все еще выбираемыми элементами в этом кластере. Таким образом, именно мгновенное самое высокое ранжирование (оценка) кластера управляет тем, какой кластер затем будет выбран, но внутри выбранного кластера выбирается элемент с самой высокой связанностью, потому что ранжирование элементов внутри конкретного кластера определяется значением связанности конкретного элемента по сравнению со значением связанности других элементов в этом кластере.

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

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

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

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

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

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

Цель изобретения дополнительно достигается с помощью способа сортировки элементов посредством создания отсортированного списка, при этом способ содержит этапы, на которых:

предоставляют порождающий элемент (опорный элемент);

сравнивают множество дополнительных элементов с упомянутым опорным элементом (порождающим элементом) и определяют значение связанности для каждого дополнительного элемента, при этом упомянутое значение связанности отражает степень подобия упомянутого дополнительного элемента из упомянутого множества элементов с опорным элементом;

кластеризуют упомянутые дополнительные элементы в некоторое количество кластеров посредством сравнения упомянутых дополнительных элементов друг с другом для определения степени взаимного подобия среди упомянутых дополнительных элементов и группируют упомянутые дополнительные элементы в кластерах так, чтобы каждый элемент принадлежал одному кластеру, который содержит элементы с относительно высокой степенью подобия среди них по сравнению с элементами в других кластерах;

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

a) назначают первоначальные оценки упомянутым кластерам, при этом первоначальная оценка может быть предварительно определенным значением, таким как ноль, или может зависеть от значения связанности элемента, имеющего самое высокое значение связанности в каждом из упомянутых кластеров,

и на каждом итеративном этапе

b) обновляют оценки посредством добавления добавляемой оценки к упомянутым кластерам, при этом упомянутая добавляемая оценка может зависеть от значения связанности элемента, имеющего самое высокое значение связанности в соответствующем одном из упомянутых кластеров относительно значения связанности элемента, имеющего самое высокое значение связанности в других кластерах, либо добавляемая оценка может быть предварительно определенным значением,

c) выбирают тот элемент для добавления к упомянутому списку, который имеет самое высокое значение связанности в кластере, имеющем самую высокую оценку,

d) выбранный элемент добавляют к упомянутому списку и удаляют из упомянутого кластера,

e) уменьшают оценку кластера, из которого был удален добавленный элемент,

повторяют этапы b)-e), пока не добавят все или предварительно определенное количество упомянутых дополнительных элементов к упомянутому списку.

Следует отметить, что добавление оценки к кластерам лишь корректирует относительный ранг кластеров по сравнению с другими кластерами, в то время как значение связанности элементов в кластерах не подвергается корректировке, и таким образом относительный ранг самих элементов не изменяется при изменении оценки кластеров.

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

Соответственно, предпочтительным является электронное устройство, которое содержит пользовательский интерфейс для регулировки значения пороговой величины.

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

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

Говоря в более общем смысле, цель изобретения дополнительно достигается посредством устройства сортировки для автоматической сортировки элементов согласно связанности с порождающим (опорным) элементом, причем устройство сортировки содержит средство, основанное на связанности сортировки, и средство содействия разнообразности, и средство регулировки, соединенное с входом устройства, в котором средство регулировки выполнено с возможностью содействия разнообразности в верхней части списка результатов, отклоняющихся от определенного порядка строгой связанности списка результатов в зависимости от коэффициента разнообразности, введенного пользователем. Коэффициент разнообразности предпочтительно задается пороговой величиной для выбора кластеров элементов, которые подходят для выбора элементов, добавляемых к отсортированному списку элементов.

Кластеризация предпочтительно выполняется посредством этапов, на которых

- начинают с N кластеров, в которых каждый кластер содержит уникальный одиночный элемент,

- осуществляют слияние двух наиболее подобных кластеров, в которых подобие между двумя кластерами может быть задано минимальным или средним подобием между его элементами, и

- повторяют слияние кластеров, пока не получат предварительно определенное количество кластеров.

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

Следовательно, проблема состоит в том, как увеличить разнообразность в верхней части списка, при этом по-прежнему отдавая предпочтение видеозаписям, которые имеют высокую связанность, и при этом избегая элементов (например, результатов поиска) в верхней части, которые имеют очень низкую связанность.

Согласно данному изобретению предлагается решение, которое осуществляет балансировку связанности и разнообразности. В данном решении пользователь способен указывать, сколько разнообразности он предпочтет.

Основная идея, лежащая в предпочтительных вариантах осуществления изобретения, состоит в упорядочивании элементов (например, результатов поиска или результатов запроса) в R_total, то есть в набор всех элементов, которые возвращаются различными запросами, принимая во внимание как связанность, так и разнообразность. Подход основан на объединении следующих двух составляющих.

1. Этапа кластеризации, выполняемого кластеризующим механизмом, который кластеризует дополнительные элементы (например, видеозаписи) R_total в набор кластеров C₁, C₂, …, C_k так, что каждый кластер содержит подобные элементы как, например, видеозаписи. Для удобства предполагаем, что элементы в кластере задаются в качестве списка элементов, упорядоченных по уменьшающейся связанности. Другими словами, элемент с самым высоким значением связанности в кластере имеет самый высокий ранг.

2. Затем, этап основанного на оценке планирования, выполняемого избирателем, используется для повторного выбора первого элемента - который является элементом с самым высоким значением связанности - одного из кластеров для удаления его из кластера и добавления его к окончательному списку результатов. Данная процедура повторяется, пока все элементы не добавятся к окончательному списку результатов и все кластеры не станут пустыми.

Альтернативно процедура может быть остановлена, если достаточное количество элементов добавлено к окончательному списку результатов.

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

Далее изобретение описывается в качестве примера со ссылкой на чертеж.

Фиг.1 является схематичным представлением устройства сортировки согласно изобретению.

На фиг.1 изображено электронное устройство 10 сортировки, которое временно или постоянно соединено с хранилищем 12 элементов. Электронное устройство 10 сортировки имеет пользовательский интерфейс 14 с регулятором 16 связанности/разнообразности. Также может быть предоставлен дополнительный пользовательский интерфейс для ввода или выбора порождающего элемента.

Электронное устройство 10 сортировки имеет порт вывода для вывода отсортированного списка 18 элементов (в данном описании также называемого окончательным списком элементов или окончательным списком результатов).

Между электронным устройством 10 сортировки и хранилищем 12 элементов может быть предоставлен генератор запросов для генерирования запросов, которые следует отправить в хранилище элементов. Эти запросы предпочтительно основаны на порождающем элементе, например, сохраненном в запоминающем устройстве 22 для опорного элемента электронного устройства 10 сортировки. Поэтому, генератор запросов предпочтительно соединен с запоминающим устройством 22 для опорного элемента. Генератор запросов дополнительно выполнен с возможностью приема результатов упомянутых запросов, представляющих собой дополнительные элементы, которые так или иначе связаны с порождающим элементом и которые должны быть подвергнуты сортировке.

Компонентами электронного устройства 10 сортировки являются определитель 20 связанности, который соединен с запоминающим устройством 22 для опорного элемента. В запоминающем устройстве 22 для опорного элемента хранятся атрибуты, слова или данные, характеризующие опорный элемент. Опорный элемент, заданный таким образом, выступает в качестве порождающего элемента для генерирования списка связанных элементов, найденных в хранилище 12 элементов.

Определитель 20 связанности дополнительно соединен с кластеризующим механизмом 24, который при использовании кластеризует элементы, найденные в хранилище элементов, в зависимости от их связанности с порождающим или опорным элементом, заданным в запоминающем устройстве 22. В результате кластеризующий механизм 24 генерирует кластеры дополнительных элементов, связанных с порождающим элементом.

Вывод кластеризующего механизма 24 пересылается в запоминающее устройство 26 для кластеризованных элементов, к которому можно осуществлять доступ посредством генератора 28 списка, который может выступать в качестве планировщика элементов для планирования элементов в отсортированном списке элементов.

Генератор 28 списка содержит оценщика 30 кластеров и избирателя 32 элементов.

Оценщик 30 кластеров выполнен с возможностью назначения и обновления оценок кластерам элементов, сохраненных в запоминающем устройстве 26 для кластеризованных элементов.

Селектор элементов выполнен с возможностью выбора элемента, имеющего самое высокое значение связанности в кластере, имеющем самую высокую оценку. Элемент, выбранный таким образом, затем добавляется к списку 18 и удаляется из кластера в запоминающем устройстве 26 для кластеризованных элементов.

Дополнительно оценка кластера, из которого удаляется элемент, понижается, например, на 1, как раскрывается более подробно далее.

Выбор элементов избирателем элементов включает в себя выбор кластеров, которые подходят для выбора элемента. Такой выбор кластеров основан на значении связанности элемента с самым высоким рангом в каждом кластере. Селектор элементов выполнен с возможностью выбора только тех кластеров, в которых элемент с самым высоким рангом имеет значение связанности, которое соответствует предварительно определенной составляющей самого высокого значения связанности всех элементов и всех кластеров. Таким образом, данная составляющая задает пороговую величину, которую можно регулировать посредством регулятора 16 связанности/разнообразности из пользовательского интерфейса 14.

Таким образом, электронное устройство сортировки задает механизм для автоматической сортировки элементов согласно их связанности с порождающим элементом. Устройство сортировки содержит средство сортировки связанности, и средство содействия разнообразности, и средство регулировки для регулировки пороговой величины, которая содействует либо разнообразности списка результатов, либо порядку более определенной связанности в зависимости от того, каким образом отрегулирована пороговая величина.

Теперь более подробно и в качестве примера будут раскрыты функционирование электронного устройства 10 сортировки и способа сортировки элементов.

Кластеризующий механизм и этап кластеризации

Для кластеризации рассматриваются два возможных варианта осуществления. Первый вариант осуществления может просто осуществлять кластеризацию, которая является результатом различных запросов, которые были использованы. Другими словами, если используется n запросов q₁, q₂, …, q_n, и даны соответствующие наборы элементов R(q₁), R(q₂), …, R(q_n), то предполагается наличие n кластеров C₁, C₂, …, C_n, где кластер C_i задается с помощью R(q_i) и таким образом представляет собой результаты (элементы) от одного запроса. Предположение в данном варианте осуществления состоит в том, что каждый запрос дает набор результатов (элементов), которые являются взаимно подобными, но неподобными по отношению к элементам, которые являются результатами других запросов.

Альтернативный вариант осуществления получается посредством начального объединения всех результатов всех запросов в один набор элементов и затем кластеризации этих элементов на основе взаимного подобия. Для измерения взаимного подобия двух элементов r_ik и r_jl снова можно использовать косинусное подобие соответствующих векторов слов. На основе данного подобия можно использовать один из многочисленных хорошо известных подходов кластеризации. Один из этих подходов заключается в начинании с N кластеров, где каждый кластер содержит уникальный одиночный элемент. Затем осуществляется повторное слияние двух самых подобных кластеров, где подобие между двумя кластерами может быть задано минимальным или средним подобием между его элементами (то есть результатами или элементами, соответственно). Слияние кластеров может повторяться, пока не получится заметное количество кластеров.

Следует отметить, что в течение кластеризации в данном последнем варианте осуществления определяется подобие между элементами. Это может дополнительно использоваться для удаления некоторых из элементов, которые подобны другим элементам, но имеют более низкую или равную связанность с p.

Основанное на оценках планирование посредством оценивания кластеров и выбор элемента в избирателе элементов

Основанное на оценке планирование дополнительных элементов осуществляется следующим образом. Предполагается наличие заданного набора кластеров, где для каждого кластера элементы в кластере задаются в качестве списка элементов, упорядоченных по уменьшающейся связанности (и таким образом, уменьшающемуся рангу) с p. Затем на каждой итерации выбирается кластер, который вносит свой текущий верхний элемент в конечный список элементов и удаляет данный элемент из своего списка. Данный процесс выбора осуществляется следующим образом. Сначала будет представлена упрощенная версия без пороговой величины.

Основанное на оценках планирование без пороговой величины

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

Кластеры обозначаются как C₁, C₂, …, C_k. Для кластера C_i пусть r(i,t) обозначает связанность самого высокосвязанного результата, который все еще находится в C_i в начале итерации t. Следовательно, учитывая, что хранится упорядоченный список элементов для каждого кластера C_i, для определения r(i,t) нужно лишь определить связанность элемента, который является первым в данном списке. Затем в начале каждой итерации t добавляется доля величиной

r(i,t)/Σ_j r(j,t)

к оценке кластера C_i. Другими словами, для каждого кластера C_i в начале итерации t

c_i:=c_i + r(i,t)/Σ_j r(j,t).

Пусть i_max(t) является индексом кластера, который имеет самую высокую оценку на итерации t после увеличения оценок. Другими словами, . Тогда, первый элемент упорядоченного списка элементов кластера удаляется из данного списка и добавляется к окончательному списку элементов. А оценка понижается на единицу, то есть . В случае, если существует множество кластеров, которые имеют максимальное значение оценок, то может быть выбран один произвольный кластер из этих кластеров.

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

Основанное на оценках планирование с пороговой величиной

Основанный на оценках подход, обсужденный выше, не избегает случая, когда элементы с очень низкой связанностью в итоге занимают относительно высокие позиции в окончательном списке элементов. Чтобы избежать этого, вводится относительная пороговая величина α, которая делает результат r_j, пригодным для добавления к окончательному списку элементов, только если

rel(r_j,p) ≥ α∙rel_max(t),

где rel_max(t) = max_i r(i,t) обозначает максимальную связанность элемента, который еще не добавлен к окончательному списку элементов. Следовательно, если самая высокая связанность элементов в заданном кластере равна 0,2 и если пороговая величина α установлена в 0,5, то первый элемент данного кластера станет пригодным для добавления к окончательному списку элементов только тогда, когда максимальная связанность элементов, которые все еще должны быть назначены окончательному списку элементов, снизится до 0,4.

Таким образом, вышеупомянутое основанное на оценках планирование адаптируется следующим образом. Теперь, в начале каждой итерации t, определяется начальная связанность rel_max(t) всеобщего самого высокосвязанного элемента, то есть

rel_max(t) = max_ir(i,t),

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

ПРИМЕР

Далее на примере будет продемонстрирован вышеупомянутый подход основанного на оценках планирования. Предположим, что пороговая величина α установлена в 0,5. Результирующая пороговая величина для каждого итеративного этапа указана под каждой таблицей и определяет пригодность кластера; см. столбец 3 каждой таблицы. Следует обратить внимание на то, что на соответствующем итеративном этапе обновляются оценки только пригодных кластеров; см. столбец 4 каждой таблицы. После обновления оценки выбирается кластер, имеющий самую высокую оценку, и элемент, имеющий самое высокое значение связанности при данной оценке, выбирается затем для добавления к отсортированному списку; см. столбец 5 каждой таблицы. После этого оценка данного конкретного кластера уменьшается на 1; см. столбец 6 каждой таблицы.

В следующих таблицах этапы вычисления определения значений оценки указаны курсивом.

Итерация 1:
	Связанность последующих элементов	Пригодный	Оценка в начале итерации	Выбранный	Оценка в конце итерации
Кластер 1	0,9; 0,6; 0,6	X	0,0→1,00,0 + 0,9/0,9	x	1,0→0,01,0-1
Кластер 2	0,4; 0,4; 0,3		0,0		0,0
Кластер 3	0,2; 0,1; 0,1		0,0		0,0

пороговая величина для пригодности: 0,9*0,5 = 0,45

Связанность элементов в отсортированном окончательном списке элементов после итерации 1:0,9.

Итерация 2:
	Связанность последующих элементов	Пригодный	Оценка в начале итерации	Выбранный