An Efficient Brute Force Approach to Fit Finite Mixture Distributions | SpringerLink
Skip to main content
Springer Nature Link
Log in

An Efficient Brute Force Approach to Fit Finite Mixture Distributions

  • Conference paper
  • First Online:
Measurement, Modelling and Evaluation of Computing Systems (MMB 2020)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 12040))

  • 714 Accesses

Abstract

This paper presents a brute force approach to fit finite mixtures of distributions considering the empirical probability density and cumulative distribution functions as well as the empirical moments. The fitting problem is solved using a non-negative least squares method determining a mixture from a larger set of distributions.

The approach is experimentally validated for finite mixtures of Erlang distributions. The results show that a feasible number of component distributions, which accurately fit to the empirical data, is obtained within a short CPU time.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    \(g(x|\cdot )\) denotes \(g(x|({{\varvec{\pi }}},{{\varvec{\theta }}}))\) for arbitrary parameters \(({{\varvec{\pi }}},{{\varvec{\theta }}})\).

  2. 2.

    \(\pi ,\mathrm {e}\) the transcendental numbers.

References

  1. Akaike, H.: A new look at the statistical model identification. IEEE Trans. Autom. Control 19(6), 716–723 (1974)

    Article  MathSciNet  Google Scholar 

  2. Asmussen, S., Nerman, O., Olsson, M.: Fitting phase-type distributions via the EM algorithm. Scand. J. Stat. 23(4), 419–441 (1996)

    MATH  Google Scholar 

  3. Bause, F., Buchholz, P., Kriege, J.: ProFiDo - the processes fitting toolkit Dortmund. In: Proceedings of the 7th International Conference on Quantitative Evaluation of SysTems (QEST 2010), pp. 87–96. IEEE Computer Society (2010)

    Google Scholar 

  4. Bause, F., Horvath, G.: Fitting Markovian arrival processes by incorporating correlation into phase type renewal processes. In: Proceedings of the 2010 Seventh International Conference on the Quantitative Evaluation of Systems, QEST 2010, pp. 97–106. IEEE Computer Society, Washington, DC, USA (2010)

    Google Scholar 

  5. Bobbio, A., Horváth, A., Telek, M.: Matching three moments with minimal acyclic phase type distributions. Stoch. Models 21(2–3), 303–326 (2005)

    Article  MathSciNet  Google Scholar 

  6. Bobbio, A., Telek, M.: A benchmark for PH estimation algorithms: results for acyclic-PH. Commun. Stat. Stoch. Models 10(3), 661–677 (1994)

    Article  MathSciNet  Google Scholar 

  7. Buchholz, P., Felko, I., Kriege, J.: Transformation of acyclic phase type distributions for correlation fitting. In: Dudin, A., De Turck, K. (eds.) ASMTA 2013. LNCS, vol. 7984, pp. 96–111. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39408-9_8

    Chapter  Google Scholar 

  8. Buchholz, P., Kriege, J.: A heuristic approach for fitting MAPs to moments and joint moments. In: Proceedings of the 6th International Conference on Quantitative Evaluation of SysTems (QEST 2009), pp. 53–62. IEEE Computer Society, Los Alamitos, CA, USA, (2009)

    Google Scholar 

  9. Buchholz, P., Kriege, J., Felko, I.: Input Modeling with Phase-Type Distributions and Markov Models - Theory and Applications. SpringerBriefs in Mathematics. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-319-06674-5

    Book  MATH  Google Scholar 

  10. Buchholz, P., Telek, M.: Stochastic Petri nets with matrix exponentially distributed firing times. Perform. Eval. 67(12), 1373–1385 (2010)

    Article  Google Scholar 

  11. David, A., Larry, S.: The least variable phase type distribution is Erlang. Commun. Stat. Stoch. Models 3(3), 467–473 (1987)

    Article  MathSciNet  Google Scholar 

  12. Fang, Y.: Hyper-Erlang distribution model and its applications in wireless mobile networks. Wirel. Netw. 7, 211–219 (2001)

    Article  Google Scholar 

  13. Freedman, D., Diaconis, P.: On the histogram as a density estimator: \(L_2\) theory. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 57(4), 453–476 (1981)

    Article  MathSciNet  Google Scholar 

  14. Frühwirth-Schnatter, S.: Finite Mixture and Markov Switching Models. Springer Series in Statistics. Springer, New York (2006). https://doi.org/10.1007/978-0-387-35768-3

    Book  MATH  Google Scholar 

  15. Frühwirth-Schnatter, S., Celeux, G., Robert, C.: Handbook of Mixture Analysis. Chapman & Hall/CRC Handbooks of Modern Statistical Methods. CRC Press, Taylor & Francis Group, Boca Raton (2019)

    Book  Google Scholar 

  16. Hardy, G., Wright, E.: An Introduction to the Theory of Numbers, 5th edn. Oxford Science Publications. Clarendon Press, Oxford (1979)

    Google Scholar 

  17. Horváth, A., Telek, M.: Markovian modeling of real data traffic: heuristic phase type and MAP fitting of heavy tailed and fractal like samples. In: Calzarossa, M.C., Tucci, S. (eds.) Performance 2002. LNCS, vol. 2459, pp. 405–434. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45798-4_17

    Chapter  MATH  Google Scholar 

  18. Horváth, G.: Moment matching-based distribution fitting with generalized hyper-Erlang distributions. In: Dudin, A., De Turck, K. (eds.) ASMTA 2013. LNCS, vol. 7984, pp. 232–246. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39408-9_17

    Chapter  Google Scholar 

  19. Horváth, G., Telek, M.: On the canonical representation of phase type distributions. Perform. Eval. 66(8), 396–409 (2009). Selected Papers of the Fourth European Performance Engineering Workshop (EPEW) 2007 in Berlin

    Article  Google Scholar 

  20. Internet Traffic Archive. ftp://ita.ee.lbl.gov/html/traces.html. Accessed: 13 Nov 2019

    Google Scholar 

  21. Johnson, M.A., Taaffe, M.R.: Matching moments to phase distributions: mixtures of Erlang distributions of common order. Commun. Stat. Stoch. Models 5(4), 711–743 (1989)

    Article  MathSciNet  Google Scholar 

  22. Khayari, R.E.A., Sadre, R., Haverkort, B.R.: Fitting world-wide web request traces with the EM-algorithm. Perform. Eval. 52(2–3), 175–191 (2003)

    Article  Google Scholar 

  23. Lawson, C., Hanson, R.: Solving Least Squares Problems. Society for Industrial and Applied Mathematics. SIAM, New Delhi (1995)

    Google Scholar 

  24. Neuts, M.: A versatile Markovian point process. J. Appl. Probab. 16(4), 764–779 (1979)

    Article  MathSciNet  Google Scholar 

  25. Neuts, M.: Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (1981)

    Google Scholar 

  26. O’Cinneide, C.A.: Phase-type distributions: open problems and a few properties. Commun. Stat. Stoch. Models 15(4), 731–757 (1999)

    Article  MathSciNet  Google Scholar 

  27. Okamura, H., Dohi, T., Trivedi, K.S.: A refined EM algorithm for PH distributions. Perform. Eval. 68(10), 938–954 (2011)

    Article  Google Scholar 

  28. Panchenko, A., Thümmler, A.: Efficient phase-type fitting with aggregated traffic traces. Perform. Eval. 64(7–8), 629–645 (2007)

    Article  Google Scholar 

  29. Reinecke, P., Krauß, T., Wolter, K.: Cluster-based fitting of phase-type distributions to empirical data. Comput. Math. Appl. Theory Pract. Stoch. Model. 64(12), 3840–3851 (2012)

    MathSciNet  MATH  Google Scholar 

  30. Reinecke, P., Krauß, T., Wolter, K.: Phase-type fitting using HyperStar. In: Balsamo, M.S., Knottenbelt, W.J., Marin, A. (eds.) EPEW 2013. LNCS, vol. 8168, pp. 164–175. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40725-3_13

    Chapter  Google Scholar 

  31. Telek, M., Horvath, G.: A minimal representation of Markov arrival processes and a moments matching method. Perform. Eval. 64(9–12), 1153–1168 (2007)

    Article  Google Scholar 

  32. Thümmler, A., Buchholz, P., Telek, M.: A novel approach for fitting probability distributions to real trace data with the EM algorithm. In: Proceedings of the International Conference on Dependable Systems and Networks, DSN 2005, pp. 712–721, June 2005 (2005)

    Google Scholar 

  33. Titterington, D.M., Smith, A.F.M., Makov, U.E.: Statistical Analysis of Finite Mixture Distributions. Wiley, Hoboken (1985)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LS Informatik IV, Department of Computer Science, TU Dortmund, 44221, Dortmund, Germany

    Falko Bause

Authors
  1. Falko Bause
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Falko Bause .

Editor information

Editors and Affiliations

  1. Saarland University, Saarbrücken, Germany

    Holger Hermanns

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bause, F. (2020). An Efficient Brute Force Approach to Fit Finite Mixture Distributions. In: Hermanns, H. (eds) Measurement, Modelling and Evaluation of Computing Systems. MMB 2020. Lecture Notes in Computer Science(), vol 12040. Springer, Cham. https://doi.org/10.1007/978-3-030-43024-5_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-43024-5_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-43023-8

  • Online ISBN: 978-3-030-43024-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation