Способ и устройство для кластеризации

Способ и устройство для кластеризации

Иллюстрации

Показать все

Реферат

Перекрестные ссылки на связанные заявки

[0001] Настоящая заявка ссылается на приоритет заявки на патент Китайской Народной Республики №CN 201410097422.5, которая была зарегистрирована 14 марта 2014 года. При этом содержание упомянутой заявки полностью включено в настоящий документ путем ссылки.

Область техники

[0002] Настоящее изобретение относится, в общем, к области компьютерных технологий, а более конкретно, к способу кластеризации и к соответствующему устройству.

Предпосылки создания изобретения

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

[0004] Например, если способ кластеризации применяют для классификации изображений человеческих лиц, когда требуется, чтобы изображение одного и того же человека было отнесено к одному классу, то для измерения сходства между двумя человеческими лицами в способе кластеризации применяют расстояние рангового порядка (Rank-Order distance), благодаря чему изображения одного и того же человека могут быть отнесены к одному кластеру. Однако в случае, когда количество лиц в группе изображений слишком велико, а количество изображений каждого отдельного человека слишком мало, точность результатов кластеризации, полученных данным способом, является сравнительно низкой.

Сущность изобретения

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

[0006] Для решения поставленной выше технической задачи в настоящем изобретении предложены технические решения, которые будут изложены ниже.

[0007] В соответствии с первым аспектом вариантов осуществления настоящего изобретения предложен способ кластеризации, включающий в себя:

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

[0009] В сочетании с первым аспектом настоящего изобретения, в первом возможном методе реализации этого аспекта, получение степени внутриклассового сходства, соответствующей классу после итеративного слияния, с использованием межобъектных расстояний внутри класса, выполняют следующим образом:

[0010] получают соответствующие межобъектные расстояния внутри класса; и вычисляют среднее расстояние по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса, в результате чего получают степень внутриклассового сходства данного класса.

[0011] В сочетании с первым аспектом настоящего изобретения, во втором возможном методе реализации этого аспекта, получение степени внутриклассового сходства, соответствующей классу после итеративного слияния, с использованием межобъектных расстояний внутри класса, выполняют следующим образом:

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

[0013] В сочетании с первым методом реализации первого аспекта настоящего изобретения или со вторым методом реализации первого аспекта настоящего изобретения в третьем методе реализации первого аспекта настоящего изобретения для каждого класса, полученного итеративным слиянием, группирование объектов внутри класса, имеющих расстояние, меньшее, чем упомянутая степень внутриклассового сходства, в новый класс и обновление количества классов выполняют следующим образом:

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

[0015] В сочетании с первым аспектом настоящего изобретения, в четвертом возможном методе реализации этого аспекта, выполнение итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка выполняют следующим образом:

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

[0017] В соответствии со вторым аспектом вариантов осуществления настоящего изобретения предложено устройство для кластеризации, включающее в себя:

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

[0019] В сочетании со вторым аспектом настоящего изобретения, в первом возможном методе реализации этого аспекта, упомянутый блок получения включает в себя:

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

[0021] В сочетании со вторым аспектом настоящего изобретения, во втором возможном методе реализации этого аспекта, упомянутый блок получения включает в себя:

[0022] второй подблок получения, сконфигурированный для получения соответствующих межобъектных расстояний внутри класса; второй подблок вычисления, сконфигурированный для вычисления среднего расстояния по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса; и подблок нормализации, сконфигурированный для нормализации упомянутого среднего расстояния, в результате чего получают степень внутриклассового сходства данного класса.

[0023] В сочетании с первым методом реализации второго аспекта настоящего изобретения или со вторым методом реализации второго настоящего изобретения в третьем методе реализации второго аспекта настоящего изобретения упомянутый блок разделения включает в себя:

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

[0025] В сочетании со вторым аспектом настоящего изобретения, в четвертом возможном методе реализации этого аспекта, упомянутый блок итеративного слияния включает в себя:

[0026] третий подблок получения, сконфигурированный для получения межклассовых расстояний рангового порядка и для получения нормализованных межклассовых расстояния рангового порядка; подблок слияния, сконфигурированный для слияния классов, имеющих межклассовое расстояние рангового порядка меньше, чем пороговое значение расстояния, и нормализованное межклассовое расстояние рангового порядка, меньшее 1; и второй подблок определения, сконфигурированный, если количество классов после слияния меньше, чем количество классов до слияния, для управления упомянутым третьим подблоком получения с целью выполнения шага получения межклассовых расстояний рангового порядка после слияния и получения нормализованных расстояний рангового порядка между классами.

[0027] В соответствии со вторым аспектом вариантов осуществления настоящего изобретения предложено терминальное устройство, включающее в себя:

[0028] процессор; и память, сконфигурированную для хранения инструкций, исполняемых упомянутым процессором;

[0029] при этом процессор сконфигурирован:

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

[0031] Технические решения, предложенные в вариантах осуществления настоящего изобретения, могут давать следующие полезные результаты: сначала, при помощи способа кластеризации, согласно межклассовым расстояниям рангового порядка выполняют слияние классов, удовлетворяющих определенному условию, в результате чего сокращают количество классов; затем, в соответствии с межобъектными расстояниями внутри класса, вычисляют степень внутриклассового сходства; и наконец, объекты внутри класса, расстояние между которыми меньше степени внутриклассового сходства, выделяют в новый класс, до тех пор, пока все классы не будут разделены. Затем снова выполняют итеративное слияние разделенных классов и их разделение до тех пор, пока никакой из классов более не сможет быть разделен, в результате чего получают классы, содержащие множество объектов, и классы, содержащие единичные объекты. Благодаря тому, что объекты со сравнительно высокой степенью несходства в процессе кластеризации удаляют, точность результатов кластеризации может быть повышена. В частности, появляется возможность повысить точность результатов кластеризации в случае, когда набор данных является сравнительно большим, а количество объектов одного класса сравнительно малым.

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

Краткое описание чертежей

[0033] На приложенных чертежах, которые входят в состав настоящего описания и являются его неотъемлемой частью, проиллюстрированы варианты осуществления, соответствующие настоящему изобретению. Приложенные чертежи, вместе с описанием, служат для разъяснения замысла настоящего изобретения:

[0034] Фиг. 1 представляет собой эскизную иллюстрацию, на которой показано множество объектов, ранжированных в виде последовательностей;

[0035] Фиг. 2 представляет собой блок-схему алгоритма, иллюстрирующую способ кластеризации в соответствии с одним из примеров осуществления настоящего изобретения;

[0036] Фиг. 3 представляет собой блок-схему алгоритма, иллюстрирующую шаг S110 на фиг. 2 в соответствии с одним из примеров осуществления настоящего изобретения;

[0037] Фиг. 4 представляет собой блок-схему алгоритма, иллюстрирующую шаг S110 на фиг. 2 в соответствии с другим примером осуществления настоящего изобретения;

[0038] Фиг. 5 представляет собой блок-схему алгоритма, иллюстрирующую шаг S120 на фиг. 2 в соответствии с одним из примеров осуществления настоящего изобретения;

[0039] Фиг. 6 представляет собой блок-схему алгоритма, иллюстрирующую шаг S130 на фиг. 2 в соответствии с одним из примеров осуществления настоящего изобретения;

[0040] Фиг. 7 представляет собой блок-схему, иллюстрирующую устройство для кластеризации в соответствии с одним из примеров осуществления настоящего изобретения;

[0041] Фиг. 8 представляет собой блок-схему, иллюстрирующую терминальное устройство в соответствии с одним из примеров осуществления настоящего изобретения;

[0042] Фиг. 9 представляет собой блок-схему, иллюстрирующую сервер в соответствии с одним из примеров осуществления настоящего изобретения.

[0043] Конкретные варианты осуществления настоящего изобретения, проиллюстрированные на приложенных чертежах, будут более подробно рассмотрены ниже. Чертежи и их текстовое описание никоим образом не призваны ограничить объем настоящего изобретения, а предназначены для разъяснения, специалистам в данной области техники, замысла настоящего изобретения на примере конкретных вариантов его осуществления.

Подробное описание изобретения

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

