상용 클러스터로 대규모 그래프의 연결 요소를 계산하기 위한 효율적인 알고리즘

김채은 국민대학교 일반대학원 2021 국내석사

최근 웹의 데이터가 폭발적으로 증가함에 따라 상용 클러스터 서버에서 수천억 개의 정점과 간선을 가지는 거대한 그래프에서 연결 요소(Connected Components)를 효율적으로 계산하는 것이 매우 중요한 문제가 되었다. 지금까지 연구된 단일 머신 및 분산 메모리 알고리즘들은 입력 데이터와 처리 과정에서 생성되는 모든 데이터를 주 메모리에 적재하여 실행하기 때문에 확장성이 제한된다. 단일 머신 및 분산 메모리 알고리즘에서 거대한 데이터를 처리하기 위해서는 방대한 메모리가 탑재되어 있는 고가의 머신이 필요하다. 또한 기존에 연구된 맵리듀스 알고리즘들은 분산 파일 시스템을 이용하여 거대한 그래프 처리를 시도하지만 중간 데이터 폭증 문제로 인하여 처리에 실패한다. 최근에 제안된 맵리듀스 알고리즘들은 두 개의 분산 연산으로 이루어진 star-operation을 교대로 실행하여 중간 데이터 폭증 문제를 해결하지만 두 개의 분산 연산을 반복하여 실행하기 때문에 심각한 네트워크 트래픽과 디스크 I/O를 발생시킨다. 본 논문에서는 두 개의 분산 연산으로 이루어진 star-operation을 하나로 통합하는 분산 연산 UniStar를 제안하고, UniStar를 이용하여 거대한 그래프에서 연결 요소를 계산하는 분산 알고리즘 UniCon을 제안한다. UniStar는 파티션 인식 처리 기법을 통해 중간 데이터 폭증 문제를 해결한다. 또한 연산 과정에서 불필요한 간선들을 제거하고, 새로운 하이브리드 자료구조를 이용하여 UniStar 연산을 최적화한다. UniCon은 10대의 저가의 머신으로 이루어진 상용 클러스터 서버에서 실험이 진행되어 실제 그래프 데이터에서 경쟁 알고리즘들보다 최대 13배 빠르게 실행된다. 실험 결과, UniCon은 1,290억 개의 간선을 가지는 거대한 그래프 처리에 성공하여 경쟁 알고리즘들보다 최대 4096배 큰 데이터 처리에 성공한다. With a cluster of commodity hardware, how can we efficiently find all connected components of a web-scale graph containing hundreds of billions of nodes and edges? Most existing single-machine and distributed-memory algorithms are limited in scalability as they have to load all data generated during the process into the main memory; they require expensive machines with vast memory capacities to handle large graphs. Several MapReduce algorithms try to handle large graphs by exploiting distributed storage but fail due to data explosion problems. The latest MapReduce algorithms resolve the problem by proposing two distinguishing star-operations and executing them alternately, while the star-operations still cause massive network traffic. In this paper, we unite the two star-operations into a single operation, namely UniStar, and propose UniCon, a new distributed algorithm for finding connected components in web-scale graphs using UniStar. The partition-aware processing of UniStar effectively resolves the data explosion problems. We further optimize UniStar by filtering dispensable edges and exploiting a hybrid data structure. Experimental results with a cluster of 10 cheap machines show that UniCon is up to 13 times faster than competitors on real-world graphs. UniCon succeeds in processing a tremendous graph with 129 billion edges, which is up to 4096 times larger than graphs competitors can process.

딥러닝 기반의 교차로 환경 운전자 좌회전 주행 maneuver 분류 및 예측에 관한 연구

이승민 국민대학교 2022 국내석사

