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

Изобретение относится к способам кластеризации данных, в частности к кластеризации изображений. Техническим результатом является повышение точности результатов кластеризации. В способе кластеризации согласно межклассовым расстояниям рангового порядка выполняют слияние классов, удовлетворяющих определенному условию, в результате чего сокращают количество классов. В соответствии с межобъектными расстояниями внутри класса вычисляют степень внутриклассового сходства. Степень внутриклассового сходства представляет собой среднее расстояние или нормализованное среднее расстояние по всем межобъектным расстояниям внутри класса. Объекты внутри класса, расстояние между которыми меньше степени внутриклассового сходства, выделяют в новый класс до тех пор, пока все классы не будут разделены. Выполняют итеративное слияние и разделение классов до тех пор, пока никакой из классов не сможет быть разделен. Для каждого полученного класса удаляют объекты, для которых межобъектное расстояние до любого другого объекта внутри одного и того же класса не меньше степени внутриклассового сходства, из числа объектов внутри того же класса, для которых межобъектное расстояние до любого другого объекта внутри того же класса меньше степени внутриклассового сходства. 3 н. и 8 з.п. ф-лы, 9 ил., 1 табл.

 

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

[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 объектов, соответственно, i1, i2, i3, i4, i5, i6…in, и если в качестве опорного выбран объект i1, то вычисляют расстояние между каждым из остальных объектов и данным объектом i1, и ранжируют объекты согласно величине расстояния, в результате чего получают последовательность О1, проиллюстрированную на фиг. 1; если в качестве опорного выбран объект i2, то вычисляют расстояние между каждым из остальных объектов и данным объектом i2, в результате чего получают последовательность O2, проиллюстрированную на фиг. 1.

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

[0047]

[0048] В формуле (1) O2(i1) представляет собой порядковый номер объекта i1 в последовательности O2, O2(i3) представляет собой порядковый номер объекта i3 в последовательности O2, O2(i4) представляет собой порядковый номер объекта i4 в последовательности O2, a O2(i2) представляет собой порядковый номер объекта i2 в последовательности O2.

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

[0050]

[0051] где DR(il,i2) представляет собой нормализованное расстояние

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

[0052]

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

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

[0055]

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

[0057] Нормализованное расстояние DN(Ci,Cj) рангового порядка между классами вычисляют на основе расстояния DR(Ci,Cj) между классами. При этом нормализованное межклассовое расстояние рангового порядка вычисляют в соответствии с формулой (5):

[0058]

[0059]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[0075] Если в классе имеются n объектов, то получают матрицу d расстояний размера n×n в соответствии с расстояниями между каждыми двумя из объектов внутри класса. В этой матрице каждый из векторов представляет собой расстояние между двумя соответствующими объектами. Например, вектор dij в матрице 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] Для каждого объекта внутри класса проверяют, является ли расстояние между этим объектом и каждым из остальных объектов класса, по матрице межобъектных расстояний внутри класса, меньшим, чем степень внутриклассового сходства, и если межобъектное расстояние меньше, чем степень внутриклассового сходства, выполняют указание на то, что сходство между объектами является большим и объекты могут быть сгруппированы в один класс. В этот момент двум объектам, соответствующим этому расстоянию, может быть присвоена метка связи. Например, если расстояние dij между двумя изображениями человеческих лиц меньше, чем степень внутриклассового сходства, то 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 итеративного слияния может также включать в себя третий подблок получения и подблок слияния; при этом

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

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

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

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

[00113] Первый подблок получения сконфигурирован для получения межобъектных расстояний внутри класса; и

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

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

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

[00117] второй подблок получения сконфигурирован для вычисления среднего расстояния по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса; и

[00118] подблок нормализации сконфигурирован для нормализации среднего расстояния, в результате чего получают степень внутриклассового сходства данного класса.

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

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

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

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

[00123] Подблок выявления сконфигурирован для выявления связанных элементов внутри класса в соответствии с метками связи.

[00124] Подблок разделения сконфигурирован для разделения класса на новые классы в соответствии с этими связанными элементами и для обновления количества классов.

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

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

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

[00128] Фиг. 8 представляет собой блок-схему, иллюстрирующую терминальное устройство 800 для кластеризации в соответствии с одним из примеров осуществления настоящего изобретения. Например, устройство 800 может представлять собой мобильный телефон, компьютер, терминал цифрового вещания, устройство приема и передачи сообщений, игровую приставку, планшетное устройство, медицинское оборудование, тренажерное оборудование, карманный персональный компьютер и т.п.

