Разработка автоматизированной системы классификации товаров по их изображениям

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых»

Факультета прикладной математики и физики

Специальности 10 501 — прикладная математика и информатика

ДИПЛОМНАЯ РАБОТА

Тема: Разработка автоматизированной системы классификации товаров по их изображениям

Студента Богданова Ильи Дмитриевича

Руководитель работы: Павлова О.Н.

Аннотация

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

Ключевой частью работы является получение достаточно объёмной базы классифицированных товаров для обучения нейронных сетей. В качестве источника исходных данных взят один из крупных интернет-аукционов (molotok.ru).

Введение

Глава 1. Обзор объекта и методов исследования

1.1 Описание объекта исследования

1.2 Описание привлекаемых методов

1.2.1 Искусственные нейронные сети

1.2.2 Метод обратного распространения ошибки

1.3 Среда разработки и причины ее выбора Глава 2. Методика

2.1 Способ получения информации с веб-ресурсов

2.2 Методика классификации товаров

2.3 Алгоритм классификации товаров

2.4 Принцип хранения данных о товарах Глава 3. Программная реализация. Апробация методики

3.1 Описание программного обеспечения

3.2 Апробация методики Заключение Список использованной литературы Приложение

Введение

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

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

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

Глава 1. Обзор объекта и методов исследования

1.1 Описание объекта исследования

Молоток.ру — один из крупнейших интернет аукционов в России. На сайте представлено порядка 5 000 000 уникальных лотов, все они хорошо структурированы и находятся более чем в 5000 категорий.

Рассмотрим принцип работы интернет-аукциона. Продавец выставляет товар на продажу и заявляет начальную цену. Вариантов приобретения товара может быть два: по блиц-цене и по принципу аукциона. В первом случае ожидать окончания торгов не нужно. Можно сразу оплатить товар и договориться с продавцом о доставке, как это происходит в интернет-магазинах. Во втором — товар достается тому, кто сделал продавцу наиболее выгодное предложение.

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

1.2 Описание привлекаемых методов

1.2.1 Искусственные нейронные сети

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

Рис. 1. Схема трехслойной нейронной сети

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

Персептрон — математическая и компьютерная модель восприятия информации мозгом (кибернетическая модель мозга), предложенная Фрэнком Розенблаттом.

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

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

1.2.2 Метод обратного распространения ошибки Метод обратного распространения ошибки — метод обучения многослойного персептрона, один из вариантов обучения с учителем. Впервые метод был описан Полом Дж. Вербосом. Далее существенно развит в 1986 г. Дэвидом И. Румельхартом, Дж. Е. Хинтоном и Рональдом Дж. Вильямсом. Это итеративный градиентный алгоритм, который используется с целью минимизации ошибки работы многослойного перцептрона и получения желаемого выхода.

Основная идея этого метода состоит в распространении сигналов ошибки от выходов сети к её входам, в направлении, обратном прямому распространению сигналов в обычном режиме работы. Барцев и Охонин предложили сразу общий метод («принцип двойственности»), приложимый к более широкому классу систем, включая системы с запаздыванием, распределённые системы, и т. п.

Метод является модификацией классического метода градиентного спуска.

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

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

(1)

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

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

(2)

где весовой коэффициент j-го нейрона n-го слоя для связи с i-м нейроном (n-1)-го слоя.

Параметр называется параметром скорости обучения.

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

(3)

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

. (4)

Третий сомножитель / есть ни что иное, как выход i-го нейрона (n-1)-го слоя, то есть

. (5)

Частные производные целевой функции по весам нейронов выходного слоя теперь можно легко вычислить. Производя дифференцирование (1) по и учитывая (3) и (5) будем иметь

(6)

Введем обозначение

. (7)

Тогда для нейронов выходного слоя

. (8)

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

(9)

Заметим, что в этой формуле первые два сомножителя есть не что иное, как. Таким образом, с помощью (9) можно выражать величины для нейронов n-го слоя черездля нейронов (n+1)-го. Поскольку для последнего слоя легко вычисляется по (8), то можно с помощью рекурсивной формулы

(10)

получить значения для вех нейронов всех слоев.

Окончательно формулу (2) для модификации весовых коэффициентов можно записать в виде

