\PassOptionsToPackage{pdfpagemode=FullScreen,hyperfootnotes=false}{hyperref}
\documentclass[14pt,xcolor=dvipsnames,professionalfont]{beamer}

\usepackage{amsmath,amssymb,amsfonts} 
\usepackage{tikz} 
\usepackage{graphicx}
\usepackage{listings}
\usepackage{ptext}

\usetheme{Ilmenau}
\usefonttheme{serif}
\usecolortheme[named=purple]{structure}
\setbeamercovered{transparent}
\expandafter\def\expandafter\insertshorttitle\expandafter {%
	\insertshorttitle\hfill%
	\inserttotalframenumber\,/\,\insertframenumber}
%\useoutertheme{infolines}
\usepackage[logo=off,inlinemathdigits=persian,displaymathdigits=persian]{xepersian}
\settextfont{XB Niloofar}
%\setlatintextfont{Times New Roman}
\setdigitfont{XB Niloofar}

\defpersianfont\nasi[Scale=1]{IranNastaliq}
\defpersianfont\titr[Scale=1.3]{B Titr}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\definecolor{mygreen}{RGB}{28,172,0} 
\definecolor{mylilas}{RGB}{170,55,241}
\lstset{language=Matlab,
	breaklines=true,basicstyle=\ttfamily\scriptsize,
	morekeywords={matlab2tikz},
	keywordstyle=\color{blue},
	morekeywords=[2]{1}, keywordstyle=[2]{\color{black}},
	identifierstyle=\color{black},
	stringstyle=\color{mylilas},
	commentstyle=\color{mygreen},
	showstringspaces=false
}


\input{command}
\raggedleft
%%%%%%%%%%%%%%%%%%5
\newcommand*{\co}[1]{\nas\textcolor{blue}{#1}}
\logo{\includegraphics[scale=.009]{logo.png} }
\newcommand{\nologo}{\setbeamertemplate{logo}{}}
\setbeamertemplate{theorems}[numbered]
%بولد 
\providetranslation{Theorem}{\large \bf قضیه}
\providetranslation{Definition}{تعریف}
\providetranslation{Example}{مثال}

\subtitle{مروری بر الگوریتم‌های وزن‌دهی به متغیرها در خوشه‌بندی 
$k$-میانگین}
\author{سحر همتی باغبانانی}
\institute{دانشکده‌ی علوم ریاضی\\
	گروه آمار}
\date{}
%\linespread{1.5}
\begin{document}
		\begin{frame}[plain,noframenumbering]
		\centerline{\includegraphics[width=\paperwidth,height=\paperheight]{1}}
	\end{frame}

\begin{frame}
\begin{block}{\titr{عنوان}}
\begin{center}
	\titr{مروری بر الگوریتم‌های وزن‌دهی به متغیرها در خوشه‌بندی 
		$k$-میانگین}
\end{center}
\end{block}
\begin{center}
\nasi{
\textcolor{blue}{ سحر همتی باغبانانی}

  \textcolor{violet}{استاد راهنما:}
\textcolor{blue}{دکتر محمدرضا فقیهی حبیب‌آبادی}

 \textcolor{violet}{استاد مشاور:}
\textcolor{blue}{دکتر حمیده داریوش همدانی}
}
\end{center}

\end{frame}

\fontsize{12}{12}\selectfont
\begin{frame}{روش‌های خوشه‌بندی
	$k$-میانگین موزون}
3 روش مورد بررسی قرار می‌گیرد:

\vspace{1cm}
\begin{enumerate}
	\item 
\pause
	خوشه‌بندی $k$-میانگین موزون ترکیبی
	\item
	\pause
		خوشه‌بندی $k$-میانگین موزون اصلاح شده
		\item
	\pause
	خوشه‌بندی $k$-میانگین موزون برمبنای وزن‌دهی بهینه
	
\end{enumerate}
\end{frame}
\begin{frame}{خوشه‌بندی 
	$k$-میانگین موزون ترکیبی }
یک روش دو مرحله‌ای است:
\vspace{1cm}
\begin{enumerate}
\item
\pause
افراز مجموعه‌ی متغیرها به زیر مجموعه‌ای از متغیرها و وزن‌دهی به هر زیر مجموعه
\item
\pause
وزن‌دهی به هر متغیر در هر زیر مجموعه و یافتن متغیرهای تاثیر گذار 
\end{enumerate}
\end{frame}
\begin{frame}{خوشه‌بندی 
	$k$-میانگین موزون اصلاح شده}
در این روش الگوریتم نسبت به روش قبلی پایدارتر است. 
\vspace{1cm}
\begin{enumerate}
	\item 
	\pause
	اختصاص وزن‌های بهینه به متغیرهای استاندارد شده
	\item
	\pause
	معرفی یک پارامتر تاوان
	\item
	\pause
	استفاده از الگوریتم بهینه‌سازی نلدر-مید
	
\end{enumerate}
\end{frame}
\begin{frame}{خوشه‌بندی $k$-میانگین موزون بر مبنای وزن‌دهی بهینه}
در این روش پیشنهادی الگوریتم برای مجموعه داده‌‌های با بعد بالا بهتر عمل می‌کند.
\vspace{1cm}
\begin{enumerate}
	\item 
	\pause
	استفاده از مدل خوشه‌بندی $k$-میانگین اصلاح شده
	\item
	\pause
	معرفی یک الگوریتم جدید برای یافتن وزن بهینه متغیرها
	\item
	\pause
	بهره‌گیری از شرایط کاروش-کهن-تاکر برای بررسی وزن‌های بهینه متغیرها
\end{enumerate}
\end{frame}
\begin{frame}{مدل پیشنهادی خوشه‌بندی 
	$k$-میانگین موزون}

$$f(w;\alpha)=\sum_{j=1}^{m}w_j \sum_{g=1}^{k}\sum_{i \in I_g} \frac{(z_{ij}-c_{ij})^2}{n-1}+\alpha \sum_{j=1}^{m} \frac{(w_j-1)^2}{m-1}$$
\pause
* $w_j$: وزن متغیر $j$ام
\\
* $z_{ij}$: مجموعه داده‌های استانداردشده 
\\
* $c_{gj}$: عنصر $j$ام 
گرانیگاه خوشه‌ای
\\
* $\alpha$: پارامتر تاوان

\end{frame}
\begin{frame}{مینیمم‌سازی مدل با استفاده از ضرایب لاگرانژ}

ضریب $w_j$ مانند $\beta_j$ در نظر گرفته می‌شود. بطوریکه:

$$\sum_{j=1}^{m} w_j=m$$
و
$$w_j \ge 0 ,\qquad j=1,2,\dots,m$$
\pause
با استفاده از ضرایب لاگرانژ مدل مذکور مینیمم می‌شود:
$$L(w,\lambda,\mu;\alpha)=f(w;\alpha)+\lambda(\sum_{j=1}^{m}w_j-m)+\sum_{j=1}^{m}\mu_j w_j$$
\end{frame}
\begin{frame}{شرایط کاروش-کهن-تاکر}
وزن‌های بهینه $w_1,w_2,\dots,w_m$ شرایط $KKT$ را برآورده می‌کند:
$$
\frac{\partial L}{\partial w_j}=\beta_j+\frac{2\alpha}{m-1}(w_j-1)+\lambda+\mu_j ,\qquad j=1,2,\dots,m
$$
\pause
$$
\sum_{j=1}^{m}w_j-m=0
$$
\pause
$$
\mu_j w_j=0,\qquad j=1,2,\dots,m 
$$
\pause
$$
w_j \ge 0 ,\qquad j=1,2,\dots,m
$$
\end{frame}
\begin{frame}{وزن متغیرها}
تعداد وزن‌های غیر صفر $t$ در نظر گرفته می‌شود:
\begin{equation}
\begin{cases}
w_j(\alpha,t)=\frac{(\bar{\beta_t}-\beta_j)(m-1)}{2\alpha}+\frac{m}{t},& \qquad j \le t \\
w_j(\alpha,t)=0,& \qquad j>t
\end{cases}
\end{equation}
و
\pause
$$\bar{\beta_t}=\frac{\sum_{j=1}^{m}\beta_j}{t}$$
\end{frame}
\begin{frame}{پیدا کردن وزن‌های بهینه متغیرها}
\begin{block}{پیدا کردن $t_{opt}$}
$$ g(t)=\frac{t(\beta_t-\bar{\beta_t})(m-1)}{2m}$$
\pause
هنگامیکه  	$\beta_1 \le \beta_2 \le \dots \le \beta_m$ 
$\leftarrow$
$g(t)$
تابع یکنوا
$$T(\alpha)=\{t \lvert g(t)<\alpha \le g(t+1)\}$$
\pause
پس:
$$ t_{opt}=argmin_{t \in T(\alpha)}f(w;\alpha)$$
\end{block}
\end{frame}
\begin{frame}{الگوریتم پیشنهادی}
\begin{enumerate}
	\item 

	استاندارد سازی ماتریس داده‌ها، مشخص کردن پارامتر  $\alpha$ و $\beta$
	\item 
    \pause
	محاسبه وزن متغیرها بهینه با توجه به $\alpha$ و $\beta$
	\item
	\pause
	انجام خوشه‌بندی $k$-میانگین روی متغیرهای موزون 
	$Z^*=Z\boldsymbol{*}D$ 
	\item
	\pause
	تکرار مراحل 2 و 3 تا همگرایی بردار پارامتر $\beta$
\end{enumerate}
\end{frame}
\begin{frame}{برآورد اولیه پارامتر $\beta$}
\begin{enumerate}
\item
تولید یک طرح سیمپلکس شبکه‌ای $\{m,2\}$ و بدست آوردن مجموعه‌ای از بردارهای 
$p=(p_1,p_2,\dots,p_m)$
\item
\pause
اجرای خوشه‌بندی $k$-میانگین با متغیرهای موزون 
$w=m\boldsymbol{*}p$
برای هر طرح
\item
\pause
محاسبه میانگین مربعات درون خوشه‌ای
\item
\pause
برازش مدل خطی متناسب
\item
\pause
در نظر گرفتن حداقل برآورد توان دوم بعنوان مقدار شروع پارامتر $\beta$
\end{enumerate}
\end{frame}
\begin{frame}{انتخاب پارامتر تاوان $\alpha$}
\begin{enumerate}
\item
تعیین مقدار $t$ با استفاده از $RV$:
$$RV_i=\frac{1-\beta_i}{\sum_{i=1}^{m}(1-\beta_i)} ,\qquad \sum_{i=1}^{m} RV_i=1.$$
\pause
$$t_{selected}=min\{t\lvert \sum_{i=1}^{m}RV_i>\frac{m-1}{m}\}$$
\item
\pause
انتخاب پارامتر تاوان:
$$\alpha_{selected}=\frac{g(t_{selected})+g_(t_{selected}+1)}{2}$$
\end{enumerate}
\end{frame}

\begin{frame}{مطالعه شبیه‌سازی}
\begin{itemize}
\item
5 گروه 3 بعدی، هر گروه شامل 100 مشاهده
\begin{figure}[H]
	\centering
	\includegraphics[height=3cm,width=4cm]{sh1}
\end{figure}
\pause
\begin{table}[h!]
	\begin{center}
		\scalebox{0.8}{
			\begin{tabular}{|c|c|c|c|}
				\hline
				
				\text{}
				&\text{پارامتر $\beta$} 
				&\text{انتخاب $\alpha$} 
				&\text{وزن‌های بهینه متغیرها}\\ \hline
				
				\text{برآورد اولیه}	
				& $0.087,0.087,0.222$ &$0.045$ &	$1.506,1.494,0$  \\
				
				\text{تکرار اول}	
				& $0.027,0.027,0.996$ &$0.32$ &	$1.506,1.494,0$  \\
				
				\text{تکرار دوم}	
				&$0.027,0.027,0.996$ &$0.32$ &	$1.50,1.50,0$  \\
				\hline
			\end{tabular}
		}
	\end{center}
\end{table}

\end{itemize}
\end{frame}

\begin{frame}{مطالعه شبیه‌سازی}
\begin{itemize}
\item
7 گروه 8 بعدی، هر گروه شامل 100 مشاهده
\begin{figure}[H]
	\centering
	\includegraphics[height=3cm,width=4cm]{sh2}
\end{figure}

\pause
\begin{table}[h!]
	\begin{center}
		\scalebox{0.52}{
			\begin{tabular}{|c|c|c|c|}
				\hline
				
				\text{}
				&\text{پارامتر $\beta$} 
				&\text{انتخاب $\alpha$} 
				&\text{وزن‌های بهینه متغیرها}\\ \hline
				
				\text{برآورد اولیه}	
				& $0.06,0.06,0.06,0.18,0.18,0.18,0.18,0.19$ &$0.17$ &	$2.5,2.5,2.5,0.11,0.09,0.06,0.05,0$  \\
				
				\text{تکرار اول}	
				& $0.03,0.03,0.03,0.99,0.99,0.99,0.99,0.99$ &$0.63$ &	$2.5,2.5,2.5,0.11,0.09,0.06,0.05,0$  \\
				
				\text{تکرار دوم}	
				& $0.03,0.03,0.03,0.99,0.99,0.99,0.99,0.99$ &$0.63$ &	$2.6,2.6,2.6,0,0,0,0,0$  \\
				\hline
			\end{tabular}
		}
	\end{center}
\end{table}
\end{itemize}
\end{frame}

\begin{frame}{مقایسه دقت خوشه‌بندی}
\begin{table}[h!]
	\renewcommand{\arraystretch}{2}
	
	\begin{center}
		\resizebox{\textwidth}{!}{
			
			\begin{tabular}{|c c|c|c|  }
				\hline
				
                &
				&\text{مطالعه شبیه‌سازی اول}
				&\text{مطالعه شبیه‌سازی دوم}
				 \\ \hline
				
	
				\textbf{روش ها و لیم}
				&\text{احتمال بد رده‌بندی} 
	            &1/500	
	            &189/700
	            \\ 
				
				&\text{درصد بد رده‌بندی}
				&$0.2\%$
				&$27\%$
				\\ \hline	
				
			    \textbf{روش پیشنهادی}
		    	&\text{احتمال بد رده‌بندی}  
			    &0/500	
			    &0/700
		       \\	
			
			    &\text{درصد بد رده‌بندی}
			    &$0$
			    &$0$
			\\ \hline	
			\end{tabular}
		}
	\end{center}
\end{table} 
\end{frame}
\begin{frame}{مقایسه ثبات الگوریتم‌ها}
	\begin{figure}[H]
		\centering
		\includegraphics[height=2.5cm,width=10cm]{sh3}
	\end{figure}

		\begin{figure}[H]
		\centering
		\includegraphics[height=2.5cm,width=10cm]{sh4}
	\end{figure}
\end{frame}
\begin{frame}{کاربرد روی داده‌های هزینه-درآمد خانوار در سال 1398}
\pause
\begin{block}{معرفی متغیرها}

*
هزینه خوراکی و دخانیات $\leftarrow$ c1\\
*
هزینه مسکن$\leftarrow$ c2\\
* 
هزینه مبلمان$\leftarrow$ c3\\
* 
هزینه بهداشت$\leftarrow$ c4\\
* 
هزینه حمل‌ونقل$\leftarrow$ c5\\
* 
هزینه ارتباطات$\leftarrow$ c6\\
* 
هزینه کالاوخدمات$\leftarrow$ c7

\end{block}
\end{frame}
\begin{frame}{نتیجه خوشه‌بندی}
\begin{block}{وزن‌های متغیرها}

\begin{table}[h!]
	\begin{center}
		\scalebox{0.9}{
			\begin{tabular}{c| c c c c c c c}
				\hline
				
				&\lr{c1}
				&\lr{c2}
		    	&\lr{c3}
				&\lr{c4}
				&\lr{c5}
				&\lr{c6}
				&\lr{c7}
				\\ \hline
				
				\text{برآورد اولیه}
                &$2.60$
                &$1.56$
		        &$1.12$
		        &$1.11$
		        &$0.45$
		        &$0.139$
		        &$0$	
				\\ 
				
				
				\text{تکرار اول}
				&$2.93$
				&$2.85$
				&$0.99$
				&$0.11$
				&$0.09$
				&$0$
				&$0$	
				\\ 
				
				\text{تکرار دوم}
				&$3.30$
				&$3.30$
				&$0.54$
				&$0.10$
				&$0$
				&$0$
				&$0$		
				\\
				\text{تکرار سوم}
				&$3.36$
				&$3.11$
				&$0.40$
				&$011$
				&$0$
				&$0$
				&$0$	
				\\	
				
				\text{تکرار چهارم}
				&$3.37$
				&$3.11$
				&$0.39$
				&$0.11$
				&$0$
				&$0$
				&$0$	
				\\
				
				\text{تکرار پنجم}
				&$3.42$
				&$3.17$
				&$0.28$
				&$0.11$
				&$0$
				&$0$
				&$0$	
				\\	
				\text{تکرار ششم}
				&$3.45$
				&$3.22$
				&$0.22$
				&$0.09$
				&$0$
				&$0$
				&$0$
				\\
				
				\text{تکرار هفتم}
				&$3.45$
				&$3.22$
				&$0.22$
				&$0.10$
				&$0$
				&$0$
				&$0$	
				\\
			\end{tabular}
		}
	\end{center}
\end{table} 

\end{block}
\end{frame}


\begin{frame}{نتیجه خوشه‌بندی}
\begin{block}{برآورد پارمترهای $\beta$ و $\alpha$}
	
	\begin{table}[h!]
		\begin{center}
			\scalebox{0.9}{
				\begin{tabular}{c| c c c c c c c|c}
					\hline
					
					&\lr{c1}
					&\lr{c2}
					&\lr{c3}
					&\lr{c4}
					&\lr{c5}
					&\lr{c6}
					&\lr{c7}
					&\lr{$\alpha$}
					\\ \hline
					
					\text{برآورد اولیه}
					&$0.32$
					&$0.38$
					&$0.40$
					&$0.40$
					&$0.43$
					&$0.45$
					&$0.46$
					&$0.14$	
					\\ 
					
					
					\text{تکرار اول}
			    	&$0.45$
				    &$0.46$
			    	&$0.74$
		     		&$0.88$
		    		&$0.88$
			     	&$0.91$
			    	&$0.94$
			    	&$0.45$	
					\\ 
					
					\text{تکرار دوم}
						&$0.4$
					&$0.44$
					&$0.83$
					&$0.89$
					&$0.93$
					&$0.95$
					&$0.98$
					&$0.46$			
					\\
					\text{تکرار سوم}
						&$0.39$
					&$0.43$
					&$0.85$
					&$0.9$
					&$0.93$
					&$0.95$
					&$0.95$
					&$0.46$		
					\\	
					
					\text{تکرار چهارم}
					&$0.39$
					&$0.43$
					&$0.86$
					&$0.9$
					&$0.93$
					&$0.95$
					&$0.95$
					&$0.46$		
					\\
					
					\text{تکرار پنجم}
					&$0.39$
					&$0.43$
					&$0.87$
					&$0.9$
					&$0.93$
					&$0.95$
					&$0.95$
					&$0.45$		
					\\	
					\text{تکرار ششم}
					&$0.39$
					&$0.43$
					&$0.88$
					&$0.9$
					&$0.93$
					&$0.95$
					&$0.95$
					&$0.45$	
					\\
					
					\text{تکرار هفتم}
					&$0.39$
					&$0.43$
					&$0.89$
					&$0.9$
					&$0.93$
					&$0.96$
					&$0.96$
					&$0.45$		
					\\
				\end{tabular}
			}
		\end{center}
	\end{table} 
\end{block}
\end{frame}

\begin{frame}{نتیجه خوشه‌بندی}
\begin{block}{بررسی نیم‌رخ خوشه‌ها}
\begin{table}[h]
	%	\renewcommand{\arraystretch}{1.1}	
	\begin{center}
		%\resizebox{\textwidth}{!}{
		
		\begin{tabular}{|c|c|c|c|}
			
			\hline
			&\text{خوشه‌ی اول} 
			&\text{خوشه‌ی دوم} 
			&\text{خوشه‌ی سوم} 
			\\ \hline
			
			
			\text{درآمد}
			&\text{ زیاد}
			&\text{ متوسط}
			&\text{ کم}
			\\ \hline
			
			
			\text{سن}
			&\text{ زیاد}
			&\text{ متوسط}
			&\text{ کم}
			\\ \hline
			
			\text{سطح زیربنا}
			&\text{زیاد}
			&\text{متوسط}
			&\text{کم}
			\\	\hline
			
			\text{مدرک تحصیلی}
			&\text{ بالا}
			&\text{ متوسط}
			&\text{ پایین}
			\\\hline
			
			\text{تسهیلات رفاهی}
			&\text{بالا}
			&\text{متوسط}
			&\text{پایین}
			\\
			\hline
		\end{tabular}
		%	}
	\end{center}
	
\end{table}
\end{block}
\end{frame}
\begin{frame}{نتیجه خوشه‌بندی}
	\begin{figure}[H]
	\centering
	\includegraphics[height=5cm,width=7cm]{sh5}
\end{figure}
\end{frame}
\begin{frame}{پیشنهاداتی برای ادامه مسیر}
\begin{enumerate}
\item
استفاده از روش دیگری برای برآورد پارامتر $\beta$ 
\item
\pause
انتخاب بهینه تعداد خوشه‌  
\item
\pause
اضافه کردن متغیرهای دودویی

\end{enumerate}
\end{frame}



\begin{frame}{مراجع}
\begin{thebibliography}{999}
\begin{latin}
	\bibitem[ژانگ و همکاران (2019)]{zhang2019iterative}
	Zhang, \& Shaonan. (2019) An iterative algorithm for optimal variable weighting in K-means clustering. \textit{Communications in Statistics-Simulation and Computation} \textbf{48.5}: 1346-1365.

	\bibitem[دیزاربو و همکاران (1984)]{desarbo1984synthesized}
	DeSarbo, \& Wayne S. (1984) Synthesized clustering: A method for amalgamating alternative clustering bases with differential weighting of variables. \textit{Psychometrika} \textbf{49.1}: 57-78.
	
	\bibitem[ها و لیم (2009)]{huh2009weighting}
	Huh, \& Lim. "Weighting variables in K-means clustering. \textit{Journal of Applied Statistics} \textbf{36.1}: 67-78.

\end{latin}
\end{thebibliography}
\end{frame}
\begin{frame}{مراجع}
	\begin{thebibliography}{999}
		\begin{latin}
	\bibitem[شمولی و همکارارن (2018)]{shmueli2011data}
Shmueli, \& Galit. (2018). Data mining for business intelligence: \textit{Concepts, techniques, and applications in R}. John Wiley and Sons.

\bibitem[کاروش و همکاران(1939)]{karush1939minima}
Karush, \& William. (1939). Minima of functions of several variables with inequalities as side constraints. \textit{M. Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago}.

\bibitem[]{kuhn1951}
Kuhn,\& Tucker. (1951). Proceedings of 2nd Berkeley Symposium on Mathematical Statistics and Probability. \textit{Berkeley: University of California Press}
		\end{latin}
	\end{thebibliography}
\end{frame}
\end{document}