Удосконалений метод х2-кластеризації та його застосування до аналізу аварійності на автомобільному транспорті

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

Удосконалений метод х²-кластеризащї та його застосування доаналізу аварійності на автомобільному транспорті

Ханін О.Г. к.ф.-м.н., Східноєвропейський національний університет ім. Лесі Українки; Лотиш В.В., к.т.н, Гуменюк П.О., к.т.н, Гуменюк Л.О. к.т.н. Луцький національний технічний університет

Анотація

Існує чимало методів кластеризації даних, але вони мають ряд недоліків, зокрема, з одного боку, це - неоднозначність розбиття масиву даних на групи, а з іншого - неможливість оцінити ступінь однорідності об'єктів, що належать одному і тому ж кластеру. Мета цієї роботи - розробити метод кластерного аналізу багатовимірних даних різної природи, який забезпечить однозначність розбиття набору незалежних вибірок на кластери, що не перетинаються, так, щоб ймовірність помилкової кластеризації не перевищувала певного наперед заданого рівня. Метод кластеризації ґрунтується на використанні критерію узгодженості X.

З іншої сторони, проблема аварійності на автомобільному транспорті є достатньо гострою у вітчизняних реаліях, оскільки рівень ДТП з потерпілими значно перевищує середній європейський. В той же час, кластеризація регіонів України за видами дорожньо-транспортних пригод з постраждалими, їх причинами та винуватцями дозволить зрозуміти спільні регіональні фактори, що впливають на рівень аварійності, визначити та впровадити кращі практики її запобігання. Саме тому представляється актуальним застосування запропонованого методу до аналізу аварійності на автомобільному транспорті в Україні. Розроблений метод реалізований програмно та застосований до порівняльного аналізу рівня аварійності на автомобільному транспорті по регіонах України.

Ключові слова: кластерний аналіз, біноміальний розподіл, довірчий інтервал, критерій узгодженості у², перевірка статистичних гіпотез, похибка кластеризації, дорожньо-транспортні пригоди з постраждалими.

Аннотация

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

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

Ключевые слова: кластерный анализ, биномиальное распределение, доверительный интервал, критерий согласия х², проверка статистических гипотез, погрешность кластеризации, дорожно-транспортные происшествия с пострадавшими.

Abstract

There is a large variety of methods for data clustering, but all of them have numerous defects. On the one hand, it is the ambiguity of splitting the data array into groups, and on the other the impossibility to assess the degree of homogeneity of objects belonging to the same cluster. The purpose of thH work is to develop the method for cluster analysis of multidimensional data of a different nature, which will ensure unambiguity of splitting a set of independent samples into clusters that do not intersect, so that the probability of false clustering does not exceed a certain predetermined level. The clustering method is based on the use of the X consistency criterion.

Besides, the problem of accidents on road transport is quite acute in the domestic realities, since the level of accidents with victims significantly exceeds the average European. At that, the clustering of the regions of Ukraine according to the types of road accidents with the victims, their causes and culprits will help to understand the general regional factors affecting the accident rate, to identify and implement the best practices for its prevention. That is why the application of the proposed method to the analysis of accidents on road transport in Ukraine is quite relevant. The developed method is implemented programmatically and applied to a comparative analysis of the accident rate in road transport in the regions of Ukraine.

Keywords: cluster analysis, binomial distribution, confidence interval, x² consistency criterion, verification of statistical hypotheses, clustering error, road traffic accidents with victims.

кластеризація автомобільний транспорт пригода

Постановка проблеми. Кластеризація, тобто розбиття даних на однорідні, в певному розумінні, групи, представляє собою поширений метод аналізу даних шляхом зменшення розмірності їх масиву, допомагає виявити спільні та відмінні риси об'єктів дослідження [1]. Цей метод знайшов застосування при розгляді багатовимірних систем в техніці, економіці, фінансах, маркетингу, соціології, психології, медицині, тощо. Однак, головними його недоліками є, як правило, неоднозначність розбиття залежно від вибору першого (базового) об'єкту, з якого починається процес кластеризації, та відсутність міри якості кластеризації даних. Тому, головним чином, цей метод використовується як метод попереднього, розвідувального аналізу, який дозволяє на якісному рівні побачити певні закономірності і сформулювати гіпотези, що потребують подальшого дослідження. Задачею авторів була побудова такого методу кластерного аналізу, який би, по можливості, був позбавлений цих недоліків, тобто відрізнявся однозначністю кластеризації та забезпечував певну наперед задану ймовірність її похибки. З іншого боку, оскільки проблема аварійності на автомобільному транспорті в Україні в останні роки є надзвичайно гострою [2 - 4] та її рівень суттєво перевищує середньоєвропейський [4], представляє інтерес застосування запропонованого алгоритму до регіонального аналізу причин, видів та винуватців ДТП з постраждалими на автотранспорті в Україні.