[0045] Перед рассмотрением примеров осуществления настоящего изобретения сначала будет приведена краткая информация о расстоянии рангового порядка, для получения которого вычисляют расстояния (например, близость косинусов, эвклидово расстояние и т.п.) между объектами, и затем объекты повторно ранжируют в соответствии с величинами расстояний, в результате чего получают некоторую последовательность. Например, если имеются n объектов, соответственно, i₁, i₂, i₃, i₄, i₅, i_6…i_n, и если в качестве опорного выбран объект i₁, то вычисляют расстояние между каждым из остальных объектов и данным объектом i₁, и ранжируют объекты согласно величине расстояния, в результате чего получают последовательность О₁, проиллюстрированную на фиг. 1; если в качестве опорного выбран объект i₂, то вычисляют расстояние между каждым из остальных объектов и данным объектом i₂, в результате чего получают последовательность O₂, проиллюстрированную на фиг. 1.

[0046] Асимметричное расстояние D(i₁,i₂) рангового порядка между объектами i₁ и i₂ вычисляют в соответствии с порядковыми номерами смежных объектов в последовательности O₂, которые находятся между объектами i₁ и i₂ в последовательности О₁. А именно, в проиллюстрированном на фиг. 1 примере порядковые номера объектов, i₁, i₃, i₄, и i₂ в последовательности O₂ равны, соответственно, 5, 2, 4 и 0, и поэтому D(i₁,i₂) вычисляют в соответствии со следующей формулой:

[0047]

[0048] В формуле (1) O₂(i₁) представляет собой порядковый номер объекта i₁ в последовательности O₂, O₂(i₃) представляет собой порядковый номер объекта i₃ в последовательности O₂, O₂(i₄) представляет собой порядковый номер объекта i₄ в последовательности O₂, a O₂(i₂) представляет собой порядковый номер объекта i₂ в последовательности O₂.

[0049] Аналогичным образом вычисляют асимметричное расстояние D(i₂,i₁) между объектами i₁ и i₂. Затем вычисляют нормализованное расстояние D^R(i₁,i₂) рангового порядка между объектами i₁ и i₂ в соответствии с формулой (2):

[0050]

[0051] где D^R(i_l,i₂) представляет собой нормализованное расстояние

рангового порядка между объектами. Вычисление межклассового расстояния рангового порядка аналогично вычислению межобъектного расстояния рангового порядка, при этом: один из классов выбирают в качестве опорного и выполняют повторное ранжирование класса согласно расстоянию между классами. Межклассовое расстояние вычисляют в соответствии с формулой (3):

[0052]

[0053] В формуле (3) C_i и C_j представляют собой классы.

[0054] Межклассовое расстояние рангового порядка вычисляют в соответствии с формулой (4):

[0055]

[0056] В формуле (4) D(C_i,C_j) представляет собой асимметричное расстояние рангового порядка между классами C_i и C_j, D(C_j,C_i) представляет собой асимметричное расстояние рангового порядка между классами C_i, и C_j; O_Ci(C_j) представляет собой порядковый номер класса C_j в последовательности, для которой в качестве опорного был выбран класс C_i, а O_Cj(C_i) представляет собой порядковый номер класса C_i, в последовательности, для которой в качестве опорного был выбран класс C_j.

[0057] Нормализованное расстояние D^N(C_i,C_j) рангового порядка между классами вычисляют на основе расстояния D^R(C_i,C_j) между классами. При этом нормализованное межклассовое расстояние рангового порядка вычисляют в соответствии с формулой (5):

[0058]

[0059]

[0060] В формуле (5) d(C_i,C_j) представляет собой расстояние между классами C_i и C_j; |C_i| и |C_j| представляют собой количество объектов в классе; K - константа; f_a(k) представляет собой k-й смежный объект для объекта а; а φ(C_i,C_j) представляет собой среднее расстояние между K объектами, наиболее близкими к классам C_i или C_j.

[0061] Если объектами являются изображения человеческих лиц, то при помощи способа кластеризации, предложенного в настоящем изобретении, может быть выполнено группирование изображений одного и того же человека в один кластер. Характеристические признаки в изображении лица преобразуют в группу векторов. То есть, расстояниями между объектами являются расстояния между векторами. Очевидно, способ кластеризации, предложенный в настоящем изобретении, допускает также применение и к данным другого типа.

