발표자 : 홍익대학교 소프트웨어 공학 연구실 변은영 지도교수 : 김영철

Presentation on theme: "발표자 : 홍익대학교 소프트웨어 공학 연구실 변은영 지도교수 : 김영철"— Presentation transcript:

1 발표자 : 홍익대학교 소프트웨어 공학 연구실 변은영 지도교수 : 김영철 2018. 06. 21
Louvain 클러스터링 알고리즘을 통한 요구 사항 상관성 추출 Extracting Association Relationships among Requirements through Louvain Clustering Algorithm 발표자 : 홍익대학교 소프트웨어 공학 연구실 변은영 지도교수 : 김영철

2 Contents I. 연구 배경 II. 관련 연구 III. 요구사항 클러스터링 기법 및 자동화 시스템
IV. 사례 적용 및 결과 분석 V. 결론 및 향후 연구

3 연구 배경 소프트웨어 개발 프로세스 “Software Development Process produes highest quality and lowest cost in the shortest time. It includes a detailed plan for how to develop, maintain, and replace a software system.” “소프트웨어 개발 프로세스는 소프트웨어의 품질을 향상시키고, 소모되는 비용과 시간을 절감시킨다. 이는 소프트웨어 시스템의 개발, 유지보수에 대한 체계적인 계획을 포함한다.” - Stackify Requirement Analysis Design Coding Testing Analysis Design Coding Testing Requirements Questions Answers ? ? Stakeholders Developers

4 연구 배경 Software Modeling Type Use Ratio of UML Diagram UML Diagram All Sources [Co. Visual Paradigm]

5 연구 배경 “Use Case Diagram can be a good communication tool for stakeholders. It provides a view for the stakeholders to understand how the system is going to be designed.” “유스 케이스 다이어그램은 개발자와 이해 관계자를 위한 훌륭한 커뮤니케이션 도구가 될 수 있다. 이는 이해 관계자가 시스템이 어떻게 설계될지 이해할 수 있는 뷰를 제공한다.” - Vidgen, R. ‘Requirements Analysis and UML’, 2003 Requirements Questions Answers 자동화 Approach 요구 사항 상관성 추출 자동화를 위한 시스템 구축 ? ? 이해관계자와 개발자 간의 커뮤니케이션 활성화 소프트웨어 개발 효율성 증대 Use Case Diagram Stakeholders Developers

6 관련 연구 UML Tools Requirements Tools
Use Case Use Case 자동 추출 ArgoUML x Dia Modelio Nclass NetBeans PaPyrus Umbrello UML Modeller Genmymodel Visual Paradigm Use Case Use Case 자동 추출 Doors x RequisitePro CaliberRM Accept Requirements Atlassian JIRA Accompa GatherSpace eRequirements Cameo Requirements 설계 측면의 기능만을 제공함 설계와의 추적성을 제공하기 위한 시도 중  유스 케이스 자동 추출 기능은 제공 X 이는 현재까지 연구 단계  요구사항을 대상으로 POS Tagging 을 수행하여 주어, 동사 분류  반자동화 - Best UML Tools, BestTools [2018]

7 Strongly Connected Component
관련 연구 Graph Clustering Theory Strongly Connected Component 방향성 그래프에서 서로 다른 노드가 접근할 수 있는 경로가 있는 경우 하나의 컴포넌트는 순환 그래프 Strongly Connected Component Requirement Graph * 요구사항 그래프에서 순환 그래프가 생성되기 위해서는 동사를 중심으로 주어와 관련 명사가 변경되어야 함  위와 같은 제약 사항으로 인해 클러스터링 어려움

