ABSTRACT

Effective adaptive instruction depends on knowing what a student has mastered and what they are ready to learn next. Traditional scale scores, such as those obtained from item response (IRT) models, provide only limited support for this purpose. Consequently, several recent approaches conduct student assessment within hierarchical structures of test items or competencies. While these approaches are theoretically promising, practically applicable methods for identifying such structures from empirical data remain scarce, particularly in the presence of missing item responses. To address this gap, this contribution introduces MCAR-IITA— a new implementation of Inductive Item Tree Analysis (IITA) that provides three variants of handling missing responses. To evaluate its performance, the following research question was addressed: At what percentage of missing responses can the proposed variants still recover the underlying structure? Response data were simulated along a true structure under two conditions: 1) without noise and 2) with noise, using fixed careless errors and guessing probabilities of .20 per item. Missing responses were introduced incrementally across conditions, and performance was assessed in terms of the proportion of missing data up to which the true structure could still be recovered. Additionally, the same procedure was applied to a subset of the PISA 2003 dataset based on a previously identified structure. For each dataset, the three variants were evaluated using 1,000 replications. On average, the algorithm recovered the underlying structure with a missing response percentage of 28.47% (SD = 4.49pp) for the error-free simulation, 19.93% (SD = 4.44pp) for the simulation with noise, and 15.41% (SD = 4.65pp) for the PISA data. As this study examines a first implementation and is restricted to a limited set of conditions, the results provide an initial estimate of missing-data tolerance while highlighting substantial opportunities for further optimization.

Keywords

INTRODUCTION

Tailoring instruction to students’ current states of learning requires fine-grained information about both their mastered skills and their next feasible learning opportunities. Since traditional scale scores, such as those obtained from Item Response Theory (IRT) models, provide only limited support for this purpose, novel statistical frameworks that employ hierarchical structures have been developed (e.g., DBN [7], HCDM [13], KST [5]). While these approaches are theoretically promising and some methods and software exist that make their application feasible in certain contexts, successful applications remain limited and further development is needed to expand their range of use.

In this contribution, Inductive Item Tree Analysis (IITA) [15], which is one of the primary methods for establishing hierarchical structures from response data, will be introduced briefly, followed by an illustration of its use in educational assessment using Knowledge Space Theory (KST) [5] as an example. Afterward, MCAR-IITA—a new software implementation of IITA that provides three different versions of missing response handling—will be presented. The performance of this implementation with different proportions of missing data will be evaluated in a simulation study.

Theoretical Background

IITA is a method of Boolean analysis used to derive hierarchical structures among items. The IITA algorithm takes a table of Boolean values as an input. Each column represents an item, e.g. a problem from a test or a question in a survey, and each row represents a student. Each value in the table shows if the subject represented by the row solved the item represented by the column correctly (1) or incorrectly (0). In this study, the algorithm will be discussed in the context of items within competence tests.

The output of the algorithm is a binary relation on a set of items $Q$, represented by ordered pairs of the form $a \leq b$ for $a,b \in Q$. The relation $a \leq b$ on the set of items $Q$ indicates that mastering item $a$ is a prerequisite for mastering item $b$. Since from the mastery of item $b$, the mastery of item $a$ can be surmised, this relation is called surmise relation. It forms a quasi-order among the items of $Q$, i.e. it is assumed to be reflexive, ($\forall a\ \in Q:\ a \leq a$), and transitive, $(\forall a,\ b,c\, \in Q:\,(a \leq b \land \ b \leq \ c)$ $\Rightarrow b \leq c$).

The surmise relation might be viewed as a theoretical model of the cognitive organization of knowledge in a given item domain and, as such, constitutes a latent construct, that is not directly observable from data. In practice, measurement errors introduce a probabilistic discrepancy between the latent surmise relation and the manifest response patterns, making it impossible to directly infer relationships from observed data. Therefore, the IITA algorithm aims to inductively derive the quasi-order that best fits the observed response data, thereby reconstructing the latent surmise relation from empirical observations.

These quasi-orders find direct application in educational assessment, most notably in KST, which is the basis of the commercial assessment platform ALEKS [1] and is considered one of the most efficient frameworks for adaptive instruction [6]. Unlike traditional psychometric approaches—both classical test theory and IRT—KST does not attempt to compute a numerical score representing a learner's proficiency level. Instead, the goal of assessment is to provide a precise description of what a learner knows and does not know at a given moment [5].

Student assessment in KST is based on a hierarchical structure. Let $Q\$denote a nonempty, finite set of items (or problems) that can be formulated within a particular topic-domain. In KST, a learner's knowledge is represented by a subset $K \subseteq Q\$containing exactly those items that the learner is capable of solving.

Not all subsets of $Q\$necessarily are knowledge states. Logical and pedagogical dependencies among items impose constraints on which subsets are practically possible. One way of modeling these dependencies is by establishing a surmise relation on $Q.$

The collection of all knowledge states existing in a population of learners is called a knowledge structure, formally defined as a pair $\left( Q,\mathcal{K} \right)$, where $\mathcal{K \subseteq}2^{Q}\$is a family of subsets of $Q\$containing at least the empty set $\varnothing\$(representing a learner who has mastered none of the items) and $Q\$itself (representing a learner who has mastered all items). A knowledge structure $\left( Q,\mathcal{K} \right)$ is called a knowledge space if $\mathcal{K}$ is closed under set union. Every knowledge structure induced by a surmise relation is a knowledge space.

Even though new data-driven methods for building general knowledge structures have been developed IITA remains the only procedure capable of extracting a quasi-order from the data [3] and can thus still be considered as the standard [12]. The quasi-order resulting from IITA can be directly translated into the basis of a knowledge space. As an example, consider the quasi-order represented by the ordered pairs $(I1,\ I2),\ \ (I1,\ I3),\ \ (I1,\ I4),\ \ (I1,\ I5),\ \ (I2,\ I3),\ \ (I2,\ I4),\ \ (I2,\ I5),\ \ (I3,\ I4),\ \ (I3,I5)$. The surmise relation can be visualized in an incidence matrix (see Table 1).

The basis of a knowledge space, which is the minimal set of knowledge states $K$ from which all other knowledge states can be derived by set union, can be constructed by transposing the incidence matrix. The knowledge states $K$ are the rows of the resulting matrix. The corresponding knowledge space is the union closure of the knowledge states from the basis. It can be visualized through a directed acyclic graph (see Figure 1).

Despite the benefits of KST and its close connection with IITA, current software implementations of IITA lack practical applicability mainly due to restrictive assumptions on the input response data. IITA and its predecessor Item Tree Analysis (ITA) [16] have publicly accessible implementations in R and Python. While there is an ITA version in the R package pks, IITA can be found in the R package DAKS [14] and the Python package kst available from Milan Segedinac. Importantly, all implementations require binary datasets without missing data.

Missing data constitutes a longstanding and well-known challenge in statistical inference, particularly with respect to decisions on how missing responses should be treated in data analysis [2]. Even under carefully controlled data collection procedures, missing responses

frequently occur for a variety of reasons. In educational assessment contexts, such reasons include a lack of knowledge about an item, accidental skipping, time constraints during test completion, or design-related factors such as adaptive testing procedures. Moreover, many large-scale educational studies deliberately employ test designs in which each participant is administered only a subset of a substantially larger item pool. Such matrix sampling or booklet designs, as used for example in the PISA study, induce a large proportion of structurally missing responses by design rather than by student behavior. Consequently, missing data is not an exceptional phenomenon but rather an inherent characteristic of empirical educational data, especially in large-scale and computer-based assessments.

One of the first researchers to provide a systematic framework for addressing missing data mechanisms was Rubin [9]. He emphasized that decisions about the treatment of missing data should not be made without explicitly considering the process that generated the missingness. To formalize this idea, a complete dataset $Y_{com}$ be a tuple $Y_{com} = \left( Y_{obs},Y_{miss} \right)$ of observed data and missing data. Furthermore, let $U\$be a missingness indicator specifying which responses are observed and which are missing.

Within this framework, Rubin distinguished three fundamental missing data mechanisms. Data are said to be missing completely at random (MCAR) if the probability of missingness is independent of both observed and unobserved data, that is, $P\left( U \middle| Y_{com} \right) = P(U).$

A less restrictive mechanism is missing at random (MAR), where missingness may depend on observed data but not on the missing responses themselves, formally $P\left( U \middle| Y_{com} \right) = P\left( U \middle| Y_{obs} \right).$

Finally, data are missing not at random (MNAR) if the probability of missingness depends directly on the unobserved values $Y_{mis}$.

While missing response handling has been thoroughly studied within IRT [8], it has not played a critical role in KST literature. Even though models for parameter estimation based on incomplete data have been developed within KST [4], the construction of the knowledge structure from data with missing responses has not yet been addressed.

Against this background, the present contribution introduces MCAR-IITA—a new implementation of IITA with three different variants of handling missing responses—assuming that missingness is completely at random (MCAR). Its performance was initially evaluated by addressing the following research question: At what percentage of missing data can the proposed IITA variants recover the true structure from response data?

The missing-COMPletely-at-Random IITA (MCAR-IITA)

In this section, the three variants of the new implementation of IITA for handling missing responses are presented. Python code for the implementation and the subsequently reported simulation study can be found at the following link: https://anonymous.4open.science/r/iita_python_testing/.

The implementation is developed following the three steps of IITA outlined in the Theoretical Background. In the first step, the number of counterexamples for each item pair is calculated. In the second step, an array of inductively generated quasi-orders is output, which are evaluated regarding their fit in the third step.

For handling missing values, our implementation primarily adapts the first step of the IITA procedure. We provide three variants for this step, of which the first (IITA-ABS) serves as default. This default variant ignores missing responses entirely when counting counterexamples, proceeding only with the observed responses for each item pair. A potential limitation of the IITA-ABS variant arises from the fact that the original IITA algorithm counts counterexamples in absolute numbers rather than proportions. In the context of complete datasets this approach is unproblematic, since all item pairs are observed with equal frequency across respondents. However, when missing responses are distributed unevenly across items, this assumption no longer holds. The second variant (IITA-REL) accounts for the issue described above by dividing the absolute number of counterexamples by the number of cases where a counterexample can appear (i.e., where neither response is missing) for every item pair. Thereby, a relative counterexample counter with values between 0 and 1 is obtained. In the third variant (IITA-IMP), the missing responses are first imputed by the item-mean imputation, replacing each missing value with the mean of the available responses of the respective item. Afterwards the counterexamples are calculated as in the second variant.

SIMULAtION STUDY

To evaluate the IITA implementation and its three variants of missing data handling, a simulation study was conducted.

Methods

As in previous studies about the performance of IITA [10, 15], we used the pisa dataset from the DAKS package, which contains the item responses by 340 German students on a five-item dichotomously scored mathematical literacy test. This dataset will be referred to as pisa-orig. Applying IITA to this dataset results in the surmise relation depicted in Table 1. Since it is real world data, the relation among the items is naturally latent. Accounting for that fact, additional data was simulated along this structure. The resulting datasets pisa-sim-0-0 and pisa-sim-2-2 also contain 340 response patterns to five items. While pisa-sim-0-0 was simulated with zero noise such as careless errors and lucky guesses, thereby containing only knowledge states as response patterns, the dataset pisa-sim-2-2 was simulated with a probability of .20 for guessing and careless errors. Originally all three datasets do not contain any missing responses.

The quasi-order, identified originally from the pisa-orig dataset was taken as the true underlying structure for all three datasets. To test the percentage of missing data that the three different variants of the implementation can handle, missing responses were inductively added at random positions via a data amputation procedure [11]. Therefore, in every iteration, possible positions for missing responses in the dataset are identified. A position is possible, if there is no missing value already and if neither a column nor a row is completely empty after adding the missing value. From the pool of possible positions, two are chosen randomly. The data at these positions of all three datasets are replaced by missing responses. After introducing the missing responses, all variants are applied to all three datasets. The quasi-order extracted by each variant is compared with the true quasi-order. If one variant produces a different quasi-order from one of the datasets, it is not applied to that dataset again in the next iteration. The procedure ends if no variant produces the correct quasi-order on any of the datasets anymore. This was repeated for 1,000 iterations to account for positional differences in the missing responses. The data were descriptively analyzed by calculating the means and standard deviations for each dataset-variant combination.