Метою роботи було, ґрунтуючись на методології порівняння емпіричних розподілів за критерієм узгодженості %² [5], запропонувати та обґрунтувати удосконалений метод кластерного аналізу, який би забезпечив однозначність розбиття набору незалежних вибірок на кластери, що не перетинаються, так, щоб ймовірності помилкового віднесення вибірок до різних кластерів не перевищувала певного наперед заданого рівня; за допомогою розглянутого методу провести кластерний аналіз регіонів України за структурою ДТП з постраждалими на автомобільному транспорті за причинами, видами та винуватцями.

Запропонований метод кластерного аналізу ґрунтується на критерії узгодженості %² [5], а ідея його застосування до задач кластерного аналізу в галузі маркетингу була представлена у роботі [6]. Однак, як і решта методів кластерного аналізу, цей метод мав неоднозначність результуючого розбиття, а також відсутність конкретної оцінки ймовірності помилкового віднесення до різних кластерів однорідних об'єктів. В даній роботі представлено удосконалений метод кластеризації багатовимірних даних, який дає однозначні результати, а також відповідні оцінки похибки кластеризації. На основі цього алгоритму в середовищі Delphi створена програма, яка застосована до аналізу значного масиву даних, пов'язаних з рівнем аварійності на автомобільному транспорті по регіонах України.

Аналіз досліджень. Як відомо, кластеризація - це процес розбиття заданої вибірки об'єктів на підмножини, що не перетинаються, які називаються кластерами, так, щоб кожен кластер складався зі схожих об'єктів, а об'єкти різних кластерів суттєво відрізнялися [7]. Термін «кластерний аналіз» уперше ввів Трайон (Tryon) [8] у 1939 році. Відтоді розроблено чимало методів кластерного аналізу, певну класифікацію яких наведено у багатьох роботах, зокрема [2,9 -11]. Згідно цієї класифікації, запропонований нами метод відноситься до ієрархічних методів дівізівної кластеризації (Divisive Methods) із чітким багатоетапним алгоритмом. Заздалегідь невідомо, на скільки кластерів буде розбита сукупність багатовимірних даних. Вхідні дані для застосування запропонованого методу кластеризації повинні бути представлені у вигляді таблиці «Ознака - Кількість її спостережень».

Такий авторитет у галузі аналізу даних, як Тьюкі (Tukey) [12] поділяє статистичний аналіз на два етапи: розвідувальний та підтверджуючий. Перший етап включає перетворення даних спостережень і способи їх наочного представлення, що дозволяє виявити внутрішні законом ірності, які проявляються в даних, тобто, фактично, сформулювати певні гіпотези. На другому етапі застосовуються традиційні статистичні методи оцінки параметрів і перевірки гіпотез. Загальноприйняті методи кластеризації є потужними засобами саме розвідувального аналізу [13]. Запропонований нами метод відрізняється тим, що забезпечує певну однозначність процесу кластеризації, і поєднує у собі обидва етапи. Він, завдяки розбиттю даних на підмножини, які складаються з багатовимірних даних, із ймовірнісними розподілами, схожими між собою за критерієм узгодженості Пірсона, надає інформацію для подальшого формулювання гіпотез щодо змістовних причин схожості чи відмінності даних, та одночасно дає можливість оцінити ймовірність помилкового віднесення «схожих» об'єктів до різних кластерів, тобто зробити певні статистичні висновки.

Однією з цілей кластеризації є стиснення великих обсягів даних: замість дослідження всього їх неосяжного масиву можна розглядати та порівнювати між собою по одному типовому представнику від кожного кластеру [7]. Безумовно, це дає можливість виявити глибинні причини, що розділяють представників різних кластерів. Оскільки нас цікавили саме такі причини регіональних відмінностей рівня аварійності на автомобільному транспорті в Україні, ми вирішили застосувати запропонований нами метод кластерного аналізу до цієї актуальної задачі.

