Robust Spectral Clustering on Highly Noisy Data

Kim, Jeong-Hun 충북대학교 2023 국내박사

Spectral clustering is one of the representative graph-based clustering methods. This method is widely used in various fields because it can cluster datasets with any data type and find non-convex-shaped clusters. However, spectral clustering has a chronic problem of being sensitive to noise. This noise problem makes spectral clustering impractical for real-world applications with highly-noisy data. To address this noise problem, many researchers have proposed robust spectral clustering methods. However, these methods have limitations in improving robustness against noise because they do not provide solutions suitable for the challenge of each noise type. In this dissertation, we divide noises into two types, internal and external noises, and define the challenge of spectral clustering for each noise type. To deal with the different problems caused by both types of noise, we propose a novel robust spectral clustering method named KNN-RSC. The proposed KNN-RSC filters out potential external noises that are relatively sparse data using k-nearest neighbor based density estimation. Then, KNN-RSC constructs the filtered density-based affinity graph using a nearest-neighbor graph. By adaptively scaling each connected component of the nearest-neighbor graph based on local densities of vertices, the filtered density-based affinity graph capture the cluster structure, which is complicated by internal noises. In addition, KNN-RSC finds clusters with varying sizes, shapes, and densities by solving the graph-cut problem for the filtered density-based affinity graph. In experiments for real-world datasets, KNN-RSC achieves a clustering accuracy of at least 1.2 times and a maximum of 2.1 times better than existing robust spectral clustering methods. However, KNN-RSC often provides impractical clustering results for high-dimensional data due to the “curse of dimensionality” problem. To alleviate the problem, in this dissertation, we propose KNN-SSC, incorporating KNN-RSC and subspace learning to improve the clustering accuracy for high-dimensional data. KNN-SSC effectively alleviates the “curse of dimensionality” problem by learning low-dimensional subspaces for each cluster. In particular, KNN-SSC learns the subspaces that inflect density-based similarity relationships by reducing the influence of internal and external noises using the filtered density-based affinity graph of KNN-RSC. By integrating the advantages of KNN-RSC and subspace learning, KNN-SSC achieves clustering accuracy up to 1.2 times better than the existing state-of-the-art subspace clustering method. In particular, for high-dimensional datasets, KNN-SSC achieves better clustering accuracy from a minimum of 1.2 times to a maximum of 2.0 times than that of KNN-RSC. To utilize the proposed methods widely in various fields, we apply the proposed KNN-RSC and KNN-SSC to deep learning applications, action recognition and image classification. 데이터 군집화는 데이터집합으로부터 유사한 데이터들로 구성된 하위집합들을 찾는 대표적인 비지도 학습 방법이다. 데이터 군집화로부터 식별된 군집은 다른 군집과 차별화될 수 있는 특징을 별도의 데이터 학습 과정과 학습을 위한 데이터 레이블 없이 식별할 수 있어 비지도 학습이 요구되는 다양한 응용분야에서 오랜 기간 동안 연구되어 왔다. 데이터 군집화는 군집을 정의하는 방법에 따라 중심 값, 계층, 밀도, 그리고 그래프 기반 접근방식으로 구분되며, 이 중 그래프 기반 접근방식은 데이터의 종류에 관계없이 데이터 간의 유사성으로 관계를 정의한 유사도 그래프로 표현 가능한 모든 데이터에 적용 가능하다는 장점과 원형의 군집을 포함한 다양한 형태의 군집을 찾을 수 있다는 장점으로 인해 상당한 주목을 받고 있다. 하지만 대표적인 그래프 기반 군집화 방법인 스펙트럴 군집화 방법은 잡음 데이터에 의해 유사성 그래프가 쉽게 변형되어 잘못된 데이터 군집을 찾게 되는 심각한 문제가 있다. 이러한 문제를 해결하기 위해 기존의 연구들은 잡음 데이터에 의한 영향을 최소화하여 최적의 유사성 그래프를 구성하는 방법에 초점을 두었다. 하지만 잡음 데이터는 어떤 군집에도 포함되지 않는 외부 잡음과 군집 내에서 데이터의 분포를 복잡하게 만드는 내부 잡음으로 분류될 수 있으며, 잡음 데이터의 종류에 따라 유사도 그래프에 미치는 영향이 다르기 때문에 기존의 연구들은 두 가지 상이한 종류의 잡음 데이터를 효과적으로 처리하지 못해 군집화 성능을 개선하는데 한계를 보였다. 본 학위논문에서는 기존 연구들의 한계점을 극복하기 위해 밀도 기반 잡음 데이터 필터링 방법과 밀도 기반 유사도 그래프에 기초하여 외부 잡음으로 인한 유사도 그래프의 변형을 최소화하고 내부 잡음으로 인한 복잡한 데이터 분포를 효과적으로 나타낼 수 있는 밀도 기반 유사도 그래프를 구축함으로써 향상된 군집화 성능을 제공하는 잡음 데이터에 강인한 새로운 스펙트럴 군집화 방법 KNN-RSC를 제안한다. 이를 위해 먼저 외부 잡음 데이터를 식별하여 제거하기 위한 최인접 이웃 그래프와 최인접 이웃을 활용한 밀도 추정 방법을 제안한다. 최인접 이웃 그래프는 가장 인접한 이웃 노드와 간선으로 연결된 방향 그래프로 데이터 집합의 밀도 분포를 효과적으로 나타낸다. 외부 잡음 데이터는 군집에 포함된 데이터들과 달리 상대적으로 희소하기 때문에 최인접 이웃과 밀도 차이가 크고 희소한 데이터를 잠재적 외부 잡음 데이터로 식별할 수 있다. 이러한 잠재적 외부 데이터를 필터링한 후 최인접 이웃 그래프를 확장하여 내부 잡음 데이터에 의해 복잡해진 데이터 분포를 반영한 유사도 그래프를 구성한다. 내부 잡음 데이터로 인해 군집들의 밀도가 다양화되며, 이를 식별하기 위해 최인접 이웃을 기반으로 인접한 노드 간의 밀도차이를 계산하여 데이터 분포에 적응적인 데이터 유사성을 정의한다. 이러한 밀도 기반 데이터 유사성에 기초하여 유사도 그래프를 구축하고 스펙트럴 군집화를 수행한다. 추가적으로 고차원 데이터에서 차원의 저주로 인한 데이터 밀도 추정의 단점을 보완하기 위해 KNN-RSC에 부분공간 학습 방법을 적용하여 확장한 KNN-SSC를 추가적으로 제안한다. 또한 제안된 방법들의 이론적 배경을 서술하는데 그치지 않고, 기존에 널리 사용되는 베이스라인 군집화 방법들과 우수한 성능을 보유한 스펙트럴 군집화 방법들과의 광범위한 비교 실험을 통해 제안된 방법들의 성능적 우수성을 실증하고자 한다. 먼저 잡음 데이터에 대한 강인성을 평가하기 위해 잡음 데이터의 수가 점진적으로 증가하는 합성 데이터를 생성하여 실험을 수행하며, 실제 분석환경의 시나리오를 충분히 고려할 수 있도록, 실세계에서 얻어진 데이터집합들을 이용한 실험 또한 수행한다. 이러한 실험 결과를 통해, 본 학위 논문에서 제안된 KNN-RSC와 KNN-SSC는 잡음 데이터의 종류에 관계없이 강인한 군집화 성능을 제공하며, 베이스라인 군집화 방법과 우수한 성능을 보유한 기존의 스펙트럴 군집화 방법들보다 우수한 군집화 성능을 제공함으로써 기존 군집화 연구들이 가진 한계성을 해결할 수 있음을 보인다. 또한, 제안된 군집화 방법들을 대표적인 심층학습 기반 컴퓨터 비전 작업인 행동 인식에 적용하여 제안된 군집화 방법들이 다양한 분야에서 유용하게 활용될 수 있음을 실험적으로 실증한다.

