EM最大期待アルゴリズム

13255 ワード
アルゴリズム データマイニング 技術
参考資料:http://blog.csdn.net/zouxy09/article/details/8537620
http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html
マイデータ・マイニング・アルゴリズム・コードの実装:
https://github.com/linyiqun/DataMiningAlgorithm
紹介する
Emアルゴリズムは,暗黙変数を含むパラメータモデルの最大尤度推定または極大後験確率推定に用いる反復アルゴリズムである.EMアルゴリズムは,フレームワークの考え方として,データクラスタリング領域であるファジイクラスタリングの処理など多くの分野に応用可能であり,後でこのような実現例を示す.
EMアルゴリズムの原理
EMアルゴリズムは名前から2つの部分に分けられ,E−StepとM−Stepに分けられる.E-Stepを所望化ステップと呼び、M-Stepを最大化ステップとする.
全体アルゴリズムの手順は次のとおりです.
1、分布パラメータを初期化する.
2、(E−Step)期待Eを算出し、隠蔽変数に対する既存の推定値を用いてその最大尤度推定値を算出し、期待化を実現するプロセス.
3、(M-Step)E-ステップでの最大尤度推定値を最大化してパラメータの値を算出する
4、収束するまで2、3の手順を繰り返します.
以上がEMアルゴリズムの核心原理であり、本当に簡単だと思うかもしれませんが、実は私がその中の複雑なデータ導出の過程を省略したのです.EMのアルゴリズム原理を理解しなければ、その中のデータ公式の導出を見て、もっと気絶するからです.はい、次はデータの導出過程を与えて、本人は数学もよくなくて、そこで他の人の導出過程を使って、人はすでにとても詳しく書いています.
EMアルゴリズムの導出過程
Jensen不等式
導出過程を紹介する時、jensen不等式を理解する必要があり、彼は凸関数に関する定理であり、直接公式定義を行う.
fが凸関数,Xがランダム変数である場合,
       clip_image010
      特に、fが厳密な凸関数である場合、clip_image012であり、clip_image014である場合、すなわちXは定数である.
      ここでは、clip_image016をclip_image018と略記します.
      図面で表示すると、次のようになります.
       EM最大期望算法_第1张图片
ここで説明する必要があるのは、E(X)の値がなぜ(a+b)/2なのか、0.5の確率がaであり、0.5の確率がbであるため、彼の期待はa,bの和の中間値である.同様にy軸上の値も同様である.
EMアルゴリズムの公式表現形式
EMアルゴリズムを式に変換する表現形式は以下の通りである.
      与えられたトレーニングサンプルはclip_image023であり、サンプル間は独立しており、p(x,z)を最大にするために、各サンプルに隠されているカテゴリzを見つけたい.p(x,z)の最大尤度推定は以下の通りである.
       EM最大期望算法_第2张图片
そしてこの公式を少し変えると、jensen不等式を使うことができます.不思議な一筆です.
前に説明した内容から次の式を得ることができます.
       EM最大期望算法_第3张图片
      (1)から(2)までは直接的であり,分子分母に等しい関数を乗算する.(2)から(3)までJensen不等式を利用した.各サンプルiについて、clip_image032に、そのサンプルに隠された変数zのある分布を示させ、clip_image032[1]が満たす条件はclip_image034である.そこで問題の鍵に来て、上の不等式を通じて、私たちは式の下界を確定することができて、それから私たちは絶えずこの下界を高めて最後の真実の値に近づく目的の値を達成することができて、それではいつ考えた時に達して、間違いなく、この不等式が等式になった時、それから前に説明したjensen不等式の説明に基づいて、不等式が等式になった場合、clip_image012は、clip_image014、すなわちXが定数である場合にのみ、次の式を出す.
EM最大期望算法_第4张图片
     さらに、(Qはランダム変数z(i)の確率密度関数であるため)では、分子の和はc(分子分母はすべてのz(i)に対して和を求める:複数の等式分子分母の加算は変わらず、これは各サンプルの2つの確率比がcであると考えられる)に等しく、再び導出を継続することができる.
       EM最大期望算法_第5张图片は最後にEMアルゴリズムの一般的なプロセスを得た.
収束まで繰り返す
      (Eステップ)i毎に計算
                   clip_image074
      (Mステップ)計算
                   clip_image075あなたはこの数学の導き出した過程を見終わってすでに頭がぼんやりしているかもしれませんが、大丈夫です.以下にEMアルゴリズムの不思議さを実感させる例を示します.
EMアルゴリズムのファジイクラスタリング実装
ここでは、EMアルゴリズムに基づく計算ファジイクラスタリングを独自に実装します.
テストのデータファイルを入力します.a-f 7点座標が含まれています.
3 3
4 10
9 6
14 8
18 11
21 7

開始時の既定のクラスタ中心点C 1,C 2はa,bである.これはパラメータの初期付与であっても、主な操作である.
1、E-Step:現在のファジイクラスタまたは確率クラスタのパラメータに基づいて、クラスタにオブジェクトを割り当てることが望ましい.
2、M-Step:ステップを最大化して新しいクラスタリングまたはパラメータを発見し、ファジイクラスタリングのSSEを最小化する(オブジェクトの誤差二乗和、これはプログラムに現れる).この式はMステップで用いられ,計算クラスタの中心は分割行列に基づいて再調整される.
最後の収束条件は,計算したクラスタ中心点の座標の横縦座標軸の誤差と1.0を超えないことであり,ほとんど変化しないことを意味する.メイン・プログラム・クラス:
package DataMining_EM;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;

