Distance Measures for Surgical Process Models

S. Schumann; U. Bühligen; T. Neumuth

doi:10.3414/ME12-01-0111

Methods of Information in Medicine, Table of Contents

Methods Inf Med 2013; 52(05): 422-431
DOI: 10.3414/ME12-01-0111

Original Articles

Schattauer GmbH

Distance Measures for Surgical Process Models

S. Schumann

¹Universität Leipzig, Innovation Center Computer Assisted Surgery, Leipzig, Germany

,

U. Bühligen

²University Medical Center, Department of Pediatric Surgery, Leipzig, Germany

,

T. Neumuth

¹Universität Leipzig, Innovation Center Computer Assisted Surgery, Leipzig, Germany

› Author Affiliations

Abstract

Summary

Background: The development of new resources, such as surgical techniques and approaches, results in continuous modification of surgery. To assess these modifications, it is necessary to use measures that quantify the impact of resources on surgical processes.

Objectives: The objective of this work is to introduce and evaluate distance measurements that are able to represent differences in the courses of surgical interventions as processes.

Methods: Hence, we present four different distance measures for surgical processes: the Jaccard distance, Levenshtein distance, Adjacency distance, and Graph matching distance. These measures are formally introduced and evaluated by applying them to clinical data sets from laparoscopic training in pediatric surgery.

Results: We analyzed the distances of 450 surgical processes using these four measures with a focus on the difference in surgical processes performed by novices and by experienced surgeons. The Levenshtein and Adjacency distances were best suited to measure distances between surgical processes.

Conclusion: The measurement of distances between surgical processes is necessary to estimate the benefit of new surgical techniques and strategies.

Keywords

Workflow - computer-assisted surgery - surgical process model - distance measures

Full Text

References

