お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

距離を求めるプログラムを書こう(2)

データサイエンス

こんにちは。前回はライブラリをインポートして距離のプログラムを書きました。といっていいのかな?

今回は、自分で計算式を書きます。車輪の再発明です。書くのが楽なので、Pythonで書きます。ライブラリがあってもそんなこと知りません。

ミンコフスキー距離・ユークリッド距離・マンハッタン距離

これらは次数の違いだけなので、まとめてしまいます。プログラムは次のとおりです。

def myMinkowski( list1, list2, dimension = 2 ):
	if len( list1 ) != len( list2 ):
		return None
	sum = 0
	for ( x1, x2 ) in zip( list1, list2 ):
		sum += abs( x1 - x2 )**dimension
	return sum ** ( 1 / dimension )

if __name__ == '__main__':
	a = [ 5, 9, 6, 3 ]	#ごくろうさん
	b = [ 4, 6, 4, 9 ]	#よろしく
	c = [ 1, 1, 2, 9 ]	#いい肉

	print( myMinkowski( a, b, 2 ) )
	print( myMinkowski( b, c, 2 ) )
	print( myMinkowski( c, a, 2 ) )

	print( myMinkowski( a, b, 1 ) )
	print( myMinkowski( b, c, 1 ) )
	print( myMinkowski( c, a, 1 ) )

そして、実行結果です。

7.0710678118654755
6.164414002968976
11.489125293076057
12.0
10.0
22.0

チェビシェフ距離

プログラムです。

def myChebyshev( list1, list2 ):
	if len( list1 ) != len( list2 ):
		return None
	max = 0
	for ( x1, x2 ) in zip( list1, list2 ):
		max = max if max > abs( x1 - x2 ) else abs( x1 - x2 )
	return max

if __name__ == '__main__':
	a = [ 5, 9, 6, 3 ]	#ごくろうさん
	b = [ 4, 6, 4, 9 ]	#よろしく
	c = [ 1, 1, 2, 9 ]	#いい肉

	print( myChebyshev( a, b ) )
	print( myChebyshev( b, c ) )
	print( myChebyshev( c, a ) )

そして、実行結果です。

6
5
8

ジャッカード係数・ジャッカード距離

プログラムです。

def myJaccard_distance( set1, set2 ):
	return ( len( set1 | set2 ) - len( set1 & set2 ) ) / len( set1 | set2 )

if __name__ == '__main__':
	sato = { "高橋", "田中", "伊藤", "渡辺" }
	suzuki = { "高橋", "田中", "伊藤", "山本" }

	print( myJaccard_distance( sato, suzuki ) )
	print( 1 - myJaccard_distance( sato, suzuki ) )

そして、実行結果です。

0.4
0.6

ハミング距離

プログラムです。

def myHamming_distance( string1, string2 ):
	if len( string1 ) != len( string2 ):
		return None
	count = 0
	for ( x , y ) in zip( string1, string2 ):
		count = count + 1 if x != y else count
	return count

if __name__ == '__main__':
	a = '5963'	#ごくろうさん
	b = '4949'	#よろしく
	c = '1129'	#いい肉

	print( myHamming_distance( a, b ) )
	print( myHamming_distance( b, c ) )
	print( myHamming_distance( c, a ) )

そして、実行結果です。

3
3
4

コサイン類似度

プログラムです。

def myCosine( list1, list2 ):
	if len( list1 ) != len( list2 ):
		return None
	sum = 0
	norm1 = 0
	norm2 = 0
	for ( x , y ) in zip( list1, list2 ):
		sum += x * y
		norm1 += x * x
		norm2 += y * y
	return 1 - sum / ( norm1 ** 0.5 * norm2 ** 0.5 )

if __name__ == '__main__':
	import math
	 
	a = [ 5, 9, 6, 3 ]	#ごくろうさん
	b = [ 4, 6, 4, 9 ]	#よろしく
	 
	theta = math.acos( 1 - myCosine( a, b ) )
	print( math.degrees(theta) )

そして、実行結果です。

33.55539016862236

次回予告ですが、レーベンシュタイン距離を書きます。レーベンシュタイン距離だけ、今回取り上げなかった理由は、アルゴリズムが動的計画法によるもので、ちゃんと説明すると長くなりそうだったからです。ということで内容を積み残して、今回はおしまい。それではまた。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai