# Sustainable Adaptive Security

Liliana Pasquale
University College Dublin  Kushal Ramkumar
University College Dublin  Wanling Cai
Trinity College Dublin  John McCarthy
University College Cork  Bashar Nuseibeh
University of Limerick  Gavin Doherty
Trinity College Dublin  Liliana Pasquale1, Kushal Ramkumar1, Wanling Cai2,
John McCarthy3, Gavin Doherty2, Bashar Nuseibeh4  1 Lero@University College
Dublin  2 Lero@Trinity College Dublin  3 Lero@University College Cork  3
Lero@University of Limerick

###### Abstract

With software systems permeating our lives, we are entitled to expect that
such systems are secure by design, and that such security endures throughout
the use of these systems and their subsequent evolution. Although adaptive
security systems have been proposed to continuously protect assets from harm,
they can only mitigate threats arising from changes foreseen at design time.
In this paper, we propose the notion of _Sustainable Adaptive Security_ (SAS)
which reflects such enduring protection by augmenting adaptive security
systems with the capability of mitigating newly discovered threats. To achieve
this objective, a SAS system should be designed by combining automation (e.g.,
to discover and mitigate security threats) and human intervention (e.g., to
resolve uncertainties during threat discovery and mitigation). In this paper,
we use a smart home example to showcase how we can engineer the activities of
the MAPE (Monitor, Analysis, Planning, and Execution) loop of systems
satisfying sustainable adaptive security. We suggest that using anomaly
detection together with abductive reasoning can help discover new threats and
guide the evolution of security requirements and controls. We also exemplify
situations when humans can be involved in the execution of the activities of
the MAPE loop and discuss the requirements to engineer human interventions.

##  I Introduction

Security threats are on the rise. Many recent critical cyber security
incidents, such as log4j and SolarWinds, arose from newly discovered threats
[1]. Therefore, there is a need to build systems that are secure by design,
but that can also detect and mitigate newly discovered security threats over
extended periods of time. Although adaptive security approaches [2, 3] have
been proposed to mitigate evolving security threats, they only address threats
arising from changes foreseen at design time. However, unanticipated changes,
such as newly discovered assets and vulnerabilities or wrong domain
assumptions, can bring new security threats and require security requirements
and controls to evolve at runtime.

In this paper, we propose the notion of _Sustainable Adaptive Security_ (SAS)
which reflects the capability of adaptive security systems to preserve
security requirements throughout their use and subsequent evolution. Systems
satisfying sustainable adaptive security (hereafter referred to as SAS
systems) should be capable of discovering changes that may bring unanticipated
security threats and managing the evolution of security requirements and
controls to mitigate such threats. Although autonomy is a desired property of
SAS systems, human intervention can be beneficial to preserve security
requirements in the long run, for example, by monitoring security-relevant
data and supporting decision making [4, 5, 6].

We use an example of a smart home to motivate the need for sustainable
security. We explain how we can engineer the activities of the MAPE (Monitor,
Analysis, Planning, and Execution) loop [7] of SAS systems. We showcase that
combining anomaly detection with abductive reasoning can help discover new
security threats and guide the evolution of security requirements and controls
to mitigate such threats. We also exemplify how humans can assist the SAS
system in executing the activities of the MAPE loop. Using our example, we
discuss three requirements (security, trust, and usability) to be considered
when engineering human interventions. Finally, we conclude with a discussion
of a future research agenda for the research community to develop SAS systems.

##  II Smart Home Security Example

Fig. 1 illustrates the plan of the smart home (on the left) and exemplifies
some of the unexpected changes that can occur (on the right). The home has a
WiFi router and a smart lock which secures the physical space of the home.
Devices connected to the WiFi network can potentially control the smart lock
[8] and send commands to open and close the door. A security goal [9] that we
aim to maintain is the integrity of the smart home. This goal can be achieved
by preventing unauthorised access to the smart home. Specifically, the smart
lock should only lock or unlock the door when an authorised user (tenant)
intends for the action to occur. We focus the scope of our research on a
system that is currently deployed. This is because modern systems include
components built by different vendors. Discovering threats during development
may not be feasible because new threats can emerge depending on how a system
is deployed and configured, e.g., depending on the type and location of the
devices in the smart home.

Figure 1: Smart Home Example

A _new digital device can connect to the WiFi network_. Such device may be
unknown and can control the smart lock letting an outsider inside the house
unaccompanied. In such case, a new security control should prevent the new
device from controlling the smart lock. The presence of unknown devices
connected to the WiFi network can indicate security misconfiguration (e.g.,
weak passwords, insecure encryption protocols) or new vulnerabilities in the
WiFi router. Therefore, any security control initially selected by the system
will not preserve security in the long run because it may not address the root
cause of the problem.

A new device (e.g., smart speaker) connecting to the WiFi network may,
instead, be known and trustworthy and require temporary authorisation to
access the smart lock and other appliances in the smart home. However, adding
a new device, can also bring new vulnerabilities. For example, a smart speaker
may be authorised to control the smart lock, but may be vulnerable to
ultrasonic voice command attacks that are inaudible [10]. This not only
violates the security requirement from the example, but also puts other
devices controllable by the smart speaker at risk.

If new devices connect too frequently to the WiFi network, an adaptive
security system can learn that new devices should not be allowed to connect to
the WiFi network. The system can also ask the tenant to confirm whether the
security control should be enacted. However, an abrupt notification without
any explanation of why such security control is necessary can decrease the
trust in the system and in the security posture of the smart home. Also, the
tenant may not have the expertise to understand whether the suggested security
control is effective.

The smart home can also be vulnerable to attacks exploiting _unmitigated or
new vulnerabilities_. Some vulnerabilities, although they are known, they are
not mitigated due to insufficient security knowledge [11] or delayed updates
[12]. For example, an unmitigated vulnerability in the smart lock (e.g.,
CVE-2022-32509) may enable man in the middle attacks and allow an outsider
inside. Other vulnerabilities are new and a fix does not exist for them yet.

##  III Sustainable Security

In the system security community, sustainable security has been defined as the
capability of an organisation to continuously secure a multitude of devices,
running potentially outdated versions of software, for long periods of time
[13]. It has also been considered as the property of a network intrusion
detection system to ensure continuous reliable operation [14], or the
capability of organisational processes to be more resilient to insider threats
[15]. The notion of sustainable security is also related to cyberresilience
[16], i.e. ”the ability to prepare for and recover quickly from both known and
unknown threats”. Although cyberresilience metrics [17] have been defined to
compare system design and prioritise upgrades and maintenance, previous work
has not considered how to engineer systems that can address unknown threats
and satisfy evolving security requirements over time, an extension of the
concept of sustainability in software engineering [18, 19].

As systems are increasingly socio-technical, our definition of sustainable
security considers both a system and a human perspective. We define
sustainable security as _the capability of a system to preserve security
requirements over sustained periods of time_. To achieve this aim, systems
need to continuously identify and mitigate emerging threats by _adapting_
their security controls or evolving the requirements specification. When
mitigating threats they should identify short-term security controls that stop
the malicious action, but also long-term controls that address the root-cause
of the threat and prevent the recurrence of the same threat.

From a human perspective, sustainable security should refer to _the design of
technology that enables interactions between the system and the humans to
achieve cyberresilience_. To the best of our knowledge, the notion of
cyberresilience has not been explored in the HCI community. Previous work has
studied how technology plays a role in various forms of resilience to disaster
and displacement [20, 21, 22], and also how individuals respond to mandated
technology adoption [23]. Humans should complement the system functionality to
support selection and execution of effective security controls that preserve
security in the long run. Human participation can be sustained by engineering
usable interactions that also increase trust in the system and its security
posture. Usability can be achieved by avoiding obtrusiveness. Trust can be
fostered by enabling humans to understand how the system operates and what is
happening at the current moment.