. (11)

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

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

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

Рассчитать по формуле (8). Затем с помощью рекурсивной формулы (10) подсчитываются все остальные и, наконец, с помощью (11) изменение весовых коэффициентов сети.

Скорректировать веса сети:

.

Рассчитать целевую функцию (1). Если она достаточно мала, считаем сеть успешно обучившейся. Иначе возвращаемся на шаг 2.

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

(12)

где — требуемое значение выходного сигнала.

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

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

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

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

Размер шага Внимательный разбор доказательства сходимости показывает, что коррекции весов предполагаются бесконечно малыми. Ясно, что это неосуществимо на практике, так как ведёт к бесконечному времени обучения. Размер шага должен браться конечным. Если размер шага фиксирован и очень мал, то сходимость слишком медленная, если же он фиксирован и слишком велик, то может возникнуть паралич или постоянная неустойчивость. Эффективно увеличивать шаг до тех пор, пока не прекратится улучшение оценки в данном направлении антиградиента и уменьшать, если такого улучшения не происходит. П. Д. Вассерман описал адаптивный алгоритм выбора шага, автоматически корректирующий размер шага в процессе обучения. В книге А. Н. Горбаня предложена разветвлённая технология оптимизации обучения.

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

1.3 Среда разработки и причины ее выбора

Разработка приложения будет осуществляться на языке программирования C# с фреймворком. NETFramework4.0 в среде разработки MicrosoftVisualStudio 2010. Фрагменты кода, требующие массивных вычислений, разработаны на языке C++. MSVisualStudio 2010 включает в себя полный набор новых и улучшенных функций, упрощающих все этапы процесса разработки от проектирования до развертывания.

MicrosoftVisualStudio 2010 Ultimate — интегрированная среда инструментальных средств и серверная инфраструктура, упрощающая процесс разработки приложения в целом. Для создания бизнес-приложений используются эффективные, предсказуемые, настраиваемые процессы. Детальная аналитика повышает прозрачность и прослеживаемость всего жизненного цикла приложения. Как при создании новых решений, так и при доработке существующих, доступна разработка с помощью мощных инструментов создания прототипов, проектирования архитектуры и разработки, которые позволяют разрабатывать приложения для всевозможных платформ и технологий, таких как обработка данных в облаке и параллельная обработка данных. Расширенные возможности координирования совместной деятельности наряду с интегрированными инновационными инструментами тестирования и отладки обеспечат повышение производительности группы и создание высококачественных и недорогих решений.

Разработка приложений в MicrosoftVisualStudio2010 Ultimate на языке C# с фреймворком. NETFramework4.0 осуществляется с применением объектно-ориентированного программирования и визуального программирования.

Глава 2. Методика

2.1 Способ получения информации с веб-ресурсов

При исследовании средств получения информации с сайта molotok.ru выявлено отсутствие API, позволяющего получить необходимые исходные данные. Поэтому получение информации будет производиться непосредственно с веб-страниц сайта. Для этого необходим программный доступ к элементам страницы. Также необходимо учесть, что часть элементов на странице генерируются при помощи JavaScript и AJAX. Поэтому выполнения простых HTTP запросов (классы WebRequestи WebResponse) недостаточно, необходимо обеспечить выполнение JavaScriptи AJAX на странице. В связи с этим в качестве объекта, получающего страницы с сайта, был выбран стандартный для MSVisualStudioкласс WebBrowser, который представляет оболочку для неуправляемого объекта на основе браузераInternet Explorer, версии идентичной установленному в системе.

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

