Оптимизация иерархических структур с учетом индивидуальных характеристик узлов иерархии

Размещено на http://www.allbest.ru/

Оптимизация иерархических структур с учетом индивидуальных характеристик узлов иерархии

М.В. Губко, А.И. Даниленко

Учреждение Российской академии наук

Институт проблем управления им. В.А. Трапезникова РАН,

Москва, Российская федерация

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

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

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

Опишем общую постановку задачи. Иерархическое меню строится на основе множества элементов N = {1, …, n} (например, команд или ссылок в Интернет-каталоге), к которым необходимо обеспечить доступ посредством меню. Через µ(w) обозначим популярность элемента w  N - вероятность того, что этот элемент потребуется пользователю. Для построения меню проектировщику необходимо решить, на какие категории следует разбить элементы, как далее следует разбить элементы каждой категории на подкатегории и так далее, как назвать категории и в каком виде представить их пользователю, чтобы меню было удобно для использования. Как правило, в качестве критерия удобства принимают среднее время доступа к искомому элементу меню (время одной пользовательской сессии).

Введем необходимые определения на основе [2]. Группой назовем любое подмножество s  N элементов нижнего уровня. Для произвольного узла m любой иерархии H группой этого узла sH(m) назовем множество элементов нижнего уровня, непосредственно или опосредовано подчиненных этому узлу в иерархии H. Так, если при построении каталога сайтов в нем появляется узел с меткой «Спорт», то группой этого узла будет множество спортивных сайтов (к которым можно перейти, выбрав данную категорию). Каждому элементу нижнего уровня µ ставится в соответствие его вес µ(w). Для каждой группы s  N можно определить ее вес как сумму весов входящих в нее элементов нижнего уровня:

Рассмотрим произвольный узел иерархии m с весом , которому подчинены узлы m1, …, mk с весами 1, …, k. Тогда 1 + … + k = s и можно обозначить относительные веса подчиненных узлов за yi = i/s. В задаче оптимизации меню в роли веса выступает популярность пункта меню. В этом случае величины yi определяют условную вероятность выбора пункта i при нахождении в панели меню m.

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

,

где c(y1, …, yk) - затраты узла иерархии с мерами подчиненных узлов y1, …, yk.

В [2] показано, что нижняя оценка затрат оптимальной иерархии с хорошей точностью описывается выражением

оптимизация иерархия пользовательский алгоритм

.

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

В докладе описывается модель, учитывающая индивидуальные характеристик узлов иерархии. Каждому потенциальному узлу иерархии m сопоставляется вектор его индивидуальных характеристик ?(m). К примеру, для иерархических меню этот вектор может характеризовать длину и сложность восприятия заголовка категории. Естественно, эти характеристики влияют на затраты узла в иерархии: теперь затраты записываются в виде c(y1, …, yk, ?(m)).

Часто затраты можно представить в виде суммы из A произведений c1(y1, …, yk)1(?(m)) + ... + cA(y1, …, yk)A(?(m)), когда влияние персональных характеристик сепарабельно. Для этого случая, взяв минимум функций j(?) по всевозможным ?, легко вычислить нижнюю оценку затрат узла, которая является однородной функцией. Подставляя в формулу (1) вместо затрат узла их нижнюю оценку, получаем нижнюю оценку затрат оптимальной иерархии с учетом персональных характеристик узлов. Точность этой оценки определяется шириной разброса параметров узлов.

На базе математической модели предлагается алгоритм построения иерархии, обобщающий описанный в [1] жадный алгоритм, в котором иерархия строится от корня вниз. В нем структура текущего узла выбирается из минимизации локального критерия, представляющего собой оценку затрат дерева, корнем которого является формируемый узел. Идея оценки состоит в том, что затраты дерева представляются в виде суммы затрат его корня и суммы затрат подчиненных корню поддеревьев. При этом в затратах корня точно учитываются индивидуальные характеристики узла, а затраты поддеревьев вычисляются с использованием усредненных характеристик. Варьируя вектор усредненных характеристик аналогично тому, как это делается, например, в жадном алгоритме EG2 построения дерева решений [5] (задачи интеллектуального анализа данных - это еще одно из возможных приложений данной теории), получаем набор «хороших» деревьев, из которых в качестве результата работы алгоритма выбирается наилучшее.

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

Литература

1. Губко М.В., Даниленко А.И. Математическая модель оптимизации структуры иерархического меню // Проблемы управления. № 4. 2010. С. 49-58.

2. Губко М.В. Математические модели оптимизации иерархических структур. М.: ЛЕНАНД. 2006. 264 с.

3. Даниленко А.И. Система автоматизированного проектирования иерархических меню // Сборник трудов конференции «ИТиС - 2010». 2010. C. 200-205.

4. Dumais S.T., Landauer T.K. Using examples to describe categories // Proceedings of the SIGCHI conference on Human Factors in Computing Systems CHI '83. New York, USA: ACM Press. 1983. P. 112-115.

5. Nunez, M. The use of background knowledge in decision tree induction. Machine Learning, 6, 1991. P. 231-250.

Размещено на Allbest.ru