際際滷

際際滷Share a Scribd company logo
Leopold-Franzens-University Innsbruck
Institute of Computer Science

Categorization of Snow

Profile Data into
Predefined Class
Templates
MASTER THESIS
Christian Schaiter

Academic advisors: Univ.-Prof. Dr. G端nther Specht
DI Robert Binna
Content
What you may expect in the next 15 minutes...

1

Introduction and motivation

2

Overview of the developed system

3

Alignment of hardness profiles

4

Conclusion

Categorization of Snow Profile Data into Predefined Class Templates

2
Overview
Current chapter: Introduction

1

Introduction and motivation

2

Overview of the developed system

3

Alignment of hardness profiles

4

Conclusion

Categorization of Snow Profile Data into Predefined Class Templates

2
Introduction and motivation
Aim of the thesis
 Master thesis was done in cooperation with the Tyrolean

avalanche warning service (TAWS)
 Goal: Find a way to

determine the potential
magnitude of an
avalanche

Categorization of Snow Profile Data into Predefined Class Templates

3
Introduction and motivation
Snow profiles, hardness profiles, template types
 TAWS frequently takes snow profiles from different areas

 Most relevant property of a snow profile for this thesis:

Hardness profile

Hardness
profile

Snow height [cm]



Snow hardness

Categorization of Snow Profile Data into Predefined Class Templates

4
Introduction and motivation
Snow profiles, hardness profiles, template types
 Some example hardness profiles (collected from the TAWS):

Categorization of Snow Profile Data into Predefined Class Templates

5
Introduction and motivation
Snow profiles, hardness profiles, template types
 Idea: Introduce a group of predefined hardness profile types

(template types, class templates)
 These template types describe the overall composition of the

snowpack
 They may be used to

Profile types (class templates)

estimate the magnitude
of avalanches
 10 types defined so far

Categorization of Snow Profile Data into Predefined Class Templates

6
Introduction and motivation
Snow profiles, hardness profiles, template types
 Goal: Automatically find the associated profile type for

each collected hardness profile


Reject hardness profile if no reasonable profile type is found
Profile types (class templates)

Snow height [cm]

Hardness profile

Determine type

Snow hardness

Categorization of Snow Profile Data into Predefined Class Templates

7
Overview
Current chapter: Overview of the developed system

1

Introduction and motivation

2

Overview of the developed system

3

Alignment of hardness profiles

4

Conclusion

Categorization of Snow Profile Data into Predefined Class Templates

8
Overview of the developed system
Schematic view of the proposed classification system

Categorization of Snow Profile Data into Predefined Class Templates

9
Overview
Current chapter: Alignment of hardness profiles

1

Introduction and motivation

2

Overview of the developed system

3

Alignment of hardness profiles

4

Conclusion

Categorization of Snow Profile Data into Predefined Class Templates

10
Alignment of hardness profiles
Representation format of hardness profiles
 Hardness profiles may be viewed as

time series (clockwise rotated by 90属)


Height corresponds to time axis



Hardness values map to the amplitude
dimension

 Desired properties of an internal data

format:


Height independence



Shape preservation



90属

Local height warping

Categorization of Snow Profile Data into Predefined Class Templates

11
Alignment of hardness profiles
Representation format of hardness profiles
 Hardness profiles may be viewed as

time series (clockwise rotated by 90属)


Height corresponds to time axis



Hardness values map to the amplitude
dimension

 Desired properties of an internal data

format:


Height independence



Shape preservation



Local height warping

Categorization of Snow Profile Data into Predefined Class Templates

matching

11
Alignment of hardness profiles
Hardness profiles as weighted strings
 Idea: Use symbolic representation (weighted strings)

 A weighted string is composed of weighted characters


Direction character:
D (down), U (up)



Height (as a percentage)

6

5

4

3

2

1



Hardness difference
(among adjacent layers)

Compact form uses only
direction characters

D

D, 0.15,  1.5
U, 0.05, 3.5

D
U

D, 0.35,  0.5

D

D, 0.1,  1
D, 0.05,  3
U, 0.1, 6



D, 0.05,  1.5
D, 0.15,  1

D
D
U

Categorization of Snow Profile Data into Predefined Class Templates

D

12
Alignment of hardness profiles
Principle of hardness profile alignment
 Hardness profiles are aligned based on their compact strings


Weights are required to calculate a penalty score

 Goal: Find a global alignment with a maximum number of

matching characters (optimal alignment)
 Edit transcript describes operations (match M, deletion D,

insertion I) required to transform the first string into the second
String alignment examples
 The compact string UUDUD and DUDUU may be aligned as
 U U D  U D
D  U D U U 
I D M M I M D

or

U U D U D  
  D U D U U , etc
D D M M M I I

Categorization of Snow Profile Data into Predefined Class Templates

13
Alignment of hardness profiles
Principle of hardness profile alignment
Well-matching profile

U D D  U U D D D
U D D D  U D D D
M M M I D M M M M
Categorization of Snow Profile Data into Predefined Class Templates

Badly-matching profile

U D D U U D D D
U  D     
M D M D D D D D
14
Alignment of hardness profiles
Calculation of optimal alignments
 Algorithms for calculating optimal string alignments:

Categorization of Snow Profile Data into Predefined Class Templates

15
Alignment of hardness profiles
Calculation of optimal alignments

Categorization of Snow Profile Data into Predefined Class Templates

16
Alignment of hardness profiles
Computation of penalty scores
 After all optimal alignments have been found: Compute penalty

scores
 2 types of penalties:
 Match-penalty

for differences in:
- Height
- Hardness
 Mismatch-penalty

for mismatching blocks
- Much more severe

Categorization of Snow Profile Data into Predefined Class Templates

match-penalty

17
Overview
Current chapter: Conclusion

1

Introduction and motivation

2

Overview of the developed system

3

Alignment of hardness profiles

4

Conclusion

Intrusion Detection Systems for SOA

18
Conclusion
What you have heard in the last 15 minutes
 Template types are used to

estimate magnitude of avalanches
 Classification is based on string

alignment techniques
 Well matching strings

similar

hardness profiles
 Achieved success rate of > 90% for

example set (if not rejected)
 Approach may be used for any time

series data

Categorization of Snow Profile Data into Predefined Class Templates

19
Thank you for your
attention!

Any Question?
Backup slides
Distance measures: Cosine of angle, Euclidean Distance
 Similarity measure: Cosine of angle

 Dissimilarity measure: Euclidean Distance

Euclidean Distance:
Take the smallest distance
between points
in the vector space

Categorization of Snow Profile Data into Predefined Class Templates

Cosine of angle:
Take the smallest angle
between vectors

21
Backup slides
Problems with the Euclidean Distance
 Consider the hardness profile

(in blue) and its dedicated
template (in green)
 In principle they are

well-matching
 Nevertheless, a large error

occurs (in red) when applying
the Euclidean Distance
measure
 ED does not handle height

warps

Categorization of Snow Profile Data into Predefined Class Templates

22
Backup slides
Calculation of optimal alignments
 Compute a distance table (with dynamic programming)


Example: Compact strings UUDUD and DUDUU

Categorization of Snow Profile Data into Predefined Class Templates

23
Backup slides
Calculation of optimal alignments
 Based on the distance table, compute the edit graph and

perform a traceback

U U D U D  
  D U D U U
D D M M M I I

 U U D  U D
D  U D U U 
I D M M I M D

Categorization of Snow Profile Data into Predefined Class Templates

24
Backup slides
Template type duplication
 Template type versioning:


Create different versions with multiple gradation steps

Categorization of Snow Profile Data into Predefined Class Templates

25
Backup slides
Template type duplication
 Variations of template type versions:


Scale up one layer at the cost of the other layers

Categorization of Snow Profile Data into Predefined Class Templates

26
Backup slides
Profile matching
 Alignment of hardness layers: Limitations


Example should be of type 4, but perfectly matches type 3

Categorization of Snow Profile Data into Predefined Class Templates

27
Backup slides
Profile matching
 Alignment of hardness layers: Limitations


Problem of deceptive local extremes



Causing false negatives
badly matching

perfect match

Categorization of Snow Profile Data into Predefined Class Templates

28
Backup slides
Profile matching
 Alignment of hardness layers: Limitations


Problem of abusing misalignments



Causing false positives



Apparently wrong profiles may achieve too good penalty scores
(see examples)

Categorization of Snow Profile Data into Predefined Class Templates

29
Backup slides
Genetic Algorithm principles
 Mechanics of a simple Genetic Algorithm: 5 Steps


Step I: Encoding of the search domain with a small alphabet



Step II: Creation of an initial string population



Step III: Reproduction of strings



Step IV: Crossover of strings



Step V: Mutation of strings

Categorization of Snow Profile Data into Predefined Class Templates

30

More Related Content

Categorization of Snow Profile Data into Predefined Class Templates

  • 1. Leopold-Franzens-University Innsbruck Institute of Computer Science Categorization of Snow Profile Data into Predefined Class Templates MASTER THESIS Christian Schaiter Academic advisors: Univ.-Prof. Dr. G端nther Specht DI Robert Binna
  • 2. Content What you may expect in the next 15 minutes... 1 Introduction and motivation 2 Overview of the developed system 3 Alignment of hardness profiles 4 Conclusion Categorization of Snow Profile Data into Predefined Class Templates 2
  • 3. Overview Current chapter: Introduction 1 Introduction and motivation 2 Overview of the developed system 3 Alignment of hardness profiles 4 Conclusion Categorization of Snow Profile Data into Predefined Class Templates 2
  • 4. Introduction and motivation Aim of the thesis Master thesis was done in cooperation with the Tyrolean avalanche warning service (TAWS) Goal: Find a way to determine the potential magnitude of an avalanche Categorization of Snow Profile Data into Predefined Class Templates 3
  • 5. Introduction and motivation Snow profiles, hardness profiles, template types TAWS frequently takes snow profiles from different areas Most relevant property of a snow profile for this thesis: Hardness profile Hardness profile Snow height [cm] Snow hardness Categorization of Snow Profile Data into Predefined Class Templates 4
  • 6. Introduction and motivation Snow profiles, hardness profiles, template types Some example hardness profiles (collected from the TAWS): Categorization of Snow Profile Data into Predefined Class Templates 5
  • 7. Introduction and motivation Snow profiles, hardness profiles, template types Idea: Introduce a group of predefined hardness profile types (template types, class templates) These template types describe the overall composition of the snowpack They may be used to Profile types (class templates) estimate the magnitude of avalanches 10 types defined so far Categorization of Snow Profile Data into Predefined Class Templates 6
  • 8. Introduction and motivation Snow profiles, hardness profiles, template types Goal: Automatically find the associated profile type for each collected hardness profile Reject hardness profile if no reasonable profile type is found Profile types (class templates) Snow height [cm] Hardness profile Determine type Snow hardness Categorization of Snow Profile Data into Predefined Class Templates 7
  • 9. Overview Current chapter: Overview of the developed system 1 Introduction and motivation 2 Overview of the developed system 3 Alignment of hardness profiles 4 Conclusion Categorization of Snow Profile Data into Predefined Class Templates 8
  • 10. Overview of the developed system Schematic view of the proposed classification system Categorization of Snow Profile Data into Predefined Class Templates 9
  • 11. Overview Current chapter: Alignment of hardness profiles 1 Introduction and motivation 2 Overview of the developed system 3 Alignment of hardness profiles 4 Conclusion Categorization of Snow Profile Data into Predefined Class Templates 10
  • 12. Alignment of hardness profiles Representation format of hardness profiles Hardness profiles may be viewed as time series (clockwise rotated by 90属) Height corresponds to time axis Hardness values map to the amplitude dimension Desired properties of an internal data format: Height independence Shape preservation 90属 Local height warping Categorization of Snow Profile Data into Predefined Class Templates 11
  • 13. Alignment of hardness profiles Representation format of hardness profiles Hardness profiles may be viewed as time series (clockwise rotated by 90属) Height corresponds to time axis Hardness values map to the amplitude dimension Desired properties of an internal data format: Height independence Shape preservation Local height warping Categorization of Snow Profile Data into Predefined Class Templates matching 11
  • 14. Alignment of hardness profiles Hardness profiles as weighted strings Idea: Use symbolic representation (weighted strings) A weighted string is composed of weighted characters Direction character: D (down), U (up) Height (as a percentage) 6 5 4 3 2 1 Hardness difference (among adjacent layers) Compact form uses only direction characters D D, 0.15, 1.5 U, 0.05, 3.5 D U D, 0.35, 0.5 D D, 0.1, 1 D, 0.05, 3 U, 0.1, 6 D, 0.05, 1.5 D, 0.15, 1 D D U Categorization of Snow Profile Data into Predefined Class Templates D 12
  • 15. Alignment of hardness profiles Principle of hardness profile alignment Hardness profiles are aligned based on their compact strings Weights are required to calculate a penalty score Goal: Find a global alignment with a maximum number of matching characters (optimal alignment) Edit transcript describes operations (match M, deletion D, insertion I) required to transform the first string into the second String alignment examples The compact string UUDUD and DUDUU may be aligned as U U D U D D U D U U I D M M I M D or U U D U D D U D U U , etc D D M M M I I Categorization of Snow Profile Data into Predefined Class Templates 13
  • 16. Alignment of hardness profiles Principle of hardness profile alignment Well-matching profile U D D U U D D D U D D D U D D D M M M I D M M M M Categorization of Snow Profile Data into Predefined Class Templates Badly-matching profile U D D U U D D D U D M D M D D D D D 14
  • 17. Alignment of hardness profiles Calculation of optimal alignments Algorithms for calculating optimal string alignments: Categorization of Snow Profile Data into Predefined Class Templates 15
  • 18. Alignment of hardness profiles Calculation of optimal alignments Categorization of Snow Profile Data into Predefined Class Templates 16
  • 19. Alignment of hardness profiles Computation of penalty scores After all optimal alignments have been found: Compute penalty scores 2 types of penalties: Match-penalty for differences in: - Height - Hardness Mismatch-penalty for mismatching blocks - Much more severe Categorization of Snow Profile Data into Predefined Class Templates match-penalty 17
  • 20. Overview Current chapter: Conclusion 1 Introduction and motivation 2 Overview of the developed system 3 Alignment of hardness profiles 4 Conclusion Intrusion Detection Systems for SOA 18
  • 21. Conclusion What you have heard in the last 15 minutes Template types are used to estimate magnitude of avalanches Classification is based on string alignment techniques Well matching strings similar hardness profiles Achieved success rate of > 90% for example set (if not rejected) Approach may be used for any time series data Categorization of Snow Profile Data into Predefined Class Templates 19
  • 22. Thank you for your attention! Any Question?
  • 23. Backup slides Distance measures: Cosine of angle, Euclidean Distance Similarity measure: Cosine of angle Dissimilarity measure: Euclidean Distance Euclidean Distance: Take the smallest distance between points in the vector space Categorization of Snow Profile Data into Predefined Class Templates Cosine of angle: Take the smallest angle between vectors 21
  • 24. Backup slides Problems with the Euclidean Distance Consider the hardness profile (in blue) and its dedicated template (in green) In principle they are well-matching Nevertheless, a large error occurs (in red) when applying the Euclidean Distance measure ED does not handle height warps Categorization of Snow Profile Data into Predefined Class Templates 22
  • 25. Backup slides Calculation of optimal alignments Compute a distance table (with dynamic programming) Example: Compact strings UUDUD and DUDUU Categorization of Snow Profile Data into Predefined Class Templates 23
  • 26. Backup slides Calculation of optimal alignments Based on the distance table, compute the edit graph and perform a traceback U U D U D D U D U U D D M M M I I U U D U D D U D U U I D M M I M D Categorization of Snow Profile Data into Predefined Class Templates 24
  • 27. Backup slides Template type duplication Template type versioning: Create different versions with multiple gradation steps Categorization of Snow Profile Data into Predefined Class Templates 25
  • 28. Backup slides Template type duplication Variations of template type versions: Scale up one layer at the cost of the other layers Categorization of Snow Profile Data into Predefined Class Templates 26
  • 29. Backup slides Profile matching Alignment of hardness layers: Limitations Example should be of type 4, but perfectly matches type 3 Categorization of Snow Profile Data into Predefined Class Templates 27
  • 30. Backup slides Profile matching Alignment of hardness layers: Limitations Problem of deceptive local extremes Causing false negatives badly matching perfect match Categorization of Snow Profile Data into Predefined Class Templates 28
  • 31. Backup slides Profile matching Alignment of hardness layers: Limitations Problem of abusing misalignments Causing false positives Apparently wrong profiles may achieve too good penalty scores (see examples) Categorization of Snow Profile Data into Predefined Class Templates 29
  • 32. Backup slides Genetic Algorithm principles Mechanics of a simple Genetic Algorithm: 5 Steps Step I: Encoding of the search domain with a small alphabet Step II: Creation of an initial string population Step III: Reproduction of strings Step IV: Crossover of strings Step V: Mutation of strings Categorization of Snow Profile Data into Predefined Class Templates 30