Сайт molotok.ru является крупным интернет-аукционом с большим количеством категорий, в которых может представляться товар. Таким образом, сначала необходимо получить полный список категорий, с сохранением уровней вложенности т.к. это потребуется в дальнейшем. Это удобно сделать при помощи веб-страницы сайта «Карта категорий» (http://molotok.ru/category_map.php). На сайте представлено более 5000 категорий, которые могут быть вложены одна в другую. То есть фактически список категорий является древовидной структурой. Максимальный уровень вложенности — четвёртый. Категории нулевого уровня не содержат товаров, а являются лишь агрегаторами для категорий первого уровня. На веб-странице «Карта категорий» представлены ссылки на все категории интернет-аукциона, каждая категория содержится внутри отдельного html-элемента

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

Рис. 2. Алгоритм получения категорий с веб-ресурса

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

, который содержит в себе товары и всю информацию о каждом из них. Информацию о товаре можно разделить на два типа: текстовая (Идентификатор товара) и графическая (Изображения товара). Интернет-аукцион сохраняет все изображения товаров на внутреннем хостинге изображений, где они проходят предварительную обработку и приводятся к двум форматам: 64×48 и 400×300. Для каждого товара извлекаются и сохраняются в БД ссылки на его изображения. Следует отметить, что ссылки разделаются на два типа, согласно двум форматам изображений. Этот этап происходит в многопоточном режиме для уменьшения времени, требуемого для обработки товаров. На рисунке далее приведена схема алгоритма.

Рис. 3. Схема алгоритма получения информации о товарах

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

2.2 Методика классификации товаров

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

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

2.3 Алгоритм классификации товаров

На первом этапе классификации программе на вход подаётся изображение товара, после чего изображение подготавливается для подачи на входы нейронных сетей. Для предварительной обработки изображения применяется алгоритм, аналогичный тому, что используются при обработке изображений для обучения нейронных сетей. Суть алгоритма состоит в том, что цвет каждого пикселя усредняется путём нахождения среднего арифметического из его RGB-составляющих, затем полученное число делится на 255 и вычитается из единицы. Таким образом, наибольшей значимостью для нейронных сетей будут обладать тёмные цвета. Так же, если размер изображения отличается от необходимого для подачи на вход нейронной сети, он приводится к требуемому при помощи стандартных алгоритмов для работы с растровыми изображениями, встроенных в платформу.NET. Результатом будет массив выходов нейронных сетей для данного товара.

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

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

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

Рис. 4. Схема алгоритма классификации товаров

2.4 Принцип хранения данных о товарах

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

Для хранения дерева категорий, ссылок на изображения товаров и настроек программы используется реляционная база данных. В качестве СУБД используется MSSQLServer 2008 R2 ExpressSP1.

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

На рисунке ниже приведена структура базы данных.

Рис. 5. Структура базы данных

Приведем описание таблиц, полей и типов данных, использованных в базе данных:

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

setting — хранит название настройки, тип данных varchar.

value — хранит значение настройки, тип данных varchar.

Таблица Imagesхранит данные о изображениях товаров, о том, к какому товару и какой категории принадлежит изображение. Приведем описание полей:

itemId — хранит идентификатор изображения, полученных с веб-ресурса, тип данных bigint.

categoryId — хранит идентификатор категории, к которой относится изображение, тип данных int.

URL — хранит ссылку на изображение, тип данных varchar.

isBig — флаг, определяющий, имеет ли изображение большое разрешение, тип данных bit.

Таблица Categoriesхранит данные о категориях и их структуре. Приведем описание полей:

id — хранит идентификатор категории, полученный с веб-ресурса, тип данных int.

[level] - уровень категории, тип данных int.

name — название категории, тип данных varchar.

url — ссылка на категорию, тип данных varchar.

parentUrl — ссылка на родительскую категорию, тип данных varchar.

Глава 3. Программная реализация. Апробация методики

3.1 Описание программного обеспечения

интернет аукцион нейронный сеть товар

Для обработки данных разработана программа на языке программирования C# на платформе.NET4.0 В среде программирования MicrosoftVisualStudio 2010 UltimateEdition. Хранение данных осуществлено с использованием СУБД MSSQLServer2008 R2 ExpressEditionSP1.

Программа, извлекающая данные с веб-ресурса обрабатывает информацию следующего вида:

1. Страница, с данными о товарах.

2. Идентификатор товара.

3. Ссылка на товар

4. Категория товара

5. Изображения товара.

Результатами работы приложения является:

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

Структурированные, сохранённые локально изображения товаров.

Программа, классифицирующая товары обрабатывает информацию следующего вида:

1. Изображения товаров

2. Информация для обучения сетей

3. Конфигурации сетей Результатами работы приложения является:

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

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

На рисунке 6представлена структурная схема приложения:

Рис. 6. Структурная схема приложения

На рисунке 7 представлена структура работы приложения, извлекающего данные с веб-ресурса:

Рис. 7. Структура работы приложения извлекающего данные с веб-ресурса

На рисунке 8 представлена структура работы приложения, классифицирующего товары:

Рис. 8. Структура работы приложения классифицирующего товары

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

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

Grabber — модуль отвечающий за загрузку данных и парсинг веб-ресурса

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

DBEngine — модуль для осуществления работы с БД.

ThreadHelper — модуль, содержащий функции для распределения общего объёма работы между потоками.

Loggerмодуль, осуществляющий работу с лог-файлами.

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

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

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

TrainDataмодуль формирования информации для обучения нейронных сетей.

NetworkControllerмодуль для управления работой массива нейронных сетей.

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

Описание классов.

Для реализации задачи поставленной в рамках данной дипломной работы был разработан набор классов следующей структуры:

Класс Categoryописывает категорию товаров.

Приведём структуру класса:

public class Category

{

public int id; //ИД категории в системе сайта

public int level; //Уровень вложения

public string name; //Название

public string url; //ссылка

public string parentURL; //ссылка на категорию-родитель

public List categoryImages; //изображения товаров

}

Класс Image описывает изображение товара.

Приведём структуру класса:

public class Image

{

public Int64 itemId; //ИД товара

public int categoryId; //ИД категории

public string URL; // ссылка на изображения

public bool isBig; // флаг, показывающий, имеет ли изображение большое разрешение

}

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

Класс DBEngineявляется контроллером при работе с базой данных.

Приведём структуру класса:

public class DBEngine

{

string connectionString; //строка подключения

public CategoryTable categoryTable; //таблица категорий

public ImageTable imageTable; //таблица изображений

public SettingsTable settingsTable; //таблица настроек

}

Класс EngineTable является классом-родителем классам для работы с таблицами базы данных.

Приведём структуру класса:

public class EngineTable

{

protected string tableName; //Имя таблицы

protected string connectionString; //строка подключения

}

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

Класс ImageTable используется для работы с таблицей изображений в базе данных, является наследником класса EngineTable.

Класс SettingsTable используется для работы с таблицей настроек в базе данных, является наследником класса EngineTable.

Класс BrowserExtensions используется для расширения возможностей встроенного классаWebBrowser.

Класс TreeViewExtension используется для расширения возможностей встроенного классаTreeView.

Класс Grabberслужит для извлечения информации с веб-ресурса.

Приведём структуру класса:

class Grabber

{

DBEngine.DBEngine dbEngine; //движок БД

List categories; //категории

int getItemCounter; //счетчик получения товаров

int getItemWorkAmount; //объём работы получения товаров

int getItemThreadCount; //количество потоков получения товаров

public int GetItemThreadCount

{

get { return getItemThreadCount; }

set { getItemThreadCount = value; }

}

int saveImageCounter; //счетчик сохранения изображений

int saveItemWorkAmount; //объём работы сохранения изображений

int saveItemThreadCount; //количество потоков сохранения изображений

public int SaveItemThreadCount

{

get { return saveItemThreadCount; }

set { saveItemThreadCount = value; }

}

}

Класс NeuralNetworkу управляет единичной нейронной сетью.

Приведём структуру класса:

partial class NeuralNetwork

{

NeuralNet net; //нейронная сеть

uint[] neuronsInLayers; //количество нейронов в слоях

public int id; //ИД

public Category levelTwoParent; //категория родитель уровня 2

public Category category; //категория

public string Name //имя

{

get { return category.name; }

}

public int Level //уровень

{

get { return category. level; }

}

}

Класс NetworkPool используется для группировки сетей и определения результата классификации, не содержит полей.

Класс NetworkController управляет массивом нейронных сетей.

Приведём структуру класса:

class NetworkController

{

DBEngine dbEngine; //движок БД

List smallNetworks; //маленькие сети

List bigNetworks; //большие сети

public Dictionary workResult; //результат работы сетей

bool smallNetworksInitialized; //флаг инициализации малых сетей

public bool SmallNetworksInitialized

{

get { return smallNetworksInitialized; }

}

bool bigNetworksInitialized; //флаг инициализации больших сетей

public bool BigNetworksInitialized

{

get { return bigNetworksInitialized; }

set { bigNetworksInitialized = value; }

}

string initialDirectory; //рабочая директория

public string InitialDirectory

{

get { return initialDirectory; }

}

uint[] smallNetworkLayers = { 3072, 512, 1 }; //слои малых сетей

uint[] bigNetworkLayers = { 12 000, 1000, 1 }; //слои больших сетей

int trainDataCreationCounter; //счетчик создания данных для обучения

int trainDataCreationWorkAmount; //объём работы данных обучения

int trainDataCreationThreadCount; //количество потоков данных обучения

public int TrainDataCreationThreadCount

{

get { return trainDataCreationThreadCount; }

set { trainDataCreationThreadCount = value; }

}

int networkTrainCounter; //счетчик обучения сетей

int networkTrainWorkAmount; //объём работы обучения сетей

int networkTrainThreadCount; //количество потоков обучения сетей

public int NetworkTrainThreadCount

{

get { return networkTrainThreadCount; }

set { networkTrainThreadCount = value; }

}

int networkCreateCounter; //счетчик создания сетей

int networkCreateWorkAmount; //объём создания сетей

int networkCreateThreadCount; //потоки создания сетей

public int NetworkCreateThreadCount

{

get { return networkCreateThreadCount; }

set { networkCreateThreadCount = value; }

}

}

Описание интерфейса работы программы При запуске программы появляется главное окно приложения:

Рис. 9. Окно программы после запуска

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

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

Рис. 10. Окно программы с загруженным списком категорий

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

Рис. 11. Процесс парсинга указанных категорий

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

Рис. 12. Работа окончена

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

Рис. 13. Главное окно программы для классификации товаров

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

При нажатии кнопки подготовить данные для обучения программа начнет работу:

Рис. 14. Создание файлов обучения

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

Для классификации товара, нужно нажать кнопку «Работать», затем выбрать изображение этого товара, и дождаться результата классификации.

Рис. 15. Результат классификации

3.2 Апробация методики

Для тестирования методики классификации товаров была произведена случайная выборка 20 категорий, общее количество товаров составило 8442, образов — 19 863. Классификация осуществлялась в восемь потоков. Для осуществления тестирования были отобраны 2000 случайных товаров, по 100 штук для каждой категории, успешным результат тестирования для одного товара считался, если сеть, к категории которой принадлежит данный товар, возвращала выходной сигнал на 90% и более соответствующий эталонному сигналу. Настройки нейронных сетей: число нейронов во входном слое — 3072, в скрытом — 512, в выходном — 1, шаг обучения 1*10^-10, максимальное количество эпох при обучении — 1*10⁹, максимально допустимая погрешность — 1*10^-10.

Рис. 16. Процент верно классифицированных товаров по категориям

Как видно из графика, представленного на рисунке выше, точность классификации товаров варьируется от 66 до 89%. Точность классификации напрямую зависит от количества образов, которое было дано сети для обучения. Максимальная точность была достигнута для сети с 4867 образами. Соответствие категорий их идентификаторам приведено в таблице 1.

Таблица 1

Наименование категории	Идентификатор
Ножи
Фонари
Цифровые зеркальные камеры
Роликовые коньки
Дефлекторы
Палатки
Фаркопы
Гири
Гантели
Мячи
Материнские платы
Шахматы
iPhone
iPhone3GS
iPhone 3GS White
iPhone4S
iPhone 4S White
USB флешки
Металлоискатели

Нейронные сети в основе системы были выбраны потому, что немаловажным аспектом работы программы является её быстродействие, далее будет осуществлено тестирование скорости работы приложения.

Тестовая конфигурация аппаратного обеспечения приведена в таблице 2.

Таблица 2

Процессор	AMD FX-8120 4600 MHz
Оперативная память	Kingston HyperXT1 16Gb 1866 MHz
Жесткий диск	OCZ Vertex Turbo 30Gb, 2xWD Caviar Green 1Tb Raid1
Блок питания	Enermax Revolution85+ 920W

Результаты тестирования производительности будут представлены в порядке последовательного выполнения всех узлов программы: от парса категорий до непосредственной работы нейронных сетей. Всего на сайте представлено 5116 категорий, общее время парса всех категорий составляет 36−38 секунд.

Рис. 17. Время парсинга категорий

На графике, изображенном на рисунке 17, представлены произвольные 11 категорий, максимальное время парса составляет 0,0204 сек, минимальное — 0,0058 сек, среднее — 0,0122 сек.

Теперь будет приведён тест производительности при парсинге товаров. Товары на сайте представлены страницами по 25 товаров на каждой странице. Максимальное время парса страницы -2,8057 сек, минимальное -1,6170 сек, среднее — 2,1116 сек.

Рис. 18. Время парсинга товаров

На рисунке 18изображен график, на котором представлены 50 случайных товаров и время их парсинга. Минимальное время составляет 0,0003 сек, максимальное — 0,0023 сек, среднее время — 0,0007 сек.

Рис. 19. Время сохранения изображений на диск

На данном графике (рис. 19) представлен результат тестирования производительности сохранения 250 случайных изображений на диск. Минимальное время равно 0,0662 сек, максимальное составляет 0,3213 сек, среднее — 0,0996 сек.

Ранее упоминалось, что общее число изображений для тестирования составляет 19 863. Приведём тестирование производительности на этапе подготовки образов для дальнейшего обучения нейронных сетей. Образы обрабатывались для подготовки различным нейронным сетям. Максимальное время обработки — 0,3 217 сек, минимальное — 0,1 103 сек, среднее — 0,2 054. График, наглядно отображающий время, затраченное на обработку каждого набора изображений, представлен на рисунке 20.

Рис. 20. Время подготовки данных для обучения нейронных сетей

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

Рис. 21. Время обучения нейронных сетей

На рисунке 21 представлен график, на котором отображено время обучения нейронных сетей. Максимальное время составляет 0,2057 сек, минимальное — 0,1054 сек, среднее — 0,0932 сек.

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

Рис. 22. Время сохранения файлов конфигурации нейронных сетей на диск

Как видно из графиков, представленных на рисунке 22, максимальное время сохранения конфигурационного файла сети составляет 5,68 сек, минимальное — 5,52 сек, среднее — 5,60 сек.

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

Рис. 23. Время инициализации нейронных сетей

Из графиков, представленных на рисунке 23, видно, что максимальное время инициализации нейронной сети равно 6,12 сек, минимальное — 5,95 сек, среднее — 6,00 сек.

Последним и самым значимым в плане производительности этапом работы программы является непосредственно работа нейронных сетей.

Рис. 24. Время работы нейронных сетей

Изучив графики с рисунка 24 можно сделать вывод, что максимальное время работы одиночной нейронной сети составляет 0,1 046 сек, минимальное — 0,860 сек, среднее — 0,915 сек.

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

Заключение

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

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

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

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

Разработанная система классификации товаров была внедрена и используется для осуществления коммерческой деятельности на предприятии ООО «Алсени».

1. Абрамян М. VisualC# на примерах. — Санкт Петербург: BHV-Санкт-Петербург, 2008 — 496с.

2. Евсеева О. Н., Шамшев А. Б. Работа с базами данных на языке C#. Технология ADO.NET. — Ульяновск: УлГТУ, 2009 — 176с.

3. Комарцова Л. Г., Максимов А. В. Нейрокомпьютеры. — М.: МГТУ им. Н. Э. Баумана, 2004. — 400с.

4. Круглов В. В., Борисов В. В. Искусственные нейронные сети. Теория и практика. — М.: Горячая линия — Телеком, 2001. — 382с.

5. Хабрахабр [Электронный ресурс]: Распараллеливание задач. Случай «идеальной параллельности». Часть 1. Режим доступа: http://habrahabr.ru/post/104 078/ - Загл. с экрана.

6. Хабрахабр [Электронный ресурс]: Распараллеливание задач. Случай «идеальной параллельности». Часть 2. Режим доступа: http://habrahabr.ru/post/104 103/ - Загл. с экрана.

7. Эндрю Троелсен. Язык программирования C# 2010 и платформа.NET 4. — М.: Вильямс, 2010. — 1392с.

8. MSGeeks [Электронный ресурс]: Регулярные выражения в C#. Режим доступа: http://www.msgeeks.ru/?artid=47 — Загл. с экрана.

Приложение

Листинг программы

Модуль Threading

using System;

using System.Collections.Generic;

using System. Linq;

using System. Text;

namespace grabberMolotok. Threading

{

public class ThreadHelper

{

public static List[] SplitList (List list, int splits)

{

int count = list. Count;

if (count < splits)

{

List[] resultList = new List[count];

for (int i = 0; i < count; i++)

{

resultList[i] = new List ();

resultList[i]. Add (list[i]);

}

return resultList;

}

List[] splittedList = new List[splits];

int splitSize = count / splits;

int lastSplit = count% splits;

for (int i = 0; i < splits — 1; i++)

{

splittedList[i] = new List ();

for (int j = 0; j < splitSize; j++)

{

splittedList[i]. Add (list[i * splitSize + j]);

}

}

splittedList[splits — 1] = new List ();

for (int j = 0; j < splitSize + lastSplit; j++)

{

splittedList[splits — 1]. Add (list[splits — 1 * splitSize + j]);

}

return splittedList;

}

public static int CountWorkAmount (List[] list)

{

int counter = 0;

foreach (var l in list)

foreach (var el in l)

counter++;

return counter;

}

}

}

МодульDBWorker

using System;

using System.Collections.Generic;

using System. Linq;

using System. Text;

using System. Data;

using System.Data.SqlClient;

namespace grabberMolotok. DBEngine

{

public class DBEngine

{

string connectionString; //строка подключения

public CategoryTable categoryTable; //таблица категорий

public ImageTable imageTable; //таблица изображений

public SettingsTable settingsTable; //таблица настроек

public DBEngine ()

{

SqlConnectionStringBuilder builder = new SqlConnectionStringBuilder ();

builder.DataSource = «.\SQLExpress» ;

builder.InitialCatalog = «molotokdb» ;

builder.IntegratedSecurity = true;

connectionString = builder. ToString ();

InitTables ();

}

void InitTables ()

{

categoryTable = new CategoryTable (connectionString);

imageTable = new ImageTable (connectionString);

settingsTable = new SettingsTable (connectionString);

}

public void ClearTables ()

{

categoryTable.Clear ();

imageTable.Clear ();

}

}

}

using System;

using System.Collections.Generic;

using System. Linq;

using System. Text;

using System. Data;

using System.Data.SqlClient;

namespace grabberMolotok. DBEngine

{

public class CategoryTable: EngineTable

{

public CategoryTable (string connectionString)

{

this.tableName = «Categories» ;

this.connectionString = connectionString;

}

public void Insert (List categories)

{

lock (this)

{

SqlConnection connection = new SqlConnection (connectionString);

SqlCommand insertCategoryCommand = new SqlCommand («sp_InsertCategory», connection);

insertCategoryCommand.CommandType = CommandType. StoredProcedure;

insertCategoryCommand.UpdatedRowSource = UpdateRowSource. OutputParameters;

GetCommandParameters (insertCategoryCommand.Parameters);

connection.Open ();

foreach (var category in categories)

{

FillCommandParameters (insertCategoryCommand.Parameters, category);

insertCategoryCommand.ExecuteNonQuery ();

}

connection.Close ();

}

}

public void Insert (Category c)

{

lock (this)

{

SqlConnection connection = new SqlConnection (connectionString);

SqlCommand insertCategoryCommand = new SqlCommand («sp_InsertCategory», connection);

insertCategoryCommand.CommandType = CommandType. StoredProcedure;

insertCategoryCommand.UpdatedRowSource = UpdateRowSource. OutputParameters;

GetCommandParameters (insertCategoryCommand.Parameters);

connection.Open ();

FillCommandParameters (insertCategoryCommand.Parameters, c);

insertCategoryCommand.ExecuteNonQuery ();

connection.Close ();

}

}

public List GetAll ()

{

lock (this)

{

SqlConnection connection = new SqlConnection (connectionString);

List categoryList = new List ();

SqlCommand getCommand = new SqlCommand («SELECT * FROM «+ tableName, connection);

connection.Open ();

SqlDataReader reader = getCommand. ExecuteReader ();

while (reader.Read ())

{

categoryList.Add (GetFromReader (reader));

}

connection.Close ();

return categoryList;

}

}

public Category GetById (int id)

{

lock (this)

{

Category c = null;

SqlConnection connection = new SqlConnection (connectionString);

List categoryList = new List ();

SqlCommand getCommand = new SqlCommand («SELECT * FROM «+ tableName + «WHERE id=@id», connection);

getCommand.Parameters.Add (new SqlParameter («@id», id));

connection.Open ();

SqlDataReader reader = getCommand. ExecuteReader ();

if (reader.Read ())

c = GetFromReader (reader);

connection.Close ();

return c;

}

}

#region Мелкие функции

protected Category GetFromReader (SqlDataReader reader)

{

Category c = new Category ();

c.id = (int)reader[" id" ];

c.level = (int)reader[" level" ];

c.name = (string)reader[" name" ];

c.url = (string)reader[" url" ];

c.parentURL = (string)reader[" parentUrl" ];

return c;

}

protected void GetCommandParameters (SqlParameterCollection parameters)

{

parameters.Clear ();

parameters.Add («@id», SqlDbType.Int);

parameters.Add («@level», SqlDbType.Int);

parameters.Add («@name», SqlDbType. VarChar);

parameters.Add («@url», SqlDbType. VarChar);

parameters.Add («@parentUrl», SqlDbType. VarChar);

}

protected void FillCommandParameters (SqlParameterCollection parameters, Category c)

{

parameters[" @id" ]. Value = c. id;

parameters[" @level" ]. Value = c. level;

parameters[" @name" ]. Value = c.name;

parameters[" @url" ]. Value = c. url;

parameters[" @parentUrl" ]. Value = c. parentURL;

}

#endregion

}

}

Модуль Grabber

using System;

using System.Collections.Generic;

using System. Linq;

using System. Text;

using System.Net;

using System. IO;

using System.Windows.Forms;

using System.Text.RegularExpressions;

using System. Threading;

using System. Diagnostics;

using grabberMolotok. Threading;

namespace grabberMolotok

{

class Grabber

{

DBEngine.DBEngine dbEngine; //движок БД

List categories; //категории

int getItemCounter; //счетчик получения товаров

int getItemWorkAmount; //объём работы получения товаров

int getItemThreadCount; //количество потоков получения товаров

public int GetItemThreadCount

{

get { return getItemThreadCount; }

set { getItemThreadCount = value; }

}

int saveImageCounter; //счетчик сохранения изображений

int saveItemWorkAmount; //объём работы сохранения изображений

int saveItemThreadCount; //количество потоков сохранения изображений

public int SaveItemThreadCount

{

get { return saveItemThreadCount; }

set { saveItemThreadCount = value; }

}

#region События

public delegate void AllCategoriesParseCompletedEventHandler ();

public static event AllCategoriesParseCompletedEventHandler AllCategoriesParseCompletedEvent;

public delegate void AllCategoriesImageSaveCompletedEventHandler ();

public static event AllCategoriesImageSaveCompletedEventHandler AllCategoriesImageSaveCompletedEvent;

public delegate void CategoriesGotEventHandler ();

public static event CategoriesGotEventHandler CategoriesGotEvent;

void OnCategoryParseComplete ()

{

getItemCounter++;

if (getItemCounter == getItemWorkAmount)

{

AllCategoriesParseCompletedEvent ();

}

}

void OnCategoryImageSaveComplete ()

{

saveImageCounter++;

if (saveImageCounter == saveItemWorkAmount)

{

if (AllCategoriesImageSaveCompletedEvent ≠ null)

AllCategoriesImageSaveCompletedEvent ();

}

}

#endregion События

public Grabber ()

{

Category.CategoryParseCompletedEvent += new Category. CategoryParseCompletedEventHandler (this.OnCategoryParseComplete);

Category.CategoryImageSaveCompletedEvent += new Category. CategoryImageSaveCompletedEventHandler (this.OnCategoryImageSaveComplete);

dbEngine = new DBEngine. DBEngine ();

categories = new List ();

getItemCounter = 0;

getItemWorkAmount = -1;

getItemThreadCount = 8;

saveImageCounter = 0;

saveItemWorkAmount = -1;

saveItemThreadCount = 8;

}

/// Получает список категорий с молотка

public void GetCategories ()

{

Debug.WriteLine («Получение категорий с сайта»);