8 관련 연구 Graph Clustering Theory 𝒎𝒐𝒅𝒖𝒍𝒂𝒓𝒊𝒕𝒚 ≈𝟎.𝟑𝟒
Louvain Clustering Algorithm 네트워크에서 커뮤니티를 탐지 하기 위한 Greedy Optimization 알고리즘 그래프 노드 간의 모듈성을 -1~1 사이 값으로 측정 SCC(Strongly Connected Component)와는 다르게 비방향성 그래프를 대상으로 하고, 연결선의 가중치를 고려할 수 있음 Algorithm 1. Put all vertices into distinct communities 2. Refine communities ▶ For each vertex i Compute ∆ 𝑄 𝑖→𝑐(𝑗) for each neighbor j Join the community c(j) that yields the largest gain in ∆𝑄 ▶ Repeat until no movement yields a gain 3. Reconstruct the graph ▶ The partitions become super vertices ▶ The weights of edges between communities are summed 4. Repeat steps 2 and 3 until convergence 𝒎𝒐𝒅𝒖𝒍𝒂𝒓𝒊𝒕𝒚 ≈𝟎.𝟑𝟒

9 Louvain Clustering Algorithm
요구사항 클러스터링 기법 및 자동화 시스템 대상이 되는 요구사항을 입력한다. Step1 (Input) Step2 (Parsing) NLPT(Natural Language Parsing Tool)을 사용하여 자연어를 Tree형태로 파싱 한다. Requirements Semantic Tree Step3 (List Generation) Tree를 기반으로 주어로부터 동사, 동사로부터 관련명사에 방향성을 갖는 리스트를 생성한다. Hotels can be searched based on city selection, check-in out dates, room type and bed type. R1 Requirement Graph Linked List Step4 (Graph Generation) 연결 리스트를 기반으로 비방향성을 갖는 그래프를 생성한다. Louvain Clustering Algorithm Requirement Cluster Step5 (Requirements Clustering) Louvain 알고리즘을 적용하여 요구사항을 클러스터링 한다.

10 Louvain Clustering Algorithm
요구사항 클러스터링 기법 및 자동화 시스템 대상이 되는 요구사항을 입력한다. Step1 (Input) Step2 (Parsing) NLPT(Natural Language Parsing Tool)을 사용하여 자연어를 Tree형태로 파싱 한다. Requirements Semantic Tree Step3 (List Generation) Tree를 기반으로 주어로부터 동사, 동사로 부터 목적어에 방향성을 갖는 리스트를 생성한다. Hotels can be searched based on city selection, check-in out dates, room type and bed type. R1 Requirement Graph Linked List Step4 (Graph Generation) 연결 리스트를 기반으로 비방향성을 갖는 그래프를 생성한다. Tree Louvain Clustering Algorithm Requirement Cluster Step5 (Requirements Clustering) Louvain 알고리즘을 적용하여 요구사항을 클러스터링 한다.

11 Louvain Clustering Algorithm
요구사항 클러스터링 기법 및 자동화 시스템 대상이 되는 요구사항을 입력한다. Step1 (Input) Step2 (Parsing) NLPT(Natural Language Parsing Tool)을 사용하여 자연어를 Tree형태로 파싱 한다. Requirements Semantic Tree Step3 (List Generation) Tree를 기반으로 주어로부터 동사, 동사로부터 관련명사에 방향성을 갖는 리스트를 생성한다. Requirement Graph Linked List Step4 (Graph Generation) 연결 리스트를 기반으로 비방향성을 갖는 그래프를 생성한다. Tree Louvain Clustering Algorithm List Requirement Cluster Step5 (Requirements Clustering) Louvain 알고리즘을 적용하여 요구사항을 클러스터링 한다.

12 Louvain Clustering Algorithm
요구사항 클러스터링 기법 및 자동화 시스템 Requirement Graph 대상이 되는 요구사항을 입력한다. Step1 (Input) Step2 (Parsing) NLPT(Natural Language Parsing Tool)을 사용하여 자연어를 Tree형태로 파싱 한다. Requirements Semantic Tree Step3 (List Generation) Tree를 기반으로 주어로부터 동사, 동사로부터 관련명사에 방향성을 갖는 리스트를 생성한다. Requirement Graph Linked List Step4 (Graph Generation) 연결 리스트를 기반으로 비방향성을 갖는 그래프를 생성한다. Louvain Clustering Algorithm List Requirement Cluster Step5 (Requirements Clustering) Louvain 알고리즘을 적용하여 요구사항을 클러스터링 한다.

