Be the first to rate this file! 16 Downloads (last 30 days) File Size: 223 KB File ID: #22711
image thumbnail

Free Split and Merge Expectation Maximization for MultiVariate Gaussian Mixture

by

 

18 Jan 2009 (Updated )

FSMEM can estimate MVGM parameters and number of conpounds via split/merge cluster moves

| Watch this File

File Information
Description

Free Split and Merge Expectation-Maximization algorithm for Multivariate Gaussian Mixtures. This algorithm is suitable to estimate mixture parameters and the number of conpounds

 Usage
 ------

 [M , S , P ,logl] = fsmem_mvgm(Z , [option] , [M0] , [S0] , [P0]);

 Inputs
 ------

 Z Measurements (d x N)
 M0 Initial mean vector. M0 can be (d x 1 x K) (default [Kini random elements from Z])
 S0 Initial covariance matrix. S0 can be (d x d x K) (default [cov(Z)/40])
 P0 Initial mixture probablities (1 x 1 x K) : (default [1/Kini])
 options
Kini Initial number of compounds (default [5])
Kmax Maximum number of compounds (default [15])
                    maxite_fsmem Number of maximum iteration for the main loop of the fsmem (default [100])
maxite_fullem Number of maximum iteration for the full EM inside the main loop (default [100])
maxite_partialem Number of maximum iteration for the partial EM inside the main loop (default [100])
epsi_fullem Tolerance in loglikelihood improuvement of the Full EM (default [1e-6])
epsi_partialem Tolerance in loglikelihood improuvement of the Partial EM (default [1e-6])
lambda Covariance regularization parameter (default [0.01])
maxcands_split Maximum number of split candidate (default [5])
splitinit_epsi Split Initialisation parameter for the mean of splitted cluster (default [1])
maxcands_merge Maximum number of merge candidate (default [5])
covtype Covariance type : 0 = full , 1 = elliptical , 2 = spherical (default [0])
fail_exit Number of tentatives of split/merge operations before exit. If fail_exit = 0, then FSMEM = EM
 

 Ouputs
 -------

 M Estimated mean vector (d x 1 x Kest), where Kest is the number of estimated coupounds
 S Estimated covariance vector (d x d x Kest)
 P Estimated initial probabilities (1 x 1 x Kest)
 logl Final loglikelihood

Please run mexme_fsmem_mvgm.m in order to compile mex-files on your own plateform (Be sure than "mex -setup" have been previously)

Please run test_fsmem_mvgm for the demo

Required Products MATLAB
MATLAB release MATLAB 7.8 (R2009a)
Other requirements A C compiler
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (14)
08 Feb 2012 Ahmed

Sebastien
Thank you very much for your reply, and thanks for the nice code.
i tried the second example (without initial parameters) but i didn't get how to get the data points that belong to a certain cluster?
hope that this is not a stupid question ..

03 Feb 2012 Sebastien PARIS

Ahmed,

Please open fsmem_mvgm.c for references.
Regards,

31 Jan 2012 Ahmed

Hi, do you have a paper that explains this algorithm?
Thanks

27 Jan 2012 Sebastien PARIS

Jonathan,
you have another example to show this effect? coz it shouln't be larger ...

26 Jan 2012 Jonathan Schachter

Hi, Sebastien. No, it hasn't crashed for a while. I was giving it bad input data -- linear combo of two normals, instead of a blended normal. with proper input, it hasn't crashed at all.

However, I might point out that the function pdf_mvgm may be in error. The pdf's look to be larger than the ordinary definition of pdf's by a factor of sqrt(2 * pi * sigma). But I don't think this affects fsmem_mvgm.

25 Jan 2012 Sebastien PARIS

Jonathan,
Still crashing for the example ?. For me I excuted it thousands times without any problem ...

23 Jan 2012 Jonathan Schachter

Thanks for the fix. It ran successfully for a while for me this morning, but now it is crashing again. Here is the latest error:

------------------------------------------------------------------------
Segmentation violation detected at Mon Jan 23 11:49:56 2012
------------------------------------------------------------------------

Configuration:
Crash Decoding : Disabled
Default Encoding: windows-1252
MATLAB Root : \\ms\dist\fidcore\PROJ\matlab\R2011b
MATLAB Version : 7.13.0.564 (R2011b)
Operating System: Microsoft Windows XP
Processor ID : x86 Family 6 Model 7 Stepping 10, GenuineIntel
Virtual Machine : Java 1.6.0_17-b04 with Sun Microsystems Inc. Java HotSpot(TM) Client VM mixed mode
Window System : Version 5.1 (Build 2600: Service Pack 3)

