본문 바로가기

분류 전체보기

 (104)
[암호수학] 암호수학 요약 - 대수학 대수적 구조(Algebraic Structures) 집합과 집합 내 원소들에 적용되는 연산을 통틀어 대수적 구조라 한다. 일반적 세 개의 대수적 구조는 군(Group), 환(Ring), 체(Field) 이다. 정의 1. 군 (Group) 공집합이 아닌 집합 \(G\) 위에 다음 조건을 만족하는 이항연산 \(\circ\) 가 정의될 때, \( \) 를 군이라 한다. (닫힘) 집합 \(G\) 의 원소 \(a, b\) 에 대해 정의된 이항연산 \(\circ\) 를 했을 때의 값 \(c\) 는 집합 \(G\)의 원소이다. \( a \circ b = c \ (a, b, c \in G) \) (결합법칙) \(G\) 의 임의의 원소 \( a, b, c\ \) 에 다음이 성립한다. \( (a\circ b) \circ ..
알고리즘과 효율성 분석 알고리즘이란? 문제를 해결하는 단계적인 절차를 말한다. 알고리즘을 설계하고 분석하는 기술을 배우는 이유는 무엇일까? 새로운 문제에 직면했을 때 그 문제를 해결하기 위한 방법들을 익혀두기 위함이다. 여러 가능한 방법들이 있을 때 알고리즘 분석을 통해 어떤 방법을 선택할 지 결정할 수 있도록 수치화 하는 능력을 길러야 한다. -> 문제 해결력 제고 알고리즘 분석 요소 알고리즘을 수행했을 때 소요되는 시간 알고리즘을 수행할 때 차지하는 메모리 공간 알고리즘 분석 Time Complexity Analysis (시간 복잡도 분석) input size에 따라서 basic operation이 몇번 수행되는 지 결정하는 절차를 말한다. CPU에서의 실제작동 시간, 명령문의 개수, 프로그래밍 언어, 프로그래머, 포인터의..
[2022 연말결산] 이 글을 빌어 2022년 한해를 돌아보는 시간을 가져봅니다. 1월 1월은 제가 큰맘먹고 스마일라식 수술을 했습니다. 대략 300만원 정도 들었습니다. 1월 중순정도에 수술을 했고, 일주일간은 수술이 잘 안된줄 알았습니다. 바로 다음날 좌우 나안시력 1.0을 찍는 사람이 대부분이었는데 저는 한쪽은 1.0이고 다른 한쪽은 0.5정도 나왔던것 같습니다. 그렇게 한 2주가 지나니까 좌우 모두 1.2정도 나오더라구요. 수술후 한달 뒤, 세달 뒤, 여섯달 뒤 병원에 가서 검사를 받아야 하는데 게으른 저는 한달 뒤에만 병원을 갔습니다. 지금까지는 별 이상없이 잘 살고 있습니다. 다시 돌아가도 스마일 라식 수술을 할 것 같아요. 지금은 안경없는 삶이 너무 만족스럽고 좋습니다. 2월 고등학생들에게 학과를 소개하는 동아리..
[Data Mining] 4 - K-means clustering k-means Algorithm 유클리디안 공간/distance 를 가정. k (cluster 수)를 뽑으면서 시작. (1). 초기 centroid k개를 뽑는다. (2). 각 점들을 가장 가까운 centroid를 포함하는 cluster에 할당한다. (3). 각 cluster의 centroid를 다시 계산한다. (4). (2), (3)을 centroid가 변경되지 않을 때까지 계속한다. k는 어떻게 선정하는가? k를 진행하면서 centroid까지의 평균 distance가 빠르게 덜어지는 구간에서 선택.
[Data Mining] 4 - Clustering Clustering 점들이 주어지고, 점들 사이에 distance가 정의되어있다. N개의 cluster로 점들을 그룹화 하자. cluster의 멤버들은 비슷하거나 가깝다.(distance가 작다.) cluster가 다른 멤버들은 서로 비슷하지 않다. Usually: 점들은 고차원 공간에 존재한다. Similarity는 distance 척도로 정의된다. (유클리디안, 코사인, Jaccard, edit distance 등) clustering 고려 사항. 몇개의 cluster로 나눌지? 차원이 높으면 어렵다. 고차원 공간에서 clustering은 어려워 보인다. 거의 모든 pair들은 비슷한 distance를 가진다. -> 차원의 저주 차원의 저주 차원이 증가하면서 관측할수록 빈 공간이 많아지고 데이터간 거..
[Data Mining] 3 - Finding Similar Items : Locality Sensitive Hashing Finding similar items ex. - pages with similar words - Customers who purchased similar products - Images with similar features - Recommendations and search Problem definition 고차원 데이터 points x1, x2, .... , xn이 주어진다. distance fuction d(x1, x2) 가 주어진다. 이는 x1과 x2 사이의 거리를 나타낸다. d(xi, xj)가 s보다 작은 모든 pair of data points(xi, xj)를 찾아보자. Naive solution : O(N^2) N은 data points의 크기를 나타낸다. LSH를 사용하면 O(N)만에 가..
[Data Mining] 2 - Frequent Items : A-Priori algorithm A pirori algorithm 2-pass 접근법으로 메인 메모리 사용을 줄일 수 있다. Key Idea : Monotonicity 만약 아이템 셋 I가 적어도 s번 등장한다면, 집합 I의 모든 부분집합 J 또한 s번 이상 등장한다. 만약 아이템 i가 s 미만으로 등장한다면 i를 포함안 아이템 부분집합이 s 번 미만으로 등장한다. A-priori algorithm 구성 1. pass-1 : 모든 transaction을 1회 읽으면서 메인 메모리에 각각의 아이템의 등장횟수를 저장한다. item수만큼의 메모리 저장 공간이 필요하다. items that appear >= s times are frequent items 2. pass-2 : 모든 transaction을 다시 읽으면서 각각의 아이템의 등장횟수..
[Data Mining] 2 - Frequent Itemset 연관 규칙 찾기 많은 transaction이 존재한다고 하자. 각 transaction에는 아이템들의 부분집합이 있을 때 연관규칙을 찾아보자. Q1 : transaction들에서 빈번하게 등장하는 아이템 부분집합을 찾자 Support 란? 부분집합 I를 모두 포함하는 transaction의 수 또는 부분집합 I를 모두 포함하는 transaction의 비율 다음 표는 각 transaction에 해당하는 Item들을 나타낸 표이다. Transaction ID Items 1 Bread, Coke, Milk 2 Beer, Bread 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Coke, Diaper, Milk 위 표에 따르면 부분집합 {Beer, Brea..

티스토리툴바