As the interest grows regarding autonomous driving and V2X technology research, CDA also has been attracted because it guarantees the efficiency and stability of transportation by linking traffic situation information with autonomous vehicles. However, CDA dosen't work perfectly in mixed traffic situations with autonomous vehicles and non-autonomous vehicles because non-autonomous vehicles do not have connectivity with autonomous vehicles and road infrastructures. To overcom this, the technologies for classification and prediction of future trajectories or maneuvers of non-autonomous vehicles are required. Recently, Deep Learning and Artificial Intelligence technologies have been applied in this field. Based on this background, this study proposes the method to classify driver’s maneuvers in road environments based on deep learning. According to domestic and foreign statistics and reports [2], [3], intersections are the area where the most traffic accidents occur. Also, the rate of accidents at intersecions is the highest when left-turning maneuvers were performed and more than 80% of the accidents are caused by driver's situational awareness and judgment errors [3], so it is very meaningful work for an autonomous vehicle to classify and predict left-turning maneuvers of vehicles in the intersection environments and it would be the key to the development of AI for autonomous driving. In addition, according to NHTSA report [3], focussing on the fact that the rate of accidents by abnormal maneuvers among the detailed cases of driver's judgment error is the highest, this study proposes a model that considers not only normal maneuvers but also abnormal maneuvers which is differentiate from previous studies. To do this, we have collected the data through vehicle driving in the real intersection environment, and represented as 3-second time-series vehicle position and motional data. Finally we have trained the data with an RNN-based deep learning model to classify and predict four normal and abnormal left-turn maneuvers. 최근 자율주행과 V2X 기술 개발이 가속화됨에 따라 도로 인프라에서 검지 된 도로 상황 정보를 자율주행차량과 연계하여 교통의 안정성과 효율성을 높이는 CDA기술이 주목받고 있다. 하지만, 자율주행차량 및 도로 인프라와 connectivity가 없는 일반차량이 혼재된 혼합류 교통에서는 해당 기술을 완전히 적용하는 데는 어려움이 있다. 이를 극복하기 위하여 현재 도로 내 일반차량들의 미래 경로나 maneuver를 예측하는 기술들이 도입되고 있는데 최근 해당 분야에 딥러닝 및 인공지능 기술이 활발히 적용되고 있는 추세이다. 이러한 배경을 바탕으로 본 논문에서는 도로환경에서 일반차량들의 maneuver를 분류하여 예측하는 딥러닝 모델에 관한 연구를 제안하고자 한다. 특히 본 논문에서는 도로 환경 중 사고 위험도가 높은 교차로환경에 주목하였다. 국내외 통계 및 보고서 [2], [3] 에 따르면 교차로는 교통사고통계에서 사고가 가장 많이 발생한 지역이며, 이 중에서도 좌회전 maneuver를 수행했을 때 사고의 비율이 가장 높았다. 그리고 교차로 사고 원인 중 약 80% 이상이 운전자의 상황인식 및 판단의 오류로 인하여 발생한다는 점 [4] 을 비추어 보았을 때 교차로 환경에서 일반차량들의 좌회전 maneuver를 분류하고 예측하는 것이 자율주행 인공지능 개발에 큰 기여가 될 것임을 알 수 있었다. 또한, NHTSA 보고서 [4]에서 교차로/비교차로 사고 발생 상대비율을 분석 시 운전자 판단 오류에 의한 사고 중 비정상적인 maneuver에 따른 사고가 교차로에서 상대적으로 많이 발생한 높은 점에 주목하여 본 논문에서는 교차로 내 정상적인 maneuver 뿐만 아니라 비정상 maneuver들도 함께 고려한 모델을 제안하여 기존 연구와의 차별성을 갖고자 한다. 본 논문의 연구 수행을 위해 실제 교차로 환경에서 좌회전 신호 시 차량 주행을 통해 데이터를 수집하였다. 여기서 수집된 데이터를 3초 길이의 시계열(time-series) 차량 위치 및 거동 데이터로 표현하였고, 이를 RNN 기반의 딥러닝 모델로 학습하여, 4개의 정상, 비정상 좌회전 maneuver를 분류하고 예측한다.

멀티모달을 이용한 한국어 영상 감정인식

조윤정 국민대학교 소프트웨어융합대학원 2022 국내석사