Fault Count: 1

Abnormal termination:
Segmentation violation

Register State (from fault):
EAX = 0e0a3230 EBX = 0e0a0000
ECX = 3ff00000 EDX = 00000000
ESP = 00c2cf80 EBP = 00c2cf8c
ESI = 0e0a3228 EDI = 0e0a3240

EIP = 7c911689 EFL = 00210246

CS = 0000001b DS = 00000023 SS = 00000023
ES = 00000023 FS = 0000003b GS = 00000000

Stack Trace (from fault):
[ 0] 0x7c911689 C:\WINDOWS\system32\ntdll.dll+00071305 ( RtlInitializeCriticalSection+000108 )
[ 1] 0x7c91084c C:\WINDOWS\system32\ntdll.dll+00067660 ( wcsncpy+000717 )
[ 2] 0x78ab01cb C:\WINDOWS\system32\MSVCR100.dll+00065995 ( free+000028 )
[ 3] 0x0e0857ed \\msad\root\na\ny\users\schachte\Op Risk\Matlab\Log Normal Mix\fsmem_mvgm.mexw32+00022509 ( ???+000028 )
[ 4] 0x02086cf4 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libmex.dll+00027892 ( mexRunMexFile+000132 )
[ 5] 0x020859e9 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libmex.dll+00023017 ( inSwapMexfileReader+000201 )
[ 6] 0x02085c14 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libmex.dll+00023572 ( inSwapMexfileReader+000756 )
[ 7] 0x7f63ec53 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_dispatcher.dll+00060499 ( Mfh_file::dispatch_fh+000403 )
[ 8] 0x7f63e686 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_dispatcher.dll+00059014 ( Mfunction_handle::dispatch+000694 )
[ 9] 0x7b99ac96 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00502934 ( inDestroyWS+247110 )
[ 10] 0x7b927165 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00029029 ( inGetFunctionHandleInterface+021493 )
[ 11] 0x7b99909f \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00495775 ( inDestroyWS+239951 )
[ 12] 0x7b9a6807 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00550919 ( inDestroyWS+295095 )
[ 13] 0x7b9a6922 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00551202 ( inDestroyWS+295378 )
[ 14] 0x7b9862c7 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00418503 ( inDestroyWS+162679 )
[ 15] 0x7b9882cc \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00426700 ( inDestroyWS+170876 )
[ 16] 0x7b978989 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00362889 ( inDestroyWS+107065 )
[ 17] 0x7f63ec53 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_dispatcher.dll+00060499 ( Mfh_file::dispatch_fh+000403 )
[ 18] 0x7f63e686 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_dispatcher.dll+00059014 ( Mfunction_handle::dispatch+000694 )
[ 19] 0x7b99ac96 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00502934 ( inDestroyWS+247110 )
[ 20] 0x7b927165 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00029029 ( inGetFunctionHandleInterface+021493 )
[ 21] 0x7b99909f \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00495775 ( inDestroyWS+239951 )
[ 22] 0x7b9a6807 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00550919 ( inDestroyWS+295095 )
[ 23] 0x7b9a6922 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00551202 ( inDestroyWS+295378 )
[ 24] 0x7b9862c7 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00418503 ( inDestroyWS+162679 )
[ 25] 0x7b9882cc \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00426700 ( inDestroyWS+170876 )
[ 26] 0x7b978989 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00362889 ( inDestroyWS+107065 )
[ 27] 0x7f63ec53 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_dispatcher.dll+00060499 ( Mfh_file::dispatch_fh+000403 )
[ 28] 0x7f63e686 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_dispatcher.dll+00059014 ( Mfunction_handle::dispatch+000694 )
[ 29] 0x7b9eba06 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00834054 ( inAnonymousFunction+001046 )
[ 30] 0x7b9f6bcf \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00879567 ( init_cleaner+001119 )
[ 31] 0x7b9f76e9 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00882409 ( init_cleaner+003961 )
[ 32] 0x7b9f76c5 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00882373 ( init_cleaner+003925 )
[ 33] 0x7b9f7680 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00882304 ( init_cleaner+003856 )
[ 34] 0x7b9dabe4 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00764900 ( inCallFcn+002052 )
[ 35] 0x7b9f2cb0 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00863408 ( inTerminate+007552 )
[ 36] 0x7b9f2cf9 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00863481 ( inTerminate+007625 )
[ 37] 0x7b9f2d1e \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\m_interpreter.dll+00863518 ( inEvalCmdWithLocalReturn+000030 )
[ 38] 0x7e1ccf73 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libmwbridge.dll+00053107 ( mnDebugPrompt+000163 )
[ 39] 0x7e1ce61e \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libmwbridge.dll+00058910 ( mnParser+000478 )
[ 40] 0x7f2a51e3 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00217571 ( mcrInstance::mnParser_on_interpreter_thread+000051 )
[ 41] 0x7f288fc2 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00102338 ( DepfunRules::postWarning+027282 )
[ 42] 0x7f28a345 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00107333 ( DepfunRules::postWarning+032277 )
[ 43] 0x7f28a3c6 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00107462 ( DepfunRules::postWarning+032406 )
[ 44] 0x74e0a509 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\uiw.dll+00304393 ( UIW_IsUserMessage+000121 )
[ 45] 0x74e0aabe \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\uiw.dll+00305854 ( ws_ProcessPendingEventsWaitForWindows+000286 )
[ 46] 0x7e431923 C:\WINDOWS\system32\USER32.dll+00137507 ( UnhookWinEvent+000119 )
[ 47] 0x7e42b317 C:\WINDOWS\system32\USER32.dll+00111383 ( MoveWindow+000121 )
[ 48] 0x7e4278d0 C:\WINDOWS\system32\USER32.dll+00096464 ( GetWindowTextLengthW+000154 )
[ 49] 0x7c90e473 C:\WINDOWS\system32\ntdll.dll+00058483 ( KiUserCallbackDispatcher+000019 )
[ 50] 0x74debd04 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\uiw.dll+00179460 ( UIW_SetCurrentDialog+000564 )
[ 51] 0x74debd5f \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\uiw.dll+00179551 ( UIW_SetCurrentDialog+000655 )
[ 52] 0x74e0ba95 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\uiw.dll+00309909 ( ws_FreeSystemFont+000485 )
[ 53] 0x7de962e7 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libuij.dll+00156391 ( sysq::ws_ppeHook::~ws_ppeHook+007015 )
[ 54] 0x7de969bc \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libuij.dll+00158140 ( sysq::ws_ppeHook::~ws_ppeHook+008764 )
[ 55] 0x7de97943 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libuij.dll+00162115 ( svWS_CommitDatabaseUpdates+002051 )
[ 56] 0x7de9816b \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libuij.dll+00164203 ( svWS_CommitDatabaseUpdates+004139 )
[ 57] 0x7de98366 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libuij.dll+00164710 ( svWS_CommitDatabaseUpdates+004646 )
[ 58] 0x7de9844a \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libuij.dll+00164938 ( svWS_CommitDatabaseUpdates+004874 )
[ 59] 0x7de985b2 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\libuij.dll+00165298 ( UIJ_WS_ProcessPendingEvents+000018 )
[ 60] 0x7f28b0ee \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00110830 ( DepfunRules::postWarning+035774 )
[ 61] 0x7f28b346 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00111430 ( DepfunRules::postWarning+036374 )
[ 62] 0x7f28b66c \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00112236 ( DepfunRules::postWarning+037180 )
[ 63] 0x7f28c8d6 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\mcr.dll+00116950 ( mcr_invoke_on_interpreter_thread+001014 )
[ 64] 0x00406242 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\MATLAB.exe+00025154 ( ???+001014 )
[ 65] 0x00406305 \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\MATLAB.exe+00025349 ( ???+001014 )
[ 66] 0x004063cd \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\MATLAB.exe+00025549 ( ???+001014 )
[ 67] 0x004067ad \\ms\dist\fidcore\PROJ\matlab\R2011b\bin\win32\MATLAB.exe+00026541 ( ???+001014 )
[ 68] 0x7c817077 C:\WINDOWS\system32\kernel32.dll+00094327 ( RegisterWaitForInputIdle+000073 )

This error was detected while a MEX-file was running. If the MEX-file
is not an official MathWorks function, please examine its source code
for errors. Please consult the External Interfaces Guide for information
on debugging MEX-files.

If this problem is reproducible, please submit a Service Request via:
http://www.mathworks.com/support/contact_us/

A technical support engineer might contact you with further information.

Thank you for your help.** This crash report has been saved to disk as C:\DOCUME~1\schachte\LOCALS~1\Temp\matlab_crash_dump.1644-1 **

Caught MathWorks::System::FatalException
[Please exit and restart MATLAB]>>

23 Jan 2012 Sebastien PARIS

Ok,

please locate
if(Kcurrent == Kmin)
{ next = 1;
}
and change for next = -1;

I will update soon with this fix and improvements. Thank you for reporting ...

S├ębastien

23 Jan 2012 Sebastien PARIS

problem confirmed with Intel compiler, no with MSVC. Works in debug mode, so ... probably a out of index somewhere .... I will investigate ...

22 Jan 2012 Jonathan Schachter

Even though I ran the example file with no errors, I am getting core dumps. Namely, I attempt to fit simulated data of one normal distribution (script below). The fit works. I then rerun it, but i get a core dump and crash out of MATLAB. I compiled it under MSVS 2010 with no errors. I run Windows XP.

