2021-11-22 21:31 작성

자카드 유사도

정의

자카드 유사도는 집합 간의 유사도를 검사하는 방법 중 하나다. 두 집합 A, B 사이의 자카드 유사도는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값이다. 이 때, A, B가 모두 공집합일 경우, 나눗셈이 정의되지 않으므로 1로 정의한다.

예시

“FRANCE”와 “FRENCH”를 2글자씩 끊어 자카드 유사도를 구한다면,

• FRANCE: {FR, RA, AN, NC, CE}
• FRENCH: {FR, RE, EN, NC, CH}
• 교집합: {FR, NC}
• 합집합: {FR, RA, AN, NC, CE, RE, EN, CH}
• 유사도: 2 / 8 = 0.25

  두 집합 간의 합집합은 서로 중복되는 값을 제거하고 계산한다. 예를 들어, {1, 1}과 {1, 2}의 합집합은 {1, 1, 2}다.

생각 1. 어디에 사용 가능할까?

• 정렬 기능에 있어서 비슷한 주제로 사용자에게 데이터를 제공할 필요가 있는 경우
• 고객 간 유사도

예를 들어, A 고객의 상품 결제 내역을 일렬로 나열한다고 하고,

- A: [샤넬가방, 구찌지갑, 구찌드레스, 태그호이어 시계]

B고객의 상품 결제 내역이 다음과 같다고 할 때,

- B: [샤넬가방, 구찌지갑, 구찌드레스, 에르메스 가방, 태그호이어 시계]

A 고객에게 비슷한 선호를 가진 B 고객의 상품을 추천한다면 A 고객도 만족할 확률이 높을 것이다(유사도: 4/5, 80%의 유사도를 가짐). 이와 같이 고객 간 데이터를 바탕으로 한 이런 추천 알고리즘을 짜는 것도 가능할 듯 하다.

function solution(str1, str2) {
	var answer = clustering(str1, str2);
	return answer;
}

const clustering = (str1, str2) => {
	const constant = 65536;
	let splited1 = str1.trim().toLowerCase().split("");
	let splited2 = str2.trim().toLowerCase().split("");

	// 두 개로 쪼갠 문자열 array
	let set1 = [];
	let set2 = [];

	// 교집합
	let intersection = [];

	// 합집합
	let union = [];

	// splited1 문자열 두 개로 쪼개기
	for (let e = 0; e < splited1.length; e++) {
		// 각 element가 영문만 포함할 경우 저장
		if (
			splited1[e + 1] &&
			/[a-z]/.test(splited1[e]) &&
			/[a-z]/.test(splited1[e + 1])
		)
			set1.push(splited1[e] + splited1[e + 1]);
	}

	// splited2 문자열 두 개로 쪼개기
	for (let e = 0; e < splited2.length; e++) {
		if (
			splited2[e + 1] &&
			/[a-z]/.test(splited2[e]) &&
			/[a-z]/.test(splited2[e + 1])
		)
			set2.push(splited2[e] + splited2[e + 1]);
	}

	// 교집합 변경 전 합집합 저장
	union = set1.concat(set2);

	// 교집합 구하기
	set1.forEach((elem) => {
		let i = set2.findIndex((e) => e === elem);
		if (i >= 0) {
			intersection.push(elem);
			set2.splice(i, 1);
		}
	});

	// 합집합 구하기 (집합 A) + (집합 B) - (교집합)
	intersection.forEach((elem) => {
		let i = union.findIndex((e) => e === elem);
		union.splice(i, 1);
	});

	// 교집합의 분자, 분모가 0인 경우 constant를 반환하고 그 이외에는 모두 계산된 값으로 반환
	return intersection.length === 0 && union.length === 0
		? constant
		: Math.trunc((intersection.length / union.length) * constant);
};