Методологія досліджень. Припустимо, що спостерігаються m незалежних вибірок об'ємів n1, n2, ..., nm, відповідно, з генеральних сукупностей, елементи яких приймають одне з r можливих значень. В якості таких значень можуть виступати певні якісні ознаки (групи факторів), наприклад, групи причин скоєння ДТП, або належність до певного інтервалу для кількісних ознак (в останньому випадку значення кількісних ознак повинні бути розбиті на r інтервалів, що не перетинаються). Нехай для кожної спостереженої вибірки побудовано емпіричний розподіл частот по групах.

Наприклад, в таблиці 1 наведені розподіли частот по п'ятьох групах факторів, отримані за чотирма вибірками.

В один кластер хотілося б об'єднати ті вибірки, в яких співпадають теоретичні розподіли, тобто розподіли генеральних сукупностей, яким вони належать. Однак, на практиці теоретичні розподіли невідомі. Методологія попарного порівняння емпіричних розподілів за допомогою критерію х² була розглянута нами в [5], але вона призводить до неоднозначного результату кластерного аналізу залежно від вибору еталонного розподілу на кожному кроці кластеризації.

Таблиця 1. Розподіл вибіркових частот по групах

Модифікуємо запропонований у роботі [6] алгоритм кластеризації так, щоб на кожному новому кроці кластеризації в якості еталонної вибірки обиралася вибірка, найбільша за об'ємом. Розподіл цієї вибірки будемо називати еталонним вибірковим розподілом. Відповідно, генеральну сукупність, з якої узята ця вибірка будемо також називати еталонною, а її розподіл - еталонним теоретичним розподілом. Так, в нашому прикладі на першому кроці в якості еталонної оберемо вибірку 2. Об'єм еталонної вибірки за таблицею 1 становить п=681. Будемо по черзі розглядати попадання спостереження з еталонної вибірки в певну групу як «успіх», а в решту - як «невдачу». Тоді ми матимемо справу з біноміальними розподілами, для теоретичних ймовірностей яких легко побудувати двосторонній асимптотичний довірчий інтервал будь-якої наперед заданої надійності [14].

Наприклад, попадання значення еталонної вибірки в групу 1 будемо вважати «успіхом», а в одну з решти груп - «невдачею». Вибіркова оцінка невідомого стандартного відхилення ймовірності «успіху» для еталонної генеральної сукупності з п=681

Тоді права межа довірчого інтервалу надійності 99% становить

межа

для двостороннього розподілу Стьюдента з п-1=680 ступенями вільності (в ЕхсеІ-2010 його можна знайти за допомогою функції «СТЬЮДЕНТ.ОБР.2Х(0,01;680)»).

Тобто, з надійністю 99% теоретична ймовірність того, що довільно обраний елемент еталонної генеральної сукупності належить групі 1, знаходиться в інтервалі (0,23; 0,32).

Так само побудуємо довірчі інтервали надійності 99% для теоретичних ймовірностей, що відповідають іншим групам (таблиця 2).

Таблиця 2. Межі довірчих інтервалів надійності 99% для невідомих теоретичних ймовірностей еталонної генеральної сукупності

X - відстань між емпіричним та теоретичним розподілом знаходять за формулою [15]

Якщо спостережена вибірка належить саме тій генеральній сукупності, теоретичні ймовірності якої розглядаються, то величина (1) має асимптотичний х² - розподіл з г-1 ступенями вільності. Залишається порівняти отриману відстань (1) з критичним значенням, що відповідає певному рівню істотності а. Якщо відстань не перевищує критичного значення (в Excel 2010 його можна знайти за допомогою функції ХИ2.ОБР.ПХ(а;г-1)) приймають рішення про справедливість нульової гіпотези, що вибірковий розподіл співпадає з теоретичним, у протилежному випадку - приймають альтернативну гіпотезу.

Однак, в нашому випадку ймовірності р- невідомі, проте відомі довірчі інтервали для них (див. табл. 2), побудовані за еталонною вибіркою. Замінимо pi на такі значення з довірчих відрізків А- (тобто з довірчих інтервалів, разом із їх кінцями), які зроблять значення виразу (1) найменшим з можливих. Тим самим при перевірці гіпотези про узгодженість розподілів ми мінімізуємо помилку 1 - то роду. Таким чином, замість відстані (1) будемо розглядати відстань

Будемо вважати, що вибірки належать одному кластеру, якщо побудована для них відстань (2) до еталонного теоретичного розподілу не більша за критичне значення ХЈр⁼ХИ2.0БР.ПХ(а;г-1).

