Differences

This shows you the differences between two versions of the page.

--- mdd:uc_clustering [2016/12/25 15:00] – [Результаты эксперимента.] annamedvedeva
+++ mdd:uc_clustering [2026/08/29 07:59] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
+====== Identification of System Software Components Using Clustering Approach ======
+Оригинал статьи:
+Shahmohammadi G., Jalili S., Hasheminejad S. M. H. Identification of System Software Components Using Clustering Approach, Journal of Object Technology. – 2010. – Т. 9. – №. 6. – С. 77-98.
+==== Краткое описание ====
+В статье предлагается использовать кластеризацию вариантов использования с целью определения компонент системы и их зон ответственности. Для определения важности признаков вариантов используется анализ чувствительности. Также для определения числа кластеров используется метрика внутренной сплоченности между кластерами и между их объединениями.
+Достоинства предложенного метода следующие:
+  - Не нужно взвешивать признаки
+  - Можно проводить анализ влияния признаков на точность кластеризации
+  - Новый точный метод идентификации компонент и их зон ответственности
+==== Матрицы взаимоотношений объектов ====
+Рассматриваем граф:
+  * вершины - объекты с наборами признаков (варанты использования)
+  * вершины соединяются ребрами с весами, вес ребра - коэффициент схожести объектов.  Вычисляется на основе признаков.
+Пусть <latex>N</latex> -- число вариантов использования.
+. Матрица схожести <latex>S</latex> - матрица размера NхN, где
+  * <latex>s_{ij} = s_{ji},</latex>
+  * <latex>s_{ii} = 1,</latex>
+  * <latex>0 <= s_{ij} <= 1\ \forall 1 <= i,j <= N.</latex>
+Матрицу схожести удобно использовать в случае, если признаки бинарные. Элементы матрицы обычно вычисляются следующим образом.
+Пусть <latex>n_{00}\ (n_{11})</latex> --- число признаков, которые отсуствуют (присутствуют) у обоих объектов. <latex>n_{01},\ (n_{10})</latex> --- число признаков, которые есть только у первого (второго) объекта. Ниже приведены формулы, использующиеся для подсчета схожести объектов:
+<latex> s_{ij} = \frac{n_{11} + n_{00}}{n_{11} + n_{00} + w(n_{01} + n_{10})},</latex>
+ <latex>s_{ij} = \frac{n_{11}}{n_{11} + w(n_{01} + n_{10})}</latex>,
+где параметр w берут обычно из множества <latex>\{1/2, 1, 2\}.</latex>
+. Матрица расстояний <latex>D</latex> между объектами - матрица размера NxN, где:
+  * <latex>d_{ij} = d_{ji},</latex>
+  * <latex>d_{ii} = 1,</latex>
+  * <latex>0 <= d_{ij} <= 1\ \forall 1 <= i,j <= N.</latex>
+Матрицу расстояний удобно использовать, если признаки - числа. Элементы матрицы считаются по косинусному расстоянию:
+<latex>d_{ij} = 1 - \frac{\vec{v_{i}} \cdot \vec{v_{j}}}{\sqrt{||\vec{v_i}||_2 * ||\vec{v_j}||_2}}.</latex>
+==== Методы кластеризации ====
+  * Иерархическая кластеризация. Сначала считаем, что всего N кластеров : <latex>\{C_1, \ldots, C_N \}</latex>, потом соединяем пару тех <latex>i,j</latex>, где <latex>d(C_i, C_j) = \min_{i\in C_i, j\in C_j} d_{ij}.</latex> Продолжаем итеративно, пока не останется  K кластеров.
+  * Метод k -- средних. Сначала выбирается начальное приближение из K объектов - центров кластеров. Основная идея заключается в том, что на каждой итерации перевычисляется центр масс каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.
+  * RB - разделение. K - 1 раз разбиваем кластеры на 2, оптимизируя значение кластерной функции. Обычно берут отношение средней попарной похожести элементов внутри кластера к средней похожести элементов внутри кластера с элементами вне кластера.
+  * RBR - разделение. Так же, как RB, но в конце все разделения оптимизируются с одновременно.
+  * Прямая кластеризация. Одновременно ищутся все K кластеров.
+  * Fuzzy Clustering Method. Ищет разделения объектов, минимизируя функцию потерь.
+  * Алгоритмы из теории графов. Бинаризуем матрицу схожести S по порогу (ребро остается, если вес больше порога, иначе ребра нет), далее применяются алгоритмы поиска кластеров в графе.
+  * E- Neural Networks-Based Clustering. Номер кластера определятся номером нейрона, имеющего наибольшую активацию на данный объект.
+Более подробное описание см. [1,2].
+==== Методы оценки числа кластеров ====
+. CH - индекс.
+<latex> CH(K) = \frac{Tr(S_b)}{K-1} / \frac{Tr(S_w)}{N - K} \rightarrow max_{K},</latex> где <latex>Tr(S_b)</latex> --- среднее расстояние внутри между точками внутри кластеров, <latex>Tr(S_w)</latex> --- между точками разных кластеров.
+. Ray и Turi индекс.
+Пусть <latex>\{z_1, \ldots, z_K\}</latex> --- центры кластеров.
+<latex> Validity(K) = Intra / Inter \rightarrow max_{K} </latex>
+<latex> Intra = \frac{1}{N} \sum_{i=1}^{k}\sum_{x\in C_i} ||x - z_i||^2</latex> --- среднее расстояние до центра кластера. <latex> Inter = min(||z_i - z_j||^2), i = 1, \ldots , K - 1; j = i + 1, \ldots, K.</latex>--- минимальное расстояние между центрами кластеров.
+==== Выделение признаков вариантов использования ====
+признаки выделяются с использованием диаграммы классов, коллобораций и диаграммы вариантов использования.
+Признаки:
+. Актеры. Актер, который вызывает данный вариант использования. 1 в колонке того актора, который вызывает данный сценарий, во всех остальных 0.
+. Классы-сущности. По одной колонке для каждого класса-сущности. 1 если данный класс присутствует и варианте использования, иначе 0.
+. Управляющие классы - классы, ответственные за взаимодействие между классами-сущностями и классами интерфейсов. Аналогично по колонке для каждого класса.
+. Отношения между вариантами использования.
+  * extend - 1 всем, кто связан данным отношением с каким-то конкретным вариантом использования и самому варианту использования.
+  * generalize -- аналогично extend.
+  * include -- если <latex>U_i, U_j</latex> связаны отношением include, то 1 в колонке для <latex>U_i</latex> и для всех других <latex>U_k,</latex> связанных отношением include с <latex>U_j.</latex>
+. Вес управляющего класса. <latex>WCC_i = \frac{Nec_i + Nic_i}{\sum_{j=1}^m Nec_j + \sum_{j=1}^{l} Nic_j},</latex> где
+<latex>Nec_i</latex> - число сущностей, находящихся под контролем класса <latex>i</latex>,
+<latex>Nic_i</latex>  - число интерфейсов, находящихся под контролем класса <latex>i</latex>,
+<latex>m</latex> -- предполагаемое число сущностей,
+<latex>l</latex> -- предполагаемой число интерфейсов.
+. Ассоциативный вес варианта использования
+<latex>AWUC = \frac{N_{CC_j} + N_{aec_j} + N_{ec_j}}{\sum_{j=1}^{u}(N_{CC_j} + N_{aec_j} + N_{ec_j})},</latex>
+где <latex>N_{CC_j}</latex> -- число управляющих классов, связанных с данным вариантом использования,
+<latex>N_{aec_i}</latex> -- число отношений между сущностями и данным вариантом использования,
+<latex>N_{ec_i}</latex> -- число сущностей, связанных с данным вариантом использования.
+. Коэффициент сходства данного варианта использования с остальными вариантами. Считается между конкретным вариантом использования и всеми остальными, используя формулу для подсчета элементов матрица похожести.
+==== Cоздание матрицы сходства вариантов использования ====
+При подсчете матрицы нужно учитывать, что признаки вариантов использования есть бинарные, а есть числовые. Поэтому сходство вариантов использования считается по формуле:
+<latex>s(i, j) = \frac{w_1s_1(i,j) + w_2s_2(i,j)}{w_1 + w_2},</latex> где
+<latex>s_1(i,j)</latex> -- мера сходства, посчитанная только на бинарный признаках по формуле подсчета элементов матрицы похожести c <latex>w = 1,</latex>
+<latex>s_2(i,j) = 1 - d(i,j)</latex> -- мера сходства для числовых признаков, где <latex>d_{ij}</latex> считается по формуле \ref{desim},
+<latex>w_1, w_2</latex> - веса, подобраны в соответствии с важностью матриц схожести и расстояний, авторы положили <latex>w_1 = w_2 = 0.5.</latex>
+==== Оценка предложенного метода ====
+Сначала авторы статьи выбрали наиболее подходящий способ кластеризации. Для этого они привлекли экспертов и считали ошибку по формуле:
+<latex> Error = \frac{1}{2} \sum_{i=1}^{K} NC_{i} \bigtriangleup NE_{i},</latex> где кластер <latex>NC_{i}</latex> разметил метод кластеризации, <latex>NE_{i}</latex> -- кластер, размеченный экспертом. Авторы усреднили ошибку между 4 различными системами:
+  * Education System(ES),
+  * Online Stock Brokerage System(OSBS),
+  * Chain-Store System(CSS),
+  * Home Appliance Control System(HACS).
+По следующей формуле:
+<latex>QCF_i = \frac{1}{4}\sum_{j=1}^{4}\frac{NCE_{ij}}{NUC_{j}},</latex>
+где <latex>NCE_{ij}</latex> -- ошибка <latex>i</latex>-ого метода кластеризации на j-ой системе, <latex>NUC_{j}</latex> -- число вариантов использования в j-ой системе.
+ Далее авторы провели анализ чувствительности признаков -- они удаляли поочередно признаки и смотрели, ухудшилось ли качество. Если не уменьшалось, то удаляли этот признак. Таким образом авторы получили набор признаков, достаточный для качественной кластеризации.
+==== Результаты эксперимента ====
+Лучшим методом кластеризации оказался метод RBR, средняя ошибка: 0.05, далее  прямой поиск кластеров с результатом 0.095. Среди методов оценки числа кластеров лучше оказался метод 2 - Ray и Tury индекс, его погрешность не более одного кластера (в сравнении с экспертной оценкой числа кластеров).
+Анализ влияния признаков показал, что признаки на основе актеров, управляющих классов и классов-сущностей важны, при их удалении качество кластеризации ухудшалось на всех системах. Далее авторы попробовали поменять веса <latex>w_1</latex> и <latex>w_2</latex> при подсчете матрицы сходства вариантов использования. Оказалось, что веса <latex>w_1 = w_2 = 0.5</latex> оптимальны для задачи кластеризации. Авторы сравнили свой метод с методом Кима и оказалось, что их метод дает меньшую ошибку на всех рассмотренных системах.
+==== Список литературы ====
+  - R. Xu and D. Wunsch, "Survey of Clustering Algorithms , " IEEE Transactions on Neural Networks, Vol. 16, No. 3, MAY 2005, pp. 645- 678.
+  - G. Karypis, CLUTO: A Clustering Toolkit. Dept. of Computer Science, University of Minnesota, USA, 2002.