Clustering-based Data Dissemination Protocol Using the Forward Direction for Autonomous Vehicles

서민석 경희대학교 대학원 2019 국내석사

VANET (Vehicle Ad Hoc Network) is gathering attention as autonomous vehicles and MANET (Mobile Ad Hoc Network) are attracting interest as well. Therefore, efforts have been made to overcome the challenges of the VANET in which the topology changes in real time and instability exists due to the difference in speed and physical phase. Particularly in the IoT era, the total amount of network nodes in addition to vehicle nodes is expected to increase dramatically. Therefore, a clustering algorithm for a mesh network capable of autonomous configuration is suitable to reduce the load of the central control device and data redundancy on the network, which will increase according to the IoT era. However, since clustering algorithms based on the existing research have been developed for the current traffic situation, inefficiency is inevitable in the future autonomous navigation period in which traveling path prediction can be accurately performed. Therefore, this paper proposes a clustering algorithm and a data propagation algorithm between clusters using path information. The main content of this paper is as follows. First, we propose a clustering algorithm using path information considering the existing research results. In a related study, it was assumed that each vehicle node is G / G / 1 Queue and the vehicle follows Brownian motion. In this case, the node's successful transmission rate was modeled as the probability that nakagami-m fading would not occur or within a certain distance. In the autonomous navigation period, if the path is predictable, the probability that the nodes in the same cluster are in the same block for a longer time than the conventional one can converge to 100%. Therefore, the survival time of the cluster can be dramatically improved. In addition, if the cluster survival time increases, unnecessary clustering processes are reduced so that the overhead is reduced. Furthermore, frequent clustering in the dissemination process between clusters can increase the loss rate of the data dissemination message. Second, we developed a data propagation algorithm that can increase the information propagation rate of the entire network using path information. The cluster head is propagated using the member closest to the neighboring cluster as a gateway role, and the neighboring cluster is a cluster directed to another path. The cluster temporarily stores the data to be disseminated and then disseminates it when it encounters another cluster of neighbors. Since the cluster that receives the data is a cluster with a different path, the cluster that is newly encountered is likely to be a cluster that is encountered in another path. Therefore, data can be disseminated even for noncontiguous clusters. To summarize, this paper proposes clustering-based data dissemination algorithms and protocols using vehicle pathways for autonomous navigation and compares them with clustering-based data dissemination algorithms using existing directions. 자율주행차량과 MANET(Mobile Ad Hoc Network)가 화제를 모음에 따라 VANET(Vehicle Ad Hoc Network) 역시 화두에 올랐다. 이에 따라 토폴로지가 실시간으로 변하며 속도와 위상 차에 따른 불안정성이 존재하는 VANET의 문제점을 극복하기 위한 노력이 계속되어왔다. 특히, IoT 시대에 들어서 증가하는 네트워크 노드들의 총량에 더불어, 차량 노드들 역시 급증할 것으로 예상되고 있다. 그 중에서도 특히 클러스터링 알고리즘에 기반한 VANET은, IoT시대에 따라 증가할 중앙 제어 장치의 부하를 줄이는 한편, 네트워크 상의 데이터 중복성 등을 줄이기에 적합하다. 그러나 기존 연구에 기반한 클러스터링 알고리즘들은 현재의 교통 상황에 맞춰져 있기에 주행 경로를 정확히 예측할 수 있는 자율 주행 시대에서는 필연적인 비효율성이 발생한다. 따라서 본 논문에서는 경로 정보를 이용한 클러스터링 알고리즘과 클러스터들간의 데이터 전파 알고리즘을 제안한다. 본 논문의 주요 내용은 다음과 같다. 먼저, 기존 연구 결과를 고려하여 경로 정보를 이용한 클러스터링 알고리즘을 제안한다. 관련 연구에서는 각 차량 노드를 G/G/1 Queue로 가정하고 차량이 브라운 운동을 따른다고 가정하였다. 이 때, 노드의 전송 성공률을 nakagami-m 페이딩이 일어나지 않고 일정 거리 이내에 있을 확률로 모델링하였다. 자율주행시대에서 경로가 예측가능할 경우, 동일한 클러스터의 노드가 더 오랜 시간 동안 지속될 확률을 100%에 가깝게 수렴하도록 할 수 있다. 따라서, 클러스터의 생존 시간을 극적으로 향상시킬 수 있다. 더불어, 클러스터의 생존 시간이 늘어날 경우 불필요한 클러스터링 과정이 줄어들어 오버헤드가 감소한다. 게다가 클러스터간의 전파 과정에서 발생하는 클러스터링은 데이터 전파 메시지의 유실률을 높일 수 있다. 둘 째로, 본 논문에서는 경로 정보를 이용하여 전체 네트워크 상의 정보 전파율을 증가시킬 수 있는 데이터 전파 알고리즘을 개발하였다. 클러스터 헤드는 가장 가까운 이웃 클러스터를 게이트웨이의 역할로서 이용해 정보를 전파하고, 이웃 클러스터는 다른 방향으로 향하는 클러스터로 구성된다. 클러스터는 전파하려는 데이터를 일시적으로 저장한 후, 다른 이웃 클러스터를 만날 경우 다시 전파한다. 데이터를 전달받은 클러스터는 다른 경로를 가진 클러스터이기에 마주친 클러스터 역시 다른 경로를 가지고 있을 확률이 높다. 따라서 데이터가 인접하지 않은 클러스터에도 전파될 수 있다. 최종적으로 본 논문에서는 자율주행을 위한 차량 경로를 이용한 클러스터링 기반 데이터 전파 알고리즘과 프로토콜을 제안하며, 이를 현존하는 방향을 이용한 클러스터링 기반 데이터 전파 알고리즘과 비교하려 한다.

Hierarchical Density-Based Clustering for Data Stream over Sliding Window

온드라 서울대학교 대학원 2022 국내석사

데이터 스트림은 응용 프로그램이 급격히 증가함에 따라 최근 몇 년 동안 뜨거운 관심 주제가 되었다. 또한, 전자 기기 및 네트워크의 과도한 사용으로 인해 데이터 스트림이 지속적으로 생성되고 있다. 따라서 데이터 스트림은 빠른 데이터 포인트 생성과 같은 정적 데이터와 다른 고유한 특성을 가지며 시간이 지남에 따라 무한한 크기에 도달할 수 있다. 위에서 언급한 데이터 스트림의 고유한 특성으로 인해 데이터 스트림 클러스터링 알고리즘에 대한 요구 사항은 점점 더 복잡해지고 있다. 정적 데이터에 대한 클러스터링 알고리즘의 기본 요구 사항은 데이터 내에서 임의의 모양과 클러스터 수를 추출할 수 있어야 한다. 또한 스트림 클러스터링 알고리즘은 시간과 공간의 제약으로 인해 들어오는 데이터를 빠르고 효율적으로 처리하는 것이 중요하다. 기존의 밀도 기반 알고리즘은 들어오는 스트림 내에서 임의의 모양과 숫자의 클러스터를 성공적으로 찾았지만 밀도(ε)가 클러스터당 최소 포인트(minPts)와 함께 사용자 고정 매개변수인 경우가 많기 때문에 밀도 변화를 발견할 때는 여전히 부족하다. 본 논문에서는 데이터 스트림 내에서 밀도가 다른 클러스터를 감지할 수 있는 계층적 밀도 기반 클러스터링 알고리즘을 기반으로 하는 StreamHD 라는 스트림 클러스터링 알고리즘을 제안한다. 제안된 알고리즘은 사용자 개입을 최소화하면서 클러스터의 밀도 임계 값을 독립적으로 감지합니다. 또한 StreamHD 는 코어 밀도를 계산할 때 고려하고 최소 클러스터 크기도 결정하는 주어진 지점의 인접 지점 수를 결정하는 minPts 와 윈도우 크기의 두 가지 사용자 매개변수만 필요하다. StreamHD 는 스트림 클러스터링 알고리즘 중 사용자 개입이 가장 적다고 할 수 있다. 또한 실제 데이터셋과 합성 데이터셋에 대한 실험 결과 우리가 제안한 알고리즘이 각 윈도우 처리 시간과 클러스터 품질 측면에서 비교 알고리즘 중 가장 우수한 성능을 보였다. Data stream has become a hot topic of interest in recent years as its applications are increasing drastically. In addition, data streams are being continuously generated as a result of excessive usage of electronic devices and network. Thus, data streams have these unique characteristics differing to the static data such as speedy data point generation and possibly get to an unbounded size over time. Due to the distinctive nature of data stream as mentioned above, requirements for the data stream clustering algorithms are becoming more and more complex. The basic requirements for clustering algorithms for static data are being able to extract arbitrary shape and numbers of clusters within the data. In addition, it is crucial for stream clustering algorithms to process incoming data fast and efficiently due to the time and space limitation. Although existing density-based stream clustering algorithms successfully find clusters of arbitrary shape and numbers within incoming stream, it has two user parameters density (ε) and minimum points per cluster(minPts) that has to be tuned carefully to obtain the desired clustering outcome. In this paper, we propose a stream clustering algorithm called StreamHD, which is based on a hierarchical density-based clustering algorithm that can detect clusters ii of arbitrary shapes within the data stream. The proposed algorithm independently detects density thresholds of the clusters without much user intervention. In addition, StreamHD requires only two user parameters, window size and minPts which determines the number of neighboring points of the given point to consider when calculating core density and also determines the minimum cluster size. It can be said that StreamHD has the least user intervention among the stream clustering algorithms. Furthermore, experiment results on real and synthetic datasets have shown that our proposed algorithm performs the best among the comparison algorithms in terms of window processing time and cluster quality.

