СПОСОБ И УСТРОЙСТВО ДЛЯ КЛАССИФИКАЦИИ ОБЪЕКТА Российский патент 2023 года по МПК G06F16/20 G06N20/00 

Область техники, к которой относится изобретение

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

Уровень техники

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

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

Среди подобных способов известен, например, способ классификации текста, раскрытый в CN 109993216 B (11.05.2021), в котором раскладывают текст на слова; извлекают слова, представляющие информацию о признаках текста; кодируют текст в характеристический вектор строки с использованием извлеченного слова; вычисляют сходство между упомянутым характеристическим вектором строки и характеристическим вектором строки примера из модели kNN с помощью модели kNN; определяют классификационную метку упомянутого характеристического вектора строки в соответствии со степенью схожести и классификационной меткой, соответствующих характеристическому вектору строки примера; и выводят классификационную метку.

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

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

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

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

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

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

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

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

В одном из вариантов осуществления граф состоит из множества вершин и ребер;

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

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

причем поиск объекта, предполагаемого в качестве наиболее близкого к целевому объекту, содержит этапы, на которых:

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

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

В одном из вариантов осуществления граф представляет собой граф NSW (граф «мир тесен» с возможностью навигации) или HNSW (иерархический граф «мир тесен» с возможностью навигации).

В одном из вариантов осуществления процесс жадного поиска содержит этапы, на которых:

определяют текущую вершину для поиска;

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

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

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

В одном из вариантов осуществления граф представляет собой граф NSW;

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

В одном из вариантов осуществления граф представляет собой граф NSW;

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

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

В одном из вариантов осуществления способ дополнительно содержит этап, на котором:

выбирают среди найденного набора объектов объект, наиболее близкий к целевому объекту;

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

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

определяют метки классов объектов из найденного набора объектов;

при этом класс, к которому относится целевой объект, определяют как наиболее частую метку среди найденного набора объектов.

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

определяют метки классов объектов из найденного набора объектов;

каждому из найденного набора объектов присваивают вес в зависимости от его близости к целевому объекту;

определяют сумму весов для каждого класса;

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

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

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

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

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

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

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

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

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

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

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

В одном из вариантов осуществления определение границы между классами содержит этапы, на которых:

выбирают из набора ребер поднабор самых коротких ребер;

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

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

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

В одном из вариантов осуществления граф представляет собой граф NSW;

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

В одном из вариантов осуществления граф представляет собой граф HNSW;

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

В одном из вариантов осуществления процесс жадного поиска дополнительно содержит этап, на котором:

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

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

В одном из вариантов осуществления количество классов равно двум;

при этом определение класса, к которому относится целевой объект, содержит этапы, на которых:

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

если число пересечений четное, то в качестве класса, к которому относится целевой объект, задают класс объекта, соответствующего упомянутой последней вершине, или

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

Согласно второму аспекту настоящего изобретения, предложено устройство для классификации объекта, содержащее:

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

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

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

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

Технический результат

Настоящее изобретение позволяет повысить эффективность способов и устройств для классификации объектов. При этом обеспечивается:

- повышение скорости получения результата;

- снижение вычислительной сложности;

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

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

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

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

На Фиг. 1 показана блок-схема способа классификации объекта согласно настоящему изобретению.

На Фиг. 2 показана блок-схема устройства для классификации объекта согласно настоящему изобретению.

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

Подробное описание

Общее описание способа

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

На Фиг. 1 представлена блок-схема способа классификации объекта согласно настоящему изобретению. Способ 100 классификации объекта содержит следующие этапы.

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

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

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

