Using Regression Analysis Methods for Building an Optimal Model of Dependency Between the Queue Size and Hurst Exponent when Transforming a Self-Similar Input Packet Flow into a Flow with Exponential Distribution

Full Text

Одной из проблем телекоммуникационных сетей является неэффективное использование узловых и канальных ресурсов при обслуживании самоподобного трафика. Важным параметром информационного обмена, влияющим на качество обслуживания пользователей, а также на производительность сети, служит вероятность потери сообщений за счет переполнения буферных запоминающих устройств (БЗУ) в узлах коммутации. Основной причиной, ведущей к переполнению буфера, является наличие долговременной зависимости в сетевом трафике, обусловленной его самоподобием, вследствие чего суммарный кумулятивный эффект в широком диапазоне задержек может значительно отличаться от того, который наблюдается в кратковременно зависимом процессе [1]. Для устранения самоподобия сетевого трафика используются различные модели и устройства преобразования трафика [2], одной из них является асинхронная имитационная модель, описанная в [2], для которой существует программная реализация [3]. Важным показателем работы данной модели является размер очереди, используемый в процессе преобразования трафика. Поскольку из-за ограниченности ресурсов ЭВМ очередь не может иметь бесконечный размер, возникает задача предсказания размера очереди в зависимости от меры самоподобия входного трафика, в качестве которой выступает показатель Херста. Постановка задачи С использованием методов машинного обучения необходимо разработать модель для предсказания размера очереди в зависимости от показателя Херста на основании данных, полученных при выполнении преобразования входного самоподобного потока, распределенного по закону Парето в поток, имеющий экспоненциальное распределение. Так как машинное обучение включает в себя множество методов, на начальном этапе для дальнейшего сравнения с более сложными моделями,построенными, в частности, с использованием методов глубокого обучения, целесообразно рассмотреть только методы парного регрессионного анализа, изотонической регрессии и метод опорных векторов. Введем метрику качества (штраф), которая является комплексным показателем и учитывает как потери пакетов в процессе преобразования трафика, так и неэффективное использование буферного пространства. Проведем выбор наилучшей модели для осуществления предсказания размера очереди в зависимости от показателя Херста входного потока с помощью следующих метрик качества: - коэффициент детерминации; - среднеквадратичная ошибка регрессии; - средняя абсолютная ошибка; - величина штрафа. Решение задачи Имитационная модель, представленная в [2], обеспечивает преобразование входного потока пакетов, который является заведомо самоподобным, в заданный закон распределения, в частности в экспоненциальный. Объектом преобразования является одномерная плотность распределения интервалов времени между пакетами входного потока. С использованием разработанной модели проведены 1,1·103 испытаний и получены данные для статистического анализа. Поскольку величина потерь в общем случае не дает никаких сведений об эффективности использования очереди в процессе преобразования трафика, для оценки качества полученной модели введем метрику качества - штраф, которая учитывает не только величину потерь, но и нерациональное использование буферной памяти. Пусть i y - истинное значение размера очереди в выборке; ˆi y - предсказанное значение размера очереди в выборке, соответствующее истинному значению . i y Если ˆ , ii yy > будем штрафовать обучаемую систему на величину ( ) ˆ . ii yy + b- Если ˆ , ii yy ≥ величина штрафа будет зависеть от величины разности ˆ , i ii yy ∆= - при i ∆ ≥∆ ве- личина штрафа составит ( ) - b ∆ -∆ , i и 0 - в противном случае. Проиллюстрируем сказанное примером (рисунок 1). Рассмотрим три случая, каждому из которых соответствуют истинные значения размеров очереди 1, y 2 y и 3. y Допустим, предсказанные значения размеров очереди в каждом из трех случаев совпадают, иными словами, 12 ˆˆ yy = = 3 ˆˆ. yy = Тогда, в первом случае 1 ˆ yy > и величина штрафа определяется как ( ) 1 ˆ . yy + b- Во втором случае ˆ y -∆≤ 2 y ≤∆ и величина штрафа равна 0, предполагается, что ˆ y - предпочтительный размер очереди для 2 . y В третьем случае 3 ˆ , yy < -∆ величина штрафа определяется из выражения ( ) 3 ˆ . yy - b - -∆ Таким образом, величина штрафа будет вычисляться из равенства: ( ) ( ) 0. ˆˆ ,, ˆˆ ,, , åñëè åñëè â ïðîòèâíîì ñëó÷àå i ii i ii ii yy yy p yy yy + + b - >  = b - -∆ - >∆    Общий штраф для всех испытаний определяется как среднее арифметическое между штрафами по каждому испытанию 1 1 , n i i pp n = = ∑ где n - число испытаний. В процессе обучения модели необходимо обеспечить минимальное значение штрафа для всех испытаний, иными словами, min. p→ Представленная система штрафов предусматривает введение трех гиперпараметров: , + b - b и , ∆ где 0 +- b >b > и 0. ∆> Установим их значение следующим образом: 03 ,, - b= 1, + b= 50. ∆= Рисунок 1. График зависимости величины штрафа от объема буфера Первоначальный анализ данных На рисунке 2 показана диаграмма рассеивания зависимости размера очереди от показателя Херста. Из рисунка отчетливо видно, что существует определенная корреляция между показателем Херста и объемом буферной памяти. Уровень значимости в статистике является важным показателем, отражающим степень уверенности в точности, истинности полученных (прогнозируемых) данных. Большой объем проведенных испытаний позволяет не вычислять p - уровень значимости, поскольку, как показывает практика, в данном случае p - значение гораздо меньше 0,05 [4]. Предварительно сгруппируем испытания по значению показателя Херста. Выделим 30 групп для оценки разброса размера очереди. Построим box-plot для каждой группы. Из рисунка 3 следует, что наибольшее количество выбросов сверху наблюдается для первых 10 групп, что соответствует показателю Херста, близкому к 0,5. Следовательно, при этих значениях показателя Херста возможно появление потерь из-за того, что требуемый объем буфера будет больше предсказанного. Для групп с 28 по 30 наблюдаются значительные выбросы снизу, что приводит к неэффективному использованию буферной памяти. Регрессионный анализ Машинное обучение - это подраздел искусственного интеллекта, в котором изучаются и исследуются алгоритмы, способные обучаться без прямого программирования. Линейная регрессия является типичным представителем алгоритмов машинного обучения [5]. Выделяют следующие задачи, решаемые машинным обучением: обучение с учителем, обучение без учителя, обучение с подкреплением, активное обучение, трансфер знаний и т. д. Регрессия (как и классификация) относится к классу задач обучения с учителем, когда по заданному набору признаков наблюдаемого объекта необходимо спрогнозировать некоторую целевую переменную. Как правило, в задачах обучения с учителем опыт E представляется в виде множества пар признаков и целевых переменных: ( ) { } 1 , ... . ii i D xy n = = В случае линейной регрессии признаковое описание объекта - это действительный вектор , m xR ∈ где R - множество действительных чисел, а целевая переменная - это скаляр . yR ∈ Самой простой мерой качества L для задачи регрессии является ( ) ( ) 2 ˆˆ ,, Lyy y y = - где ˆ y - это оценка реального значения целевой переменной [5; 6]. Восстановим зависимость, представленную на рисунке 2, используя регрессионный анализ, основу которого составляет метод наименьших квадратов (МНК), где в качестве уравнения регрессии берется функция ( ) y fx = - такая, чтобы сумма квадратов разностей удовлетворяла условию ( ) 2 1 min ˆ . n ii i S yy = = -→ ∑ С использованием методов парного регрессионного анализа проведем статистический анализ данных, полученных при выполнении преобразования входного самоподобного потока, распределенного по закону Парето в поток, имеющий экспоненциальное распределение. Рассмотрим методы, наиболее широко используемые на практике, позволяющие находить объем буфера для входного потока с заданным показателем Херста. Рисунок 1. График зависимости величины штрафа от объема буфера Рисунок 2. Диаграмма рассеивания зависимости размера очереди от показателя Херста Рисунок 3. Box-plot 30 групп анализируемых данных Таблица 1. Метрики качества линейной регрессионной модели Коэффициент детерминации R2 0,584792 Среднеквадратичная ошибка регрессии RMSE 130,908538 Средняя абсолютная ошибка MAE 96,808209 Величина штрафа p 55,710275 Линейный регрессионный анализ В этом случае взаимосвязь между показателем Херста H и размером очереди ˆ y определяется согласно линейному уравнению 01 ˆ . y b bH = + При помощи метода наименьших квадратов получим уравнение регрессии 611 18263 1077 4 5 42810 ,. ˆ , y H + = - (1) В таблице 1 приведены метрики качества полученной линейной регрессионной модели применительно к исходным данным. Полученное значение коэффициента детерминации говорит о том, что только около 58 % случаев изменения показателя Херста приводят к изменению размера очереди в рамках линейной модели. Полученный результат является неудовлетворительным для практики, поэтому в простейшем случае имеет смысл рассмотреть другие способы, воспользовавшись методами линеаризации нелинейных зависимостей. В результате нелинейная зависимость может быть приведена к линейной, и далее можно использовать метод наименьших квадратов. Гиперболическая регрессия Для гиперболической регрессии взаимосвязь между H и ˆ y может быть описана как 1 0 ˆ . b yb H = + Линеаризация гиперболического уравнения достигается заменой 1/H на новую переменную, которую обозначим через z [4]. Тогда уравнение гиперболической регрессии примет вид 01 ˆ . y b bz = + Уравнение регрессии получим при помощи метода наименьших квадратов: 875 438048 489 379751 ,, ˆ . H y - = (2) В таблице 2 приведены метрики качества полученной гиперболической регрессионной модели применительно к исходным данным. Полученное значение коэффициента детерминации говорит о том, что около 45 % случаев изменения показателя Херста приводят к изменению размера очереди. Поскольку это гораздо хуже показателя линейной модели, имеет смысл рассмотреть модель гиперболической регрессии вида 01 1 ˆ . y b bH = + При помощи метода наименьших квадратов получаем уравнение регрессии вида 1 0 039996 0 039720 ˆ . ,, y H - = (3) В таблице 3 отражены метрики качества измененной гиперболической регрессионной модели применительно к исходным данным. Полученное значение коэффициента детерминации около 59 %, что несколько лучше линейной модели. Таблица 2. Метрики качества гиперболической ре- грессионной модели Коэффициент детерминации R2 0,453263 Среднеквадратичная ошибка регрессии RMSE 150,218740 Средняя абсолютная ошибка MAE 110,511548 Величина штрафа p 63,841249 Таблица 3. Метрики качества измененной гиперболи- ческой модели Коэффициент детерминации R2 0,591293 Среднеквадратичная ошибка регрессии RMSE 223,798030 Средняя абсолютная ошибка MAE 77,543626 Величина штрафа p 39,537133 Степенная регрессия В случае степенной регрессии взаимосвязь между H и ˆ y имеет вид 1 0 ˆ . b y bH = Данное уравнение является нелинейным по коэффициенту 1 b и относится к классу моделей регрессии, которые можно привести [4] к линейному виду ln y = 01 = + ln ln . bbH Показательная функция является внутренне линейной, поэтому оценки неизвестных параметров ее линеаризованной формы можно найти также при помощи метода наименьших квадратов. Уравнение регрессии имеет вид 3 596636 401 143661 , . ˆ , H y = (4) В таблице 4 показаны метрики качества полученной степенной регрессионной модели применительно к исходным данным. Полученное значение 70 % гораздо лучше коэффициента детерминации линейной модели. Таблица 4. Метрики качества степенной регрессионной модели Коэффициент детерминации R2 0,699138 Среднеквадратичная ошибка регрессии RMSE 128,675573 Средняя абсолютная ошибка MAE 72,823850 Величина штрафа p 53,042530 Экспоненциальная регрессия Для показательной регрессии взаимосвязь H и ˆ y имеет вид 1 0 ˆ . bH y be = Данное уравнение является нелинейным по коэффициенту 1 b и относится к классу моделей регрессии, которые, согласно [4], также приводятся к линейному виду ˆ ln y =01 ln ln . b Hb = + Показательная функция является внутренне линейной, поэтому оценки неизвестных параметров ее линеаризованной формы можно найти при помощи классического метода наименьших квадратов. Уравнение регрессии имеет вид 5 089127 2 926343 , ˆ ,. H e y = (5) В таблице 5 приведены метрики качества экспоненциальной регрессионной модели применительно к тем же исходным данным. Полученное значение коэффициента детерминации говорит о том, что около 74 % случаев изменения показателя Херста приводят к изменению размера очереди в рамках экспоненциальной модели, что является наилучшим результатом при использовании методов парного регрессионного анализа. Такой же результат дает и анализ величины штрафа. Проведем сравнение полученных результатов. Графики уравнений регрессии (1)-(5) представлены на рисунке 4. Очевидно, что экспоненциальная регрессия и степенная регрессия наиболее близко описывают зависимость между показателями Херста и объемом буфера. Тривиальные модели парной регрессии, описанные выше, недостаточно хорошо описывают зависимость размера очереди от показателя Херста, поэтому произведем усложнение модели. Одним из возможных вариантов является изотоническая регрессия. Изотоническая регрессия В статистике изотоническая регрессия или монотонная регрессия - это метод подгонки линии свободной формы к последовательности наблюдений при следующих ограничениях: подобранная линия свободной формы должна быть неубывающей (или неувеличивающейся) на области определения и должна лежать как можно ближе к наблюдениям [11]. В процессе построения изотонической кривой решается следующая задача [11]: ( ) 2 ˆ min, ii i i wy y -→ ∑ где значение весового коэффициента 0. i w > Это дает вектор, который состоит из неубывающих элементов, наиболее близких по среднеквадрати- ческой ошибке. На практике этот список элементов образует кусочно-линейную функцию. Выполним обучение модели изотонической регрессии с использованием пакета scikit-learn языка программирования Python 3 [7]. Построим график, соответствующий модели, построенной с помощью изотонической регрессии, - см. рисунок 5. В таблице 6 приведены метрики качества полученной регрессионной модели применительно к исходным данным. Полученное значение коэффициента детерминации говорит о том, что около 92 % случаев изменения показателя Херста приводят к изменению размера очереди в рамках данной модели, что гораздо лучше моделей, построенных на основе методов парной регрессии. При этом величина штрафа для изотонической регрессии в два раза меньше соответствующей величины для парной регрессии. Таблица 5. Метрики качества экспоненциальной регрессионной модели Коэффициент детерминации R2 0,745779 Среднеквадратичная ошибка регрессии RMSE 112,443773 Средняя абсолютная ошибка MAE 65,199678 Величина штрафа p 46,768626 Таблица 6. Метрики качества изотонической регрессии Коэффициент детерминации R2 0,928199 Среднеквадратическая ошибка регрессии RMSE 54,437567 Средняя абсолютная ошибка MAE 39,500659 Величина штрафа p 21,269167 Метод опорных векторов Метод опорных векторов, или SVM (от англ. Support Vector Machines) - это линейный алгоритм, используемый в задачах классификации и регрессии (для задач регрессии он носит название SVR - Support Vector Regression). Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки оптимальным способом [8-10]. Рисунок 4. Сравнительный анализ результатов парного регрессионного анализа Рисунок 5. Построение изотонической кривой применительно к набору данных Метод опорных векторов максимизирует отступы объектов, что тесно связано с минимизацией вероятности переобучения. При этом он позволяет очень легко перейти к построению нелинейной разделяющей поверхности благодаря ядерному переходу [8; 9]. Выполним обучение модели на основе SVR. Нелинейный характер зависимости между показателем Херста и размером очереди говорит о необходимости выбора радиально-базисного ядра для модели SVR. Обучение данной модели произведено с использованием пакета scikit-learn языка программирования Python 3 [10]. На рисунке 6 представлен график зависимости между размером очереди и показателем Херста, соответствующий обученной модели SVR. В таблице 7 приведены метрики качества полученной модели, использующей SVR. Полученное значение коэффициента детерминации - около 90 %, что немного хуже, чем у метода с использованием изотонической регрессии. Однако величина штрафа у этого метода меньше, чем в случае применения изотонической регрессии. Исходя из характера зависимости между размером очереди QS и показателем Херста H, целесообразно при использовании SVR оценивать не QS, а значение 1 ln ( ), QS + переходя, таким образом, к спрямляющему пространству. Выполним обучение модели на основе SVR с использованием пакета scikit-learn языка программирования Python 3 [10]. На рисунке 7 представлен график зависимости размера очереди и показателя Херста, соответствующий обученной модели методом опорных векторов с переходом в спрямляющее пространство. В таблице 8 приведены метрики качества полученной модели, использующей SVR в логарифмическом масштабе, применительно к исходным данным. Полученное значение коэффициента детерминации порядка 92 % практически совпадает с методом изотонической регрессии. Однако величина штрафа в этом случае меньше, чем для метода SVR. Таким образом, переход к спрямляющему пространству не приводит к улучшению качества обучения на основании значений введенной метрики качества, которой является штраф. Таблица 7. Метрики качества модели опорных векторов Коэффициент детерминации R2 0,901167 Среднеквадратичная ошибка регрессии RMSE 63,868307 Средняя абсолютная ошибка MAE 52,506259 Величина штрафа p 18,374489 Таблица 8. Метрики качества модели опорных векто- ров в логарифмическом масштабе Коэффициент детерминации R2 0,923960 Среднеквадратичная ошибка регрессии RMSE 56,021631 Средняя абсолютная ошибка MAE 39,583393 Величина штрафа p 21,724137 Таблица 9. Сравнительная характеристика методов регрессии при 0,5 < H < 1 Коэффициент детерминации R2 Среднеквадратич- ная ошибка регрес- сии RMSE Средняя абсолют- ная ошибка MAE Величина штрафа p Линейная регрессия 0,584792 130,908538 96,808209 55,710275 Гиперболическая регрессия 1 0,453263 150,218740 110,511548 63,841249 Гиперболическая регрессия 2 0,591293 223,798030 77,543626 39,537133 Степенная регрессия 0,699138 128,675573 72,823850 53,042530 Экспоненциальная регрессия 0,745779 112,443773 65,199678 46,768626 Изотоническая регрессия 0,928199 54,437567 39,500659 21,269167 Метод опорных векторов SVR 0,901167 63,868307 52,506259 18,374489 Метод опорных векторов в логариф- мическом масштабе 0,923960 56,021631 39,583393 21,724137 Сравнительный анализ моделей Результаты исследования представлены в таблице 9 для оценки и выбора наилучшего метода в интересах предсказания размера очереди по значению показателя Херста. На основании данных сводной таблицы можно сделать вывод, что наилучшей предикативной способностью на основании введенной метрики качества является модель, построенная с использованием метода опорных векторов. В рамках данного исследования можно заключить, что усложнение SVR путем перехода в спрямляющее пространство не приводит к улучшению качества обучения. Рисунок 6. График, соответствующий модели, обученной методом опорных векторов Рисунок 7. График, соответствующий модели, обученной методом опорных векторов, применительно к набору данных Выводы Таким образом, исследованы восемь моделей, позволяющие предсказать размер очереди при преобразовании входного потока, имеющего распределение Парето, в выходной поток с экспоненциальным распределением в зависимости от показателя Херста входного потока, построенные на основании методов машинного обучения. Поскольку величина потерь в общем случае не дает никаких сведений об эффективности использования очереди в процессе преобразования трафика, для оценки качества полученной модели введен штраф, учитывающий не только величину потерь, но и нерациональное использование буферной памяти. Каждая модель исследована с использованием следующих метрик качества: коэффициента детерминации, среднеквадратичной ошибки регрессии, средней абсолютной ошибки, величины штрафа. Лучшими по выбранным метрикам качества являются модели, которые используют методы изотонической регрессии и опорных векторов.

About the authors

G. I Linets

North-Caucasus Federal University

Email: kbytw@mail.ru
Stavropol, Russian Federation

R. A Voronkin

North-Caucasus Federal University

Email: kbytw@mail.ru
Stavropol, Russian Federation

S. V Govorova

North-Caucasus Federal University

Email: kbytw@mail.ru
Stavropol, Russian Federation

V. P Mochalov

North-Caucasus Federal University

Email: kbytw@mail.ru
Stavropol, Russian Federation

I. S Palkanov

North-Caucasus Federal University

Email: kbytw@mail.ru
Stavropol, Russian Federation

References

Supplementary files