Results

As illustrated in Figure 2, the true partial order was extracted up to a missing data proportion of 21.22% (SD = 7.29pp) on average across all three variants and datasets. For the real-world dataset pisa-orig, all three variants performed on average worse than on the synthetic ones, with an average missing data proportion of 15.41% (SD = 4.65pp). The best-performing variant on this dataset was IITA-ABS with an average tolerance of 15.6% (SD = 5.75pp) of missing data.

As expected, on the two synthetic datasets all three variants performed better on the noiseless dataset pisa-sim-0-0. The average missing data coverage on this dataset across all three variants is 28.31% (SD = 4.49pp). The ranking across the three variants is the same as on the pisa-orig dataset: the IITA-ABS performs best (M = 28.6, SD = 4.68pp), the IITA-REL performs slightly worse (M = 28.47, SD = 4.53pp) and the IITA-IMP performs worst (M = 27.88, SD = 4.79pp).

Interestingly, the picture changes when considering the pisa-sim-2-2 dataset, where careless errors and lucky guesses were introduced with a noise probability of .20. On average, a tolerance for missing data of 19.93% (SD = 4.44pp) was achieved across all three variants, with IITA-IMP performing best (M = 20.37%, SD = 4.31pp). The IITA-REL variant performed slightly worse (M = 19.84%, SD = 5.01pp), while IITA-ABS—previously the best-performing variant on the other two datasets—performed worst on this dataset (M = 19.58%, SD = 5.35pp).

Discussion

The results demonstrate the capability of the MCAR-IITA implementation of handling missing data. Particularly compared to other psychometric methods, an average tolerance for missing data of 21.22% can be considered substantial [2]. Overall, all three IITA variants perform similarly, showing a good tolerance for missing data on the simulated datasets (about 20%) as well as on the real dataset (about 15%).

These findings should be interpreted in light of several limitations. First, the study design accounted only for the factor of missing value positions within the dataset. In further studies more factors like the size of the dataset and domain characteristics like the amount of pairwise relations should be included.

Furthermore, while MCAR-IITA is theoretically able to handle all MAR-data, this study evaluates only the performance on MCAR data, which represents the least complex case of missingness. While future research should continue to investigate this special case, given that it enables the application of IITA to a broad range of large-scale assessment data with multi matrix designs, examining MAR and MNAR mechanisms would also be of practical value.

Lastly, it should be noted that the proportion of missing responses at which the implementation ceases to recover the correct structure provides only an initial insight into algorithmic performance and precludes further informative analyses. For instance, if the algorithms had continued to run after outputting a non-exact structure, their behavior could have been analyzed with respect to the difference between the recovered and the true partial order.

Beyond refining the simulation study design to better understand the interaction of IITA with missing responses, several other avenues for future research warrant consideration. While the implementation presented has already yielded promising results, there is still room for improvement. Especially, since mainly the first phase of IITA was adapted to suit datasets with missing values, manipulating the fit metrics at the third step could yield further optimization potential.

Conclusion

Inductive Item Tree Analysis constitutes one of the foundational methods for enabling state-of-the-art formative student assessment. However, its practical applicability has been constrained by restrictions on the input data. In particular, handling missing responses remains one of the most pressing challenges, as they occur in the vast majority of empirical datasets. This contribution introduced and evaluated MCAR-IITA—an IITA implementation incorporating three distinct variants for handling missing responses. The results are promising, demonstrating that the implementation can recover underlying item structures even in the presence of substantial proportions of missing values (i.e., up to about 20%). Beyond these findings, this work opens a variety of avenues for further investigation, both with respect to the implementation presented here and regarding additional algorithmic optimizations. Thus, this contribution represents an important step toward making state-of-the-art psychometric methods more broadly applicable in educational practice.

ADDITIONAL AUTHORS