Clustering analysis for nonlinear and noisy patterns in high dimensional data

유재홍 Graduate School, Korea University 2018 국내박사

Many modern industries generate an unprecedented wealth of data because of the recent rapid improvement in the technology for sensing, accumulating, and storing. Data mining algorithms facilitate the discovery of useful concepts or information from these huge amounts of data. Of the numerous data mining techniques available, in recent years unsupervised learning methods have attracted the interest of numerous analysts. Among the approaches to unsupervised learning in use, clustering analysis is one of the most widely used to facilitate the extraction of hidden patterns from data and thus elicit their natural groupings. Clustering analysis systematically partitions a data set by minimizing within-group variations and maximizing between-group variations. Clustering analysis techniques have been applied in various industrial fields. These include manufacturing, text categorization, image segmentation, and biomedicine. To obtain superior results in clustering analysis requires appropriate clustering algorithms and distance measures. Although most of the existing clustering analysis techniques perform reasonably well within the situations for which they were designed, no consensus exists about which one is the best all-around performer in real-life situations. In real-world situations, clustering analysis encounters several obstacles in the data structures. These include nonlinearity and locality, noisy patterns, and high dimensionality. To address these data structural issues, this thesis is aimed at establishment of unsupervised learning methods to yield more robust clustering analysis. First, a graph-based clustering algorithm based on a novel density-of-graph structure is proposed. Numerous researchers have focused recently on graph-based clustering algorithms because their graph structure is useful in modeling the local relationships among observations. By doing so, these algorithms can successfully discover nonlinear and local patterned clusters. However, no consensus exists about which algorithm best satisfies all the conditions encountered in a variety of real-world situations. In the proposed clustering algorithm, a density coefficient defined for each node is used to classify dense and sparse nodes. The main structures of clusters are identified through dense nodes and sparse nodes that are assigned to specific clusters. Experiments on various simulation data sets and benchmark data sets were conducted to examine the properties of the proposed algorithm and to compare its performance with that of existing spectral clustering and modularity-based algorithms. The experimental results demonstrated that the proposed clustering algorithm performed better than its competitors; this was especially true when the cluster structures in the data were inherently noisy and nonlinearly distributed. To ensure more satisfactory results from clustering analysis, an appropriate distance measure should be used. In spite of its significance, relatively few studies have been conducted to determine the most effective distance measures to use. Recently, geodesic distance has been widely applied to clustering algorithms for nonlinear and local patterned groupings. However, geodesic distance is sensitive to noisy patterns; hence, geodesic distance-based clustering may fail to identify nonlinear and local patterned clusters in the region of the noise. To overcome this sensitivity to noisy patterns, this thesis proposes a density-based geodesic distance that can identify clusters in nonlinear and noisy situations. Experiments on various simulation and benchmark data sets were conducted to examine the properties of the proposed geodesic distance and to compare its performance with that of existing distance measures. The experimental results confirm that a clustering algorithm with the proposed distance measure demonstrated superior performance compared with the competitors. This is especially true when the cluster structures in the data were inherently noisy and nonlinearly patterned. Finally, this thesis proposes a feature ranking method to address high dimensionality. Feature ranking is a widely used feature selection method. It uses importance scores to evaluate the features and selects those with high scores. Conventional unsupervised feature ranking methods do not consider the information on cluster structures; therefore, these methods may be unable to select the features relevant to clustering analysis. To address this limitation, I propose a feature ranking algorithm based on silhouette decomposition. The proposed algorithm calculates the ensemble’s importance scores by decomposing the silhouette statistics of random subspaces. By doing so, the contribution of a feature in generating cluster structures can be represented more clearly. Experiments were conducted on different benchmark data sets to examine the properties of the proposed algorithm and to compare it with the existing ensemble-based feature ranking methods. The experiments demonstrated that the proposed algorithm outperformed its existing counterparts.

