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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[0053] фиг. 4 представляет собой блок-схему алгоритма с иллюстрацией получения весового коэффициента в соответствии с одним из примеров осуществления настоящего изобретения;

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

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

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

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

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

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

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

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

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

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

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

[0064] В одном из вариантов осуществления настоящего изобретения, в соответствии с иллюстрацией фиг. 2, шаг S110 может включать описанные ниже шаги S111-S113.

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

[0066] В одном из вариантов осуществления настоящего изобретения, в соответствии с иллюстрацией фиг. 3, шаг S111 может включать следующие шаги S1111-S1113.

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

[0068] Допустим, что первый класс обозначен за А, а второй класс обозначен за В. Вычисляют взвешенное расстояние между классом А и классом В. Сначала вычисляют расстояния d(A_i, В) между любым из объектов А_i в классе А и всеми объектами в классе В, и затем получают наибольшее расстояние сходства между объектом A_i и всеми объектами в классе В. В данном варианте осуществления настоящего изобретения используется близость косинусов. То есть, межобъектное сходство, соответствующее максимальной близости косинусов, d_max(A_i,В), является наибольшим.

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

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

[0071] Например, в случае распознавания лиц, диапазон близости косинусов cosθ для двух изображений лица может быть равен [0, 1] по признакам высокой размерности, и при этом согласно статистическим данным по большому количеству изображений лиц, делают вывод, что если близость косинусов лежит в диапазоне [0,45, 1], вероятность того, что два объекта являются одним и тем же человеком, собственно, составляет 98%; если близость косинусов лежит в диапазоне [0.35, 0.45], вероятность того, что два объекта являются одним и тем же человеком, собственно, составляет 70%; если близость косинусов лежит в диапазоне [0,25, 0,35], вероятность того, что два объекта являются одним и тем же человеком, собственно, составляет 40%; если близость косинусов лежит в диапазоне [0,15, 0,25], вероятность того, что два объекта являются одним и тем же человеком, собственно, составляет 10%; и если близость косинусов лежит в диапазоне [0, 0, 15], вероятность того, что два объекта являются одним и тем же человеком, собственно, составляет 0,1%

[0072] Согласно приведенным выше статистическим результатам соотношение между весовым коэффициентом и близостью косинусов может быть задано с помощью следующей формулы (1):

[0073]

[0074] Формула (1) является отношением соответствия между близостью косинусов и вероятностью того, что два объекта являются одним и тем же человеком. Согласно соотношению между расстояниями и соответствующими вероятностями могут выводиться заключения и по другим типам расстояний, которые в настоящем документе перечислены не будут.

[0075] На шаге S200 определяют отношение отображения между межобъектным расстоянием и весовым коэффициентом согласно упомянутому отношению соответствия, при этом весовой коэффициент определяют в соответствии с упомянутой вероятностью.

[0076] Получают межобъектное расстояние и затем определяют, в каком из диапазонов формулы (1) это межобъектное расстояние находится. Наконец, в соответствии с формулой (1) определяют отношение отображения между межобъектным расстоянием и весовым коэффициентом. Весовой коэффициент, полученный описанным выше методом на основе d_max(A_i,В) будет равен W(d_max(A_i,B))

[0077] На шаге S1112 получают минимальное взвешенное расстояние (максимальную близость косинусов) между объектом в первом классе и всеми объектами второго класса в соответствии с произведением наибольшего расстояния сходства и соответствующего первого весового коэффициента.

[0078] Минимальное взвешенное расстояние ϕ_max(A_i,В) между объектом А_i и классом В получают согласно формуле (2):

[0079]

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

[0081] Допустим, что расстояние между объектом Ai в классе А и объектом b является наибольшим, тогда среднее взвешенное расстояние ϕ_avg(A_i,B) между объектом Ai и остальными объектами, за исключением объекта b в классе В, получают согласно формуле (3):

[0082]

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

[0084] На основе минимального взвешенного расстояния ϕ_max(A_i,В) и среднего взвешенного расстояния ϕ_avg(A_i,B) между объектом A_i и классом В, взвешенное расстояние ϕ (A_i,В) между объектом A_i и классом В получают согласно формуле (4):

[0085]

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

[0087] Первое однонаправленное взвешенное расстояние S(A, В) между классом А и классом D получают согласно формуле (5):

[0088]

[0089] В формуле (5) W(d_max(A_i,B)) обозначает весовой коэффициент, соответствующий максимальной близости косинусов (минимальному расстоянию) d_max(A_i,В) между объектом A_i в классе А и всеми объектами в классе В.

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

[0091] Вычисляют второе однонаправленное взвешенного расстояния S(B, А) между классом В и классом, что аналогично вычислению первого однонаправленного взвешенного расстояния между классом А и В и не будет описано повторно.

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

[0093] Взвешенное расстояние Н(А, В) между классом А и классом В вычисляют согласно формуле (6):

[0094]

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

[0096] Заранее заданное пороговое значение может быть выбрано в соответствии с типами данных различных объектов, или может быть выбрано в соответствии с типом вычисляемого межобъектного расстояния (например, близость косинусов, евклидово расстояние и т.п.) Например, объектами могут быть изображения лиц, и при этом межобъектным расстоянием может быть близость косинусов. В этом случае пороговое значение расстояния может быть выбрано равным 0,3-0,35.

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

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

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

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

[00101] При объединении двух классов, на шаге S130, соответствующим образом объединяют все классы, которые могут быть объединены.

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

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

[00104] На шаге S150 получают результат кластеризации.

[00105] Сходство объектов, объединенных в одном классе, является высоким, а их несходство - низким. Если в качестве объектов выбраны изображения лиц, то изображения лица, помещенного в один класс, будут изображениями одного и того же человека.

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

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

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

[00109] Блок 100 получения может включать первый подблок получения, второй подблок получения, третий подблок получения и четвертый подблок получения.

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

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

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

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

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

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

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

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

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

[00119] Четвертый подблок получения сконфигурирован для получения взвешенного расстояния между первым классом и вторым классом согласно упомянутым первому однонаправленному взвешенному расстоянию и второму однонаправленному взвешенному расстоянию.

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

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

[00