Ребро в графе указывает на взаимосвязь между вершинами. Существует несколько вариантов построения графа «мир тесен» и генерации ребер. Например, в одном из вариантов осуществления ребра генерируются в процессе построения графа: из имеющегося множества объектов случайным образом отбирается один объект, формируется его представление в метрическом пространстве, соответствующая вершина добавляется в граф, для этой вершины методом kNN выполняется поиск ближайших f вершин (соседей, или друзей) (мерой близости при этом является расстояние между вершинами в метрическом пространстве), и генерируются ребра от данной вершины к каждой из ближайших f вершин. По мере добавления новых и новых вершин в граф некоторые связанные между собой ребрами вершины перестают быть ближайшими, однако наличие таких связей (ребер) обеспечивает графу свойство “мир тесен” и логарифмические свойства. Таким образом, обеспечивается возможность эффективно применять вышеупомянутый алгоритм жадного поиска, с тем чтобы с повышенной скоростью при поддержании высокой точности находить ближайший объект.

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

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

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

На этапе S124 выполняется сравнение определенного на этапе S123 наименьшего расстояния до целевой вершины с расстоянием от текущей вершины до целевой вершины.

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

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

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

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

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

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

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

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

Далее, когда класс целевого объекта определен, способ 100 переходит к этапу S140, на котором формируют сведения о классе, к которому относится целевой объект. Форма сведений о классе целевого объекта может быть различной. В одном варианте осуществления сведения о классе могут повторять описание класса – например, если метка была текстовым описанием класса («кошка», «собака», «корова»), то и сведения о классе целевого объекта могут содержать тот же текст, какой был в соответствующей метке; если метка была изобразительным или звуковым описанием, то и сведения о классе целевого объекта могут содержать то же изображение или звук, какой был в соответствующей метке, и т.д. В другом варианте осуществления сведения о классе могут быть каким-либо образом связаны с описанием класса – например, если метка была текстовым описанием класса («Австралия»), то сведения о классе целевого объекта могут содержать изображение флага Австралии, звук гимна Австралии, фрагмент карты, на которой изображена Австралия, изображения кенгуру или Сиднейского оперного театра, с которыми у многих ассоциируется эта страна, и т.д. Кроме того, сведения о классе целевого объекта могут содержать ссылку на описание класса. При необходимости сведения о классе целевого объекта могут быть включены в файл. Формат файла зависит от того, что собой представляют сведения о классе целевого объекта. Помимо сведений о классе целевого объекта, файл может содержать найденный наиболее близкий объект, его описание или представление, или ссылку на найденный наиболее близкий объект, его описание или представление. Все это позволяет адаптировать предложенный способ к требованиям конкретного применения, с тем чтобы обеспечить ускоренную идентификацию класса устройством или пользователем, запросившим выполнение классификации.

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

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

Варианты определения класса

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

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

В одном из вариантов осуществления, применимом для графа NSW, процесс жадного поиска может выполняться несколько раз (в общем случае – предварительно заданное количество раз), каждый раз с началом в разных случайных вершинах. В результате будет найден набор объектов, предполагаемых в качестве наиболее близких к целевому объекту. Число объектов в таком наборе от случая к случаю может варьироваться в пределах от одного до количества операций поиска, так как некоторые (или даже все) поиски могут привести к одинаковому наиболее близкому объекту.

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

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

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

Еще в одном сценарии для каждого из найденного набора объектов определяют метку класса, и если классов в наборе окажется больше одного, то каждому из найденного набора объектов присваивают вес в зависимости от его близости к целевому объекту. Затем для каждого класса вычисляют сумму весов, и в качестве класса целевого объекта определяют класс, имеющий наибольшую сумму весов. Принцип присвоения веса может быть разным. В самом простом с вычислительной точки зрения случае вес может быть обратно пропорционален расстоянию от данного объекта из набора до целевого объекта. Возможны и другие зависимости – например, от квадрата расстояния (позволяет уменьшить вклад более отдаленных объектов в общий результат). Например, в качестве класса целевого объекта может быть выбран класс, имеющий наибольшую сумму величин, обратных расстоянию, и т.д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура устройства

Далее со ссылкой на Фиг. 2 будет более подробно описано устройство 200 для классификации объекта согласно настоящему изобретению.

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

Устройство 210 для классификации объекта может содержать процессор и память, соединенную с процессором и содержащую инструкции, которые предписывают процессору выполнять следующие операции:

принимать (210) целевой объект, для которого требуется определить класс, к которому относится этот объект;

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

определять (230) класс, к которому относится целевой объект, согласно метке класса объекта, предполагаемого в качестве наиболее близкого к целевому объекту, или согласно пути, пройденному в процессе жадного поиска;

формировать (240) сведения о классе, к которому относится целевой объект;

передавать (250) сведения о классе целевого объекта на устройство, которое запрашивало эти сведения.

Устройство для классификации объекта может быть составной частью другого, более сложного устройства – например, робота, беспилотного летательного аппарата (БПЛА), поисковой машины, рекомендательной системы и т.д.

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

Поиск объекта, наиболее близкого к целевому объекту, определение класса целевого объекта и формирование сведений о классе выполняются аппаратно-программными или программно-аппаратными модулями: модулем 220 поиска, модулем 230 определения класса и модулем 240 формирования результата.

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

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

Следует отметить, что скорость обработки (или иными словами, время получения результата) во многом зависит от имеющегося в распоряжении объема памяти и от ее быстродействия. Соответственно, чем больше объем доступной оперативной памяти, тем выше скорость классификации. Реализация предложенного изобретения как на основе NSW, так и на основе HNSW позволяет повысить скорость классификации для структур данных любых размеров по сравнению с известными из уровня техники способами классификации. При этом, если взять один и тот же объем выделенной для классификации оперативной памяти (например, 3,5 ГБ), реализация на основе HNSW дает наибольшее ускорение (в десятки раз) на больших структурах данных (например, на графе с высокой плотностью, 128-регулярных графов) за счет того, что большая доля вычислений производится на верхних слоях графа, требующих мало памяти, а реализация на основе NSW показывает наибольшее ускорение на относительно небольших структурах данных (например, граф с плотностью 8-регулярных графов), а также позволяет повысить точность классификации за счет проверки нескольких предполагаемых наиболее близких вершин.

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

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

Например, в одном из вариантов осуществления, если устройство, запрашивающее классификацию объекта, физически расположено в рамках того же общего устройства, что и устройство для классификации объекта, или имеет программно-аппаратную реализацию на базе того же процессора и памяти, что и устройство для классификации объекта, то прием (210) целевого объекта и передача (250) сведений о классе могут выполняться в рамках собственных средств обмена данными упомянутого общего устройства.

В другом варианте осуществления, если устройство, запрашивающее классификацию объекта, физически расположено отдельно от устройства для классификации объекта, то устройство для классификации объекта может содержать выделенные аппаратные модули 210 приема и 250 передачи. Модуль 210 приема и модуль 250 передачи могут быть реализованы отдельно или могут быть частями одного приемопередающего модуля. Прием и передача данных может выполняться с помощью технологий проводного и/или беспроводного обмена данными (осуществления связи).

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

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

Варианты применения

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

В одном из возможных частных применений, если решается одна из задач компьютерного зрения, такая как распознавание или отслеживание объектов или целей, то сначала получается изображение (например, с помощью камеры), при необходимости на нем детектируется/сегментируется объект (например, с помощью ограничивающей рамки или контура с использованием нейронной сети или с использованием классических методов), а затем выполняется классификация объекта согласно настоящему изобретению. В зависимости от целей конкретного применения далее в связи с определенным классом объекта может выполняться принятие решения (например, если определено, что поверхность транспортного средства содержит дефект лакокрасочного покрытия, информация о дефекте отправляется оператору, и он принимает решение о необходимости повторной покраски, или если определено, что рентгеновский снимок указывает на наличие патологии у пациента, врач принимает решение о лечении пациента, и т.д.) или предварительно определенное управляющее воздействие на исполнительный механизм (например, если определено, что к двери приближается хозяин с хмурым лицом, в ответ на это блок управления системы «умный дом» отправляет управляющее воздействие на дверной замок, чтобы разблокировать его, и на медиасистему, чтобы включить расслабляющую музыку, или если определено, что по пешеходному переходу движется человек, блок управления беспилотным транспортным средством оказывает управляющее воздействие на двигатель, трансмиссию и тормозную систему, с тем чтобы в зависимости от текущей скорости замедлиться или остановиться, или если определено, что на пути движения БПЛА находится дерево, блок управления БПЛА оказывает управляющее воздействие на двигатели, с тем чтобы облететь это препятствие, и т.д.).

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