Clustering-Based Integrated Analysis of Time-Series Gene Expression Data to Identify Stress-Responsive Genes

안홍렬 서울대학교 대학원 2019 국내박사

본 논문은 유전자 발현 데이터를 분석할 때의 문제들을 정리하고 그 문제들을 해결하는 방법을 제시한다. 유전자 발현 데이터는 세포 내에 유전자가 활성화된 양을 수치화한 데이터이며 세포의 상태를 모델화하기 위하여 이 데이터를 사용한다. 하지만 세포는 이만 개 이상의 유전자, RNA, 단백질, 기타 화학 물질 등이 유기적으로 작용하여 구성되는 매우 복잡한 시스템이며, 이러한 세포를 모델화하기 위해서는 많은 수의 데이터가 필요하다. 그런데 현재 기술 및 자원적 한계에 의해 충분한 수의 데이터를 확보할 수 없으며, 적은 수의 데이터로 이 복잡한 세포를 모델화해야 하는 것이 유전자 발현 데이터 분석의 핵심적인 문제이다. 본 논문은 적은 수의 데이터로 세포를 효과적으로 모델화하기 위하여 클러스터링과 네트워크 기법을 사용하여 기존의 생물 지식과 공개된 데이터를 통합적으로 이용하는 방법론을 제시한다. 그 구체적인 방법은 다음과 같다. 클러스터링 분석을 통해 개별 유전자를 적은 수의 클러스터로 묶음으로써 특성 차원을 축소하고 모델화의 복잡성을 줄임으로써, 적은 수의 발현량 데이터로 세포의 상태를 모델화하고 해석하는 방법을 제시한다. 대량의 외부 데이터로부터 유전자 네트워크를 구성하고 실험 데이터로 구성한 네트워크와 통합함으로써 생물학적 도메인 데이터와 지식을 네트워크를 형태로 분석 과정에 도입하여 모델의 정확성을 향상하는 방법을 제시한다. 이질적 시간 구조를 가지는 다수의 시계열 데이터를 통합하는 분석에서, 클러스터링 방법으로 유전자의 반응 순서가 보존되는 유전자들을 찾는 방법을 제시한다. 아직 그 분포를 알지 못하는 유전자의 집합을 클러스터링하기 위해, 앙상블 기법 및 비용 최소화 기법 등 최신 클러스터링 기술을 사용하여 계층적 클러스터링 방법을 향상한다. 정리하면, 이 논문은 복잡한 시스템이면서 데이터 개수가 적어 모델화가 어렵고, 시계열 구조가 비균질한 유전자 발현 데이터 분석의 문제를 클러스터링과 네트워크를 기반으로 통합 분석하여 해결하는 방법을 제시한다. 또한 이러한 개발한 방법들을 실제 스트레스 실험 데이터에 적용하여, 가뭄 저항성 벼의 메커니즘을 설명하고, 저온 스트레스에 대해 반응하는 유전자를 검출한다. 제시된 방법론은 컴퓨터 공학의 데이터 분석 분야에서 비슷한 문제를 가진 문제들을 해결하는데 활용될 수 있을 것으로 기대된다. Microarray and RNA sequencing, highly parallel technologies for the measurement of intracellular RNA molecules, were developed in the 1990s and 2000s. They opened a new era of quantifying the amount of gene activation (expression) for every gene in a cell through a single experiment. Since then, gene expression data have been widely produced to investigate the change of the state of a cell, particularly in response to environmental stress, such as heat, drought, and cold, in plants. However, a cell is one of the most complicated systems in the universe. Understanding and modeling the system of a cell requires a huge amount of data, which we do not yet have. Thus, gene expression data analysis has to address the issue of the lack of data and the development of analytical procedures, models, and algorithms that work on small-sample-size data. This doctoral study proposes computational methodologies that solve the problem of modeling a highly complex system with small-sample-size data based on clustering and integrated analysis. We can easily understand gene expression data in the format of machine learning data: genes as features and different conditions of samples as classes. In gene expression data, the number of features is generally much greater than the number of samples due to the high cost of measurement of a sample. Performing clustering analysis on gene expression data groups individual genes into several gene clusters, resulting in the reduction of the dimension of features. This doctoral study presents a method that uses clustering analysis to reduce the dimension of features. It shows the improvement of interpreting high-dimension and small-sample-size gene expression data. In addition, the system of a cell consists of complicated interactions between genes, which leads to a computational problem known as high dependency between features. Introducing external information, domain data, and domain knowledge improves the modeling of relationships between genes to reflect real biological systems. This doctoral study proposes a method that introduces genetic data and knowledge into the analysis by constructing a template biological network. By combining the network with the condition-specific network derived from experimental data, it successfully explains the stress response mechanism of drought-resistant rice. Moreover, gene expression data are measured at multiple time points along the time axis, which is called time-series data, to track the response of cells after drug or stress treatment. However, they often have a small number of time points, usually less than ten, and different intervals across different time-series samples because of the limitation that the cells die in the process of being measured. The sparsity and heterogeneity of time-domain data in gene expression data make it difficult to clarify the time-domain signals of genes. This study proposes a method to analyze time-series gene expression data by using clustering analysis to extract the meaningful time-domain signal that is supported by many members of genes within the same cluster. Lastly, clustering analysis is sensitive to the distribution of data objects. However, we do not yet know the distribution of genes in gene expression data. Thus, clustering algorithms for gene expression data are required to work on arbitrarily distributed data. The hierarchical clustering method has been the most widely used clustering method for gene expression data analysis, but it does not always work on arbitrarily distributed data. This study also proposes an improved version of the hierarchical clustering method to work on arbitrarily distributed data by combining effective recent clustering techniques, such as network representation, phase shifting, and cost-optimization-based tree integration. In summary, this doctoral study proposes clustering-based computational methods for the analysis of gene expression data. Clustering analysis is used for dimension reduction, integration with biology-domain knowledge of genes, extraction of the time-domain signal, and development of clustering on arbitrarily distributed data. In addition, by applying it to actual stress data, this doctoral study explains the mechanism of drought-resistant rice, detects the cold-stress-responsive genes in Arabidopsis, and develops a new hierarchical clustering algorithm. The proposed methodology is expected to be useful for the analysis of other data with similar problems.

