====== 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. ==== Краткое описание ==== В статье предлагается использовать кластеризацию вариантов использования с целью определения компонент системы и их зон ответственности. Для определения важности признаков вариантов используется анализ чувствительности. Также для определения числа кластеров используется метрика внутренной сплоченности между кластерами и между их объединениями. Достоинства предложенного метода следующие: - Не нужно взвешивать признаки - Можно проводить анализ влияния признаков на точность кластеризации - Новый точный метод идентификации компонент и их зон ответственности ==== Матрицы взаимоотношений объектов ==== Рассматриваем граф: * вершины - объекты с наборами признаков (варанты использования) * вершины соединяются ребрами с весами, вес ребра - коэффициент схожести объектов. Вычисляется на основе признаков. Пусть N -- число вариантов использования. 1. Матрица схожести S - матрица размера NхN, где * s_{ij} = s_{ji}, * s_{ii} = 1, * 0 <= s_{ij} <= 1\ \forall 1 <= i,j <= N. Матрицу схожести удобно использовать в случае, если признаки бинарные. Элементы матрицы обычно вычисляются следующим образом. Пусть n_{00}\ (n_{11}) --- число признаков, которые отсуствуют (присутствуют) у обоих объектов. n_{01},\ (n_{10}) --- число признаков, которые есть только у первого (второго) объекта. Ниже приведены формулы, использующиеся для подсчета схожести объектов: s_{ij} = \frac{n_{11} + n_{00}}{n_{11} + n_{00} + w(n_{01} + n_{10})}, s_{ij} = \frac{n_{11}}{n_{11} + w(n_{01} + n_{10})}, где параметр w берут обычно из множества \{1/2, 1, 2\}. 2. Матрица расстояний D между объектами - матрица размера NxN, где: * d_{ij} = d_{ji}, * d_{ii} = 1, * 0 <= d_{ij} <= 1\ \forall 1 <= i,j <= N. Матрицу расстояний удобно использовать, если признаки - числа. Элементы матрицы считаются по косинусному расстоянию: d_{ij} = 1 - \frac{\vec{v_{i}} \cdot \vec{v_{j}}}{\sqrt{||\vec{v_i}||_2 * ||\vec{v_j}||_2}}. ==== Методы кластеризации ==== * Иерархическая кластеризация. Сначала считаем, что всего N кластеров : \{C_1, \ldots, C_N \}, потом соединяем пару тех i,j, где d(C_i, C_j) = \min_{i\in C_i, j\in C_j} d_{ij}. Продолжаем итеративно, пока не останется K кластеров. * Метод k -- средних. Сначала выбирается начальное приближение из K объектов - центров кластеров. Основная идея заключается в том, что на каждой итерации перевычисляется центр масс каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. * RB - разделение. K - 1 раз разбиваем кластеры на 2, оптимизируя значение кластерной функции. Обычно берут отношение средней попарной похожести элементов внутри кластера к средней похожести элементов внутри кластера с элементами вне кластера. * RBR - разделение. Так же, как RB, но в конце все разделения оптимизируются с одновременно. * Прямая кластеризация. Одновременно ищутся все K кластеров. * Fuzzy Clustering Method. Ищет разделения объектов, минимизируя функцию потерь. * Алгоритмы из теории графов. Бинаризуем матрицу схожести S по порогу (ребро остается, если вес больше порога, иначе ребра нет), далее применяются алгоритмы поиска кластеров в графе. * E- Neural Networks-Based Clustering. Номер кластера определятся номером нейрона, имеющего наибольшую активацию на данный объект. Более подробное описание см. [1,2]. ==== Методы оценки числа кластеров ==== 1. CH - индекс. CH(K) = \frac{Tr(S_b)}{K-1} / \frac{Tr(S_w)}{N - K} \rightarrow max_{K}, где Tr(S_b) --- среднее расстояние внутри между точками внутри кластеров, Tr(S_w) --- между точками разных кластеров. 2. Ray и Turi индекс. Пусть \{z_1, \ldots, z_K\} --- центры кластеров. Validity(K) = Intra / Inter \rightarrow max_{K} Intra = \frac{1}{N} \sum_{i=1}^{k}\sum_{x\in C_i} ||x - z_i||^2 --- среднее расстояние до центра кластера. Inter = min(||z_i - z_j||^2), i = 1, \ldots , K - 1; j = i + 1, \ldots, K.--- минимальное расстояние между центрами кластеров. ==== Выделение признаков вариантов использования ==== признаки выделяются с использованием диаграммы классов, коллобораций и диаграммы вариантов использования. Признаки: 1. Актеры. Актер, который вызывает данный вариант использования. 1 в колонке того актора, который вызывает данный сценарий, во всех остальных 0. 2. Классы-сущности. По одной колонке для каждого класса-сущности. 1 если данный класс присутствует и варианте использования, иначе 0. 3. Управляющие классы - классы, ответственные за взаимодействие между классами-сущностями и классами интерфейсов. Аналогично по колонке для каждого класса. 4. Отношения между вариантами использования. * extend - 1 всем, кто связан данным отношением с каким-то конкретным вариантом использования и самому варианту использования. * generalize -- аналогично extend. * include -- если U_i, U_j связаны отношением include, то 1 в колонке для U_i и для всех других U_k, связанных отношением include с U_j. 5. Вес управляющего класса. WCC_i = \frac{Nec_i + Nic_i}{\sum_{j=1}^m Nec_j + \sum_{j=1}^{l} Nic_j}, где Nec_i - число сущностей, находящихся под контролем класса i, Nic_i - число интерфейсов, находящихся под контролем класса i, m -- предполагаемое число сущностей, l -- предполагаемой число интерфейсов. 6. Ассоциативный вес варианта использования AWUC = \frac{N_{CC_j} + N_{aec_j} + N_{ec_j}}{\sum_{j=1}^{u}(N_{CC_j} + N_{aec_j} + N_{ec_j})}, где N_{CC_j} -- число управляющих классов, связанных с данным вариантом использования, N_{aec_i} -- число отношений между сущностями и данным вариантом использования, N_{ec_i} -- число сущностей, связанных с данным вариантом использования. 6. Коэффициент сходства данного варианта использования с остальными вариантами. Считается между конкретным вариантом использования и всеми остальными, используя формулу для подсчета элементов матрица похожести. ==== Cоздание матрицы сходства вариантов использования ==== При подсчете матрицы нужно учитывать, что признаки вариантов использования есть бинарные, а есть числовые. Поэтому сходство вариантов использования считается по формуле: s(i, j) = \frac{w_1s_1(i,j) + w_2s_2(i,j)}{w_1 + w_2}, где s_1(i,j) -- мера сходства, посчитанная только на бинарный признаках по формуле подсчета элементов матрицы похожести c w = 1, s_2(i,j) = 1 - d(i,j) -- мера сходства для числовых признаков, где d_{ij} считается по формуле \ref{desim}, w_1, w_2 - веса, подобраны в соответствии с важностью матриц схожести и расстояний, авторы положили w_1 = w_2 = 0.5. ==== Оценка предложенного метода ==== Сначала авторы статьи выбрали наиболее подходящий способ кластеризации. Для этого они привлекли экспертов и считали ошибку по формуле: Error = \frac{1}{2} \sum_{i=1}^{K} NC_{i} \bigtriangleup NE_{i}, где кластер NC_{i} разметил метод кластеризации, NE_{i} -- кластер, размеченный экспертом. Авторы усреднили ошибку между 4 различными системами: * Education System(ES), * Online Stock Brokerage System(OSBS), * Chain-Store System(CSS), * Home Appliance Control System(HACS). По следующей формуле: QCF_i = \frac{1}{4}\sum_{j=1}^{4}\frac{NCE_{ij}}{NUC_{j}}, где NCE_{ij} -- ошибка i-ого метода кластеризации на j-ой системе, NUC_{j} -- число вариантов использования в j-ой системе. Далее авторы провели анализ чувствительности признаков -- они удаляли поочередно признаки и смотрели, ухудшилось ли качество. Если не уменьшалось, то удаляли этот признак. Таким образом авторы получили набор признаков, достаточный для качественной кластеризации. ==== Результаты эксперимента ==== Лучшим методом кластеризации оказался метод RBR, средняя ошибка: 0.05, далее прямой поиск кластеров с результатом 0.095. Среди методов оценки числа кластеров лучше оказался метод 2 - Ray и Tury индекс, его погрешность не более одного кластера (в сравнении с экспертной оценкой числа кластеров). Анализ влияния признаков показал, что признаки на основе актеров, управляющих классов и классов-сущностей важны, при их удалении качество кластеризации ухудшалось на всех системах. Далее авторы попробовали поменять веса w_1 и w_2 при подсчете матрицы сходства вариантов использования. Оказалось, что веса w_1 = w_2 = 0.5 оптимальны для задачи кластеризации. Авторы сравнили свой метод с методом Кима и оказалось, что их метод дает меньшую ошибку на всех рассмотренных системах. ==== Список литературы ==== - 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.