Additional author: Jan Hochweber (St. Gallen University of Teacher Education, email: jan.hochweber@phsg.ch).

REFERENCES

1. Cosyn, E., Uzun, H., Doble, C. and Matayoshi, J. 2021. A practical perspective on knowledge space theory: ALEKS and its data. Journal of Mathematical Psychology. 101, (2021), 102512. https://doi.org/10.1016/j.jmp.2021.102512.
2. Dai, S. 2021. Handling Missing Responses in Psychometrics: Methods and Software. Psych. 3, 4 (Nov. 2021), 673–693. https://doi.org/10.3390/psych3040043.
3. De Chiusole, D., Spoto, A. and Stefanutti, L. 2024. Innovative Methods for Building Knowledge Structures. Advanced Series on Mathematical Psychology. WORLD SCIENTIFIC. 87–104.
4. De Chiusole, D., Stefanutti, L., Anselmi, P. and Robusto, E. 2015. Modeling missing data in knowledge space theory. Psychological Methods. 20, 4 (2015), 506–522. https://doi.org/10.1037/met0000050.
5. Doignon, J.-P. and Falmagne, J.-C. 1985. Spaces for the assessment of knowledge. International Journal of Man-Machine Studies. 23, 2 (Aug. 1985), 175–196. https://doi.org/10.1016/S0020-7373(85)80031-6.
6. Ihichr, A., Oustous, O., Idrissi, Y.E.B.E. and Lahcen, A.A. 2024. A Systematic Review on Assessment in Adaptive Learning: Theories, Algorithms and Techniques. International Journal of Advanced Computer Science and Applications. 15, 7 (2024). https://doi.org/10.14569/IJACSA.2024.0150785.
7. Käser, T., Klingler, S., Schwing, A.G. and Gross, M. 2017. Dynamic Bayesian Networks for Student Modeling. IEEE Transactions on Learning Technologies. 10, 4 (Oct. 2017), 450–462. https://doi.org/10.1109/TLT.2017.2689017.
8. Little, R.J.A. and Rubin, D.B. 2002. Statistical Analysis with Missing Data. Wiley.
9. Rubin, D.B. 1976. Inference and missing data. Biometrika. 63, 3 (1976), 581–592. https://doi.org/10.1093/biomet/63.3.581.
10. Sargin, A. and Ünlü, A. 2009. Inductive item tree analysis: Corrections, improvements, and comparisons. Mathematical Social Sciences. 58, 3 (Nov. 2009), 376–392. https://doi.org/10.1016/j.mathsocsci.2009.06.001.
11. Schouten, R.M., Lugtig, P. and Vink, G. 2018. Generating missing values for simulation purposes: a multivariate amputation procedure. Journal of Statistical Computation and Simulation. 88, 15 (Oct. 2018), 2909–2930. https://doi.org/10.1080/00949655.2018.1491577.
12. Segedinac, M.T., Horvat, S., Rodić, D.D., Rončević, T.N. and Savić, G. 2018. Using knowledge space theory to compare expected and real knowledge spaces in learning stoichiometry. Chemistry Education Research and Practice. 19, 3 (2018), 670–680. https://doi.org/10.1039/C8RP00052B.
13. Templin, J. and Bradshaw, L. 2014. Hierarchical Diagnostic Classification Models: A Family of Models for Estimating and Testing Attribute Hierarchies. Psychometrika. 79, 2 (Apr. 2014), 317–339. https://doi.org/10.1007/s11336-013-9362-0.
14. Uenlue, A. and Sargin, A. 2009. DAKS: Data Analysis and Knowledge Spaces.
15. Ünlü, A. and Schrepp, M. 2021. Generalized inductive item tree analysis. Journal of Mathematical Psychology. 103, (Aug. 2021), 102547. https://doi.org/10.1016/j.jmp.2021.102547.
16. Van Leeuwe, J.F. 1974. Item tree analysis. Nederlands Tijdschrift voor de Psychologie en haar Grensgebieden. 29, 6 (1974), 475–483.

© 2026 Copyright is held by the author(s). This work is distributed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license.