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

1. Способ кластеризации, включающий:
итеративное слияние классов в соответствии с межклассовыми расстояниями рангового порядка;
получение степени внутриклассового сходства, соответствующей классу после итеративного слияния, с использованием межобъектных расстояний внутри класса;
для каждого класса, полученного итеративным слиянием, группирование объектов в классе, расстояние между которыми меньше, чем упомянутая степень внутриклассового сходства, в новый класс, и обновление количества классов;
если количество классов после обновления является меньшим, чем количество классов до обновления, возврат к шагу выполнения итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка до тех пор, пока количество классов до и после обновления не будет одинаковым, в результате чего получают результат кластеризации, при этом упомянутый результат кластеризации включает в себя один или более классов, содержащих множество объектов, и один или более классов, содержащих одиночные объекты.
2. Способ по п. 1, отличающийся тем, что получение степени внутриклассового сходства, соответствующей классу после итеративного слияния, с использованием межобъектных расстояний внутри класса, выполняют следующим образом:
получают соответствующие межобъектные расстояния внутри класса; и
вычисляют среднее расстояние по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса, в результате чего получают степень внутриклассового сходства данного класса.
3. Способ по п. 1, отличающийся тем, что получение степени внутриклассового сходства, соответствующей классу после итеративного слияния, с использованием межобъектных расстояний внутри класса, выполняют следующим образом:
получают соответствующие межобъектные расстояния внутри класса;
вычисляют среднее расстояние по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса; и
нормализуют это среднее расстояние, в результате чего получают степень внутриклассового сходства данного класса.
4. Способ по п. 2 или 3, отличающийся тем, что для каждого класса, полученного итеративным слиянием, группирование объектов в классе, расстояние между которыми меньше, чем степень внутриклассового сходства, в новый класс и обновление количества классов выполняют следующим образом:
помечают объекты внутри класса, расстояние между которыми меньше, чем упомянутая степень внутриклассового сходства, с использованием метки связи;
выявляют связанные элементы внутри класса в соответствии с метками связи;
разделяют класс на новые классы в соответствии с упомянутыми связанными элементами и обновляют количество классов.
5. Способ по п. 1, отличающийся тем, что выполнение итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка выполняют следующим образом:
получают межклассовые расстояния рангового порядка и получают нормализованные межклассовые расстояния рангового порядка; и
выполняют слияние классов, если межклассовое расстояние рангового порядка меньше, чем пороговое значение расстояния, и нормализованное межклассовое расстояние рангового порядка меньше 1.
6. Устройство для кластеризации, включающее:
блок итеративного слияния, сконфигурированный для итеративного слияния классов в соответствии с расстояниями рангового порядка;
блок получения, сконфигурированный для получения степени внутриклассового сходства, соответствующей классу после итеративного слияния, с использованием межобъектных расстояний внутри класса;
блок разделения, сконфигурированный, для каждого класса, полученного итеративным слиянием, для группирования объектов внутри класса, расстояние между которыми меньше, чем степень внутриклассового сходства, в новый класс и для обновления количества классов; и
блок определения, сконфигурированный, если количество классов после обновления меньше, чем количество классов до обновления, для управления упомянутым блоком итеративного слияния с целью итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка до тех пор, пока количество классов до и после обновления не станет одинаковым, в результате чего получают результат кластеризации, при этом упомянутый результат кластеризации включает в себя один или более классов, содержащих множество объектов, и один или более классов, содержащих одиночные объекты.
7. Устройство по п. 6, отличающееся тем, что упомянутый блок получения включает в себя:
первый подблок получения, сконфигурированный для получения межобъектных расстояний внутри класса; и
первый подблок вычисления, сконфигурированный для вычисления среднего расстояния по всем межобъектным расстояниям внутри класса, в результате чего получают степень внутриклассового сходства данного класса.
8. Устройство по п. 6, отличающееся тем, что упомянутый блок получения включает в себя:
второй подблок получения, сконфигурированный для получения соответствующих межобъектных расстояний внутри класса;
второй подблок вычисления, сконфигурированный для вычисления среднего расстояния по всем межобъектным расстояниям внутри класса в соответствии с межобъектными расстояниями внутри класса; и
подблок нормализации, сконфигурированный для нормализации упомянутого среднего расстояния, в результате чего получают степень внутриклассового сходства данного класса.
9. Устройство по п. 7 или 8, отличающееся тем, что упомянутый блок разделения включает в себя:
первый подблок определения, сконфигурированный для определения, является ли межобъектное расстояние внутри класса меньшим, чем степень внутриклассового сходства;
подблок пометки, сконфигурированный для пометки, если межобъектное расстояние внутри класса меньше, чем упомянутая степень внутриклассового сходства, объектов, в соответствии с межобъектным расстоянием внутри класса, с использованием метки связи;
подблок выявления, сконфигурированный для выявления связанных элементов внутри класса в соответствии с упомянутыми метками связи; и
подблок разделения, сконфигурированный для разделения класса на новые классы в соответствии с упомянутыми связанными элементами, и для обновления количества классов.
10. Устройство по п. 6, отличающееся тем, что упомянутый блок итеративного слияния включает в себя:
третий подблок получения, сконфигурированный для получения межклассовых расстояний рангового порядка и для получения нормализованных межклассовых расстояний рангового порядка; и
подблок слияния, сконфигурированный для слияния классов, имеющих межклассовое расстояние рангового порядка, меньшее, чем пороговое значение расстояния, и нормализованное расстояние рангового порядка, меньшее 1.
11. Терминальное устройство, включающее:
процессор; и
память, сконфигурированную для хранения инструкций, исполняемых упомянутым процессором;
при этом упомянутый процессор сконфигурирован для:
итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка;
получения степени внутриклассового сходства, соответствующей классу после итеративного слияния, с использованием межобъектных расстояний внутри класса;
для каждого класса, полученного итеративным слиянием, для группирования объектов в классе, расстояние между которыми меньше, чем упомянутая степень внутриклассового сходства, в новый класс, и обновления количества классов;
если количество классов после обновления является меньшим, чем количество классов до обновления, для возврата к шагу выполнения итеративного слияния классов в соответствии с межклассовыми расстояниями рангового порядка до тех пор, пока количество классов до и после обновления не будет одинаковым, и
для получения результата кластеризации, когда количество классов до и после обновления является одинаковым, при этом упомянутый результат кластеризации включает в себя одни или более классов, содержащих множество объектов, и один или более классов, содержащих одиночные объекты.