Зауважимо, що довірчі відрізки не повинні містити нульові значення. Якщо це трапилося, тобто значення відносних частот для деяких категорій дуже малі, варто об'єднати ці категорії з іншими.

Якщо формування першого кластеру закінчено, то в якості еталонної обирається вибірка найбільшого об'єму з числа тих, що не попали у першій кластер, та процес кластеризації продовжується, і т.д.

Визначення вибірки найбільшого об'єму в якості еталонної призводить до звуження довірчого інтервалу, тобто збільшення точності оцінювання. Крім того, якщо на кожному кроці створення нового кластеру існує лише одна вибірка з найбільшим об'ємом, то результат кластеризації стає однозначним.

В нашому прикладі на першому кроці вибірки 1, 3, 4 почергово за формулою (2) порівнюються з критичним значенням Хкр⁼ХИ2.ОБР.ПХ(0,01 ;2)~9,21, де значення беруться з таблиці 1, а довірчі відрізки А - , побудовані за еталонною вибіркою (в нашому випадку - вибіркою 2) з таблиці 2. Знаходження мінімального значення виразу (2) можна здійснити за допомогою інструменту Excel «Пошук розв'язків». Процес знаходження мінімуму виразу (2) спроститься, якщо зауважити, що

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

Нехай всі довірчі інтервали, які ми будували для невідомих ймовірностей еталонного теоретичного розподілу (див., наприклад, табл. 2), мають однакову надійність, рівну у. Точні значення ймовірностей еталонного теоретичного розподілу нам принципово невідомі. Розглянемо подію А, що усі г ймовірностей еталонного теоретичного розподілу попадуть у відповідні довірчі інтервали. Оскільки відповідні довірчі інтервали будуються незалежно, то ймовірність Р(А)= у^г . Нехай подія В означає, що за критерієм X помилково прийняте рішення, що не всі генеральні сукупності мають однакові розподіли, хоча в дійсності всі вони однорідні. Ймовірність цієї події - це рівень істотності а, на якому перевіряється гіпотеза про однорідність генеральних розподілів, з яких узяті спостережені вибірки. Для визначеності будемо обирати а=1-у. Помилка кластеризації відбувається, коли наступає подія А або одночасно наступають події А та В. Оскільки ці події несумісні, то ймовірність помилки кластеризації не більша за

Якщо прийняти а=1-у, то ймовірність помилки кластеризації не перевищуватиме величини 1-y^r+l.

Якщо ми хочемо задати певний рівень похибки кластеризації р, то відповідне значення надійності довірчих інтервалів у, а отже і значення рівня істотності а=1-у, що забезпечують похибку кластеризації не вищу за р, можна знайти з рівняння

звідки

Скажімо, в нашому прикладі (таблиця 1) для рівня похибки кластеризації р=0,05 необхідно будувати довірчі інтервали надійності у=0,95^(1/б)«0,99, в цьому випадку рівень істотності при перевірці за критерієм х² гіпотези про однорідність генеральних розподілів буде вважатися рівним а =1-у ~ 0,01.

Результати. Реалізація запропонованого методу здійснена в інтегрованому середовищі розробки програмного забезпечення для Microsoft Windows, Mac OS, iOS і Android на мові Delphi (RAD - Rapid Application Development) Delphi XE6. Бібліотека наявних компонент дозволила реалізувати введення даних, проведення кластеризації та виведення отриманого результату в одному додатку (рис. 1).

Рис 1. Додаток в режимі введення даних

Початкове введення даних для кластеризації запропонованим методом здійснюється в самому додатку. Також передбачено експорт підготовлених даних з таблиці Microsoft Excel.

Для налаштування додатку необхідно задати масштаб (коефіцієнт множення), номер еталонної категорії та рівень значущості в інтерактивному режимі.

Результат, отриманий внаслідок кластеризації, представляється у вигляді схеми (рис. 2), де представлено номери отриманих кластерів та номери категорій (рядків), які входять до даного кластера.

Запропоноване представлення результатів дозволяє наочно спостерігати розподіл даних по кластерах.

Вихідні дані та результати кластеризації зберігаються в таблиці Microsoft Excel. Також надається можливість збереження результатів кластеризації в графічному форматі.

Рис 2. Представлення результатів кластеризації

Для комфортного використання передбачено зміну мови інтерфейсу додатку (англійська та українська).