[0062] Фиг. 2 представляет собой блок-схему алгоритма, иллюстрирующую способ кластеризации в соответствии с одним из примеров осуществления настоящего изобретения. В соответствии с иллюстрацией фиг. 1 способ кластеризации применяют в терминальном устройстве, при этом он может включат в себя следующие шаги:

[0063] На шаге S110 выполняют итеративное слияние классов в соответствии с межклассовыми расстояниями рангового порядка.

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

[0065] В соответствии с иллюстрацией фиг. 3 шаг S110 может включать в себя следующие шаги.

[0066] На шаге S111 получают межклассовые расстояния рангового порядка и нормализованные межклассовые расстояния рангового порядка.

[0067] Если исходное количество изображений человеческих лиц было равно N, и каждое изображение было взято как отдельный класс, то исходное количество классов равно N. Также задают пороговое значение t расстояния и константу K. Для любых классов C_i и C_j расстояние D^R(C_i,C_j) рангового порядка между классами и нормализованное расстояние D^N(C_i,C_j) между классами получают при помощи вычислений в соответствии с приведенными выше формулами (1)-(5). Исходное количество классов равно N и следовательно, получают матрицу D^R(C_i,C_j) размера N×N и матрицу D^N(C_i,C_j) размера N×N. В матрице D^R(C_i,C_j) каждый из векторов представляет собой расстояние рангового порядка между соответствующими классами, например, вектор C_ij в этой матрице представляет собой расстояние рангового порядка между классами C_i и C_j, а вектор C_ij в матрице D^N(C_i,C_j) представляет собой нормализованное расстояние рангового порядка между классами C_i и C_j.

[0068] На шаге S112, если межклассовое расстояние рангового порядка меньше, чем пороговое значение расстояния, и нормализованное межклассовое расстояние рангового порядка меньше единицы, выполняют слияние классов.

[0069] D^R(C_i,C_j), меньшее, чем пороговое значение t расстояния, выбирают из матрицы D^R(C_i,C_j), и D^N(C_i,C_j), меньшее 1 выбирают из матрицы D^N(C_i,C_j). Если D^N(C_i,C_j)<t и D^N(C_i,C_j)<1, то делают вывод, что сходство между классом C_i и C_j является большим, то есть, классы C_i и C_j являются кандидатами на слияние, и затем выполняют слияние всех классов-кандидатов. Если D^R(C_i,C_j)≥t, это означает, что сходство между классами C_i и C_j является небольшим, а если D^N(C_i,C_j)≥1, - что степень расхождения между классами велика.

[0070] На шаге S120, вычисляют степень внутриклассового сходства, соответствующую классу после итеративного слияния, с использованием межобъектных расстояний внутри класса.

[0071] В одном из вариантов осуществления настоящего изобретения, в соответствии с иллюстрацией фиг. 4, шаг S120 может включать в себя следующие шаги.

[0072] На шаге S121 получают межобъектные расстояния внутри класса. Межобъектным расстоянием может быть близость косинусов, эвклидово расстояние, расстояние Жаккара и т.п.

[0073] Следует отметить, что в настоящем изобретении, когда межобъектное расстояние вычисляют с использованием близости косинусов cosθ, межобъектное расстояние определено как 1-cosθ. То есть, чем меньше межобъектное расстояние, тем больше сходство между объектами.

[0074] На шаге S122 вычисляют среднее расстояние по всем межобъектным расстояниям внутри класса и получают степень внутриклассового сходства для этого класса.

[0075] Если в классе имеются n объектов, то получают матрицу d расстояний размера n×n в соответствии с расстояниями между каждыми двумя из объектов внутри класса. В этой матрице каждый из векторов представляет собой расстояние между двумя соответствующими объектами. Например, вектор d_ij в матрице d представляет собой расстоянием между i-м объектом и j-м объектом внутри класса. В результате выполнения этого шага получают вычисленное среднее значения d_aver по всем векторам матрицы d.