Reduction of training data for support vector machine for IoT and edge computing

Pardis, Birzhandi Sungkyunkwan university 2020 국내박사

Support Vector Machine (SVM) is a supervised machine learning technique widely applied in the various classification problems. Recently, a widespread use of IoT and advancement of networking technologies has led to development of the distributed SVM (DSVM). DSVM is developed to deal with the classification problem whose training data is distributed among several nodes in the network. Although, SVM is an efficient classification algorithm, its training time grows dramatically as the number of training data increases. As a result, the applicability of SVM to large-scale dataset is somewhat limited. In SVM only a few training samples called support vectors (SVs) affect the construction of the hyperplane. Therefore, removing training data that are not among the SVs does not degrade the performance of SVM. The problem is to correctly select SVs among non-SVs samples. In this dissertation several algorithms, namely parallel hyperplane (PH), clustering based convex hull (CBCH), support vector cluster-convex hull (SVC-CH), and clustering-based fisher distributed support vector machine (CF-DSVM) are proposed with different applicability for SVM and DSVM to decrease the number of redundant training data points and thus to reduce the training time of classification. Parallel hyperplane (PH) scheme is proposed for data reduction of linearly separable dataset to remove the data of clusters located outside of PHs applying k-mean clustering algorithm. CBCH scheme is proposed for data reduction of linearly inseparable dataset with binary class labels which divides training data points into several clusters. Only the vertices of the convex hulls of each cluster and the data points relevant to the SVs are considered as training data points. To improve the applicability of CBCH for classification of multiclass dataset, SVC-CH scheme is proposed which applies One–Against–All (OAA) technique to deal with the multiclass dataset. Moreover, CF-DSVM scheme is proposed for distributed environment to remove redundant training data points of each node by applying weighted clustering algorithm and the concept of fisher discriminant analysis (FDA). Computer simulation over various size and type of datasets and network topologies reveals that the proposed schemes are considerably faster and more accurate than the typical existing data reduction schemes. Support Vector Machine (SVM)은 일반적으로 중앙 집중형 문제에 사용되는 머신러닝 기반의 지도 학습 기법입니다. 최근 IoT의 광범위한 사용과 네트워크 기술의 발전은 분산 SVM(DSVM)의 개발로 이어져 왔습니다. DSVM은 네트워크의 여러 노드에 교육 데이터가 분산되는 분류 문제를 다루기 위해 개발되었습니다. SVM은 견고성을 바탕으로 다양한 분류 문제에 널리 적용되는 효율적인 알고리즘입니다. 그러나 교육 데이터 수가 증가함에 따라 교육 시간이 급격히 증가합니다. 결과적으로, 대규모 데이터 세트에 대한 SVM의 적용 가능성은 다소 제한적입니다. SVM에서는 Support Vectors(SVs)라는 몇 가지 교육 샘플만 초평면 구조에 영향을 줍니다. 따라서 SV에 포함되지 않은 교육 데이터를 제거해도 SVM의 성능이 저하되지 않습니다. 문제는 SV가 아닌 샘플 중에서 SV를 올바르게 선택하는 것입니다. 본 논문에서는 SVM과 DSVM이 중복 훈련 데이터 포인트 수를 줄이고 분류 교육시간을 단축하기 위한 각기 다른 적용 방법으로 Parallel Hyperplane(PH), Clustering Based Convex Hull(CBCH), Support Vector Cluster-Convex Hull(SVC-CH), Clustering-Based Fisher Distributed Support Vector Machine(CF-DSVM) 등의 몇 가지 알고리즘이 제안되었다. Parallel Hyperplane(PH) 기법은 k-mean 클러스터링 알고리즘을 적용한 PH 외부에 위치한 클러스터들의 데이터를 제거하기 위하여 선형으로 분리 가능한 데이터 세트의 데이터 축소를 위해 제안되었습니다. CBCH 기법은 교육 데이터 포인트를 여러 클러스터로 나누는 binary class label을 사용하여 선형적으로 분리할 수 없는 데이터 세트의 데이터 축소를 위해 제안되었습니다. 이때, 각 클러스터의 convex hull의 정점과 SV와 관련된 데이터 포인트만 교육 데이터 포인트로 간주됩니다. 멀티 클래스 데이터 세트의 분류를 위한 CBCH의 적용성을 향상시키기 위해 SVM의 기하학적 해석에 기초하여 SVC-CH 기법이 제안되었습니다. 이 기법은 One-Against-All(OAA) 기술을 적용하여 멀티 클래스 데이터 세트를 처리합니다. 더하여, CF-DSVM 기법은 분산 환경에서 가중 클러스터링 알고리즘과 Fisher Discriminant analysis(FDA) 개념을 적용하여 각 노드의 중복 교육 데이터 포인트를 제거하기 위해 제안되었으며, 이에 따라 local classifier를 global classifier로 융합하는데 필요한 시간을 현저히 감소시킬 수 있습니다. 다양한 크기와 유형의 데이터 세트 및 네트워크 토폴로지에 대한 컴퓨터 시뮬레이션은 제안된 기법이 기존의 일반적인 데이터 감소 기법보다 더 빠르고 정확하다는 것을 보여줍니다.