##  IV Engineering SAS Systems

We revisit the activities of the MAPE loop to engineer Sustainable Adaptive
Security (SAS) systems, as shown in Fig. 2. To discover new threats the
monitoring activity not only should assess satisfaction of requirements and
assumptions on the operating environment (domain assumptions) but should also
detect unusual behaviours (anomalies), which can provide indicators that
security requirements and controls should evolve. We assume that the SAS
system can collect data about the user behaviour (e.g., entering, exiting,
whether the door is locked or unlocked or whether new devices are present in
the network). The analysis activity should diagnose unusual behaviour and
assess whether new threats can materialise. The planning activity should
identify how security requirements and controls should evolve, if necessary.
The execution activity should enact security controls. We assume that the SAS
system is separated from the system under protection (smart home), although it
can observe/control the devices in the smart home.

Figure 2: Sustainable Adaptive Security System

Humans can be involved in the execution of the activities of the MAPE loop in
capacities other than the traditional user [24, 25] such as security and
software engineers. For example, during monitoring a user can provide
information about data that cannot be observed by the SAS system (e.g.,
whether a device connected to the WiFi network is trustworthy). During
analysis, information about a discovered anomaly can be provided to
software/security engineers to diagnose the anomaly, if it cannot be done
automatically. During planning, a user can confirm whether a security control
can be enacted (e.g., forcing closure of the door of the smart home). Finally,
humans can support execution of security controls (e.g., the tenant may be
asked to return home).

Similarly to previous work on adaptive security [26], we use a goal modeling
framework [27] to make security requirements refinements and dependencies on
environment conditions explicit. We suggest that a representation of security
requirements can help engineer the activities of the MAPE loop of a
sustainable adaptive security system. Fig. 3 shows a simplified goal model of
the smart home example. The root goal represents the security requirement
related to the authorised access to the smart home. This requirement can be
achieved by authenticating access to the smart lock and securing access to the
WiFi network. Two-Factor authentication is used to access the smart lock. An 8
character password is used for the WiFi network and the length of the password
is assumed to be sufficient to protect the network. We assume that a) trusted
devices in the WiFi network do not let an outsider in the smart home
unaccompanied; b) the smart lock cannot be tampered with; c) an outsider can
only enter if the door is unlocked and d) the tenant always locks the door
when they exit.

In the rest of this section we showcase how abductive reasoning can be used to
diagnose whether an anomaly can lead to the violation of the authorisation
requirement for the unexpected changes described in Section II. We encoded the
goal model and the system functionalities (e.g., opening/closing door,
entering/exiting) using Answer Set Programming and use clingo to perform
abductive reasoning111For reasons of space, we omit information about the ASP
models in this paper and refer the interested reader to
https://tinyurl.com/256tfktc. As suggested by Alrajeh et al. [28], symbolic
learning techniques can use traces of the system behaviour satisfying and
violating the authorisation requirement to learn how security requirements and
controls should evolve. We also exemplify how humans can participate in the
activities of the MAPE loop.

Figure 3: Goal Model

###  IV-A New Device Connects to the WiFi Network

The monitoring activity detects that a new device is connected to the WiFi
network. However, to diagnose the anomaly the SAS system needs to know whether
the device is trustworthy, i.e. known to the tenant. If the device (d1) is not
trustworthy, the ASP model will be updated accordingly and will generate a
trace showcasing how the authorisation requirement can be violated, as shown
below.

    exit(tenant,home,1), close(sl,2),
       open(d1,sl,3), enter(outsider,home,4),
          in(outsider,home,4).

After the tenant exits at time 1 and closes the door at time 2, the new device
sends a command to the smart lock (sl) to open the door and lets and outsider
inside.

The SAS system can learn to evolve the specification by, for example,
preventing the new device from sending an open command to the smart lock as
shown below.

    X!=d1 :- open(X,sl,T), net_device(X), T = 0..4.

In this case, human participation can be sought to understand whether the
security control selected by the SAS system should be enacted. To foster
trust, observability and transparency principles should be satisfied [29]. In
other words, the SAS system should indicate that a network device that is not
trustworthy was detected (observability) and that the suggested security
control is necessary to prevent the new device from letting an offender inside
unaccompanied (transparency). Alternatively, it may be desirable to evolve
security controls differently, for example by removing the new device from the
WiFi network. Although alternative security controls can be discovered
automatically by the system, the tenant may not have the expertise to select
one appropriately. Thus, intervention of the system/security engineer may be
necessary to perform this task. If an engineer is required to modify security
controls, the SAS system should also satisfy the intelligibility principle
[29] by communicating in what ways security controls can be modified without
introducing additional vulnerabilities.

However, the security controls identified above may not be sustainable if the
new device is trustworthy. For example, the tenant may want to use a new smart
speaker to send commands to the smart lock to open and close the door. Thus,
the SAS system should ask the tenant whether the device is trustworthy, to
avoid selecting ineffective security controls. To increase the likelihood that
the tenant completes the task successfully, the SAS system should satisfy the
feedforward principle [29] by providing the tenant with information about the
detected device (e.g., type of device). Similarly to the previous example, to
satisfy observability, the SAS system should indicate that a new device was
detected. To satisfy transparency the SAS system should indicate that, if the
device is trustworthy, access to the network and the home appliances will be
granted.

Now, let us imagine that new devices keep connecting to the WiFi network
frequently. To avoid sending frequent notifications to the tenant, the SAS
system may learn that new devices should not be allowed in the WiFi network by
default or can ask the tenant whether, from now on, they may want to prevent
any new device from connecting to the network. In this case, the SAS system
should satisfy observability by indicating that new devices are connected to
the network too frequently. It should also satisfy transparency by explaining
that forbidding access to new devices will require the tenant to manually
grant access to the network when a new device will connect to the WiFi network
in the future.

However, these security controls may not be sustainable, because they may not
address the root cause of the problem, which can be that the network
authentication is not effective. Thus, the SAS can use the structure of the
goal model to identify which security control is responsible to regulate
access to the network and, for example, evolve the domain assumption related
to the password strength by increasing the minimum number of characters for a
password to be considered strong. Changing the domain assumption will force
the system to learn that a longer password needs to be enforced. In this case,
human input should be sought to identify the minimum number of characters that
a password should have. Since the tenant may not have the expertise to advise
on the password length, a security/software engineer may need to be involved
to perform this task.

###  IV-B New Vulnerabilities

If the monitoring activity measures the latency of requests and responses to
and from appliances in the smart home it can discover unusual latencies that
can indicate the presence of a man-in-the-middle attack. These types of
attacks can be due to authentication vulnerabilities. For example, the Nuki
Smart Lock was found to lack SSL/TLS certificate validation, allowing an
attacker to perform a man-in-the-middle attack and intercept network traffic
(CVE-2022-32509).

Such vulnerability cannot be diagnosed automatically and the SAS system needs
to identify a security control that could prevent an attack from happening. In
such a case, the domain assumption on the trusted devices in the network may
no longer be valid. Removing that domain assumption from the ASP model makes
the system identify a violating trace where a trusted device in the network
could still let an outsider inside unaccompanied. This trace can be used to
learn a security control that blocks any incoming traffic to the smart lock.
This security control is not sustainable in the long run because it does not
address the root cause of the problem. Intervention of a security/software
engineer needs to be sought to confirm the presence of a vulnerability. If
information about the vulnerability has already been disclosed (e.g., a CVE
entry is available) a patch needs to be identified and applied to the
vulnerable device. Also, the requirement specification needs to be updated
with an indication of the vulnerability and the fix. Alternatively, advice
needs to be sought from the software/security engineer on how the disclosure
of a new vulnerability and how to fix it.

##  V Related Work

Previous work on security requirements engineering [30, 31, 32, 33, 34, 35,
36] has focused on modelling and reasoning about security concerns to assess
risks, identify security controls and estimate the impact of design choices on
the protection of the critical assets of the system. These approaches
typically require a complete model of the system and have not been designed to
support requirements evolution. Other approaches [37, 38] trigger requirements
evolution according to pre-defined rules, when security properties are
violated. More recently, Drodzov et al. [39] have used symbolic-based learning
to learn security policies from historical data produced by anomaly detectors.
The authors adopt a domain-specific function to guide the learning process
towards the best policies for anomaly detection. Although promising, this work
has not been adopted to evolve security requirements at runtime.

In the adaptive security community, previous work has suggested to evolve the
representation of threats based on the automated derivation of changing
architectural system models from runtime and operational system artifacts
[40]. Calo et al. [41] propose an approach to generate access control policies
dynamically when the environment changes, assuming that a set of constraints
associated with the resources to be accessed are satisfied. To the best of our
knowledge, there is no systematic technique to detect and prevent/mitigate
evolving threats brought by unexpected changes, such as vulnerabilities and
ineffective security controls at runtime.

Explanations have been used to involve humans in the execution of the
activities of an adaptive system [42, 43]. In the security domain, Nhlabatsi
et al. [44] help users understand security decisions by establishing
traceability relationships between requirements and security concerns (e.g.,
threats, attacks and vulnerabilities). More recently, Adepu et al. [45]
characterise explanations in terms of content, effect, and cost (i.e. human
effort necessary to understand the explanation). The authors use probabilistic
reasoning to determine when an explanation should be used to improve overall
system utility. However, they do not configure the content of an explanation
depending on the input required from the human participant. Models of human
participants have been used to decide whether humans should be involved during
the planning [46] or execution [47] activity of adaptation. Li et al. [48]
propose a framework to reason about the usage of preparatory notifications in
adaptive systems. Preparatory notifications can focus the attention of human
participants on the task to be performed and help them understand its context
before task execution. However, previous work has provided limited guidance on
how human intervention should be requested and provided. Gil et al. [29]
proposes a conceptual framework to characterise the cooperation between humans
and autonomous cyber-physical systems and provide techniques for applying the
framework to design human integration. However, this framework has not been
applied in the context of an adaptive security system.

##  VI Research Agenda

###  VI-A Engineering Autonomy in SAS Systems

During monitoring SAS systems need to identify events that can be observed by
the devices that can be controlled in the environment and those for which
human intervention is necessary. For example, a combination of device finger-
printing and human intervention [49] can be used to identify new devices
connected to the WiFi network.

During analysis, to detect the root cause of an anomaly, it will be necessary
to identify parts of the requirements model that require revision. The devices
and domain assumptions that are affected by the anomaly can be used to
identify the parts of the model that require revision automatically. In our
example, frequent connectivity of new devices to the WiFi network required us
to revise the security controls protecting the network. If not possible, human
intervention should be sought to select the parts of the model that need
revision. There can also be situations when anomalies cannot be diagnosed, for
example, when we have unanticipated or new vulnerabilities.

We will attempt to detect unanticipated vulnerabilities by referencing the
behavioural pattern of the anomaly against an up-to-date knowledge database of
attacks created from vulnerability disclosures and vulnerability databases. To
detect and mitigate new vulnerabilities, it will be necessary to identify what
type of information can be disclosed to software and security engineers to
obtain meaningful input.

During planning there can be several ways in which security controls can
evolve. This will depend on the examples that are used to perform the learning
activity. One challenge to be addressed is the generation of examples and the
identification of heuristics that can drive the learning towards the selection
of security controls that are effective in the long run, while avoiding human
intervention.

In this paper we assumed that the requirements, functionalities, and domain
assumptions of the system to be protected are specified in advance. However,
this may not always be possible, for example, when new components are added to
the system at runtime. Thus, it will be interesting to understand how the
system functionalities, domain assumptions and security controls can be learnt
from scratch. For example, transfer learning can be used to learn the
behaviour of new components from similar ones. Online learning can be used to
learn how heterogeneous components can interact when placed together. Then,
neural symbolic learning [50] can be used to learn a model of the system
behaviour. Finally symbolic learning can be used to learn the security
controls that satisfy the system security requirements. Human input will be
necessary to identify the security requirements and the security controls
available, and to revise the model learnt from scratch.

###  VI-B Engineering Human Interventions

Engineering human interventions requires identifying the tasks to be performed
by human participants. In this paper, we initially identified some of them
(e.g., provisioning of monitoring information, hypothesis on the root cause of
an anomaly, and selection/modification of security controls). However, it will
be necessary to elicit such tasks in a more systematic way using a larger set
of scenarios from different application domains (e.g., cloud computing). Once
tasks are determined, it will be desirable to identify the roles and expertise
of humans that can perform these tasks.

Moreover, SAS system should enable effective and usable interaction with
humans. To achieve this aim, it will be necessary to consider the following
aspects: (1) ”who” – who will be involved in the task, (2) ”when” – human or
the system initiate the actions, and the level of automation or human control
for performing the task [51] (e.g., some tasks can require selection but
others can require modification of security controls); (3) ”how” – human and
the system can communicate with each others (4) what information should be
exchanged between the human and the system. To foster trust the information
exchanged should satisfy some of the properties of human-system integration
[29].

Evaluating sustainable adaptive security systems also brings new research
challenges. From a system perspective, properties such as timeliness and
longevity are very relevant. Timeliness refers to how fast such systems can
prevent threats from happening compared to traditional adaptive security
systems. Longevity can refer to how long security requirements are satisfied.
To evaluate SAS systems from a human perspective, we can consider assessing
the successful completion of the task by the participants, but also evaluate
sustainable security from an ”experiential perspective” by assessing the
perceived security level of the system experienced by human participants [52].

## References

  * [1] Checkpoint. (2021) Check Point 2022 Security Report. [Online]. Available: {https://tinyurl.com/3vu8paav}
  * [2] E. Yuan, N. Esfahani, and S. Malek, “A Systematic Survey of Self-Protecting Software Systems,” _ACM Trans. Auton. Adapt. Syst._ , vol. 8, 2014.
  * [3] G. Tziakouris, R. Bahsoon, and M. A. Babar, “A Survey on Self-Adaptive Security for Large-Scale Open Environments,” _ACM Comput. Surv._ , vol. 51, 2018.
  * [4] N. Görnitz, M. Kloft, K. Rieck, and U. Brefeld, “Active learning for network intrusion detection,” in _Proc. of the 2nd ACM Workshop on Security and Artificial Intelligence_ , 2009, p. 47–54.
  * [5] K. Yang, J. Ren, Y. Zhu, and W. Zhang, “Active learning for wireless iot intrusion detection,” _IEEE Wireless Comm._ , vol. 25, no. 6, pp. 19–25, 2018.
  * [6] F. Fransen, R. Wolthuis, and N. el Ouajdi. (2019, January) Security at Machine Speed. [Online]. Available: {https://tinyurl.com/yc478pnz}
  * [7] E. Lara, L. Aguilar, M. A. Sanchez, and J. A. García, “Adaptive Security Based on MAPE-K: A Survey,” _Applied Decision-Making: Applications in Computer Sciences and Engineering_ , pp. 157–183, 2019.
  * [8] S. Veijalainen and T. Noreng Karlsson, “Evaluating the Security of a Smart Door Lock System,” 2021.
  * [9] C. P. Pfleeger, _Security in Computing_. Pearson Education India, 2009.
  * [10] J. Mao, S. Zhu, X. Dai, Q. Lin, and J. Liu, “Watchdog: Detecting Ultrasonic-Based Inaudible Voice Attacks to Smart Home Systems,” _IEEE Internet of Things Journal_ , vol. 7, pp. 8025–8035, 2020.
  * [11] E. Zeng, S. Mare, and F. Roesner, “End user security and privacy concerns with smart homes,” in _Thirteenth Symp. on Usable Privacy and Security (SOUPS 2017)_ , 2017, pp. 65–80.
  * [12] F. Li and V. Paxson, “A large-scale empirical study of security patches,” in _Proc. of the 2017 ACM SIGSAC Conf. on Computer and Comm. Security_ , 2017, p. 2201–2215.
  * [13] R. Anderson, “Making security sustainable,” _Comm. of the ACM_ , vol. 61, pp. 24–26, 2018.
  * [14] G. Koutsandria, R. Gentz, M. Jamei, A. Scaglione, S. Peisert, and C. McParland, “A real-time testbed environment for cyber-physical security on the power grid,” in _Proc of the First ACM Workshop on Cyber-Physical Systems-Security and/or PrivaCy_ , 2015, p. 67–78.
  * [15] M. Hanse, ““Insider Threats” and “Supporting Sustainable Security” – Adding the Dimension of Privacy and Data Protection, Organizational Processes for Supporting Sustainable Security (Dagstuhl Seminar 12501),” _Dagstuhl Reports_ , vol. 2, pp. 2192–5283, 2013.
  * [16] Z. A. Collier, D. DiMase, S. Walters, M. M. Tehranipoor, J. H. Lambert, and I. Linkov, “Cybersecurity Standards: Managing Risk and Creating Resilience,” _Computer_ , vol. 47, no. 9, pp. 70–76, 2014.
  * [17] I. Linkov, D. A. Eisenberg, K. Plourde, T. P. Seager, J. Allen, and A. Kott, “Resilience Metrics for Cyber Systems,” _Environment Systems and Decisions_ , vol. 33, pp. 471–476, 2013.
  * [18] B. Penzenstadler, V. Bauer, C. Calero, and X. Franch, “Sustainability in software engineering: a systematic literature review,” in _16th Int. Conf. on Evaluation & Assessment in Software Engineering (EASE 2012)_, 2012, p. 32 – 41.
  * [19] C. Becker, R. Chitchyan, L. Duboc, S. Easterbrook, B. Penzenstadler, N. Seyff, and C. C. Venters, “Sustainability design and software: The karlskrona manifesto,” in _Proc of the 37th Int. Conf. on Software Engineering_ , 2015, pp. 467–476.
  * [20] S. I. Ahmed, N. J. Mim, and S. J. Jackson, “Residual Mobilities: Infrastructural Displacement and Post-Colonial Computing in Bangladesh,” in _Proc. of the 33rd Annual ACM Conf. on Human Factors in Computing Systems_ , 2015, pp. 437–446.
  * [21] G. Mark and B. Semaan, “Resilience in Collaboration: Technology as a Resource for New Patterns of Action,” in _Proc. of the 2008 ACM Conf. on Computer Supported Cooperative work_ , 2008, pp. 137–146.
  * [22] G. J. Mark, B. Al-Ani, and B. Semaan, “Resilience Through Technology Adoption: Merging the Old and the New in Iraq,” in _Proc. of the SIGCHI Conf. on human factors in Computing systems_ , 2009, pp. 689–698.
  * [23] N. Karusala, I. Holeman, and R. Anderson, “Engaging Identity, Assets, and Constraints in Designing for Resilience,” _Proceedings of the ACM on Human-Computer Interaction_ , vol. 3, no. CSCW, pp. 1–23, 2019.
  * [24] E. P. Baumer, “Usees,” in _Proc. of the 33rd Annual ACM Conf. on Human Factors in Computing Systems_ , 2015, pp. 3295–3298.
  * [25] E. P. Baumer and J. R. Brubaker, “Post-Userism,” in _Proc. of the CHI Conf. on Human Factors in Computing Systems_ , 2017, pp. 6291–6303.
  * [26] M. Salehie, L. Pasquale, I. Omoronyia, R. Ali, and B. Nuseibeh, “Requirements-Driven Adaptive Security: Protecting Variable Assets at Runtime,” in _2012 20th IEEE international requirements engineering conference (RE)_. IEEE, 2012, pp. 111–120.
  * [27] A. Van Lamsweerde, _Requirements Engineering: From System Goals to UML Models to Software_. John Wiley & Sons, 2009, vol. 10.
  * [28] D. Alrajeh, A. Cailliau, and A. van Lamsweerde, “Adapting requirements models to varying environments,” in _2020 IEEE/ACM 42nd Int. Conf. on Software Engineering (ICSE)_ , 2020, pp. 50–61.
  * [29] M. Gil, M. Albert, J. Fons, and V. Pelechano, “Designing Human-in-the-Loop Autonomous Cyber-Physical Systems,” _International journal of human-computer studies_ , vol. 130, pp. 21–39, 2019.
  * [30] L. Liu, E. Yu, and J. Mylopoulos, “Security and Privacy Requirements Analysis within a Social Setting,” in _Proc. oif 11th IEEE Int. Requirements Engineering Conference, 2003._ , 2003, pp. 151–161.
  * [31] A. Van Lamsweerde, “Elaborating Security Requirements by Construction of Intentional Anti-Models,” in _Proceedings. 26th International Conference on Software Engineering_. IEEE, 2004, pp. 148–157.
  * [32] P. Giorgini, F. Massacci, J. Mylopoulos, and N. Zannone, “Modeling Security Requirements through Ownership, Permission and Delegation,” in _Proc. of the 13th Int. Conf. on Req. Eng._ , 2005, pp. 167–176.
  * [33] C. Haley, R. Laney, J. Moffett, and B. Nuseibeh, “Security Requirements Engineering: A Framework for Representation and Analysis,” _IEEE Trans on Software Engineering_ , vol. 34, pp. 133–153, 2008.
  * [34] Y. Yu, V. N. Franqueira, T. T. Tun, R. J. Wieringa, and B. Nuseibeh, “Automated Analysis of Security Requirements through Risk-Based Argumentation,” _Journal of Sys. and Softw._ , vol. 106, pp. 102–116, 2015\.
  * [35] L. Pasquale, P. Spoletini, M. Salehie, L. Cavallaro, and B. Nuseibeh, “Automating Trade-off Analysis of Security Requirements,” _Requirements Engineering_ , vol. 21, pp. 481–504, 2016.
  * [36] S. Türpe, “The Trouble with Security Requirements,” in _Proc. of the 25th Int. Requirement Engineering Conf._ , 2017, pp. 122–133.
  * [37] G. Bergmann, F. Massacci, F. Paci, T. T. Tun, D. Varró, and Y. Yu, “A Tool for Managing Evolving Security Requirements,” in _In Proc. of the 23rd International Conference on Advanced Information Systems Engineering Forum_. Springer, 2011, pp. 49–56.
  * [38] J. Bürger, J. Jürjens, and S. Wenzel, “Restoring security of evolving software models using graph transformation,” _International Journal on Software Tools for Technology Transfer_ , vol. 17, pp. 267–289, 2015.
  * [39] A. Drozdov, M. Law, J. Lobo, A. Russo, and M. W. Don, “Online Symbolic Learning of Policies for Explainable Security,” in _Proc. of the 3rd Int. Conf. on Trust, Privacy and Security in Intelligent Systems and Applications_ , 2021, pp. 269–278.
  * [40] D. van Landuyt, L. Pasquale, L. Sion, and W. Joosen, “Threat Modeling at Run Time: The Case for Reflective and Adaptive Threat Management (NIER track),” in _2021 Int. Symp. on Software Engineering for Adaptive and Self-Managing Systems (SEAMS)_ , 2021, pp. 203–209.
  * [41] S. Calo, D. Verma, S. Chakraborty, E. Bertino, E. Lupu, and G. Cirincione, “Self-Generation of Access Control Policies,” in _Proceedings of the 23nd ACM on Symposium on Access Control Models and Technologies_ , 2018, pp. 39–47.
  * [42] K. Welsh, N. Bencomo, P. Sawyer, and J. Whittle, “Self-Explanation in Adaptive Systems based on Runtime Goal-Based Models,” in _Trans. on Computational Collective Intelligence_. Springer, 2014, pp. 122–145.
  * [43] N. Li, S. Adepu, E. Kang, and D. Garlan, “Explanations for human-on-the-loop: A probabilistic model checking approach,” in _Proceedings of the IEEE/ACM 15th International Symposium on Software Engineering for Adaptive and Self-Managing Systems_ , 2020, pp. 181–187.
  * [44] A. Nhlabatsi, T. Tun, N. Khan, Y. Yu, A. Bandara, K. M. Khan, and B. Nuseibeh, “”Why Can’t I Do That?”: Tracing Adaptive Security Decisions,” _EAI Endorsed Trans. on Self-Adaptive Systems_ , vol. 1, no. 1, 2015.
  * [45] S. Adepu, N. Li, E. Kang, and D. Garlan, “Modeling and Analysis of Explanation for Secure Industrial Control Systems,” _ACM Trans. Auton. Adapt. Syst._ , vol. 17, no. 3–4, 2022.
  * [46] E. Lloyd, S. Huang, and E. Tognoli, “Improving Human-in-the-Loop Adaptive Systems using Brain-Computer Interaction,” in _Proc. of the 12th Int. Symp. on Software Engineering for Adaptive and Self-Managing Systems_ , 2017, pp. 163–174.
  * [47] J. Cámara, G. Moreno, and D. Garlan, “Reasoning About Human Participation in Self-Adaptive Systems,” in _2015 IEEE/ACM 10th International Symposium on Software Engineering for Adaptive and Self-Managing Systems_. IEEE, 2015, pp. 146–156.
  * [48] N. Li, J. Cámara, D. Garlan, B. Schmerl, and Z. Jin, “Hey! Preparing Humans to Do Tasks in Self-Adaptive Systems,” in _Proc. of the 16th Int. Symp. on Software Engineering for Adaptive and Self-Managing Systems_ , 2021, pp. 48–58.
  * [49] T. OConnor, R. Mohamed, M. Miettinen, W. Enck, B. Reaves, and A.-R. Sadeghi, “Homesnitch: Behavior transparency and control for smart home iot devices,” in _Proc. of the 12th Conf. on Security and Privacy in Wireless and Mobile Networks_ , 2019, p. 128–138.
  * [50] A. d. Garcez, S. Bader, H. Bowman, L. C. Lamb, L. de Penning, B. Illuminoo, H. Poon, and C. G. Zaverucha, “Neural-Symbolic Learning and Reasoning: A Survey and Interpretation,” _Neuro-Symbolic Artificial Intelligence: The State of the Art_ , vol. 342, no. 1, 2022.
  * [51] M. Muller and J. Weisz, “Extending a Human-AI Collaboration Framework with Dynamism and Sociality,” in _2022 Symposium on Human-Computer Interaction for Work_ , 2022, pp. 1–12.
  * [52] J. M. Haney, S. M. Furman, and Y. Acar, “Smart Home Security and Privacy Mitigations: Consumer Perceptions, Practices, and Challenges,” in _Proc. of the 2nd Int. Conf. on HCI for Cybersecurity, Privacy and Trust_ , 2020, pp. 393–411.


<EMAIL_ADDRESS><EMAIL_ADDRESS>Paper 2019

# A topological data analysis based classification method for multiple
measurements

Henri Riihimäki  Tampere University  Wojciech Chachólski  KTH-The Royal
Institute of Technology  Jakob Theorell  Karolinska Institutet  University of
Oxford  Jan Hillert  Karolinska Institutet  Ryan Ramanujam  KTH-The Royal
Institute of Technology

###### Abstract

Background, Machine learning models for repeated measurements are limited.
Using topological data analysis (TDA), we present a classifier for repeated
measurements which samples from the data space and builds a network graph
based on the data topology. When applying this to two case studies, accuracy
exceeds alternative models with additional benefits such as reporting data
subsets with high purity along with feature values. Results, For 300 examples
of 3 tree species, the accuracy reached 80% after 30 datapoints, which was
improved to 90% after increased sampling to 400 datapoints. Using data from
100 examples of each of 6 point processes, the classifier achieved 96.8%
accuracy. In both datasets, the TDA classifier outperformed an alternative
model. Conclusions, This algorithm and software can be beneficial for repeated
measurement data common in biological sciences, as both an accurate classifier
and a feature selection tool.

###### keywords:

topological data analysis; machine learning; multiple measurement analysis

††journal: general

##  1 Introduction

Topological data analysis (TDA) is a recently emerging method for analyzing
large-scale data using geometry and methods from algebraic topology [1, 2]. By
considering topological features of multidimensional data together with
various distance metrics imposed on the data, complex relationships within the
data can be preserved and jointly considered. This often leads to better
results than using standard analytical tools.

There have been several publications in biological research fields which have
utilized TDA successfully. These include modeling RNA hairpin folding [3],
Type-2 diabetes (T2D) subgrouping using clinical parameters [4], and
classification of breast cancer tumors based on gene expression patterns [5].

Despite this, TDA software typically allows only singular measurements. That
is, data is often input using a single measurement point per sample.
Frequently in biological data collection, multiple measurement points are
taken per sample. This may occur during sampling over some time interval, or
repeated measures which are indicative of sampling from a distribution of
events for each individual or sample. In this case, current methods are
insufficient to classify these data accurately, since all measurement points
are not considered together and in an informative manner.

To address these issues, we have developed a TDA based algorithm suitable for
repeated measurements. This method also contains a classifier built on the
network graph generated. This is accomplished using internal cross-validation
using multiple bootstraps, and as a result the partitioning is robust against
overfitting. The end result is a set of subgroupings of the relevant classes
which can then be used as a starting point for further investigation into
disease mechanisms.

We test this method on two unique data sets. The first is a simulation of six
different point processes on a unit square. The second example is data from 3D
modeling of various tree species, using laser scanning methods to determine
characteristics of tree branches. These branches are then used as an input to
the model. We demonstrate the accuracy of this method as compared to an
support vector machine (SVM) based classifier as well as determining how the
accuracy changes over given sampling rates, with the data available being
large.

##  2 Background

Topological data analysis arose from the mathematical field of algebraic
topology. It was noted that in a set of data, some geometry might be present
in the data distribution, or the data might reside on some topological
structure such as a manifold. Even though these shapes are usually quite
ideal, and obtaining data experimentally that conform to known mathematical
shapes is highly improbable, topology looks at the global connectedness of the
data set. Connections between data points correspond to relations in the data
and topological methods give insight into this relational structure. Plainly,
topological data analysis does not only look at the data points but also how
they are globally related.

When data is distributed unevenly, for example as a point cloud in some metric
space, geometric structures called simplicial complexes derived from the data
can yield important information. One computationally simple way to construct a
simplicial complex is the $r$-parameterized Vietoris-Rips construction. One
data point is a 0-simplex, or a vertex, $k+1$ datapoints pairwise at most
distance $r$ apart in the associated metric of data span a $k$-simplex at
scale $r$. For example, two datapoints create a 2-simplex, or an edge.
Simplices put together make simplicial complexes that can contain different
geometric features of the data such as connected components, or clusters, and
holes. Detecting holes in data has gathered interest for example in data base
community [6]. Homology is an algebraic method to measure the amount of
geometric features of different degrees. Homology in degree zero counts the
number of clusters, homology in degree 1 counts the number of 1-dimensional
loops etc. Computing homology is effectively matrix computations with so
called boundary matrices that contain information on how different simplices
are connected to each other. See Figure 1 for an example of a simplicial
complex and its homology.

2-simplices1-simplices0-simplices${\partial_{2}}$${\partial_{1}}$ Figure 1:
Five datapoints in two-dimensional space and the associated simplicial
complex. The full simplicial complex is the purple 2-simplex and the three
connected 1-simplices drawn here dashed. The boundary matrices are
${\partial_{1}}$ and ${\partial_{2}}$. Homology of this complex in degree 0 is
1 saying that there is one connected component. Homology in degree 1 is 1
indicating the loop created by the dashed 1-simplices.

Early success of TDA came in [7] where it was discovered that the space of
patches of natural images conform to a well-known geometric object. Another
early advance came in [5] where a TDA algorithm called "mapper" was used to
find a new subgroup of breast cancer with excellent survival prognosis. Mapper
models data as a network graph by refining standard clustering algorithms with
topological ideas. Namely, global clustering of the data may be inefficient,
especially when the data distance metric is not Euclidean. Instead data is
partitioned according to some intervals. These intervals are created by using
a filter function, meaning a function on data under which each point has
exactly one value on some interval of real numbers. Then, local clustering is
achieved based on those datapoints which map to the same interval. The
clusters make nodes of the data network. Intervals are overlapping by some
predefined amount. Clusters with non-empty intersection of points mapping to
the overlap of two adjacent intervals are then joined by an edge. This
construction creates a simplicial complex of clusters representing the
structure of data under the chosen filtering function. This modification to
standard clustering gives more insight into the global structure of data as
explained above. There are publicly available mapper versions, such as "Python
Mapper", which can be used to analyze data in this fashion [8].

This paper builds upon this foundation by integrating a sampling procedure for
the data, as well as adding a machine learning classifier which reports the
unbiased accuracy of the underlying model. Important nodes of interest can be
detected, which may yield important information about the data space, and
relationships to the main outcome.

##  3 Data Description

Two datasets were employed for this study. The first was a simulation of six
different point processes on the unit square. Point processes have gathered
interest in TDA community as case studies, see for example [9, 10, 11]. Let
$X\sim PD(k)$ denote that random variable $X$ follows probability disribution
$PD$ with parameter $k$. In particular, $\text{Poisson}(\lambda)$ denotes the
Poisson distribution with event rate $\lambda$.

Poisson: We first sampled number of events $N$, where
$N\sim\text{Poisson}(\lambda)$. We then sampled $N$ points from a uniform
distribution defined on the unit square $[0,1]\times[0,1]$. Here
$\lambda=400$.

Normal: Again number of events $N$ was sampled from $\text{Poisson}(\lambda)$,
$\lambda=400$. We then created $N$ coordinate pairs $(x,y)$, where both $x$
and $y$ are sampled from normal distribution $N(\mu,\sigma^{2})$ with mean
$\mu$ and standard deviation $\sigma$. Here $\mu=0.5$ and $\sigma=0.2$.

Matern: Poisson process as above was simulated with event rate $\kappa$.
Obtained points represent parent points, or cluster centers, on the unit
square. For each parent, number of child points $N$ was sampled from
$\text{Poisson}(\mu)$. A disk of radius $r$ centered on each parent point was
defined. Then for each parent the corresponding number of child points $N$
were placed on the disk. Child points were uniformly distributed on the disks.
Note that parent points are not part of the actual data set. We set
$\kappa$=80, $\mu$=5 and $r=0.1$.

Thomas: Thomas process is similar to Matern process except that instead of
uniform distributions, child points were sampled from bivariate normal
distributions defined on the disks. The distributions were centered on the
parents and had diagonal covariance $\text{diag}(\sigma^{2},\sigma^{2})$. Here
$\sigma=0.1$.

Baddeley-Silverman: For this process the unit square was divided into equal
size squares with side lengths $\frac{1}{28}$. Then for each tile number of
points $N$ was sampled, $N\sim\text{Baddeley-Silverman}$. Baddeley-Silverman
distribution is a discrete distribution defined on values $(0,1,10)$ with
probabilities $(\frac{1}{10},\frac{8}{9},\frac{1}{90})$. For each tile,
associated number of points $N$ were then uniformly distributed on the tile.

Iterated function system (IFS): We also generated point sets with an iterated
function system. For this a discrete distribution is defined on values
$(0,1,2,3,4)$ with corresponding probabilities
$\left(\frac{1}{3},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6}\right)$. We
denote this distribution by IFS. Number of points $N$ was then sampled,
$N\sim\text{Poisson}(\lambda)$, $\lambda=400$. Starting from an initial point
$(x_{0},y_{0})$ on the unit square, $N$ new points are generated by the
recursive formula $(x_{n},y_{n})=f_{i}(x_{n-1},y_{n-1}),$ where
$n\in\\{1,...,N\\}$, $i\sim\text{IFS}$ and the functions $f_{i}$ are given as

$f_{0}(y,x)=\left(\frac{x}{2},\frac{y}{2}\right),f_{1}(y,x)=\left(\frac{x}{2}+\frac{1}{2},\frac{y}{2}\right),f_{2}(y,x)=\left(\frac{x}{2},\frac{y}{2}+\frac{1}{2}\right)$
$f_{3}(y,x)=\left(\left|\frac{x}{2}-1\right|,\frac{y}{2}\right),f_{4}(y,x)=\left(\frac{x}{2},\left|\frac{y}{2}-1\right|\right).$

Figure 2: Example simulations of six different point processes used in the
study.

The second dataset came from Terrestrial Laser Scanning (TLS) of different
tree species, representing a classification problem to correctly assign tree
species from collected data. In this study we used data from Silver birch,
Scots pine and Norway spruce. The scans were made in the location of
Punkaharju in Finland. TLS produces point clouds of tree surfaces in 3D space.
These point clouds can contain tens of millions of points and are not very
useful for analysing tree data. Method of Quantitative Structural Modelling
(QSM) for reconstructing tree models from TLS scans was developed in [12].
This method reconstructs trees by fitting cylinders in the point clouds.
Figures 4 and 5 show, respectively, examples of laser scanned point cloud of a
Finnish spruce and its QSM reconstruction. Reconstructed models make it
possible to obtain diverse data from trees. For example, lengths and volumes
of individual branches are obtained by summing the lengths and volumes of the
cylinders making up the branch. QSMs also contain the topological structure of
trees as parent branch-child branch relations. For us branch means only the
main stem excluding the child branches as shown in Figure 3.

Figure 3: The purple main stem is the branch in our data sets. Purple part is
the parent branch of the black child branches.

Tree structures are ubiquitous in biological organisms. Some recent studies
have applied topological data analysis methods on brain arteries [13] and
neurons [14]. Biological tree structures are very naturally modelled as tree
graphs in 3D space [15, 16]. This however restricts the possibilities to
obtain various data from the tree. Our approach is to view trees as point
clouds of data and apply our topological analysis methods. As a multiple
measurement case, we take one data point in a tree data set to be a branch of
the tree with different features extracted from the QSM model. Specifically
branch data point had features {branch order (0 for trunk, 1 for branches
originating from trunk etc.), branch length in meters, branch height above
ground in meters, angle between branch and upward z-direction in radians}.
Trunk of the tree was excluded from the branch data.

Figure 4: Example of laser scanned spruce point cloud. Figure 5: Example of
QSM reconstructed model of the spruce point cloud in Figure 4.

##  4 Methods

The methodology used in this manuscript is an extension of published work in
the TDA field combined with a machine learning approach. Due to this algorithm
being created for repeated measurements, it is important to note that the term
"sample" refers to one individual or one particular example of, i.e., a tree
species, which itself contains many repeated measurement points. Each of these
measurements is referred to as a "datapoint".

The algorithm presented here begins by randomly sampling each sample using
some number of datapoints, less than or equal to the number of datapoints of
the smallest sample included. Thereafter a network graph was constructed, with
nodes and edges representing small clusters of datapoints and connections
between the clusters. This graph is built up by using the mapper algorithm as
previously described. To summarize, mapper begins by simplifying the data
space by using a one-dimensional filter function, by which each data point is
assigned a value. Then, the range of values for this filter function are
separated into overlapping intervals of some arbitrary length. Within these
intervals, local clustering is conducted and guided by standard methods. The
choice of linkage method here can be changed by the user. Nodes are then
examined to see if datapoints occur in two different nodes mapping to the
overlap of adjacent intervals. When this condition is true, an edge is drawn
between the nodes. For purposes of this investigation edges are not necessary,
and only the nodes contents themselves are used for analyses.

The next step of the algorithm is to add a machine learning on top of the
structure. Nodes contain a number of datapoints from each of the samples based
on geometry. This node information can be summarized in an $n$ by $m$ matrix
where $n$ is the number of samples and $m$ is the number of nodes in the
graph, and entries are the number of datapoints in a given node. These are
then fed into a classifier, in this case a sparse logistic regression model
was used for both binary and multi-class outcomes using the sklearn module
SVC. After an unbiased classification accuracy was obtained, the last step was
to rerun the entire data set, constructing a network graph from which feature
selection could then occur based on the resultant classifier.

In order to avoid over fitting at any step, careful measures were taken.
First, since this method samples from some data space, multiple samplings were
conducted and the results were averaged to more accurately represent the
sample distribution. Next, cross validation was conducted, as was running
multiple classifiers in order to find the average results so that a particular
data partitioning did not result in an over or under estimation of the
classification accuracy.

The general procedure was to first determine the sampling rates to use for
each data set. These were [10,20,30,40,50,60,70,80,90,100,150,200,400] for the
tree species and [10,20,30,40,50,60,70,80,90,100] for the point processes
data. For each sampling rate in the point process data, 10 runs were conducted
of the entire procedure, and the classification accuracy would be ultimately
averaged for these runs. For tree species, this was increased to 100 runs due
to larger variabiliy in the results. Within each run, a network graph was
built upon which a cross-validated classifier could be built. The logistic
regression model was created using 3-fold cross-validation, resulting in an
out of sample prediction on each sample in the dataset. The procedure of
building a classifier was repeated for an alternative model, namely an SVM
model with the optimal kernel. Via testing, this kernel was linear for the
tree data and radial basis function (rbf) for the point processes. For
alternative accuracy, the model was built on the sampled data as opposed to
the network graph to provide the strongest possible alternative model. This
also employed 3-fold cross-validation at the sample level, where a sample’s
out of sample prediction was based on the majority vote of its datapoints in
the training SVM. The alternative models were also constructed 10 and 100
times to account for variability on cross-validation sample assignment.

Lastly, a single model to indicate variable importance was conducted on tree
species data using the network graphing procedure and 400 sample points.
Thereafter, information regarding the node size, average feature values for
this node, and node purity were generated. Node purity is described as the
proportion of datapoints in the node which belong to the largest class, such
that the minimum can be 1/classes, and the maximum is 1. The average feature
values for this node was determined by calculating the arithemtic mean of each
feature for data in the node, providing a comparive mechanism to examine
differences between nodes. This provides information regarding how values
influence the outcome in a more complex manner than obtained with classical
methods.

##  5 Analyses

The first set of analyses was to test the algorithm on the two aforementioned
datasets. This was setup as a classification problem, wherein input data was
used to predict the label. In both examples, the filter function used was the
first principle component and the metric was Euclidean distance. The linkage
selected was complete linkage. For point processes data, runs testing the TDA
model as well as the alternative SVM model were conducted for sampling rates
from [10..400], for both the full six point processes as well as for only
normal and poisson point processes. The reason for the latter test was that
the SVM appeared to have difficulty with the six class problem. The cross-
validated accuracies are reported in Figure 6.

Using six point processes, the TDA accuracy was 60.7% using 10 datapoints, and
increased gradually to 96.8% using 100 datapoints. The alternative SVM model
began with 33.2% using 10 datapoints, and remained at 33.3% during sampling to
100 datapoints.

Using only the two mentioned point processes, the TDA classifier achieved an
accuracy of 99.6% after 30 datapoints, increasing to 99.975% at 100 datapoints
of sampling. The alternative SVM model achieved an accuracy of 99.1% with 100
datapoints.

The results of cross-validation for tree species is shown in Figure 7. The TDA
classifier had an accuracy of 76.5% using 10 sampled datapoints, increasing in
an asymptotic manner until 400 sampled datapoints and an accuracy of 90.1%.
The alternative model had an accuracy of 68.4%, increasing to a maximum of
68.7% using 30 datapoints, thereafter reducing slightly.

The next analysis used node output generated from the software. Table 1
presents the top nodes in the full data model using 400 datapoints, ordered by
number of datapoints. The purity, i.e. largest class proportion, gives
important information about the suitability of each node as a tool for
subgrouping data into unique partitions. The additional columns signify the
average values of each feature for the given node. Similarly, this data can be
used to find nodes with certain characteristics which are present in the data
which inform the class membership. Ideally, this data can be used on the
original dataset to better understand data partitioning and subclusters of
various classes.

##  6 Discussion

This paper presents a method to analyze data featuring repeated measurements,
in order to obtain high classification accuracy as well as information
regarding features in the data which are important for the outcome of
interest. In biological data, repeated measurements are often obtained, for
example when sampling the same individual over time, when large amounts of
data are sampled at a high frequency, or when blood is sampled and a large
number of measurement points are obtained. This algorithm builds on mapper
(see above) and extends it into the realm of machine learning.

The sampling procedure demonstrates that often only a relatively small number
of samples are required to adequately model the data space in question in
order to get high classification accuracy. Our method is both highly accurate
on these datasets when compared with other methods, and more informative than
regression and more classical statistical techniques. Most importantly, it is
able to determine which nodes are most responsible for the accuracy of the
final model, such that important determinations about complex relationships in
the data can be extracted.

Figure 6: Cross-validated prediction accuracy when using a multi-measurement
TDA classifier and compared with an SVM voting classifier. Datasets used were
2 classes of point processes (above) and 6 classes of point processes (below).
Datapoints are the number of points sampled per example.  Figure 7: Cross-
validated prediction accuracy when using a multi-measurement TDA classifier
and compared with an SVM voting classifier. The dataset used were tree
species, containing 100 examples of 3 classes. Datapoints are the number of
points sampled per individual tree.

When using the algorithms, there are a few caveats that need to be taken into
consideration. First, the user must be avoid overfitting when the user tests a
large number of filter functions and/or metrics, and selects the best one.
Second, the results can be computationally intensive when the number of points
sampled is high, due to runtime scaling to the order of $n^{2}$. This can be
remedied partially by reducing the size of the intervals in the underlying
algorithm, which could be automatically scaled for larger datasets. Lastly,
since this algorithm uses internal cross validation the accuracy reported is
based on a number of sub models which is equal to the number of cross
validation intervals. The final model which determines node characteristics
includes all samples, therefore may differ slightly from that from the
internal data, which should not be confused with the unbiased estimate
provided by the cross validated accuracy.

The cross validated accuracy of the TDA based classifiers exceeds the
alternative SVM voting classifier in all tests and sampling rates presented.
This was consistent despite using only a single metric and filter function for
the TDA model, while selecting the best kernel for the SVM based on accuracy.

An interesting note about classification accuracies is that with an increased
number of classes, the presented algorithm maintains a high accuracy as shown
in Figure 6. For 6 point process, the alternate SVM classifier appears to
maintain accuracy with two of the tree species, while confusing the other four
species in a consistent basis, leading to the nearly constant 33% cross-
validation accuracy.This surprising phenomenon possibly reflects a large
variation in the data which does not lead to data organization which is
accurately partitioned by a hyperplane. Similarly, a potential explanation for
the TDA classifier’s high accuracy with more point process classes is that
differences in datapoint location in multi-dimensional space could require
tools to tease out clusters based on similar geometry.

##  7 Potential implications

The utility of this algorithm and implementation has broad applicability
across the biological sciences as well as other fields. In particular, methods
for obtaining repeated measurements classification models have been lacking,
and our method fills a void in this manner. Furthermore, the ability to both
partition data into its most useful components, and thereafter extract the
features relevant for this partitioning, will allow researchers to identify
which characteristics or variables in the data are most correlated with the
outcomes.

Our algorithm and software can be employed by those who have repeated
measurements data, and further extensions to this method can also be made.
Also, the application of topological data analysis demonstrates a scenario
wherein data geometry becomes useful, and depending on the data
characteristics different metrics and filter functions can be applied. This
demonstration of data analysis within the framework of machine learning and
classification algorithms represents a novel utilization of TDA for common
needs.

Additional development of methods using topological data analysis might result
in further advances in classification techniques, and when combined with
machine learning there is strong potential for these methods in the future.

Table 1: Top nodes by numbers of samples included, and average node feature
values. Tree species data with 400 datapoints sampled from each data set.

Node number | Datapoints | Purity | Branch order | Branch length | Branch height | Branch angle
---|---|---|---|---|---|---
$17$ | 23479 | 0.405 | 2.570 | 0.612 | 14.202 | 1.532
$18$ | 22887 | 0.604 | 2.627 | 0.655 | 17.436 | 1.511
$14$ | 22668 | 0.581 | 2.481 | 0.543 | 11.141 | 1.505
$22$ | 17634 | 0.766 | 2.710 | 0.650 | 20.322 | 1.494
$10$ | 13763 | 0.634 | 2.264 | 0.559 | 8.145 | 1.467
$7$ | 4481 | 0.536 | 1.641 | 0.758 | 5.076 | 1.393
$6$ | 3535 | 0.778 | 2.956 | 0.392 | 4.864 | 1.485
$26$ | 2614 | 0.600 | 1.947 | 0.860 | 23.349 | 1.453
$2$ | 2317 | 0.556 | 1.634 | 0.669 | 2.129 | 1.237
$25$ | 1821 | 0.784 | 3.484 | 0.439 | 23.041 | 1.543
$9$ | 1523 | 0.724 | 4.292 | 0.298 | 7.843 | 1.520
$3$ | 839 | 0.770 | 2.771 | 0.390 | 2.594 | 1.851
$12$ | 781 | 0.647 | 4.702 | 0.289 | 11.031 | 1.933

Purity is defined as the highest proportion of datapoints in the node that
come from a single class.

Branch order is the level of branching: 0 for trunk, 1 for branches
originating from trunk etc.

Branch length is the branch length in meters.

Branch height is the height above ground in meters.

Branch angle is defined as the angle between branch and upward z-direction in
radians.

##  8 Availability of source code and requirements

The source code for this algorithm is available as follows:

  * •

Project name: Multiple measurements TDA classifier (mmTDA)

  * •

Project home page: https://github.com/ryaram1/mmTDA

  * •

Operating system(s): Platform independent

  * •

Programming language: Python

  * •

Other requirements: Python 3.0 or higher, numpy, pandas, scipy, sklearn,
matplotlib, fastcluster

  * •

License: GNU General Public License v3.0

##  9 Acknowledgements

The original TLS scans of the trees used in this study are the property of
Raisa Mäkipää<EMAIL_ADDRESS>Natural Resources Institute Finland,
Latokartanonkaari 9, FI-00790 Helsinki, FINLAND.

QSM models from the TLS scans were made by and are the property of Pasi
Raumonen<EMAIL_ADDRESS>Tampere University of Technology,
Korkeakoulunkatu 10, 33720 Tampere, FINLAND.

Ryan Ramanujam would like to acknowledge financial support by MultipleMS.

###  9.1 Author’s Contributions

R. Ramanujam, H. Riihimäki and W. Chachólski designed the study, with
contributions from J. Theorell and J. Hillert. R. Ramanujam created the
algorithm with W. Chachólski, and made the implementation. H. Riihimäki and R.
Ramanujam analyzed the data. The paper was jointly written by R. Ramanujam and
H. Riihimäki.

## References

  * Carlsson [2014] Carlsson G.  Topological pattern recognition for point cloud data.  Acta Numerica 2014;23:289–368.
  * Oudot [2015] Oudot S.  Persistence Theory: From Quiver Representations to Data Analysis.  American Mathematical Society; 2015.
  * Singh et al. [2007] Singh G, Mémoli F, Carlsson G.  Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition.  Eurographics Symposium on Point-Based Graphics 2007;p. 91–100.
  * Li et al. [2015] Li L, Cheng WY, Glicksberg BS, Gottesman O, Tamler R, Chen R, et al.  Identification of type 2 diabetes subgroups through topological analysis of patient similarity.  Science Translational Medicine 2015;7(311):311ra174–311ra174.
  * Nicolau et al. [2011] Nicolau M, Levine AJ, Carlsson G.  Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival.  Proceeding of the National Academy of Sciences 2011;108:7265–7270.
  * Lemley et al. [2016] Lemley J, Jagodzinski F, Andonie R.  Big Holes in Big Data: A Monte Carlo Algorithm for Detecting Large Hyper-rectangles in High Dimensional Data.  IEEE 40th Annual Computer Software and Applications Conference 2016;p. 563–571.
  * Carlsson et al. [2008] Carlsson G, Ishkhanov T, de Silva V, Zomorodian A.  On the Local Behavior of Spaces of Natural Images.  International Journal of Computer Vision 2008;76:1–12.
  * Müllner [????] Müllner D.  Python Mapper;http://danifold.net/mapper/.
  * Biscio and Møller [2016] Biscio C, Møller J.  The accumulated persistence function, a new useful functional summary statistic for topological data analysis, with a view to brain artery trees and spatial point process applications.  arXiv:161100630 2016;.
  * Hiraoka et al. [2018] Hiraoka Y, Shirai T, Duy TK.  Limit theorems for persistence diagrams.  The Annals of Applied Probability 2018;28:2740–2780.
  * Robinson and Turner [2017] Robinson A, Turner K.  Hypothesis testing for topological data analysis.  Journal of Applied and Computational Topology 2017;1:241–261.
  * Raumonen et al. [2013] Raumonen P, Kaasalainen M, Åkerblom M, Kaasalainen S, Kaartinen H, Vastaranta M, et al.  Fast Automatic Precision Tree Models from Terrestrial Laser Scanner Data.  Remote Sensing 2013;5:491–520.
  * Bendich et al. [2016] Bendich P, Marron J, Miller E, Pieloch A, Skwerer S.  Persistent homology analysis of brain artery trees.  The Annals of Applied Statistics 2016;10:198–218.
  * Kanari et al. [2018] Kanari L, Dłotko P, Scolamiero M, Levi R, Shillcock J, Hess K, et al.  A Topological Representation of Branching Neuronal Morphologies.  Neuroinformatics 2018;16:3–13.
  * Godin and Caraglio [1998] Godin C, Caraglio Y.  A Multiscale Model of Plant Topological Structures.  Journal of Theoretical Biology 1998;191:1–46.
  * Lamberton et al. [2015] Lamberton T, Lefevre J, Short K, Smyth I, Hamilton N.  Comparing and distinguishing the structure of biological branching.  Journal of Theoretical Biology 2015;365:226–237.