[0076] В другом варианте осуществления настоящего изобретения, в соответствии с иллюстрацией фиг. 5, шаг S120 может включать в себя следующие шаги.

[0077] На шаге S123 получают соответствующие межобъектные расстояния внутри класса.

[0078] На шаге S124 вычисляют среднее расстояние по всем расстояниям между каждыми двумя объектами в соответствии с расстояниями между каждыми двумя объектами.

[0079] На шаге S125 среднее расстояние нормализуют, в результате чего получают степень внутриклассового сходства для данного класса.

[0080] Среднее расстояние d_aver нормализуют, то есть d_aver приводят к диапазону [dleft, dright], где dleft и dright - пороговые значения. Например, dleft может быть равным 0,6, a dright может быть равным 0,75. К примеру, нормализация может выполняться в соответствии с формулой (6):

[0081]

[0082] Например, если вычисленное среднее расстояние равно 0,5, то полученная после нормализации степень внутриклассового сходства будет равна 0,6; если среднее расстояние равно 0,65, то полученная после нормализации степень внутриклассового сходства будет равна 0,65; а если среднее расстояние равно 0,78, то полученная после нормализации степень внутриклассового сходства будет равна 0,75.

[0083] В вариантах осуществления настоящего изобретения степень внутриклассового сходства оценивают при помощи меры (1-cos). Соответственно, чем меньше степень внутриклассового сходства, тем более сходны объекты внутри этого класса и тем на большее сходство объектов внутри класса она указывает. Соответственно, степень внутриклассового сходства нормализуют, например, в диапазоне [0,6, 0,75] Когда степень внутриклассового сходства лежит в диапазоне нормализации, объекты в этом классе группируют согласно степени внутриклассового сходства. Когда степень внутриклассового сходства лежит вне диапазона нормализации, объекты внутри класса группируют в соответствии с пороговым значением, в результате чего класс, имеющий высокую степень внутриклассового сходства (а именно, высокую степень расхождения) может быть соответствующим образом разделен на множество классов, благодаря чему исключается разделение класса с малой степенью внутриклассового сходства на слишком большое количество классов.

[0084] На шаге S130 для каждого класса, полученного итеративным слиянием, объекты внутри класса, расстояние между которыми меньше, чем степень внутриклассового сходства, группируют в новый класс и обновляют количество классов.

[0085] Для каждого класса после итеративного слияния, в соответствии с расстояниями рангового порядка, класс разделяют согласно межобъектным расстояниям внутри класса и степени внутриклассового сходства. В этот момент одна итерация завершается, и затем выполняют шаг S140.

[0086] В одном из вариантов осуществления настоящего изобретения, в соответствии с иллюстрацией фиг. 6, шаг S130 может включать в себя следующие шаги.

[0087] На шаге S131 объекты внутри класса, расстояние между которыми меньше степени внутриклассового сходства, помечают с использованием метки связи.

[0088] Для каждого объекта внутри класса проверяют, является ли расстояние между этим объектом и каждым из остальных объектов класса, по матрице межобъектных расстояний внутри класса, меньшим, чем степень внутриклассового сходства, и если межобъектное расстояние меньше, чем степень внутриклассового сходства, выполняют указание на то, что сходство между объектами является большим и объекты могут быть сгруппированы в один класс. В этот момент двум объектам, соответствующим этому расстоянию, может быть присвоена метка связи. Например, если расстояние d_ij между двумя изображениями человеческих лиц меньше, чем степень внутриклассового сходства, то i-й объект и j-й объект связывают.

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

[0090] На шаге S132 выявляют связанные элементы внутри класса в соответствии с метками связи.

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

[0092] На шаге S133 класс разделяют на новые классы в соответствии с этими связанными элементами и обновляют количество классов.

[0093] Объекты, соответствующие каждому из связанных элементов группируют в отдельный новый класс, то есть, большой класс разделяют на новые классы, количество которых равно количеству связанных элементов, содержащихся в этом классе, и соответствующим образом увеличивают количество классов. За счет разделения связанных элементов, объекты, не принадлежащие классу, могут быть удалены из кластера, то есть обеспечивается удаление из кластера инородных объектов.

