\documentclass[a4paper]{jsarticle}

\usepackage{tani_resume}%�X�^�C���t�@�C���̓ǂݍ���

\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

%jp�͓��{��
%e�͉p��
%title��author�͎����p�ɏ��������Ă��������B

\setcounter{page}{9}
\jptitle{�A���N���X�^�����O�@��p���������̎�������}
\etitle{Automated classification of dialect that uses connected clustering}
\jpauthor{�����@�Y��}
\eauthor{Sato Yuta}
\course{�J�@������}
\year{21}
\abstract{%�T�v(2009�����o�[�͏����Ă��܂��B)
%��������
Kolmogorov �L�q�ʂɊ�Â����f�[�^�Ԃ̗ގ��x�Ɋւ��鋗������`����ADNA �̗ގ��x�⌾��̗ގ��x�A���y��
�ގ��x����ɗL�p���Ƃ����������ʂ������Ă���B2007�N�x�A���{��w�����w�����V�X�e����͊w�ȒJ�������A
�x���A����A�֍��� Kolmogorov �L�q�ʂ�p���������̗ގ��x���͂ɂ����āANJ�@�AUPGMA�@�AQualtet Method �̂R���
�̃N���X�^�����O��@��p���ĕ����̎������ނ��s�����B[2]
�{�����ł́A���{�d�C�i���j�����A�㓡�A�������Ă����A���N���X�^�����O�@
���A�����̕��ނɗL�p���ǂ����𒲂ׂ�������s���B
%�����܂ŊT�v
}


\begin{document}%�h�L�������g�̎n��

\maketitle

\begin{multicols}{2}%���͂�2�i���ɕ����違���͂̎n��

\section{�͂��߂�}

%�w�i�E���@�E��s�����E�ړI�E�����邱�Ƃ����̉���

���݂̕��������Ƃ������̂͒P��P�ʁA�A�N�Z���g�A
�C���g�l�[�V�����ɂ�錤�����Ȃ���Ă���B��������
�͒P�ʂł̌����Ƃ������̂͗]��i�߂��Ă��Ȃ��B��
����Ming Li �炪Kolmogorov �L�q�ʂɊ�Â��f�[
�^�Ԃ̗ގ��x�Ɋւ��鋗����\��similarity metric ��
�Ă����i����DNA �̗ގ��x�⌾��̗ގ��x�A���y�̗ގ��x
����ɗL�p���Ƃ������Ƃ��������Ă���B�j�ɂ��A
2007�N�x�A���{��w�����w�����V�X�e����͊w�ȒJ�������A�x���A����A�֍���Kolmogorv �L�q�ʂ�p
���������̗ގ��x���͂��s�����B��ɁA�����R�[�h�A�O�����A
�N���X�^�����O��@�iNJ�@�AUPGMA�@�AQuartet Method�@�̂R��ށj�̈Ⴂ�ł̌������s�������ʁA
�N���X�^�����O��@�ł́ANJ�@�̗L�p�����m���߂邱�Ƃ��ł����B[2]
�{�����ł́A�x����̎����œ���ꂽ�f�[�^���A���{�d�C�i���j�����A�㓡�A�������Ă����A���N���X�^�����O�@[1]��p����
�����̎������ނ��s���A�A���N���X�^�����O�@�̗L�p���𒲂ׂ�������s���B\\
��Q�͂ł͈��k�ގ��x�ɂ��āA��R�͂ł̓N���X�^�����O�ɂ��āA
��S�͂ł͎����T�v�A��T�͂ł͎������ʁA
��U�͂ł͍l�@���q�ׂ�B

%�����܂Ł@�͂��߂�

\section{���k�ގ��x}
%���������
���w�ɂ����ċ�����ԂƂ́C�C�ӂ�2 �_�Ԃŋ�������
�߂�ꂽ��Ԃ̂��Ƃ������B\\
\fbox{��`}\\
����W��$X$ ��̋����Ƃ́C�����l�֐�$d : X \times X \rightarrow R $
�ŔC�ӂ�$x, y, z \in  X $�ɑ΂��Ď��̂悤�Ȑ����𖞂����B
\[ d(x, y) \geq 0 \]
\[ d(x, y) = 0 \Leftrightarrow x = y \]
\[ d(x, y) = d(y, x)  \]
\[ d(x, y) \leq d(x, z) + d(z, y) : �O�p�s���� \]
��������ƂɁC��񋗗��ɂ��čl����B
Ming Li,Xin Chen ��̌����ł́C���Ɋւ��鋗��
��W�������Ă���, �C�ӂ̕�����x; y �ɂ��āC�ȉ���
�悤�Ɍ��߂Ă���B
\[d(x,y) =  \frac{max \{K(x|y),K(y|x) \}}{max \{K(x),K(y) \}} \]
�܂��C$K(y) \geq K(x)$�Ƃ����Ƃ��C
\[d(x,y) = \frac{K(y|x)}{K(y)} \]
����ɑ΂��ď��ʂ̌�����p����ƁC
\[d(x,y) = \frac{K(y) - I(x:y)}{K(y)} \]
�ƂȂ�B�܂�2 �߂Ŏ������ʂ�C$O(logK(xy))$ �͈̔�
�ł�$K(xy) = K(x) + K(y|x)$ �����藧�̂ŁC
\[d(x,y) = \frac{K(xy) - K(x)}{K(y)} \]
�ƕ\�����Ƃ��ł���B\\
kolmogorov �L�q�ʂ͌v�Z�ł��̒l���Z�o���邱�Ƃ�
�s�\�ł��邽��, ���k�v���O������p���Ēl���ߎ��I
�ɋ��߂邱�ƂɂȂ�B$bz2(x) $�𕶎���$x$ ��$bzip2 $�ň��k
�����Ƃ��̃t�@�C���T�C�Y�Ƃ���Ə�񋗗�$d(x; y)$ ��
�ȉ��̂悤�ɋߎ������B
\[d(x,y) \fallingdotseq \frac{bz2(xy) - bz2(x)}{bz2(y)} \]
�@�܂����k���@$C$ ���ȉ��𖞂����Ƃ�$O(log n)$ �̌덷
�͈̔͂Ŗ��\�ł���Əؖ�����Ă���B\\
\begin{enumerate}
\item �C�ӂ̕�����$x$ �ɑ΂���$C(xx)=C(x)$ �ł���A�󕶎���ɂɑ΂��āA$C(��)=0$ �ł���B
\item �C�ӂ̕�����$x; y$ �ɑ΂���$C(xy) �� C(x)$�B
\item �C�ӂ̕�����$x; y$ �ɑ΂���$C(xy) �� C(yx)$�B
\item �C�ӂ̕�����$x; y; z$ �ɑ΂���$C(xy)+C(z)��C(xz)+C(yz)$�B
\end{enumerate}

%�����܂Ł@���������

\section{�N���X�^�����O}
%����̉ۑ�
�����NJ �@�AUPGMA�Aquartet-method �̂R�̃N
���X�^�����O��@���̗p�����B
�@�����͂ǂꂾ�����Ă��邩�������ړx�Ƃ��ċ�����
�p����Ƃ������������邱�ƂƁA��N�Ƃ̔�r���s����
�߂Ɏg�p�����B

\subsection{ NJ�@}
�ߗ׌����@�ƌĂ΂�A�S�Ă̎}�̒����̑��a���ŏ���
�Ȃ�悤�Ɍn�������쐬���Ă��������n�����B
�@�������ǂ��A���̕��@�ł͈����Ȃ��悤�ȑ�ʂ̃f�[
�^���������Ƃ��ł��邪�A�o�͂��ꂽ�؂��œK�Ƃ͌���
�Ȃ��B

\subsection{UPGMA�@}
���ϋ����@�ƌĂ΂��P���Ȍn��������@�ŁA�ł���
���ȃN���X�^�Ԃ̋����̕��ς����߂Ȃ���n�������쐬
����B�@�t���猈�܂�A�Ō�̍��̈ʒu�����܂�L���n
�����B

\subsection{Quartet Method}
�؂������\�ɂǂ̒��x�����Ă��邩�]����������
��A�����_���ɖ؂�ύX���]���l���X�V���Ă����q���[
���X�e�B�b�N�i���s����j�A���S���Y���ł���B
�@NJ �@�AUPGMA �@�Ɣ�r����Ƒ啝�ɏ������Ԃ�v
����B

%�����܂Ł@����̉ۑ�
\subsection{�A���N���X�^�����O�@}
�A���N���X�^�����O�@�́A������A�����Ȃ���N���X�^��
��������@�ł���A�}1�̎菇�Ŏ��s����B�܂��A�����W��$D$ �Ƌ��߂�N���X�^��$K$ �����͂����
�ƁA�e�������e�N���X�^�Ƃ����v�f��$N$ �̃N���X�^�W��
$C$ ���쐬����B
���ɁA�����y�A�Ԃ̔�ގ��x$NCD$ ���v�Z���A�ł��ގ�
�x�̍����i���Ȃ킿$NCD$�̏������j�����y�A$d_{x}$ ��$d_{y}$��T
���B
\\
\\
\\
\\
\\
\\
\\
\hrule width 8cm
Algorithm �F �A���N���X�^�����O�@
\hrule width 8cm


\begin{tabular}{lcr}
input : \hspace{10mm} $D$ : �����W�� \{$d{1},d{2}$,�c,$d{N}$ \}&  &  \\
\hspace{22mm} $K$ : �N���X�^�� & &  \\
output : \hspace{8mm} $C$ : �N���X�^�W�� \{$C{1},C{2}$,�c,$C{K}$ \}&  & \\
Begin &  &  \\
 \hspace{10mm} $C=\{\{d_{1}\},\{d_{2}\},�c,\{d_{N}\}\}$ &  &  \\
 \hspace{10mm} $For  k=1, 2, �c, N-K $&  &  \\
 \hspace{15mm} $(d_{x} ,d_{y} ) = argmin NCD(d_{i} ,d_{j} )$ &  &  \\
 \hspace{15mm} $d_{x} = d_{x}�Ed_{y}$ &  &  \\
 \hspace{15mm} $D =D | d_{y}$ &  &  \\
 \hspace{15mm} $C_{x} = C_{x}  \cup  C_{y}$&  &  \\
 \hspace{15mm} $C = C | C_{y}$&  &  \\
End&  &  \\

\end{tabular} 
\hrule width 8cm
�}�P     �A���N���X�^�����O�@
\\