2020년 코로나 대유행 이후 사회는 과도기적인 큰 변화를 맞이하게 되었다. 대외적인 활동이 제재되면서 익숙하고 당연하게 생각해왔던 지극히 일상적인 것들과 낯설고 생소하기만 했던 비일상적이었던 것들이 서로 뒤바뀌면서 인간의 생활 패턴이 점차 바뀌어졌다. 바뀐 패턴은 급진적인 기술의 발전을 불러일으키며 불편함을 줄여줄 편의성으로써 상용화가 되기 시작했고, 그 중 인공지능의 많은 분야와 기술들이 주목을 받기 시작했다. 인공지능이라는 단어가 익숙해진 지금, 코로나로 인해 드러난 비대면 서비스들의 한계점과 앞으로 인공지능이 더 나은 방향으로 나아가기 위해 요구되는 사람과의 소통에서 필요한 감정을 여러 신호를 통해 분석하고 학습하는 멀티모달 기술을 이용해 감정인식하는 연구를 본 논문에서 수행하고자 한다. 본 논문에서는 멀티모달 한국어 영상 데이터셋을 이용하여 각각 음성과 텍스트, 얼굴 이미지를 분리하고, 음성은 Mel Spectrogram과 MFCC 알고리즘을 사용하여 특징을 추출하고, 텍스트는 BERT 기반의 한국어가 사전 학습된 KoBERT 모델을 사용하여 특징을 추출한다. 마지막으로 얼굴 이미지는 Amazon Rekognition API를 호출하여 반환된 감정 결과값을 이용한다. 이 세 개의 신호로부터 추출된 값들을 다시 융합하여 최종 감정 추론에 도달하는 연구를 수행한다. 실험 결과, 각 신호 별로 추출된 값에 다른 가중치를 부여함으로 92%의 감정인식률을 확인할 수 있었다. After the COVID-19 pandemic in 2020, society faced a transitional change. As external activities have been limited, the human life pattern has gradually changed day by day from familiar and natural to unfamiliar and unusual ones. Accordingly, new technologies like artificial intelligence are getting attraction to reduce the inconvenience of the new human life pattern. Now that the word artificial intelligence is familiar, this paper intends to conduct a study on emotion recognition using multimodal technology that analyzes and learns the limitations of non-face-to-face services revealed by COVID-19 and the emotions required for communication with people to move in a better direction. In this paper, voice, text, and face images are separated using multimodal Korean image datasets, voice is extracted using Mel Spectrogram and MFCC algorithms, and text is extracted using a pre-learned Korean KoBERT model. Finally, the face image uses the returned emotion result value by calling the Amazon Rekognition API. We conduct a study that re-fuses the values extracted from these three signals to reach the final emotion inference. Our experimental results show that the proposed method achieves 92% of emotional recognition rate with different weight values to the multi-modal signals.

이미지 분류 문제에서의 데이터 분포에 따른 선별적 데이터 증강 연구

이휘찬 국민대학교 소프트웨어융합대학원 2021 국내석사

딥 러닝에서 사용하는 심층 신경망은 방대한 양의 데이터를 학습하여 높은 성능을 보여주는 강력한 기계 학습 시스템이다. 과거 기계 학습 및 영상 처리 분야의 주요 과업은 더 나은 심층 신경망 모델을 설계하는 것 이었다. 그러나 최근에는 딥 러닝을 적용하여 문제를 해결하는데 주로 직면하는 문제로 손꼽히는 데이터 부족을 해결하기 위해 데이터 증강에 대한 여러 연구가 진행되고 있다. 데이터 증강은 데이터를 무작위로 증가시켜 데이터의 양과 다양성을 증가시키는 기술이다. 본 논문에서는 보다 효율적인 데이터 증강을 수행할 수 있는 아이디어를 제안하기 위해, 이미지 데이터의 클래스별 데이터의 분포에 초점을 맞추어 연구를 진행하였다. 본 논문의 연구는 훈련 데이터를 사전 학습하여 클래스별 데이터 분포를 분석하는 것부터 시작하였다. 컨볼루션 신경망 기반의 인코더 모델로 학습된 데이터의 임베딩 작업을 통해 데이터의 분포를 시각화 하였다. 그 다음 데이터 클래스별 평균점을 찾아서 평균점에서 가장 멀리 떨어진 데이터들을 집중적으로 데이터 증강을 수행하였다. 이 작업은 데이터의 밀도가 낮은 부분의 데이터를 증강시켜 클래스의 데이터 밀도를 이전보다는 상대적으로 균일하게 만들어 주었다. 실험에 사용한 데이터셋은 mini-ImageNet이다. 총 100개의 클래스에 각 600개의 데이터를 가지고 있으며 이 중 5개의 클래스의 3000개 데이터를 가지고 실험을 진행 하였다. 증강시킨 데이터의 수를 조절하며 본래 데이터 수의 비율에 따라 본 논문에서 제안하는 기법과 단순 랜덤 방식의 증강 기법의 시험 정확도를 비교 분석하였다. 이를 통해 본 논문에서 제안하는 기법의 성능 향상 정도를 비교 평가 하였다. 제안한 아이디어로 데이터 증강을 수행하여 모델을 학습시킨 결과, 데이터 증강 수가 적은 경우에서 모델의 성능 향상이 기존의 단순 기법보다 우월한 것으로 나타났다. 이 결과는 고무적이라고 볼 수 있는데, 실제 데이터 학습 시에는 mini-ImageNet 같은 벤치마킹 데이터가 아닌 대용량의 데이터를 학습시키게 되는 상황이 일반적이기 때문에 증강 데이터 수를 무조건적으로 늘릴 수는 없기 때문이다. 따라서 본 논문에서 제안한 데이터 증강 아이디어는 효과적인 방법이며 데이터 학습 실무 시에도 유효할 것으로 보인다. 추가로, 데이터 밀도가 낮은 부분을 찾는 알고리즘과 데이터 증강 기법의 적용에 대해 추가적인 연구도 가능할 것으로 생각 한다. Data augmentation is a proven technique that is widely used as a method to improve the performance of image classifiers in problems with insufficient data. As the level of research on the related deep learning technology increases and interest in it is being applied to various industries in various fields, various studies on data augmentation are being researched to solve the chronic problem of data shortage. In this paper, we propose an idea for more efficient data augmentation method by focusing on data distribution. The idea starts with analyzing the distribution of trained data through a data embedding task based on a convolutional neural network. Then, data augmentation is intensively executed at a point where the data distribution density is relatively low. The dataset used for the experiment is mini-ImageNet. This idea can be used to improve the performance of not only conventional image classification learning by class, but also meta-learning's few-shot learning model, which has recently been spotlighted in the deep learning field.

Fast and Accurate Distributed k-Nearest Neighbor Graph Construction by Multiway Random Divison Forest

Kim Sanghong 국민대학교 일반대학원 2022 국내석사

k-nearest neighbor graphs, shortly k-NN graphs, are widely used in many data mining applications like recommendation, information retrieval, and similarity search. Approximate k-NN graph construction has been getting a lot of attention, and most researches focus on developing algorithms that operate efficiently and quickly on a single machine. A few pioneering studies propose distributed algorithms to increase the size of data that can be processed to billions. However, we notice that the distributed algorithms don’t perform well enough due to the problems of graph fragmentation and massive data exchange. In this paper, we propose MRDF (Multiway Random Division Forest), a scalable distributed algorithm that constructs highly accurate k-NN graph from numerous high-dimensional vectors quickly. MRDF resolves the problems that the existing distributed algorithms suffer from, through coarse-grained partitioning based on tree path annotation. Experimental results on real-world datasets show that MRDF outperforms the state-of-the-art distributed algorithms with up to 7.6 times faster speed and up to 56%p better accuracy than the second best results, and succeeds in processing a billion-scale dataset. MRDF also shows linear scalability with respect to the number of machines and the number of vectors. k-최근접이웃그래프는추천시스템,유사사례검색,정보탐색등다양한데이터마이닝애플리 케이션에 사용되고 있다. 이에 따라 근사 k-NN 그래프를 구성하는 방법이 많은 관심을 얻고 있는데, 대부분의 연구들은 하나의 연산 장치에서 빠르고 효율적으로 동작하는 알고리즘을 개발하는데만 초점을맞추고있다.몇몇연구에서는분산알고리즘을제시하여처리가능한근사k-최근접이웃그 래프의 크기를 늘렸지만, 그래프 파편화와 중간 데이터 폭증 문제로 인해 분산 알고리즘들이 충분한 성능을 달성하지 못한다. 본 연구에서는 확장성이 좋은 분산 알고리즘인 MRDF(Multiay Random Division Forest, 다방향 분할 포레스트)를 제안한다. 해당 알고리즘은 고차원의 대용량 벡터 데이터셋으로부터 높은 정확도 의 k-NN 그래프를 빠르게 구성한다. MRDF는 트리 경로 확장법에 기반한 넓은 범위 분할 기법을 활용하여 기존의 분산 알고리즘들이 가지고 있던 그래프 파편화와 중간 데이터 폭증 문제를 해결한 다. 다양한 데이터셋에 대한 실험 결과, MRDF는 경쟁 알고리즘들에 비해 최대 7.6배 빠른 속도와, 56% 이상 나은 정확도를 보였으며, 10억개의 정점으로 이루어진 데이터셋을 처리하는데 성공한다. 또한, 연산 장치의 수 또는 정점의 수를 늘리는 경우에 대해서도 선형적인 성능 향상을 이뤄내 좋은 확장성을 보인다.

Empowering GNNs in The Absence of Node Features : Generating Label-Correlated Node Features using Cumulative Snapshots of Label Propagation

Park HyunSeok 국민대학교 일반대학원 2023 국내석사

How can we generate features for effective learning of Graph Neural Network (GNN) models when the graph has no node features? GNN models have achieved state-of-the-art results on graph-related tasks using both the graph structure and node features. However, real-world graphs commonly do not have node features, posing challenges for GNN models which often assume these features. Despite numerous methods designed to generate node features in the absence of inherent node features, many overlook node labels during the generation process. Yet, a strong correlation between features and labels is paramount for training a GNN model. In this paper, we introduce CSLP (Cumulative Snapshots in Label Propagation), a novel approach aimed at producing features with a strong correlation to labels. CSLP iteratively accumulates snapshots from label propagation to formulate features. Subsequently, an autoencoder refines these features into meaningful representations of suitable dimensions. Experimental results show that features by CSLP exhibit superior correlation with labels compared to features generated by alternative methods. When integrated into a Graph Convolutional Network model, CSLP outperforms the second-best method, achieving up to 36.5% higher accuracy. 어떻게하면 그래프의 노드 특성이 없을 때 Graph Neural Network(GNN) 모델의 효과적인 학습을 위한 특성을 생성할 수 있을까? GNN 모델은 그래프 구조와 노드 특성을 모두 사용해서 그래프 관련 작업에서 좋은 성능을 달성하고 있다. 그러나 현실 세계의 그래프는 일반적으로 노드 특성이 없는 경우가 많고, 이런 경우에서 GNN 모델은 성능이 좋지 않다. 많은 연구에서는 노드의 특성이 없는 상황에서 노드 특성을 생성하기 위한 여러가지 방법을 보여주며, 이런 방법들은 노드의 라벨을 간과하고 있다. 그러나 특성과 라벨 간의 강력한 상관 관계는 GNN 모델을 학습하는데 핵심적이다. 본 연구에서 라벨과 강력한 상관 관계를 갖는 특성을 생성하는 방법인 CSLP(Cumulative Snapshots in Label Propagation)를 제안한다. CSLP는 Label Propagation 알고리즘의 결과 스냅샷을 반복적으로 축적하여 특성을 생성한다. 그 후, Autoencoder를 사용해서 적절한 차원의 유의미한 표현으로 만들어서 최종적인 특성을 생성한다. 다양한 데이터셋에서 실험한 결과 CSLP를 사용해서 생성된 특성이 다른 방법으로 생성된 특성보다 라벨과의 상관관계가 우수하게 나타났고, 생성된 노드 특성으로 Graph Convolutional Network(GCN)를 학습할 때 정확도가 최대 36.5% 증가하는 결과를 보여준다.

Latent Representation Generation for Efficient Content-Based Image Retrieval in Weather Satellite Images Using Self-Supervised Segmentation

Ismail Abdulhakin 국민대학교 일반대학원 2023 국내석사

Latent Representation Generation for Efficient Content-Based Image Retrieval in Weather Satellite Images Using Self-Supervised Segmentation With the rapid advancement of satellite sensor technology, a huge volume of high-resolution image data sets can now be acquired, and efficiently representing and recognizing scenes within these high-resolution images has emerged as a critical challenge. In this paper, we propose AES (Auto-Encoder after Segmentation), a method for learning a latent representation containing high-level semantics of meteorological satellite images. AES uses W-Net, an unsupervised segmentation model, to simplify the images. Our approach significantly improves CBIR performance in the domain of weather satellite images. Experimental results on satellite weather images demonstrate that our proposed method outperforms traditional auto-encoders in terms of mean squared error (MSE). A lower average MSE indicates stronger similarity between the retrieved and query images, suggesting that our method better represents the underlying similarities within the data. Additionally, our approach demonstrates higher recall values for similarity assessment and enhanced retrieval accuracy, showcasing its effectiveness in extracting meaningful features for content-based image retrieval in meteorological satellite images. 해상도가 높은 이미지 데이터 세트의 대량 획득이 가능해진 위성 센서 기 술의 급속한 발전으로, 이러한 고해상도 이미지 내의 장면을 효율적으로 표현하 고 인식하는 것이 중요한 과제로 떠오르고 있다. 본 논문에서는 기상 위성 이미 지의 고수준 의미론적 표현을 학습하는 AES(Auto-Encoder after Segmentation) 라는 방법을 제안한다. AES는 이미지를 단순화하기 위해 비지도 세그멘테이션 모델인 W-Net을 사용한다. 우리의 방법은 날씨 위성 이미지 분야에서 CBIR 성 능을 향상시킨다. 위성 기상 이미지에 대한 실험 결과는 우리가 제안한 방법이 MSE 에서 기존의 오토 인코더의 성능을 능가한다는 것을 입증한다. 낮은 평균 MSE는 검색된 이미지와 쿼리 이미지 간의 강한 유사성을 나타내며, 이는 우 리의 방법이 데이터 내의 기본적인 유사성을 더 잘 나타낸다는 것을 의미한다. 더해서, 우리의 방법은 유사성 평가를 위한 높은 재현율과 향상된 검색 정확도 를 나타내며, 기상 위성 이미지의 CBIR을 위해 의미 있는 특징을 추출하는 데 효과적임을 입증한다.