Способ обучения / разметки набора данных

Далее будет раскрыт способ 300 разметки набора данных на основе вышеописанного способа классификации объекта.

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

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

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

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

Способ 300 разметки набора данных может содержать следующие этапы.

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

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

На этапе S330 предсказывают класс целевого объекта согласно метке класса объекта, предполагаемого в качестве наиболее близкого к целевому объекту, или согласно пути, пройденному в процессе жадного поиска.

Этапы S320 и S330, по существу, относятся к способу классификации объекта и не требуют дополнительных пояснений.

На этапе S360 присваивают метку класса целевому объекту.

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

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

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

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

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

На этапе S360 присваивают метку класса целевому объекту на основании принятого ввода от пользователя.

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

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

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

Поисковая машина

Далее будет раскрыт способ 400 поиска похожих объектов на основе вышеописанного способа классификации объекта.

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

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

Способ 400 поиска похожих объектов в структуре данных может содержать следующие этапы.

На этапе S410 принимают целевой объект, для которого требуется найти похожие объекты.

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

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

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

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

На этапе S460 передают сформированный файл на устройство, запрашивавшее поиск.

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

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

Рекомендательная система

Далее будет раскрыт способ 500 рекомендации на основе вышеописанного способа классификации объекта.

В этом сценарии компьютерно-реализованная рекомендательная система, выполняющая способ 500, должна найти в базе данных объекты, связанные с заданным, с учетом его возможных признаков, то есть с учетом его класса. Рекомендательная система содержит устройство 200 для классификации объекта.

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

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

На этапе S510 принимают целевой объект, для которого требуется выполнить рекомендацию.

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

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

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

На этапе S550 обращаются к базе данных, содержащей данные о взаимосвязи между объектами, отличной от близости в метрическом пространстве, и выполняют поиск второго набора объектов, причем второй набор объектов содержит объекты, имеющие упомянутую взаимосвязь с объектами из сформированного на этапе S540 поднабора первого набора объектов. В качестве взаимосвязи в одном варианте осуществления может выступать, например, наличие взаимных ссылок, наличие переходов по взаимным ссылкам, наличие покупок, в которых данные объекты покупались в рамках одного заказа, и т.д. В другом варианте осуществления в качестве взаимосвязи может выступать, например, количество взаимных ссылок, количество переходов по взаимным ссылкам, количество покупок, в которых данные объекты покупались в рамках одного заказа, и т.д. Еще в одном варианте осуществления для отбора во второй набор объектов может применяться условие взаимосвязи, состоящее в минимальном пороге взаимосвязей между заданными объектами – например, объект отбирается, если он хотя бы 5 раз покупался совместно с объектами из сформированного на этапе S540 поднабора первого набора объектов (с каждым из них, с любым из них по отдельности или в сумме со всеми ними).

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

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

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

На этапе S590 передают сформированный файл на устройство, запрашивавшее рекомендацию.

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

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

Пример осуществления

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

Устройство для классификации объекта реализовано на базе ноутбука с 64-разрядной ОС Windows 10, содержащего процессор AMD Ryzen 3 3200U с частотой 2,6 ГГц и 2 физическими ядрами, 6 ГБ оперативной памяти. Для целей устройства для классификации объекта используется 1 ядро и 3,5 ГБ оперативной памяти.

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

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

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

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

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

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

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

Дополнительные особенности реализации