References
1 Cleary K, Kinsella A. OR 2020; the operating room of the future. J Laparoendosc Adv Surg Tech A 2005; 15 (05) 495 497-573.
2 Sandberg WS, Ganous TJ, Steiner C. Setting a research agenda for perioperative systems design. Semin Laparosc Surg 2003; 10 (02) 57-70.
3 Archer T, Macario A. The drive for operating room efficiency will increase quality of patient care. Curr Opin Anaesthesiol 2006; 19 (02) 171-176.
4 Geldner G, Eberhart LHJ, Trunk S, Dahmen KG, Reissmann T, Weiler T. et al. Efficient OP management. Suggestions for optimisation of organisation and administration as a basis for establishing statutes for operating theatres. Anaesthesist 2002; 51 (09) 760-767.
5 Meng F, D’Avolio LW, Chen AA, Taira RK, Kangarloo H. Generating models of surgical procedures using UMLS concepts and multiple sequence alignment. AMIA Annu Symp Proc 2005: 520-524.
6 Neumuth T, Loebe F, Jannin P. Similarity metrics for surgical process models. Artif Intell Med 2012; 54 (01) 15-27.
7 Nelson C, Luxon E, Oleynikov D. Tool Sequence Trends in Minimally Invasive Surgery: Statistical Analysis and Implications for Predictive Control of Multifunction Instruments. J Healthc Eng 2012; 3 (02) 261-278.
8 Dijkman R, Dumas M, García-Bañuelos L. Graph Matching Algorithms for Business Process Model Similarity Search. Proceedings of the 7th International Conference on Business Process Management. Berlin/Heidelberg: Springer; 2009: 48-63.
9 Dijkman R, Dumas M, Van Dongen B, Käärik R, Mendling J. Similarity of business process models: Metrics and evaluation. Inf Syst 2011; 36 (02) 498-516.
10 Cook JE, Wolf AL. Software process validation: quantitatively measuring the correspondence of a process to a model. ACM Trans Softw Eng Methodol 1999; 8 (02) 147-176.
11 Van der Aalst W, De Medeiros A, Weijters A, Dustdar S, Fiadeiro J, Sheth A. Process Equivalence: Comparing Two Process Models Based on Observed Behavior. In: Lecture Notes in Computer Science : Business Process Management, Volume 4102, 2006. Berlin/Heidelberg: Springer; 2006: 129-144.
12 Bae J, Liu L, Caverlee J, Rouse WB. Process Mining, Discovery, and Integration using Distance Measures. Int Conf Web Serv 2006; 479-488.
13 Bae J, Liu L, Caverlee J, Zhang L, Bae H. Development of Distance Measures for Process Mining, Discovery, and Integration. Int J Web Serv Res 2007; 4 (04) 1-17.
14 Zha H, Wang J, Wen L, Wang C, Sun J. A workflow net similarity measure based on transition adjacency relations. Comput Ind 2010; 61 (05) 463-471.
15 Bunke H, Shearer K. A graph distance metric based on the maximal common subgraph. Pattern Recognit Lett 1998; 19 (3-4) 255-259.
16 Riesen K, Neuhaus M, Bunke H. Bipartite graph matching for computing the edit distance of graphs. In: Escolano F, Vento M. editors. Graph-based representations in pattern recognition, Lecture Notes in Computer Science, vol. 4538. Berlin, Heidelberg: Springer-Verlag; 2007: 1-12.
17 Bunke H, Kandel A. Mean and maximum common subgraph of two graphs. Pattern Recognit Lett 2000; 21 (02) 163-168.
18 Bunke H. On a relation between graph edit distance and maximum common subgraph. Pattern Recognit Lett 1997; 18 (08) 689-694.
19 Robles-Kelly A, Hancock ER. Graph matching using spectral seriation and string edit distance. Proceedings of the 4th IAPR international conference on Graph based representations in pattern recognition. Berlin, Heidelberg: Springer-Verlag; 2003: 154-165.
20 Forestier G, Lalys F, Riffaud L, Trelhu B, Jannin P. Classification of surgical processes using dynamic time warping. J Biomed Inf 2012; 45 (02) 255-264.
21 Megali G, Sinigaglia S, Tonet O, Dario P. Modelling and evaluation of surgical performance using hidden Markov models. IEEE Trans Biomed Eng 2006; 53 (10) 1911-1919.
22 Speidel S, Zentek T, Sudra G, Gehrig T, Müller-Stich BP, Gutt C. et al. Recognition of surgical skills using hidden Markov models. Proc SPIE 7261, Medical Imaging 2009; Visualization, Image-Guided Procedures, and Modeling, 726125. 2009; 7261: 726125-726125.
23 Reiley CE, Hager GD. Task versus subtask surgical skill evaluation of robotic minimally invasive surgery. Med Image Comput Assist Interv 2009; 12 (Pt 1) 435-442.
24 Datta V, Chang A, Mackay S, Darzi A. The relationship between motion analysis and surgical technical assessments. Am J Surg 2002; 184 (01) 70-73.
25 Claus GP, Sjoerdsma W, Jansen A, Grimbergen CA. Quantitative standardised analysis of advanced laparoscopic surgical procedures. Endosc Surg Allied Technol 1995; 3 (04) 210-213.
26 Payandeh S, Lomax AJ, Dill J, Mackenzie CL, Cao CGL. On defining metrics for assessing laparoscopic surgical skills in a virtual training environment. Stud Health Technol Inform 2002; 85: 334-340.
27 Neumuth T, Durstewitz N, Fischer M, Strauss G, Dietz A, Meixensberger J. et al. Structured recording of intraoperative surgical workflows. Proc SPIE. 6145, Medical Imaging 2006; PACS and Imaging Informatics 61450A. 2006; 6145 (01) 61450A-61450A-12.
28 Neumuth T, Liebmann P, Wiedemann P, Meixensberger J. Surgical workflow management schemata for cataract procedures. process model-based design and validation of workflow schemata. Methods Inf Med 2012; 51 (05) 371-382.
29 Todd BS, Stamper R. The relative accuracy of a variety of medical diagnostic programs. Methods Inf Med. 1994; 33 (04) 402-16.
30 Stamper R, Todd BS, Macpherson P. Case-based explanation for medical diagnostic programs, with an example from gynaecology. Methods Inf Med 1994; 33 (02) 205-213.
31 Neumuth D, Loebe F, Herre H, Neumuth T. Modeling surgical processes: a four-level translational approach. Artif Intell Med 2011; 51 (03) 147-161.
32 Neumuth T, Trantakis C, Riffaud L, Strauss G, Meixensberger J, Burgert O. Assessment of technical needs for surgical equipment by surgical process models. Minim Invasive Ther Allied Technol 2009; 18 (06) 341-349.
33 Aiolli F, Burattin A, Sperduti A. A Business Process Metric Based on the Alpha Algorithm Relations. In Proceedings of the 7th International Workshop on Business Process Intelligence. Berlin Heidelberg:: Springer; 2012: 141-146.
34 Späth H. The minisum location problem for the Jaccard metric. OR Spectr 1981; 3 (02) 91-94.
35 Levenshtein VI. Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl 1966; 10 (08) 707-710.
36 Neumuth T, Jannin P, Strauss G, Meixensberger J, Burgert O. Validation of knowledge acquisition for surgical process models. J Am Med Inform Assoc 2009; 16 (01) 72-80.
37 Mettler L, Semm K. Training and regulation for endoscopic surgery. Baillieres Clin Obstet Gynaecol 1994; 8 (04) 881-894.
38 MacKenzie CL, Ibbotson JA, Cao CG, Lomax AJ. Hierarchical decomposition of laparoscopic surgery: a human factors approach to investigating the operating room environment. Minim Invasive Ther Allied Technol 2001; 10 (03) 121-127.
39 Cao CG, MacKenzie CL, Ibbotson JA, Turner LJ, Blair NP, Nagy AG. Hierarchical decomposition of laparoscopic procedures. Stud Health Technol Inform 1999; 62: 83-89.
40 Pagador JB, Sánchez-Margallo FM, Sánchez-Peralta LF, Sánchez-Margallo JA, Moyano-Cuevas JL, Enciso-Sanz S. et al. Decomposition and analysis of laparoscopic suturing task using tool-motion analysis (TMA): improving the objective assessment. Int J Comput Assist Radiol Surg. 2012; 7 (02) 305-313.
41 Neumuth T, Meissner C. Online recognition of surgical instruments by information fusion. Int J Comput Assist Radiol Surg 2012; 7 (02) 297-304.