/**
 * EM         
 * 
 * @author lyq
 * 
 */
public class EMTool {
	//         
	private String dataFilePath;
	//        
	private String[][] data;
	//          
	private ArrayList<Point> pointArray;
	//   C1 
	private Point p1;
	//   C2 
	private Point p2;

	public EMTool(String dataFilePath) {
		this.dataFilePath = dataFilePath;
		pointArray = new ArrayList<>();
	}

	/**
	 *         
	 */
	public void readDataFile() {
		File file = new File(dataFilePath);
		ArrayList<String[]> dataArray = new ArrayList<String[]>();

		try {
			BufferedReader in = new BufferedReader(new FileReader(file));
			String str;
			String[] tempArray;
			while ((str = in.readLine()) != null) {
				tempArray = str.split(" ");
				dataArray.add(tempArray);
			}
			in.close();
		} catch (IOException e) {
			e.getStackTrace();
		}

		data = new String[dataArray.size()][];
		dataArray.toArray(data);

		//        2    2    
		p1 = new Point(Integer.parseInt(data[0][0]),
				Integer.parseInt(data[0][1]));
		p2 = new Point(Integer.parseInt(data[1][0]),
				Integer.parseInt(data[1][1]));

		Point p;
		for (String[] array : data) {
			//                 
			p = new Point(Integer.parseInt(array[0]),
					Integer.parseInt(array[1]));
			pointArray.add(p);
		}
	}

	/**
	 *        2         
	 * 
	 * @param p
	 *                  
	 */
	private void computeMemberShip(Point p) {
		// p             
		double distance1 = 0;
		// p           
		double distance2 = 0;

		//        
		distance1 = Math.pow(p.getX() - p1.getX(), 2)
				+ Math.pow(p.getY() - p1.getY(), 2);
		distance2 = Math.pow(p.getX() - p2.getX(), 2)
				+ Math.pow(p.getY() - p2.getY(), 2);

		//     p1     ，        ，      ，     ，      distance2        
		p.setMemberShip1(distance2 / (distance1 + distance2));
		//     p2     
		p.setMemberShip2(distance1 / (distance1 + distance2));
	}

	/**
	 *          
	 */
	public void exceptMaxStep() {
		//           
		double p1X = 0;
		double p1Y = 0;
		double p2X = 0;
		double p2Y = 0;
		double temp1 = 0;
		double temp2 = 0;
		//    
		double errorValue1 = 0;
		double errorValue2 = 0;
		//          
		Point lastP1 = null;
		Point lastP2 = null;

		//         ，           1            
		while (lastP1 == null || errorValue1 > 1.0 || errorValue2 > 1.0) {
			for (Point p : pointArray) {
				computeMemberShip(p);
				p1X += p.getMemberShip1() * p.getMemberShip1() * p.getX();
				p1Y += p.getMemberShip1() * p.getMemberShip1() * p.getY();
				temp1 += p.getMemberShip1() * p.getMemberShip1();

				p2X += p.getMemberShip2() * p.getMemberShip2() * p.getX();
				p2Y += p.getMemberShip2() * p.getMemberShip2() * p.getY();
				temp2 += p.getMemberShip2() * p.getMemberShip2();
			}

			lastP1 = new Point(p1.getX(), p1.getY());
			lastP2 = new Point(p2.getX(), p2.getY());

			//              ,      
			p1.setX(p1X / temp1);
			p1.setY(p1Y / temp1);
			p2.setX(p2X / temp2);
			p2.setY(p2Y / temp2);

			errorValue1 = Math.abs(lastP1.getX() - p1.getX())
					+ Math.abs(lastP1.getY() - p1.getY());
			errorValue2 = Math.abs(lastP2.getX() - p2.getX())
					+ Math.abs(lastP2.getY() - p2.getY());
		}

		System.out.println(MessageFormat.format(
				"     p1({0}, {1}), p2({2}, {3})", p1.getX(), p1.getY(),
				p2.getX(), p2.getY()));
	}

}
座標点Pointクラス:
/**
 *     
 * 
 * @author lyq
 * 
 */
public class Point {
	//       
	private double x;
	//       
	private double y;
	//      P1    
	private double memberShip1;
	//      P2    
	private double memberShip2;

	public Point(double d, double e) {
		this.x = d;
		this.y = e;
	}

	public double getX() {
		return x;
	}

	public void setX(double x) {
		this.x = x;
	}

	public double getY() {
		return y;
	}

	public void setY(double y) {
		this.y = y;
	}

	public double getMemberShip1() {
		return memberShip1;
	}

	public void setMemberShip1(double memberShip1) {
		this.memberShip1 = memberShip1;
	}

	public double getMemberShip2() {
		return memberShip2;
	}

	public void setMemberShip2(double memberShip2) {
		this.memberShip2 = memberShip2;
	}

}
呼び出しクラス;
/**
 * EM            
 * @author lyq
 *
 */
public class Client {
	public static void main(String[] args){
		String filePath = "C:\\Users\\lyq\\Desktop\\icon\\input.txt";
		
		EMTool tool = new EMTool(filePath);
		tool.readDataFile();
		tool.exceptMaxStep();
	}
}
出力結果:
     p1(7.608, 5.907), p2(14.208, 8.745)
このプログラムでは,隠し変数がクラスタ中心点であり,絶え間ない反復計算により,最終的には無限に真実値に近い興味深いアルゴリズムである.
[Symbol] Pythonでxymを送金する
JAvaにおける内部クラスの使用