13 Louvain Clustering Algorithm
요구사항 클러스터링 기법 및 자동화 시스템 대상이 되는 요구사항을 입력한다. Step1 (Input) Step2 (Parsing) NLPT(Natural Language Parsing Tool)을 사용하여 자연어를 Tree형태로 파싱 한다. Requirements Semantic Tree Step3 (List Generation) Tree를 기반으로 주어로부터 동사, 동사로부터 관련명사에 방향성을 갖는 리스트를 생성한다. Requirement Graph Linked List Step4 (Graph Generation) 연결 리스트를 기반으로 비방향성을 갖는 그래프를 생성한다. Louvain Clustering Algorithm Requirement Cluster Step5 (Requirements Clustering) Louvain 알고리즘을 적용하여 요구사항을 클러스터링 한다.

14 사례 적용 및 결과 분석 여행 상품 요구사항 여행 상품 R1 Hotel Search R2 R3 R4 R5 Ticket R6
Hotels can be searched based on city selection, check-in out dates, room type and bed type R2 Hotels can be displayed along with the selected search conditions along with the photos, ratings, and information R3 Hotels can be sorted by name, rank, low-price, high-price R4 Each Hotel product can be booked, changed, and registered as a favorite product Ticket R5 The ticket can be searched based on the departure city, destination city, round-trip, one-way selection, departure date R6 The ticket show the price, TAX, date, airline, stay, destination, stopover, flight, availability R7 Each ticket can be booked, changed, or registered R8 The joint purchase has the function of the customer purchasing the ticket presented by the travel agency R9 The joint purchase list shows the date of departure, the airline, the length of stay, the price, the destination, and the waypoint

15 사례 적용 및 결과 분석 여행 상품 요구사항 R2 Tree List Requirement Graph
Hotels can be displayed along with the selected search conditions along with the photos, ratings, and information R2 Tree List Hotels be be … search conditions photos ratings information Requirement Graph

16 사례 적용 및 결과 분석 여행 상품 요구사항 R5 Tree List Requirement Graph
The ticket can be searched based on the departure city, destination city, round-trip, one-way selection, departure date R5 Tree List ticket be be … city selection dates Requirement Graph

17 사례 적용 및 결과 분석 여행 상품 요구사항 R6 Tree List Requirement Graph
The ticket show the price, date, airline, stay, destination, flight, availability R6 Tree List ticket show show price date airline stay destination flight availability Requirement Graph

18 사례 적용 및 결과 분석 Ticket Search Hotel Search 여행 상품 R1 Hotel Search R2 R3
Hotels can be searched based on city selection, check-in out dates, room type and bed type R2 Hotels can be displayed along with the selected search conditions along with the photos, ratings, and information R3 Hotels can be sorted by name, rank, low-price, high-price R4 Each Hotel product can be booked, changed, and registered as a favorite product Ticket R5 The ticket can be searched based on the departure city, destination city, round-trip, one-way selection, departure date R6 The ticket show the price, TAX, date, airline, stay, destination, stopover, flight, availability R7 Each ticket can be booked, changed, or registered R8 The joint purchase has the function of the customer purchasing the ticket presented by the travel agency R9 The joint purchase list shows the date of departure, the airline, the length of stay, the price, the destination, and the waypoint Ticket Search Hotel Search

19 결론 및 향후 연구 결론 향후 연구 자연어로 작성된 요구사항의 그래프화 연구
Louvain 알고리즘 기반의 요구사항 클러스터링 기법 연구 요구 사항 상관성 추출 자동화를 위한 시스템 구축 기능적 요구사항들의 상관성을 분석하여 유스 케이스 추출의 기반이 됨 ‘여행 상품‘ 요구사항을 테스트 케이스로 적용 이해관계자와 개발자 간의 커뮤니케이션 활성화 및 효율성 증대 향후 연구 클러스터링 기법의 정확성을 향상 시키기 위한 전처리 필요 (대소문자, 단/복수 단어 식별, 동사/명사 의미로 동일하게 사용되는 단어 처리, 수동태 문장을 능동태 문장으로 변환) 명확한 요구사항 정의 필요(동일하지만 다른 형태의 단어 정제 필요)