(A) review on clustering methods for functional data

유혜선 서울대학교 대학원 2015 국내석사

Many studies have been done for clustering functional data as considerable functional data are obtained recently. We reviewed overall approaches for clustering functional data proposed so far. Those approaches consist of a nonparametric approach which uses dissimilarity between curves as dissimilarity measure, a filtering and clustering technique which is simple and intuitive and a model-based clustering method which assumes a probability distribution of finite dimensional coefficients estimated from data. Model-based methods are reviewed in detail, particularly. Also, we provided an application to energy data using model-based models for functional data to illustrate model-based methods with specific basis.

Data-Driven Customer Segmentation for Retail Business: A Case of Shopping Mall Promotion

시띠뿌나누빱 피라팟 경상국립대학교 대학원 2024 국내석사

This study provides a complete investigation of data-driven customer segmentation using the Kaggle dataset "Customer Segmentation" gathered from a multi-category store. The collection includes client information and purchase history, offering insights into transactions and interactions over a certain period. The study methodically performs data processing stages to assure dataset quality, such as handling missing values, reducing outliers, and designing meaningful characteristics to portray client behavior. The analysis uses the K-means clustering technique in combination with principal component analysis (PCA) to identify customer groups in the dataset. PCA analysis identifies the key factors that contribute to the principal components PC1 and PC2, capturing variation in purchasing behavior, marketing receptivity, product preferences, online involvement, education, and recency. A comparative examination of several clustering situations confirms the selection of three clusters, as evidenced by assessment metrics such as the elbow method, silhouette score, and inertial score. Moreover, radar chart was used as a visual tool to demonstrate scaled attribute values across various client groupings. The graphic presented different traits or dimensions for each cluster, allowing for a more concise comparison of features. The radar chart revealed diverse trends and preferences inside each cluster by showing data like spending on certain items, online visits, recent purchases, and reaction to marketing initiatives. This visualization method revealed important insights into the differences and similarities between client segments, assisting in the understanding of segmentation results and enabling data-driven decision-making processes which allowing the business to discover of critical insights and guiding strategic decisions targeted at improving business performance.