Различные иллюстративные блоки и модули, описанные в связи с раскрытием сущности в данном документе, могут реализовываться или выполняться с помощью процессора общего назначения, процессора цифровых сигналов (DSP), специализированной интегральной схемы (ASIC), программируемой пользователем вентильной матрицы (FPGA) или другого программируемого логического устройства (PLD), дискретного логического элемента или транзисторной логики, дискретных аппаратных компонентов либо любой комбинации вышеозначенного, предназначенной для того, чтобы выполнять описанные в данном документе функции. Процессор общего назначения может представлять собой микропроцессор, но в альтернативном варианте, процессор может представлять собой любой традиционный процессор, контроллер, микроконтроллер или конечный автомат. Процессор также может реализовываться как комбинация вычислительных устройств (к примеру, комбинация DSP и микропроцессора, несколько микропроцессоров, один или более микропроцессоров вместе с DSP-ядром либо любая другая подобная конфигурация).

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

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

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

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

В качестве примера, а не ограничения, машиночитаемые носители могут содержать постоянное запоминающее устройство (ROM), программируемое постоянное запоминающее устройство (PROM), стираемое программируемое постоянное запоминающее устройство (EPROM), электронно-стираемое программируемое постоянное запоминающее устройство (EEPROM), флэш-память, оперативную память (RAM), статическую память с произвольным доступом (SRAM), динамическую память с произвольным доступом (DRAM), синхронную динамическую память с произвольным доступом (SDRAM), синхронную динамическую память с произвольной выборкой с двойной скоростью передачи данных (DDR SDRAM), синхронную динамическую память с произвольной выборкой с повышенной скоростью (ESDRAM), DRAM с синхронной линией связи (SLDRAM) и оперативную память с шиной прямого доступа (DR RAM) и т.п.

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

Процессор может включать в себя один или более процессоров. В то же время один или более процессоров могут быть процессором общего назначения, например центральным процессором (CPU), прикладным процессором (AP) и т.п., блоком обработки графики, таким как графический процессор (GPU), визуальный процессор (VPU) и т.д.

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

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

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

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

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

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

1. Компьютерно-реализуемый способ классификации объекта, содержащий этапы, на которых:

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

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

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

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

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

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

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

2. Способ по п. 1, в котором граф представляет собой граф NSW (граф «мир тесен» с возможностью навигации) или HNSW (иерархический граф «мир тесен» с возможностью навигации).

3. Способ по п. 1, в котором процесс жадного поиска содержит этапы, на которых:

определяют текущую вершину для поиска;

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

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

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

4. Способ по п. 3, в котором:

граф представляет собой граф NSW;

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

5. Способ по п. 3, в котором:

граф представляет собой граф NSW;

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

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

6. Способ по п. 5, дополнительно содержащий этап, на котором:

выбирают среди найденного набора объектов объект, наиболее близкий к целевому объекту;

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

7. Способ по п. 5, дополнительно содержащий этапы, на которых:

определяют метки классов объектов из найденного набора объектов;

при этом класс, к которому относится целевой объект, определяют как наиболее частую метку среди найденного набора объектов.

8. Способ по п. 5, дополнительно содержащий этапы, на которых:

определяют метки классов объектов из найденного набора объектов;

каждому из найденного набора объектов присваивают вес в зависимости от его близости к целевому объекту;

определяют сумму весов для каждого класса;

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

9. Способ по п. 5, дополнительно содержащий этапы, на которых:

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

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

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

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

10. Способ по п. 3, в котором:

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

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

11. Способ по п. 1, в котором определение границы между классами содержит этапы, на которых:

выбирают из набора ребер поднабор самых коротких ребер;

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

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

12. Способ по п. 1, в котором:

граф представляет собой граф NSW;

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

13. Способ по п. 1, в котором:

граф представляет собой граф HNSW;

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

14. Способ по любому из пп. 12, 13, в котором процесс жадного поиска дополнительно содержит этап, на котором:

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

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

16. Способ по п. 14, в котором количество классов равно двум;

при этом определение класса, к которому относится целевой объект, содержит этапы, на которых:

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

если число пересечений четное, то в качестве класса, к которому относится целевой объект, задают класс объекта, соответствующего упомянутой последней вершине, или

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

17. Устройство для классификации объекта, содержащее:

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

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

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

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

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