[00129] В соответствии с иллюстрацией фиг.8 устройство 800 может включать в себя один или более следующих компонентов: процессорный компонент 802, память 804, компонент 806 электропитания, мультимедийный компонент 808, аудиокомпонент 810, интерфейс 812 ввода-вывода (input/output, I/O), измерительный компонент 814 и компонент 816 связи.

[00130] Процессорный компонент 802, как правило, осуществляет общее управление функционированием терминального устройства 800, например, операциями, связанными с отображением, телефонными вызовами, обменом данными, работой с камерой и операциями записи. Процессорный компонент 802 может включать в себя один или более процессоров 820, исполняющих инструкции с целью выполнения всех шагов описанных выше способов или части этих шагов. Также, процессорный компонент 802 может включать в себя один или более модулей, обеспечивающих взаимодействие между процессорным компонентом 802 и другими компонентами. Например, процессорный компонент 802 может включать в себя мультимедийный модуль, обеспечивающий взаимодействие между мультимедийным компонентом 808 и процессорным компонентом 802.

[00131] Память 804 сконфигурирована для хранения различных типов данных с целью поддержки функционирования устройства 800. Примерами подобных данных могут служить инструкции любых приложений или методов, исполняемых на терминальном устройстве 800, контактные данные, данные телефонной книги, сообщения, изображения, видеоданные и т.п. Память 804 может быть реализована с использованием энергозависимых или энергонезависимых устройств любого типа, а также их комбинаций, например, статической памятью с произвольным доступом (static random access memory, SRAM), электрически перепрограммируемой памяти в режиме «только для чтения» (erasable programmable read-only memory, EPROM), программируемой памяти в режиме «только для чтения» (programmable read-only memory, PROM), памяти в режиме «только для чтения», магнитной памяти, флэш-памяти, магнитного или оптического диска.

[00132] Компонент 806 электропитания обеспечивает электропитание различных компонентов терминального устройства 800. Компонент 806 электропитания может включать в себя систему управления электропитанием, один или более источников питания, а также любые другие компоненты, связанные с производством, управлением и распределением электрической энергии в терминалом устройстве 800.

[00133] Мультимедийный компонент 808 включает в себя экран, который обеспечивает интерфейс вывода между терминальным устройством 800 и пользователем. В некоторых из вариантов осуществления настоящего изобретения экран может включать в себя дисплей на жидких кристаллах (liquid crystal display, LCD) и сенсорную панель (touch panel, TP). Если экран включает в себя сенсорную панель, то в этом случае экран может быть реализован как сенсорный экран, принимающий сигналы ввода от пользователя. Сенсорная панель включает в себя один или более датчиков касания, предназначенных для регистрации касаний, скольжений и других жестов на сенсорной панели. Датчики касания могут не только регистрировать границы операций касания или скольжения, но также измерять период времени и величину давления, связанные с этими операциями. В некоторых вариантах осуществления настоящего изобретения мультимедийный компонент 808 включает в себя фронтальную камеру и/или тыловую камеру. Фронтальная камера и тыловая камера могут принимать внешние мультимедийные данные, когда устройство 800 находится в определенном режиме работы, например, в режиме фотографирования или в режиме видеосъемки. Как фронтальная камера, так и тыловая камера могут представлять собой фиксированные системы оптических линз или иметь функциональность фокусировки и оптического зуммирования.

[00134] Аудиокомпонент 810 сконфигурирован для вывода и/или ввода аудиосигналов. Например, аудиокомпонент 810 включает в себя микрофон ("MIC"), сконфигурированный для приема внешнего аудиосигнала, когда терминальное устройство 800 находится в определенном режиме работы, например, в режиме вызова, в режиме записи или в режиме распознавания голоса. Принятые аудиосигналы могут затем быть сохранены в памяти 804 или переданы при помощи компонента 816 связи. В некоторых из вариантов осуществления настоящего изобретения аудиокомпонент 810 включает в себя также громкоговоритель для вывода аудиосигналов.

[00135] Интерфейс 812 ввода/вывода обеспечивает интерфейс между процессорным компонентом 802 и модулями периферийных интерфейсов, например, клавиатуры, поворотного-нажимного переключателя («колеса»), кнопок и т.п. Кнопки могут включать в себя, без ограничения перечисленным, «домашнюю» кнопку, кнопку громкости, кнопку «пуск» или кнопку блокировки.

[00136] Измерительный компонент 814 включает в себя один или более датчиков, обеспечивающих оценку состояния различных элементов терминального устройства 800. Например, измерительный компонент 814 может определять состояние устройства 800: «открыто» или «закрыто», относительное расположение компонентов, например, дисплея и клавиатуры терминального устройства 800, изменение положения терминального устройства 800 или одного из компонентов устройства 800, присутствие или отсутствие контакта пользователя с терминальным устройством 800, ориентацию или ускорение/замедление терминального устройства 800 и изменение температуры терминального устройства 800. Измерительный компонент 814 может включать в себя датчик близости, сконфигурированный для обнаружения присутствия приближенных объектов без физического контакта с ними. Измерительный компонент 814 может также включать в себя светочувствительный датчик, например, датчик изображений CMOS или CCD, для использования в приложениях формирования изображений. В некоторых из вариантов осуществления настоящего изобретения измерительный компонент 814 может также включать в себя акселерометрический датчик, гироскопический датчик, магнитный датчик, датчик давления или датчик температуры.

[00137] Компонент 816 связи сконфигурирован для обеспечения связи, проводной или беспроводной, между терминальным устройством 800 и другими устройствами. Терминальное устройство 800 может осуществлять доступ к беспроводной сети, основанной на таких стандартах связи, как WiFi, 2G или 3G, или их комбинации. В одном из примеров осуществления настоящего изобретения компонент 816 связи принимает широковещательный сигнал или соответствующую широковещательную информацию от внешней широковещательной системы управления по широковещательному каналу. В одном из примеров осуществления настоящего изобретения компонент 816 связи включает в себя также модуль ближней бесконтактной связи (near field communication, NFC) для обеспечения связи в ближней зоне. Например, NFC-модуль может быть реализован на базе технологии радиочастотной идентификации (radio frequency identification, RFID), технологии ассоциации передачи данных в инфракрасном диапазоне (infrared data association, IrDA), технологии сверхширокой полосы пропускания (ultra-wideband, UWB), технологии Bluetooth (ВТ) или других технологий.

[00138] В примерах осуществления настоящего изобретения терминальное устройство 800 может быть реализовано с использованием одной или более заказных интегральных схем (ASIC), цифровых сигнальных процессоров (DSP), цифровых устройств обработки сигналов (digital signal processing devices, DSPD), программируемых логических устройств (programmable logic devices, PLD), электрически программируемых вентильных матриц (field programmable gate arrays, FPGA), процессорах, контроллерах, микроконтроллерах, микропроцессорах или других электронных блоках, предназначенных для исполнения описанных выше способов.

[00139] В примерах осуществления настоящего изобретения предложен также машиночитаемый носитель для хранения данных, включающий в себя инструкции, например, содержащиеся в памяти 804 и исполняемые процессором 820 в терминалом устройстве 800 с целью выполнения описанных выше способов. К примеру, постоянный машиночитаемый носитель для хранения данных может представлять собой память ROM, RAM, CD-ROM, магнитную ленту, гибкий диск, оптическое запоминающее устройство для хранения данных и т.п.

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

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

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

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

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

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

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

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

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

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

[00150] Фиг. 9 представляет собой блок-схему, иллюстрирующую сервер в соответствии с одним из вариантов осуществления настоящего изобретения. К примеру, сервер 1900 может быть значительно отличающимся по конфигурации или функциональности, и может включать в себя один или более центральных процессорных блоков (central processing units, CPU) 1922 (например, один или более процессоров) и память 1932, один или боле носителей 1930 (например, одно или более запоминающих устройств большой емкости) для хранения прикладных программ 1942 и данных 1944. При этом память 1932 и носитель 1930 могут представлять собой устройство временного или постоянного хранения. Программы, хранимые на носителе 1930 могут включать в себя один или более модулей (не показаны на чертежах), каждый из которых соответствует набору инструкций в терминальном устройстве. При этом центральный процессорный блок 1922 сконфигурирован для связи с носителей 1930 и для исполнения набора инструкций, хранимых на носителей 1930, на сервер 1900.

[00151] Сервер 1900 может также включать один или более компонентов 1926 электропитания, один или более проводных или беспроводных сетевых интерфейсов 1950, а также один или более интерфейсов 1958 ввода-вывода, одну или более клавиатур и/или одну или более операционных систем 1941, например, Windows Server™, Mac OS X™, Unix™, Linux™, FreeBSD™ или аналогичные операционные системы.

[00152] В примерах осуществления настоящего изобретения предложен также машиночитаемый носитель для хранения данных, включающий в себя инструкции, например, содержащиеся в памяти 1932 или в носителе 1930 и исполняемые процессором 1922 в терминальном устройстве 1922 с целью выполнения описанных выше способов. К примеру, постоянный машиночитаемый носитель для хранения данных может представлять собой память ROM, RAM, CD-ROM, магнитную ленту, гибкий диск, оптическое запоминающее устройство для хранения данных и т.п.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

получают соответствующие межобъектные расстояния внутри класса; и

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

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

получают соответствующие межобъектные расстояния внутри класса;

вычисляют среднее расстояние по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса; и

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

4. Способ по п. 2 или 3, отличающийся тем, что для каждого класса, полученного итеративным слиянием, группирование объектов в классе, межобъектное расстояние между которыми меньше, чем степень внутриклассового сходства, в новый класс и обновление количества классов выполняют следующим образом:

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

выявляют связанные элементы внутри класса в соответствии с метками связи;

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

5. Способ по п. 1, отличающийся тем, что выполнение итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка выполняют следующим образом:

получают межклассовые расстояния рангового порядка и получают нормализованные межклассовые расстояния рангового порядка; и

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

6. Устройство для кластеризации, включающее:

блок итеративного слияния, сконфигурированный для итеративного слияния классов в соответствии с расстояниями рангового порядка;

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

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

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

7. Устройство по п. 6, отличающееся тем, что упомянутый блок получения включает в себя:

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

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

8. Устройство по п. 6, отличающееся тем, что упомянутый блок получения включает в себя:

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

второй подблок вычисления, сконфигурированный для вычисления среднего расстояния по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса; и

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

9. Устройство по п. 7 или 8, отличающееся тем, что упомянутый блок разделения включает в себя:

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

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

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

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

10. Устройство по п. 6, отличающееся тем, что упомянутый блок итеративного слияния включает в себя:

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

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

11. Терминальное устройство, включающее:

процессор; и

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

при этом упомянутый процессор сконфигурирован для:

итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка;

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

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

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

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



 

Похожие патенты:

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

Изобретение относится к области обработки изображений. Технический результат – обеспечение устранения ручной установки параметров косметической обработки.

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

Группа изобретений относится к области систем "умного дома" и касается способов уборки мусора и устройств для уборки мусора. Устройство контроля получает данные контроля контролируемой области.

Изобретение относится к области распознавания конфиденциальной фотографии. Технический результат – расширение арсенала технических средств для распознавания конфиденциальной фотографии.

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

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

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

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

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

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

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

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

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

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

Изобретение относится к способам организации хранения документов для минимизации их объема при хранении. Техническим результатом является снижение объема хранения электронных документов с квазиструктурированным информационным наполнением.

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

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

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

Изобретение относится к области распространения контента в сети. Технический результат – защищенное распространение файла одному или нескольким пользовательским устройствам. Способ управления использованием файла в пользовательском устройстве включает: передачу системе пользовательским устройством информации для аутентификации, которая содержит идентификатор пользовательского устройства и по меньшей мере один идентификатор пользователя устройства, позволяющей таким образом аутентификацию указанного пользовательского устройства, загрузку пользовательским устройством файла из системы после успешной аутентификации системой, посредством чего указанный загруженный файл связан с указанным клиентским приложением с возможностью защищенного доступа, обеспечение посредством указанного клиентского приложения на пользовательском устройстве по меньшей мере одному идентифицированному пользователю, связанному с указанным пользовательским устройством, возможности защищенного доступа к указанному файлу в течение времени, когда указанное пользовательское устройство отсоединено от указанной системы, посредством чего по меньшей мере один указанный идентифицированный пользователь является автономным пользователем, а защищенный доступ включает обеспечение клиентскому приложению возможности доступа к указанному файлу, когда указанный автономный пользователь аутентифицирован с указанным клиентским приложением, предотвращение пользовательским устройством изменения файла, печати файла и открытия файла вне клиентского приложения, сохранение пользовательским устройством комментариев к файлу в локальной области памяти отдельно от файла, передачу системе пользовательским устройством по меньшей мере части комментариев, и удаление пользовательским устройством файла из пользовательского устройства по команде системы. 4 н. и 16 з.п. ф-лы, 12 ил.
Наверх