[0094] На шаге S140 определяют, является ли количество классов после обновления меньшим, чем количество классов до обновления. Если это так, то в ходе выполнения процедуры выполняют возврат к шагу S110, а если это не так, то в ходе выполнения процедуры выполняют переход к шагу S150.

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

[0096] На одной итерации выполняют слияние классов на основе расстояний регулировки мощности сигнала маршрутизатора, а также выделение новых классов. Допустим, что количество классов до слияния равно 6, а после слияния на основе расстояний рангового порядка оно становится равным 4, и затем, наконец, эти 4 класса, полученные после слияния, разделяют на 5 классов. В этом случае количество классов после обновления равно 5, а количество классов до обновления равно 6, значит, количество классов после обновления меньше, чем количество классов до обновления, и следовательно, выполняют возврат и продолжают выполнять процедуру на еще одной итерации.

[0097] Если количество классов после обновления меньше, чем количество классов до обновления, это указывает на большую степень внутриклассового расхождения, то есть, объекты внутри класса не достаточно сходны, и могут присутствовать инородные объекты. Соответственно, над разделенными классами должно быть повторно выполнено итеративное слияние, и затем классы разделяют, до тех пор, пока количество классов после обновления будет не меньшим, чем количество классов до обновления.

[0098] Когда количество классов до и после обновления становится одинаковым, на шаге S150 получают результат кластеризации, при этом результат кластеризации включает в себя один или более классов, содержащих множество объектов, и один или более классов, содержащих одиночные объекты.

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

[00100] При помощи способа кластеризации, предложенного в данном варианте осуществления настоящего изобретения, после слияния классов с использованием расстояний рангового порядка измеряют сходство между каждыми двумя объектами с использованием межобъектных расстояний (например, близости 1-cos, эвклидова расстояния и т.п.) внутри класса, и объекты с меньшим сходством (большим несходством) удаляют из этого класса (выделяют в новый класс), то есть из класса удаляют точку шума, благодаря чему точность кластеризации может быть повышена. В частности, появляется возможность повысить точность результатов кластеризации в случае, когда набор данных является сравнительно большим, а количество объектов одного класса сравнительно малым.

[00101] Результативность способа кластеризации в соответствии с настоящим изобретением проиллюстрирована ниже с помощью конкретных опытных данных, приведенных в таблице 1.

[00102]

[00103] В таблице 1 Р - точность результата кластеризации, R - коэффициент чувствительности, a CR - среднее количество изображений человеческого лица в каждом классе в результате кластеризации.

[00104] Из таблицы 1 можно видеть, что в первом наборе общее количество человеческих лиц, содержащихся среди всех изображений равно 2291, при этом среди этих изображений имеется 562 различных человека, поэтому в среднем каждый человек соответствует 4,07 изображениям человеческих лиц. То есть среди всех изображений одному человеку в среднем принадлежит 4,07 изображений человеческих лиц. Соответственно, в результате кластеризации с использованием только расстояний рангового порядка, в соответствии с текущим уровнем техники, точность составляет 86,1%, а точность кластеризации для способа кластеризации в соответствии с настоящим изобретением составляет 99,1%, что значительно выше, чем точность кластеризации с использованием только расстояний рангового порядка. Во втором и третьем наборе точность способа кластеризации в соответствии с настоящим изобретением также выше, чем точность кластеризации с использованием только расстояний рангового порядка.

[00105] В соответствии с рассмотренными вариантами осуществления способа кластеризации в настоящем изобретении предложено устройство для кластеризации.

[00106] Фиг. 7 представляет собой блок-схему, иллюстрирующую устройство для кластеризации в соответствии с одним из примеров осуществления настоящего изобретения. В соответствии с иллюстрацией фиг.7 устройство включает в себя блок 100 итеративного слияния, блок 200 получения, блок 300 разделения и блок 400 определения.

[00107] Блок 100 итеративного слияния сконфигурирован для итеративного слияния классов в соответствии с расстояниями рангового порядка.

[00108] В одном из вариантов осуществления настоящего изобретения блок 100 итеративного слияния может также включать в себя третий подблок получения и подблок слияния; при этом

[001