perhaps i have to run a set of commands that unlocks files, deconstructs objects, etc.?

==== cut here for script

clear, clc, close all hidden;

trunc = 20000;
nsim = 1000; % may get fewer
nfit = 10;
iMax = 1000; %iterations in fit

%===================== CPBP fit by Josh
%w1 m1 s1 w2 m2 s2 <- these parameters refer to the associated normal
% distributions
w1=0.9668; Nm1=9.9922; Ns1=1.5578; w2=0.0332; Nm2=15.2537; Ns2=1.6449; % CBPP

m = [Nm1; Nm2];
sigma = [Ns1 0; 0 Ns2]; % allow for correlation later if want
p =[1; 0 ]; % to make computation easier

%=============================== create simulated data

k = size(m,1); % number of normals ("clusters")
simdata = p'*(repmat(m,1,nsim) + sigma*randn(k,nsim));
% simdata = simdata(simdata > log(trunc)); % truncate
% simdata = simdata(1:nsim);

try
tic,[Mest , Sest , Pest , logl] = fsmem_mvgm(simdata);,toc;
catch
sprintf('you f"d up')
end

12 Oct 2011 Annam

I am trying to understand the logic behind split merit. Can you please provide some explanation on "local observed distribution"? Is there any link that explains this.

10 Aug 2011 Annam

Thank u, it now works!

10 Aug 2011 Sebastien PARIS

Annam,

Thx you for reporting, now it's fixed. Update will appear in few hours. Best

10 Aug 2011 Annam

Compiling from Windows 7 (32 bit) environment, unable to compile fsmem_mvgm.c. Here is the detailed error report. Please suggest what needs to be done.

>> mexme_fsmem_mvgm
compiling likelihood_mvgm
compiling loglike_mvgm
compiling pdf_mvgm
compiling ndellipse
compiling fsmem_mvgm
Error fsmem_mvgm.c: 540 operands of < have illegal types `pointer to double' and `int'
Error fsmem_mvgm.c: 556 operands of < have illegal types `pointer to double' and `int'
Error fsmem_mvgm.c: 571 operands of < have illegal types `pointer to double' and `int'
Error fsmem_mvgm.c: 603 operands of < have illegal types `pointer to double' and `int'
4 errors, 0 warnings

D:\MATLAB\R2010A\BIN\MEX.PL: Error: Compile of 'fsmem_mvgm.c' failed.

??? Error using ==> mex at 222
Unable to complete successfully.

Error in ==> mexme_fsmem_mvgm at 137
eval(['mex ' str])

Updates
19 Jan 2009

-Add HTML file report

04 Feb 2009

Correct a bug in likelihood_mvgm.c when d=1

01 Mar 2009

- add options.Kmin
- Update qsindex with an inproved algorithm

05 Jun 2009

Minor code cleaning and should compile on non-C99 compiler

05 Oct 2009

- Improve description and mexme_fsmem_mvgm
- Should compile on Linux

19 Oct 2010

-Fixed bug for Linux64 and GCC

29 Jan 2011

-Minor changes

10 Aug 2011

- Fix a bug in parsing inputs

01 Nov 2011

-Minor changes

04 Nov 2011

-change input/output parsing
-add seed random generator option

26 Jan 2012

-Fix a bug when true number of conpounds is unity, thanks to Jonathan.

15 Mar 2012

-Correct typo in the header of fsmem_mvgm.c

Contact us