За офіційними даними аварійності [16] на основі розглянутого вище алгоритму за допомогою розробленої нами в середовищі Delphi програми був проведений кластерний аналіз регіонів України за розподілом дорожньо-транспортних пригод з постраждалими у 2016 році по видах, винуватцях та основних причинах скоєння. Ймовірність похибки кластеризації була обрана рівною 5%. Результати аналізу зведемо у таблиці 3, 4, 5.

Таблиця 3. Кластеризація регіонів за розподілом ДТП з постраждалими у 2016 році по винуватцях

Таблиця 4. Кластеризація регіонів за розподілом ДТП з постраждалими у 2016 році по їх видах

Таблиця 5. Кластеризація регіонів за розподілом ДТП з постраждалими у 2016 році по причинах скоєння

Запропонований алгоритм кластерного аналізу даних по кількох факторах (вимірах) забезпечує, на відміну від інших поширених методів, однозначність розбиття на кластери з одночасною оцінкою ймовірності похибки 1-го роду, тобто ймовірності, що однорідні дані будуть віднесені до різних кластерів. Таким чином, його перевагою є той факт, що він дозволяє проводити не тільки розвідувальний аналіз даних, але й робити математично обґрунтовані висновки. Необхідною умовою для його застосування є наявність інформації про кількість спостережень кожного фактору для кожного об'єкту, що кластеризується.

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

Запропонований метод кластеризації незалежних наборів багатовимірних даних за допомогою критерію узгодженості %2 відрізняється обчислювальною простотою, однозначністю розбиття даних на кластери, що не перетинаються, а також можливістю контролю похибки кластеризації. Цей метод був створений з метою порівняння структурних відмінностей багатовимірних систем різної природи. Кластеризація регіонів України розглянутим методом за розподілом кількості ДТП з постраждалими залежно від різних факторів дозволяє в якості наступного кроку провести аналіз спектру організаційних, технічних, кадрових та інших причин, які призвели до об'єднання регіонів в один та різні кластери, для поширення кращих практик запобігання аварійності на автомобільному транспорті в Україні та напрацювання заходів щодо зниження її загального рівня.

Список бібліографічних посилань

1. Олдендерфер М.С., Блэшфилд Р.К. Кластерный анализ // Факторный, дискриминантный и кластерный анализ: пер. с англ. / под. ред. И.С. Енюкова. -- М.: Финансы и статистика, 1989. -- 215 с.

2. Гройсман В. Безпека руху на українських дорогах має бути відчутна кожному водію / В. Гройсман. - Департамент інформації та комунікацій з громадськістю Секретаріату Кабінету Міністрів України, опубліковано 10 квітня 2018 року.

3. Семь основных причин ДТП

4. В Украине за 1,5 года на дорогах погибло больше людей, чем в АТО

5. Ханін О.Г. Методологічні особливості застосування критерію узгодженості х² в практичних задачах економіки, соціології та маркетингу / О.Г. Ханін // Економічний аналіз: зб. наук. праць / Тернопільський національний економічний університет. - 2015. - Том 22. - № 1. - С. 67-70.

6. Ханін О.Г. Метод х²-кластеризації в задачах маркетингу / О. Г. Ханін // Економічний аналіз: зб. наук. праць / Тернопільський національний економічний університет. - 2016. - Том 26. - № 1. - С. 38-42.

7. Черезов Д.С., Тюкачев Н.А. Обзор основных методов классификации и кластеризации данных // Вестник Воронежского государственного университета, - Серия: Системный анализ и информационные технологи, - №2, 2009, с.25-29

8. Tryon, R.C. (1939) Cluster Analysis: Correlation Profile and Orthometric (Factor) Analysis for the Isolation of Unities in Mind and Personality. Edwards Brothers, Ann Arbor. - 122 p.

9. Trebuna P., Halcinova J. Mathematical Tools of Cluster Analysis // Applied Mathematics, 2013, 4, 814-816.

10. Нейский И.М. Классификация и сравнение методов кластеризации

11. Jain A., Murty M., Flynn P. Data Clustering: A Review. // ACM Computing Surveys. 1999. Vol. 31, no. 3,- 69 p.

12. Тьюки Дж. Анализ результатов наблюдения. Разведочный анализ. М.: Мир,- 1981, - 696 с.

13. Кластерный анализ

14. Сигел Э. Практическая бизнес-статистика / Э. Сигел - М. : Вильямс, 2002. - 1056 с.

15. Крамер Г. Математические методы статистики / Г. Крамер - М. : Мир, 1976. - 648 с.

16. Статистика аварійності в Україні за 12 місяців 2016 року

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