Functional data clustering for high dimensional data with outliers

이승민 서울대학교 대학원 2014 국내석사

A clustering method for high dimensional data is very difficult because of the curse of dimensionality. In order to reduce the dimension of data, we use the functional data which is obtained by projecting data on a set of basis functions. There are three approaches on functional data clustering: 2-step methods, Nonparametric clustering, Model-based clustering. However, there are few studies on how to cluster the high dimensional data with outliers. In this paper, we suggest new robust functional clustering method using ES-algorithm and k-means clustering.

Can hierarchical client clustering mitigate the data heterogeneity effect in federated learning?

이승준 아주대학교 2023 국내석사

Federated learning (FL) was proposed for training a deep neural network model using millions of user data. The technique has attracted considerable attention owing to its privacy-preserving characteristic. However, two major challenges exist. The first is the limitation of simultaneously participating clients. If the number of clients increases, the single parameter server easily becomes a bottleneck and is prone to have stragglers. The second is data heterogeneity, which adversely affects the accuracy of the global model. Because data should remain at user devices to preserve privacy, we cannot use data shuffling, which is used to homogenize training data in traditional distributed deep learning. This work proposes a client clustering and model aggregation method, CCFed, to increase the number of simultaneously participating clients and mitigate the data heterogeneity problem. CCFed improves the learning performance using set partition modeling to let data be evenly distributed between clusters and mitigate the effect of a non-IID environment. Experiments show that CCFed can achieve a 2.5-7%p higher accuracy using CCFed compared with FedAvg, where CCFed requires only approximately 50% of rounds compared with FedAvg training on benchmark datasets. 연합 학습(federated learning)은 수십만 개에 달하는 사용자 데이터를 사용하여 심층 신경망을 학습시키기 위하여 제안되었다. 이 기법은 개인정보를 보호할 수 있다는 특징 덕분에 많은 관심을 받아 왔다. 하지만 아직 풀어야할 중요한 문제가 남아 있다. 첫 번째는 동시에 참여 가능한 클라이언트 수의 한계이다. 클라이언트의 수가 증가할 경우 하나만 존재하는 파라미터 서버가 쉽게 병목 지점이 될 수 있으며 또한 낙오자(straggler)가 발생하기 쉬워진다. 두 번째는 데이터 이질성 문제로 전역 모델(global model)의 정확도에 악영향을 끼치는 문제이다. 개인 정보를 보호하기 위하여 사용자 데이터는 사용자 기기에 남아있어야 하기에 기존 분산 심층 학습에서 데이터를 균질하게 만들기 위해 사용하던 데이터 섞기는 사용하기 어렵다. 이 연구에서는 동시에 참여 가능한 클라이언트의 수를 늘리고 동시에 데이터 이질성 문제를 완화하기 위한 CCFed라고 불리는 클라이언트 클러스터링 및 모델 취합(model aggregation) 방법을 제안한다. CCFed는 집합 분할 문제(set partition problem)을 사용하여 클러스터간 데이터가 균질하게 분배되도록 하고 이를 통해 비항등독립분포의 영향을 완하하여 학습 성능이 향상되도록 한다. 본 연구의 실험에서는 CCFed가 FedAvg와 비교했을 때 벤치마크 데이터셋에서 FedAvg 대비 약 50%의 라운드만으로 약 2.5에서 7%p의 정확도 향상이 있음을 보여주었다.