���ꂩ��C�ł�$NCD$ �̏����������y�A��A������$d_{x}�E
d_{y}$ �����߂�$d_{x}$ �ƁA$d_{y}$ �𕶏��W��$D$ ����폜����B
�����ŁA�����y�A�̘A���Ƃ́A����$d_{x}$��$d_{y}$ �����ɕ��ׂ�����
�ł���B�����āA�N���X�^$C_{x}$ ��$C_{y}$ ��
�������N���X�^�����߂�$C_{x}$ �Ƃ��A�N���X�^$C_{y}$ ���폜����B
����當���y�A�I���C�����̘A���C�N���X�^�̕�����
����������J��Ԃ����Ƃɂ��A�A���N���X�^�����O�@
�́A�������N���X�^�����O����D$N-K$ ��J��Ԃ��ƃN���X
�^����$K$ �ƂȂ�̂ŃN���X�^�����O���I�����A�N���X�^
�W��$C$ ���o�͂���B

\section{�����T�v}
�S��56�ӏ���9�n���ɕ�������B
(�k�C���A���k�A�֓��A�����A�ߋE�A�����A�l���A��B�A����)\\
�����āA�N���X�^�W���̐���10�Ƃ��A���ꂼ��̃N���X�^�W�����̃f�[�^���A
9�n���ɂǂ̂悤�ɕ�����Ă��邩�����؂���B
\subsection*{�����f�[�^}
�����������낤�i�ďC�E���F��������q�j�Ƃ����\�t
�g�ɐ̘b�u�����Y�v�����{�e�n�T�U�ӏ��̕����œǂ܂�
�������f�[�^������B���̉����f�[�^���e�L�X�g���i��
�炪�ȁE�B�̂ݎg�p�j�܂��u���v���u���v�A�u�ցv���u���v�A
�u�́v���u��v�A�L�΂����͑O�̉��̕ꉹ�����������
��Ƃ������͂̏������������B[2]\\


\subsection*{�O����}
�g�p�p�x����������1 ����Ή������ĕϊ�����B[2]




\section{��������}
�ǂ̃N���X�^�W���ɂǂ��̒n�悪�������ނ���Ă��邩��\���B$c1�`c10$�c�N���X�^�W��\\

\begin{itemize}
\item$c1$�c�k�C��2, �֓�4, ����3, �ߋE6, ����2, �l��4
\item$c2$�c��B2
\item$c3$�c���k1, �l��1, ��B2
\item$c4$�c���k1, �֓�4, �l��2, ��B4
\item$c5$�c���k2
\item$c6$�c����1, ��B1
\item$c7$�c���k2, �֓�4, ����2, ����1
\item$c8$�c����1, ��B1
\item$c9$�c����1
\item$c10$�c����1
\end{itemize}

\section{�l�@}
�Ǐ��ɒn�悲�Ƃ̂܂Ƃ܂�������邪�A�S�̓I�ɂ͊e�n�����΂�΂�ɂȂ����B
����͎����ɑ啝�Ȏ��Ԃ�v�����̂ŁA�O�������{�����f�[�^��1��ނ��������ł��Ȃ������B
����͑��̑O�������{�����f�[�^��p���Ď������邱�Ƃ��ۑ�B
�����āA���R�̃N���X�^�����O��@�Ɣ�r���邽�߂ɁA�ŏI�I�Ɂh�؁h�Ƃ��ĕ\��
���邱�Ƃ��K�v�B





\end{multicols}%2�i���̕��͂̏I���

\begin{thebibliography}{2}%�Q�l����({2}�F2�Q�l����������Ƃ����Ӗ�)
\bibitem{a}
���� �R�I�q�@�ܓ� �q�v�@��� �_�l�@�@�R�����S���t���G���Ɋ�Â����i�E�T�[�r�X�̉��l�]��

\bibitem{b}
�x���K�i�@Kolmogorov �L�q�ʂɊ�Â��ގ��x��p���������̎������ށ@(2007)

\end{thebibliography}%�Q�l�����I���

\end{document}%�h�L�������g�̏I���

