Iterative Item Selection of Neighborhood Clusters: A Nonparametric and Non-IRT Method for Generating Miniature Computer Adaptive Questionnaires

Abstract

The questionnaire method has always been an important research method in psychology. The increasing prevalence of multidimensional trait measures in psychological research has led researchers to use longer questionnaires. However, questionnaires that are too long will inevitably reduce the quality of the completed questionnaires and the efficiency of collection. Computer adaptive testing (CAT) can be used to reduce the test length while preserving the measurement accuracy. However, it is more often used in aptitude testing and involves a large number of parametric assumptions. Applying CAT to psychological questionnaires often requires question-specific model design and preexperimentation. The present article proposes a nonparametric and item response theory (IRT)-independent CAT algorithm. The new algorithm is simple and highly generalizable. It can be quickly used in a variety of questionnaires and tests without being limited by theoretical assumptions in different research areas. Simulation and empirical studies were conducted to demonstrate the validity of the new algorithm in aptitude tests and personality measures.

Keywords

Questionnaire length computer adaptive test item selection machine learning Likert-type scale personality measures

Introduction

Questionnaire length is an important factor in determining the response rate in various studies. Farooq (2018) focused on this topic and mentioned that a long questionnaire increases the probability of premature termination, random responses, or other behavior patterns, which results in data of lower quality. Respondents are reluctant to respond to long questionnaires, and their response rates decline. Gibson and Bowling (2020) conducted a study on the relationship between questionnaire length and careless responding. They found that varying questionnaire length had a significant effect on careless responses, but this effect was only observed in online questionnaires. Specifically, the effect was most pronounced when comparing questionnaires with few items (10) to those with many items (240). As a result, it is important to carefully control the length of questionnaires to ensure the quality of the data collected, particularly in the case of online surveys. To limit the length of questionnaires, researchers must often manually select some of the questions from the original question set. This is particularly common in studies measuring multidimensional traits, which is becoming increasingly frequent in psychological research, and it becomes a challenge to select items rationally and effectively.

Computer adaptive testing (CAT) is a computer-administered assessment in which the questions are selected based on the ability of the test taker. According to Meijer and Nering (1999), the objective of CAT is to construct an optimal test for each examinee. To achieve this, an examinee’s trait level ( $θ$ ) is estimated during test administration, and items appropriate for the examinee’s $θ$ are selected from an item bank. The advantages of CAT over paper-and-pencil (P&P) tests are shorter tests, enhanced measurement precision, testing on demand, and immediate test scoring and reporting. These advantages are also very attractive for questionnaires, especially the increased accuracy and reduced costs associated with shorter tests. Therefore, some studies have applied CAT to specific psychological questionnaires. Makransky et al. (2013) studied the performance of CAT applied to personality tests, the widely used NEO PI-R. They concluded that there can be practical and statistical advantages to incorporating the CAT model in personality testing, particularly for personality tests that contain many highly correlated facets. Fliege et al. (2005) developed CAT for depression measurement and concluded that patient-related outcome research can benefit from the advantages of CAT. Petersen et al. (2018) applied CAT to cancer research and clinical practice. They found that CAT achieved higher measurement precision and increased statistical power in psychometric evaluations than the Quality of Life Questionnaire Core 30 (QLQ-C30) scales. Using CAT, sample size requirements may be reduced by approximately 20% to 35% on average without loss of power.

However, all these studies implemented CAT based on parametric item response theory (IRT). Models such as the two-parameter logistic (2PL), three-parameter logistic (3PL; Birnbaum, 1968), and generalized partial credit (Muraki, 1992) models were employed when modeling the relationship between latent traits and item responses. Parametric models limit descriptions of the probability of correct responses to items as a function of latent traits, which brings the risk of estimation bias due to inappropriate model selection. Compared with parametric models, nonparametric models are more flexible and robust and are more suitable for complex tests. Falk and Feuerstahler (2022) reviewed two significant categories of nonparametric CAT models and evaluated their effectiveness. The idea of both types of nonparametric models is to use a nonparametric representation to indicate the probability of a correct response for items by the examinee. The difference is that Falk and Cai (2016) chose a monotonic polynomial (MP) approach, and Xu and Douglas (2006) chose a kernel smoothing (KS) approach based on Kullback–Leibler as the nonparametric representation.

Both Falk and Feuerstahler (2022) and Xu and Douglas (2006) introduced a nonparametric model but did not discard the framework of the probability of correct responses as a function of latent traits. If the reliance on the trait level’s estimation cannot be discarded, the author considers this nonparametrization to be inadequate, and both schemes can be considered semiparametric. Both schemes were tested with simulated experiments in aptitude test scenarios only. Whether the flexibility brought by nonparametrization allows for a more convenient extension of CAT to all types of questionnaire tests has not been demonstrated by any past work. The present article proposes a novel nonparametric CAT algorithm that enables item selection without the need to estimate trait levels during the response process. It can not only be used in various aptitude test scenarios but can also be very easily applied to various questionnaires. The core values of the proposed algorithm are reflected in the following three aspects:

As Xu and Douglas (2006) mentioned, nonparametric estimation can help reduce the bias that would result from fitting a misspecified parametric model. The proposed algorithm makes no assumptions about the distribution of latent abilities ( $θ$ ), the function expression of the probability of correct responses to items, or the relationships between items and abilities (Q-matrix), which makes the advantages of this algorithm even more significant.

Most psychological questionnaires measure trait levels by calculating the mean (summed) scores of specified items rather than latent variables. The proposed algorithm can be adapted to arbitrary requirements for the distribution of measurement results, which makes it more suitable for transforming traditional psychological questionnaires into CATs and maintaining sum score-like results output.

Compared with other methods, the proposed algorithm utilizes similarities between subjects rather than between items and is therefore particularly suitable for situations where the number of items in the item banks or the CAT is small.

The main idea behind the proposed algorithm is to iteratively cluster the neighboring samples of the respondent and then add the item to the questionnaire by comparing the differences in each item’s responses across classes and selecting the item with the greatest differences. In the proposed method, the most representative sequence of items is selected to find the most appropriate neighbor group for the target respondent, resulting in CAT. The average of the measurements of the neighbor group of the target respondent found by the algorithm will finally be the measurement of that respondent. The proposed algorithm is a general method, but it is proposed for the scenario of reducing the questionnaire length to ensure the quality of the subjects’ responses. Based on the study of Gibson and Bowling (2020), the data quality can only be significantly improved when the questionnaire length is kept to a minimum. As such, our subsequent studies will focus on the generation of miniature CATs (2–10 items measuring one trait/ability).

The remainder of the article is organized as follows. First, the proposed algorithm is introduced. Second, two comparison studies are presented. Third, the author summarizes the comparison results and conclude with a discussion of the findings. Finally, the author discusses future directions for research and draw conclusions.

Algorithm

The goal of the algorithm is to provide a subject with a computer adaptive test (CAT) for specified traits/abilities ( $θ$ ) measurement (item selection and $θ$ estimation) by inputting an item bank (containing sample subjects’ responses to all items and a measure of each subject’s $θ$ value).

Symbol Definition

A questionnaire includes $p$ items measuring $q$ trait levels (personal attributes) such as health, traits, abilities, or other levels. All $p$ items form a set, denoted $I$ . For a set, function $# (*)$ represents the number of elements in the set. Valid responses of $n$ subjects to the questionnaire, which is a $n \times p$ matrix, are collected. Symbol $R_{E}^{I}$ represents the response matrix of all subjects within set $E$ on all items within set $I$ . Measurements of $q$ facets are calculated for these $n$ subjects, and the results are referred to as scores. The scores of one subject are one feature vector with dimensions equal to $q$ . Symbol $S_{E}$ represents the total $q$ scores for all subjects within set $E$ , a $n \times q$ matrix. For a new questionnaire respondent, a new method called iterative item selection of neighborhood clusters (IISNC) is proposed to create a short computer adaptive questionnaire.

Function $Dist (a, b)$ represents the calculation of the distance between $a$ and $b$ , which is a function that satisfies the axioms of distance measures (e.g., Euclidean distance and Manhattan distance).

Iterative Item Selection of Neighborhood Clusters

The proposed IISNC method proceeds as follows:

Initialize the adaptive questionnaire item set to an empty set and all subjects into the neighbor group.

Build a two-class cluster for scores of subjects within the neighbor group.

Calculate the response difference between two classes for each unselected item, and select the item with the highest response difference (details discussed below).

Add the selected item into the adaptive questionnaire item set, and obtain a new respondent’s response to this item.

Calculate distances between the responses of a new respondent and all subjects within the adaptive questionnaire items set, and treat the specified number of subjects with the smallest distance as the neighbor group.

Repeat Steps 2 to 5 until the adaptive questionnaire length reaches the preset limit. The mean score of the last neighbor group with half the size is used as the score of the new respondent.

According to Meijer and Nering (1999), CAT is composed of two parts, the examinee’s trait level ( $θ$ ) estimation and item selection. Traditional $θ$ estimation is made possible by IRT, and the two main item selection approaches are maximum information selection and Bayesian item selection. For questionnaires, the closer two respondents’ trait levels ( $θ$ or scores) are, the more similar their item responses. Based on this underlying assumption, our target is to find the sample group that is closest to the respondent’s responses (i.e., the subject’s neighbor group) and use the average scores of this group as the respondent’s scores. This is a nonparametric process without model (including IRT) assumptions. The proposed algorithm replaces the $θ$ estimation step with finding the neighbor group naturally. Item selection is still accomplished by locating the item with maximum information, defined as having the greatest influence on the classification of the neighbor group. Therefore, the basic IISNC process is as follows: update the respondent’s neighbor group with all the items currently selected, find the most informative item in the existing neighbor group and select it as the new item, and repeat the whole process until the questionnaire reaches the specified length or there is only one sample left in the current neighbor group.

To locate the item with maximum information, a two-step procedure using machine learning models is employed. The first step is to cluster the subjects in the neighbor group into two classes based on their score feature vectors. This step can be achieved by a cluster model (e.g., k-means and density-based spatial clustering of applications with noise). The second step is to calculate the difference between the responses of subjects in the two classes for each item, referred to as the response difference. The item with the highest response difference is selected. In the proposed IISNC method, a simple definition of response difference is employed, which is the absolute value of the difference between the average responses of the two classes (shown as Algorithm 1). In the first step, subjects in the neighbor group are identified based on their scores, and in the second step, the item that best determines this distinction is found. With these two steps, IISNC theoretically selects an item that best reflects the variation in scores within the neighbor group. In other words, the maximum information is obtained from this item.

Algorithm 1

Iterative item selection of neighborhood clusters.

Input : responses of subject set

E

to item set

I

R_{E}^{I}

;
: scores of subject set

E

S_{E}

;
Output : adaptive questionnaire item set

AQI

;
: new respondent’s responses

R_{r}^{AQI}

;
: new respondent’s score

S_{r}

;
Hyperparameter: questionnaire length limit

L

;
: final neighbor group size

l

;
1 initialize

j = 1

;
2 initialize adaptive questionnaire item set

AQI = \emptyset

;
3 initialize score data for training

ST = S_{E}

;
4 repeat
5 build a two-class cluster with

ST

as the training data;
6 apply the cluster to

ST

to obtain the first-class set

C_{1}

and second-class set

C_{2}

;
7 for each item

k \in I / AQI

, calculate

R D_{k} = | \sum_{c \in C_{1}} \frac{R_{c}^{k}}{# (C_{1})} - \sum_{c \in C_{2}} \frac{R_{c}^{k}}{# (C_{2})} |

;
8 find one

i

s.t.

\forall k \in I / AQI, R D_{i} \geq R D_{k}

;
9

AQI = AQI \cup {i}

;
10 obtain the response of new respondent

r

to item

i

R_{r}^{i}

;
11 order set

E

, according to the ascending values of

Dist (R_{k}^{AQI}, R_{r}^{AQI})

\forall k \in E

;
12 the top-

2 l

subjects in

E

form set

N

;
13

ST = S_{N}

;
14

j = j + 1

;
15 until

j > L

;
16 the top-

l

subjects in

E

form set

N

17 output

AQI

R_{r}^{AQI}

and

S_{r} = \sum_{k \in N} \frac{S_{k}}{# (N)}

;

Studies

In the IISNC algorithm, the K-means algorithm was chosen for the cluster, the Manhattan (L1) distance was used as the distance between subjects’ responses, and the final neighbor group size was set to 20. Python3 and the extension libraries NumPy and sklearn were used to implement IISNC and obtain statistics for the results. The mirt and mirtCAT libraries in R were used to estimate ability values and item parameters and implement CAT with multidimensional item response theory (MCAT) in all studies except Study 2.1.

Simulation Study

In Study 1, the authors simulate a scenario in which a questionnaire is assumed to measure two abilities (traits) of the subjects. The result of the measurement is the sum of the scores of the items corresponding to each ability (trait). A miniature CAT ( $L = 10$ , with an average of 5 items measuring one ability) was constructed on the basis of the item bank. The performance of the proposed IISNC algorithm is compared with MCAT in this scenario. For the IISNC algorithm, an IISNC scheme using Q-matrix information noted as (Q)IISNC is considered in addition to the original scheme. Specifically, (Q)IISNC is done by applying IISNC to each ability separately, using only the items corresponding to that ability as input, and selecting half of the total number of items for each ability. For MCAT, in addition to the original algorithm, a scheme controlling the exposure of items noted as (C)MCAT was added for comparison. Specifically, the Sympson-Hetter exposure control method is implemented with a sampling probability of 0.7 for each item.

Item Bank Description

Item banks were generated by first simulating the responses of 1,000 subjects to $p$ items using a two-parameter logistic model (Equation 1). Each subject had two abilities, both of which followed a standard normal distribution. Each ability independently influenced the responses of $p / 2$ items. For the $p$ items, the discrimination parameters were drawn from a uniform distribution in (0.75, 2.5), and the intercept parameters were drawn from a standard normal distribution. The number of items $p$ took on five different values: 20, 40, 60, 80, and 100.

P_{j} (Responese = 0) = \frac{1}{1 + \exp (\sum_{k} (α_{jk} θ_{k}) + β_{j})}

(1)

P_{j} (Responese \geq i) = \frac{1}{1 + \exp (\sum_{k} (- α_{jk} θ_{k}) + β_{j} + γ_{ij})}

(2)

where $θ$ refers to ability, $α, β, γ$ are item parameters; $j$ for different item, $k$ for different ability dimension, and $i$ for different proximity level.

Simulation Design

One hundred new respondents’ responses were generated from a standard normal ability distribution corresponding to each item bank. In total, 100 different item banks and 10,000 new respondents were generated for each $p$ value. In IRT, the model selection and the correct Q-matrix corresponding to simulations were provided, and the remaining hyperparameters were set by default. In MCAT, item parameters estimated by IRT and the correct Q-matrix were provided, the estimation of ability $\hat{θ}$ was calculated by the “maximum a-posteriori (MAP)” method, the starting item was selected by “maximum information” criteria, and the adaptive item selection criterion was the “maximum determinant of the information matrix.” The root mean squared deviation (RMSD) from full-test estimates, defined as $\sqrt{\sum_{i = 1}^{m} {({\hat{S}}_{i} - S_{i})}^{2} / m}$ , was used as a metric to evaluate the performance of different algorithms. The author also reported the mean of the computing time cost and the bias, defined as $\sum_{i = 1}^{m} ({\hat{S}}_{i} - S_{i}) / m$ , where $S$ represents the measurements result which is the sum of all item scores corresponding to the ability, $\hat{S}$ refers to estimated scores, $m$ refers to the number of new respondents, and $i$ represents different respondents. For the IISNC algorithm, the summed measurements in the item banks are the score inputs and $\hat{S}$ is the direct output of the algorithm. For the MCAT algorithm, $\hat{S} = \sum_{j} {\hat{P}}_{j} (Responese = 1 | \hat{θ})$ , the expectation of the score calculated from the MCAT estimated ability and the IRT estimated model parameters.

Results

Table 1 present the mean of 100 results in Study 1.

Table 1

Results in Study 1

$p$	Method	bias1	bias2	rmsd1	rmsd2	time(s)
20	MCAT	0.0015	0.0090	0.9763	0.9706	8.2813
	(C)MCAT	0.0297	0.0027	1.9875	1.7926	7.6940
	ISSNC	–0.0084	0.0137	0.9067	0.9402	1.2611
	(Q)ISSNC	0.0044	0.0082	0.8872	0.7825	1.1180
40	MCAT	0.0175	0.0057	1.9570	1.9250	8.4253
	(C)MCAT	0.0177	0.0261	2.0632	2.0148	7.9068
	ISSNC	0.0008	–0.0085	2.0922	2.1325	1.4182
	(Q)ISSNC	0.0124	–0.0138	2.0420	1.9356	1.1976
60	MCAT	–0.0137	–0.0206	2.8680	2.8666	8.4619
	(C)MCAT	–0.0447	–0.0416	2.9943	3.0060	7.9711
	ISSNC	–0.0141	–0.0371	3.2237	3.2348	1.4740
	(Q)ISSNC	–0.0057	–0.0265	3.0882	2.9561	1.2340
80	MCAT	0.0140	–0.0177	3.8401	3.8044	8.5575
	(C)MCAT	–0.0316	0.0177	3.9543	3.9785	8.0356
	ISSNC	0.0168	–0.0079	4.2915	4.2765	1.5796
	(Q)ISSNC	0.0391	–0.0328	4.0328	3.9681	1.3099
100	MCAT	0.0699	0.0326	4.7616	4.6631	8.5763
	(C)MCAT	0.0878	0.0218	4.9167	4.9298	8.2564
	ISSNC	0.0835	–0.0439	5.3525	5.3548	1.5627
	(Q)ISSNC	0.0899	0.0417	5.0537	5.0423	1.3235

Note. MCAT = multidimensional computer adaptive testing; ISSNC = iterative item selection of neighborhood clusters.

In most cases, MCAT outperformed IISNC, especially as the total number of items in the item bank ( $p$ ) increased. However, the biases of both methods were at a similar level with no significant difference. As the data generation is based on IRT, the author anticipated that the parametric model with correct assumptions (MCAT) would perform better than the nonparametric model (IISNC). Nevertheless, this result does not discredit the validity of IISNC. Conversely, when $p$ is low, IISNC either performed equally well or even better than MCAT. In addition, IISNC exhibited more balanced item exposure than MCAT. In Figure 1, the exposure rates of items are presented for both IISNC and MCAT across 100 simulated experiments in Study 1 when $p = 60$ . It is essential to note that this comparison is not fair since several methods can control the exposure of MCAT items. Therefore, comparing (Q)IISNC with (C)MCAT would be more appropriate.

Compared with (C)MAT, (Q)IISNC demonstrated superior RMSD results for small $p$ , but this advantage dissipates as $p$ increases. The difference is not significant. The biases of the two methods were at the same level without a significant difference. Figure 2 presents the exposure rate of items on the (Q)IISNC and (C)MCAT for 100 simulated experiments in Study 1 when $p = 60$ . (Q)IISNC has higher exposure levels of the top five items compared with (C)MAT due to lack of direct control over exposure rates. However, the exposure rates for the other items are better (with lower exposure rates for items above the average frequency and higher exposure rates for items below). Overall, when exposure rates are balanced, the (Q)IISNC method can achieve similar levels of estimation as MCAT under simulated conditions. It is worth noting that the IISNC series methods perform better with low $p$ values, which are less common in ability testing scenarios but more prevalent in non-cognitive testing scenarios (e.g., 20 items for one trait: Self-Rating Depression Scale [SDS], Zung’s Self-Rating Anxiety Scale [SAS], UCLA Loneliness Scale; around 10 items for one trait: Pittsburgh Sleep Quality Index [PSQI], Williams Creativity Scale [WCS]).

In terms of computing speed, the MCAT and IISNC methods were executed on the same simulated data using the same device (i.e., Intel(R) Xeon(R) Silver 4314 CPU @ 2.40 GHz). Overall, IISNC took only approximately one fifth of the time of MCAT, and IISNC had a significantly better performance in terms of speed. A possible explanation for this is the nonparametric nature of IISNC, where finding nearest neighbors and simple averaging operations replace the complex parametric calculations. An item selection time of less than 0.2 seconds per item ensures the usefulness of IISNC for real-time testing scenarios. (Q)ISSNC demonstrated a slight speed advantage over IISNC, possibly because (Q)ISSNC performs calculations in one-dimensional space, whereas IISNC estimates scores for both dimensions simultaneously.

Empirical Studies

This subsection shows the performance of the IISNC algorithm on an NEO PI-R personality test, as applied to two studies.

Item Bank Description

The Danish version of the NEO PI-R test (Costa & McCrae, 1992) is a computer-based Big Five personality questionnaire. It consists of 240 items distributed over five constructs (neuroticism, extraversion, openness, agreeableness, and conscientiousness). The items are scored on a 5-point Likert-type scale. The raw data were obtained from Goldberg (2018) and filled in the missing responses using random values. It contains the responses of 857 subjects to all NEO PI-R items.

Validation Design

For both studies, 857-fold cross-validation was performed, which means that each subject was selected in turn as a new respondent, and the remaining 856 subjects formed the item bank, for a total of 857 tests. The raw data contained trait scores, $S$ , which were derived from the average responses to items corresponding to each trait. These scores were used as input for the IISNC algorithm. To assess the performance of different algorithms, the author continued to use the RMSD from full-test estimates, defined as $\sqrt{\sum_{i = 1}^{m} {({\hat{S}}_{i} - S_{i})}^{2} / m}$ . Here, $S$ as defined refers to the measurement result that would have been obtained if all items were administered. In the case of the IISNC algorithm, $\hat{S}$ is the direct output of the algorithm. For the MCAT algorithm, on the other hand, $\hat{S}$ is calculated as $(q / p) \sum_{j = 1}^{p / q} \sum_{i} [i \times {\hat{P}}_{j} (Responese = i | \hat{θ})]$ , which is the expectation of the score calculated from the MCAT estimated ability and the IRT estimated model parameters.

In Study 2.1, the results of IISNC were compared with two schemes named “random” and “correlate.” In the “random” scheme, one fifth of the total test length items corresponding to each trait were randomly selected. In the “correlate” scheme, one fifth of the total test length items were selected according to their Pearson correlation with each trait score, from largest to smallest. For both schemes, the average response of the corresponding items for each trait was used as the output score $\hat{S}$ .

In Study 2.2, the results of IISNC were compared with those using MCAT with item parameters estimated by IRT with the graded model (Equation 2) and the correct Q-matrix, the estimation of ability $\hat{θ}$ was calculated by the “MAP” method, the starting item selected by using the “maximum information,” and the adaptive item selected by the “maximum determinant of the information matrix.” In addition, a comparison of (Q)IISNC was added. (Q)IISNC was performed by applying IISNC to each trait separately, using only the items corresponding to the trait as input and selecting one fifth of the total number of items for each trait.

Results

Table 2 presents the average RMSD results in Study 2.1, while Table 3 presents the average RMSD results in Study 2.2.

Table 2

Cross-Validated RMSD Results in Study 2.1

L	Method	Neuroticism	Extraversion	Openness	Agreeableness	Conscientiousness	Total
10	IISNC	0.3081	0.3249	0.3177	0.3257	0.3242	0.3201
	Random	0.7071	0.7413	0.7281	0.6802	0.6756	0.7065
	Correlate	0.8299	0.6907	0.6964	0.7392	0.5760	0.7065
20	IISNC	0.2845	0.2900	0.2839	0.3002	0.3059	0.2929
	Random	0.4986	0.5098	0.4893	0.4589	0.4711	0.4855
	Correlate	0.5519	0.4154	0.5465	0.5550	0.4273	0.4992
30	IISNC	0.2603	0.2815	0.2707	0.2953	0.2864	0.2788
	Random	0.3938	0.3938	0.3941	0.3743	0.3829	0.3878
	Correlate	0.4965	0.3920	0.4848	0.4417	0.3577	0.4346
40	IISNC	0.2507	0.2731	0.2584	0.2825	0.2764	0.2682
	Random	0.3314	0.3462	0.3301	0.2995	0.3159	0.3246
	Correlate	0.4415	0.3771	0.4105	0.3800	0.3165	0.3851
50	IISNC	0.2558	0.2665	0.2489	0.2785	0.2761	0.2651
	Random	0.3019	0.3068	0.2941	0.2835	0.2807	0.2934
	Correlate	0.4315	0.3003	0.3622	0.3475	0.2796	0.3442
60	IISNC	0.2452	0.2569	0.2431	0.2672	0.2697	0.2564
	Random	0.2624	0.2657	0.2784	0.2433	0.2521	0.2604
	Correlate	0.3914	0.2711	0.3271	0.2999	0.2793	0.3138

Note. RMSD = root mean squared deviation; IISNC = iterative item selection of neighborhood clusters.

Table 3

Cross-Validated RMSD Results in Study 2.2

$L$	Method	Neuroticism	Extraversion	Openness	Agreeableness	Conscientiousness	Total
10	IISNC	0.3081	0.3249	0.3177	0.3257	0.3242	0.3201
	(Q)IISNC	0.3293	0.3139	0.3209	0.2833	0.2844	0.3063
	MCAT	0.3279	0.3349	0.3041	0.2823	0.2572	0.3013
20	IISNC	0.2845	0.2900	0.2839	0.3002	0.3059	0.2929
	(Q)IISNC	0.2753	0.2648	0.2695	0.2440	0.2331	0.2573
	MCAT	0.2561	0.2720	0.2597	0.2512	0.2298	0.2538
30	IISNC	0.2603	0.2815	0.2707	0.2953	0.2864	0.2788
	(Q)IISNC	0.2446	0.2345	0.2517	0.2221	0.2156	0.2337
	MCAT	0.2340	0.2574	0.2456	0.2117	0.2099	0.2317
40	IISNC	0.2507	0.2731	0.2584	0.2825	0.2764	0.2682
	(Q)IISNC	0.2129	0.2196	0.2271	0.2077	0.2042	0.2143
	MCAT	0.2171	0.2436	0.2393	0.1999	0.1910	0.2182
50	IISNC	0.2558	0.2665	0.2489	0.2785	0.2761	0.2651
	(Q)IISNC	0.2079	0.2095	0.2048	0.1947	0.1941	0.2022
	MCAT	0.2109	0.2205	0.2288	0.1908	0.1819	0.2066
60	IISNC	0.2452	0.2569	0.2431	0.2672	0.2697	0.2564
	(Q)IISNC	0.1977	0.1986	0.2033	0.1790	0.1813	0.1920
	MCAT	0.2021	0.2094	0.2164	0.1822	0.1759	0.1972

Note. RMSD = root mean squared deviation; ISSNC = iterative item selection of neighborhood clusters; MCAT = multidimensional computer adaptive testing.

In Study 2.1, IISNC outperformed the “random” and “correlate” schemes in terms of RMSD when the test length was less than 60, and this advantage was more obvious when the test was shorter. Because the scores are calculated based on the average response of the corresponding items, the RMSDs of the “random” and “correlate” schemes will be infinitely close to 0 as the test length increases, so this result is expected. One interesting finding is that item selection based on correlation is actually not as effective as random selection. Although this is limited to the special case of the NEO PI-R, psychologists may still need to be more careful when using correlation indicators.

In Study 2.2, MCAT was found to produce more accurate overall estimates compared to IISNC, and this difference increased slightly as the length of the test grew. Conscientiousness had the most precise estimates in both MCAT and (Q)IISNC, while Extraversion registered the least accurate estimates. IISNC’s estimates for all five traits were relatively average, likely due to its simultaneous estimation of all traits, whereas MCAT and (Q)IISNC estimated traits separately. Although the results of (Q)IISNC were inferior to those of MCAT when the questionnaire length was 10, 20, and 30 and the opposite when the questionnaire length was 40, 50, and 60, the differences were not significant. Moreover, (Q)IISNC displayed a more balanced distribution of item exposure at comparable RMSD levels. Figures 3 illustrates the exposure rate of items for all 857 experiments in Study 2.2 when the test length $L = 50$ .

Discussion

In the present article, a new algorithm, IISNC, is proposed to solve the item selection and the $θ$ estimation problems in CAT. The most important feature of IISNC is its nonparametric nature (no IRT dependence). The author showed the performance of the IISNC algorithm using RMSD metrics in simulation and empirical studies and compared them with those of the traditional MCAT method and random item selection. Two studies have demonstrated the effectiveness of the IISNC algorithm, with Simulation studies highlighting its unique advantages in smaller item banks. Empirical studies provide further evidence of IISNC’s superior overall performance when compared with both parametric and nonparametric methods using real data.

Simulation Study

The RMSD Over Scores

Figures 4 and 5 summarize the changes in RMSD results with the range of first ability scores on the IISNC and MCAT for all 100 simulated experiments in Study 1 when the number of items $p = 10$ and $20$ . The “Results” section includes a comparison of the two methods and will not be repeated here. The MCAT yields more accurate estimates for subjects with intermediate scores, but performs poorly for high and low scoring subjects, in a pattern similar to segmental monotonicity. The IISNC is more intricate, and although it also provides poor estimates for those with high and low scores, it is more responsive to extreme scores. While not the most accurate for median scores, the IISNC shows low RMSD levels for a range of intermediate scores, with the lowest values at the end of that range.

The MCAT can be reasonably interpreted based on the IRT model design and the standard normality assumptions for ability scores. Meanwhile, the IISNC algorithm’s performance might be explained by the spatial distribution of neighbors: It calculates a subject’s ability score by averaging the scores of their neighbors, whose quality determines accuracy. The simulated experiments assumed a standard normal distribution of subjects’ ability scores, with high and low scoring subjects being rare. Thus, the IISNC struggled to estimate subjects with extreme scores due to the small number of available neighbors. For subjects with intermediate scores, however, there were enough neighborhood samples to obtain consistent estimates regardless of specific score levels. The (Q)IISNC results also support this interpretation, as shown in Figure 6, which summarizes the changes in RMSD results for both (Q)IISNC and (C)MCAT across the range of first ability scores in all 100 simulated experiments of Study 1 when $p = 30$ . It demonstrates that (C)MCAT still produces worse estimates at the extreme scores but performs better in the intermediate scores. Conversely, (Q)IISNC exhibits relatively consistent performance throughout the entire score range. Since (Q)IISNC searches for neighbors on a one-dimensional score space while IISNC is on two dimensions, the former provides a more adequate sample of neighbors for each subject. This argument will be discussed again when looking at the empirical results. In conclusion, the IISNC-based scheme offers greater stability in cross-score estimation.

Item Selection Differences

Table 4 illustrates the item selection process of the MCAT and the IISNC algorithm for 20 subjects in a randomly selected simulation experiment from Study 1, where $p = 20$ . Both algorithms demonstrate stability in their selection of items for the initial few choices, after which more personalized items are selected. However, the MCAT displays greater stability than the IISNC, with no variance in the results of the first two item selections for different subjects. In the first five item selections, the MCAT covers only 10 items compared with IISNC’s selection of 18 items. As previously mentioned in the results section, differences between the two methods’ item exposure are noticed. Table 4 clearly demonstrates the high level of agreement between both methods regarding the appraisal of high-information items. Both algorithms begin with these items, gradually selecting items specific to the subject’s abilities, with IISNC introducing personalized items slightly earlier, resulting in a greater variety of selected items. The IISNC algorithm seeks out the items that effectively distinguish the performance of subjects in their respective neighborhood groups and updates these groups based on their responses to those items. This approach is highly greedy, as such algorithms tend to produce immediate gains but can be less accurate when estimating long-term trends. As a result, IISNC performs well with small item banks and miniature CATs, but is less effective as the number of items increases.

Table 4

Example Presentation on Item Selection Details in Study 1 When $p = 20$

S/N	Item number selected in sequence by MCAT										Item number selected in sequence by IISNC
1	1	12	11	6	8	20	10	9	15	17	1	17	14	9	19	15	16	13	20	12
2	1	12	11	8	20	10	5	16	17	13	1	15	8	19	10	3	5	4	13	17
3	1	12	11	6	8	20	10	16	9	17	12	8	17	9	16	10	14	13	15	20
4	1	12	6	20	9	15	8	10	19	13	1	12	9	20	2	15	4	6	14	19
5	1	12	11	6	16	9	17	20	8	13	1	12	14	19	9	17	10	6	11	16
6	1	12	11	6	16	8	10	17	13	9	12	8	14	17	2	9	16	15	6	1
7	1	12	11	6	16	8	10	17	13	9	1	17	19	9	16	13	14	15	10	3
8	1	12	11	6	20	9	16	17	8	13	1	17	12	13	9	10	20	15	4	16
9	1	12	20	8	10	5	11	15	3	13	12	1	5	4	8	20	15	9	14	2
10	1	12	11	6	16	8	10	17	20	9	1	12	14	19	13	17	16	9	20	8
11	1	12	6	20	8	10	9	15	19	3	12	1	9	19	4	3	20	6	15	8
12	1	12	11	8	5	20	10	15	3	13	12	8	10	19	20	1	7	5	17	3
13	1	12	11	8	20	10	16	5	17	15	17	1	5	3	8	10	20	9	2	11
14	1	12	6	20	8	10	11	9	15	13	1	17	12	20	9	14	19	15	4	6
15	1	12	11	6	20	9	16	17	15	13	12	8	17	13	9	15	19	20	14	6
16	1	12	6	20	8	10	11	9	15	17	1	12	9	20	19	13	17	15	14	16
17	1	12	11	6	16	8	10	17	13	9	14	1	12	19	9	7	17	15	20	13
18	1	12	20	8	5	10	3	15	7	19	12	1	5	10	20	3	15	7	13	8
19	1	12	11	6	8	20	10	16	17	9	1	12	14	17	2	19	10	15	16	9
20	1	12	11	8	5	20	16	10	3	17	1	15	10	19	5	17	3	12	13	14

Note. MCAT = multidimensional computer adaptive testing; ISSNC = iterative item selection of neighborhood clusters.

Empirical Studies

Content Coverage

Table 5 provides a summary of the number of items selected by IISNC in Study 2.1 that cover items corresponding to each trait, where the notations min, max, and mean represent the minimum, maximum, and average number of items covering the specified trait in all 857 validation experiments, respectively. On average, there was an uneven distribution of items across the five traits in IISNC. Specifically, there were more items corresponding to neuroticism and openness and fewer items corresponding to agreeableness and conscientiousness. The RMSD results shown in Table 2 confirm this finding. For the IISNC method, the more items selected on average, the better the results of the trait RMSD. Nevertheless, for each trait, the RMSDs were at the same level and did not differ significantly. In the “random” and “correlate” schemes, an equal number of items were selected for each trait, so the opposite results were obtained, with the best RMSD results for agreeableness and conscientiousness. One possible explanation is that IISNC focuses equally on the estimated effects of the five traits (Euclidean distance between score vectors), but the number of items required for the estimation of each trait is not the same, so the average number of items differs significantly despite the close RMSD results. The “random” and “correlate” schemes, in which the number of items for each trait is specified, confirm this conjecture in the opposite direction.

Table 5

Cross-Validated Item Selection Content Coverage in Study 2.1

$l_{t}$		10	20	30	40	50	60
Neuroticism	min	1	1	1	1	2	4
	mean	2.8331	5.1179	7.2649	9.7888	11.8250	13.9802
	max	6	12	18	21	24	29
Extraversion	min	0	0	1	3	3	5
	mean	2.2485	4.5158	7.0035	9.1727	11.4364	13.8530
	max	6	10	13	19	22	27
Openness	min	1	1	2	4	5	5
	mean	2.8075	5.7001	8.2882	10.8226	13.5321	16.0782
	max	6	11	17	24	25	27
Agreeableness	min	0	0	0	0	0	0
	mean	0.6884	1.6768	2.7608	3.8425	5.1120	6.3221
	max	4	6	8	11	13	17
Conscientiousness	min	0	0	0	1	2	2
	mean	1.4224	2.9895	4.6826	6.3734	8.0945	9.7666
	max	5	11	13	17	21	23

Although the number of items selected for each trait varies on average, the number of items selected for each validation experiment is still adaptive. One possible concern in IISNC is that there is no guarantee that all traits will be included in the final CAT for any given examinee. While this does not happen very often, it does happen. In a certain number of validation experiments, for some traits, there were no corresponding items selected. While this is a serious problem for traditional item selection or IRT-based CAT, it is not the case for the proposed IISNC, which stems from the difference in the underlying design logic of the algorithm. In IRT-based CAT, the item parameters of the selected items are used to estimate the subjects’ abilities. Thus, if no items corresponding to a trait are selected, the estimation error for that trait will be large. This design idea focuses on the items in the item bank. In contrast, the selected items are used to find the neighbors of the target subjects in IISNC. If the target subject’s neighbors can be found accurately, it will no longer matter whether the selected items cover all trait dimensions. This design idea focuses on the subjects in the item bank. The author took an IISNC experiment in Study 2.1, where items were selected that did not correspond to agreeableness, as an example. Twenty-three individuals were obtained as the neighborhood of the target subject. The standard deviation and extreme deviation of the five trait scores of these 23 individuals were [0.4913, 0.3739, 0.4643, 0.3834, 0.3560] and [2.0625, 1.4792, 1.75, 1.6875, 1.4583], respectively, and the estimated errors were [0.1513, 0.5236, 0.5697, 0.0670, 0.1812] (the order is neuroticism, extraversion, openness, agreeableness, and conscientiousness, respectively). Although items corresponding to agreeableness were not selected, the variability of neighborhood scores was not significantly higher than that of other traits. However, agreeableness is the best estimated trait in this example.

If readers still have concerns, IISNC can be applied using a method similar to (Q)IISNC, which was introduced in Study 1 and 2.2, in combination with the information from the Q-matrix. It is also possible to not use the Q-matrix information. IISNC can be simply used for each trait measurement (item selection among all items), and for each trait, we can specify the number of items we want to set.

Neighborhood and Trait Spaces

For Study 2.2, Table 3 shows that MCAT outperforms IISNC for most test lengths. The author would like to further explore the reasons for this result. Figure 7 shows a summary of the changes in the RMSD results based on the range of scores of openness for all 857 experiments in Study 2.2 when the test length $L = 50$ .

The poor effect of IISNC when the score value of openness is small is the direct cause of the larger overall RMSD. However, in Study 2.2, the IISNC estimate of openness was in the range 1.6233 to 2.9613. Therefore, it is clearly impossible to obtain a good estimate of score values beyond this range. The estimation of IISNC is the average of the scores within a neighborhood group, and only the range covered by the values of the group scores can be output. Only 111 subjects were out of the range of 1.6233 to 2.9613 in the item bank (score of openness ranged from 1.0625 to 3.625). Because IISNC relies more on the representativeness of the subjects in the item bank, the fact that there are not a sufficient number of samples of subjects for large ranges of scores is the cause of the poor performance of IISNC in Study 2.2.

However, for (Q)IISNC, this problem is well mitigated. A reasonable explanation is that (Q)IISNC estimates openness without considering the other four traits, and it can fully utilize the 111 subjects as neighbors to estimate the score of openness. IISNC needs to consider whether the same neighborhood can be used to estimate the other four traits at the same time while estimating openness. IISNC deals with problems in a five-dimensional space, while (Q)IISNC is one-dimensional, which is common in machine learning problems where high dimensionality brings high data sparsity.

This does not mean that IISNC is no longer a valid approach when the trait dimension is high. The ability density in the item bank needs to be considered as well. One piece of evidence for this is when the score of openness is roughly lager than 3. Subjects within this range are better estimated using IISNC than (Q)IISNC, as shown in Figure 7. If the score of openness is restricted to the range (1.5, 3), the number of subjects satisfying the condition is 772, subjects within this range are the densest, and the RMSD of IISNC (0.1979) is less than that of MCAT (0.2255). A reasonable explanation is that compared with the (Q)IISNC and MCAT approaches, IISNC integrates the information of five traits. Although the five traits are generally independent of each other, this is not always the case within a small neighborhood.

Future Directions and Conclusion

Future research should focus on the following five aspects. First, the proposed IISNC method only terminates based on a fixed test length. A termination strategy based on convergence judgment should be developed. There is no estimation of the ability value $θ$ in IISNC, but the convergence judgment based on the change in the test taker’s neighbors can be considered. Second, the selection of the hyperparameter final neighbor group size $l$ in the current IISNC method is based entirely on experience. It should at least be related to the sample size in the item bank. There should be more discussion of the impact of the $l$ value and the way to obtain it. Third, a more comprehensive simulation study is needed to examine the strengths and weaknesses of IISNC, considering other factors that may affect detection, such as the distribution of ability values and item parameters. Fourth, to use IISNC on more psychological questionnaires to build the CAT method is needed for research. The broad applicability of IISNC should be validated better. Fifth, missing data is an important problem when constructing a CAT item bank. In the empirical studies, a random fill solution was used. This treatment is effective for a small number of missing data, but how to apply IISNC to high rates of missing data scenarios is a valuable problem for us to solve.

The simulation studies described above demonstrate the validity of item selection in the proposed IISNC. When generating miniature CAT based on small item banks, lower RMSD values were obtained using IISNC, outperforming MCAT. In addition, a faster calculation speed was obtained using IISNC. The empirical study demonstrated that IISNC can be applied to the CAT of the NEO PI-R personality test while maintaining excellent trait estimation. In particular, IISNC does not rely on the information of the Q-matrix. Conversely, the IISNC algorithm has a greater advantage in estimation accuracy if the information of the Q-matrix is used. As a result, considering the IRT-free dependency and the universal implementability of IISNC, it has great potential for performing CAT in a wide range of aptitude tests and psychological questionnaires.

Footnotes

Declaration of Conflicting Interests

The author declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Yongze XU

References

Birnbaum

A. L.

(1968). Some latent trait models and their use in inferring an examinee’s ability. In Lord

F. M.

Novick

M. R.

(Eds.), Statistical theories of mental test scores (pp. 397–479). Addison-Wesley.

Costa

P. T.

Jr. McCrae

R. R.

(1992). Revised NEO Personality Inventory (NEO-PI-R) and NEO Five-Factor Inventory (NEO-FFI) professional manual. Odessa, FL: Psychological Assessment Resources.

Falk

C. F.

Cai

(2016). Maximum marginal likelihood estimation of a monotonic polynomial generalized partial credit model with applications to multiple group analysis. Psychometrika, 81(2), 434–460.

Falk

C. F.

Feuerstahler

L. M.

(2022). On the performance of semi-and nonparametric item response functions in computer adaptive tests. Educational and Psychological Measurement, 82(1), 57–75.

Farooq

(2018). How to design and frame a questionnaire. In Jeyasekar

J. J.

Saravanan

(Eds.), Innovations in measuring and evaluating scientific information (pp. 50–60). IGI Global.

Fliege

Becker

Walter

O. B.

Bjorner

J. B.

Klapp

B. F.

Rose

(2005). Development of a Computer-Adaptive Test for Depression (D-CAT). Quality of Life Research, 14(10), 2277–2291.

Gibson

A. M.

Bowling

N. A.

(2020). The effects of questionnaire length and behavioral consequences on careless responding. European Journal of Psychological Assessment, 36(2), 410–420.

Goldberg

(2018). (3) NEO-PI-R, https://doi.org/10.7910/DVN/HE6LJR, Harvard Dataverse, V1, UNF:6:Sh2iB6vpAPrVxkaoewIqrg== [fileUNF]

Makransky

Mortensen

E. L.

Glas

C. A.

(2013). Improving personality facet scores with multidimensional computer adaptive testing: An illustration with the NEO PI-R. Assessment, 20(1), 3–13.

10.

Meijer

R. R.

Nering

M. L.

(1999). Computerized adaptive testing: Overview and introduction. Applied Psychological Measurement, 23(3), 187–194.

11.

Muraki

(1992). A generalized partial credit model: Application of an em algorithm. ETS Research Report Series, 1992(1), i–30.

12.

Petersen

M. A.

Aaronson

N. K.

Arraras

J. I.

Chie

W.-C.

Conroy

Costantini

Dirven

Fayers

Gamper

E.-M.

Giesinger

J. M.

Habets

E. J.

Hammerlid

Helbostad

Hjermstad

M. J.

Holzner

Johnson

Kemmler

King

M. T.

Kaasa

Groenvold

(2018). The EORTC CAT Core—The computer adaptive version of the EORTC QLQ-C30 questionnaire. European Journal of Cancer, 100, 8–16.

13.

Douglas

(2006). Computerized adaptive testing under nonparametric IRT models. Psychometrika, 71(1), 121–137.

S/N	Item number selected in sequence by MCAT										Item number selected in sequence by IISNC
1	1	12	11	6	8	20	10	9	15	17	1	17	14	9	19	15	16	13	20	12
2	1	12	11	8	20	10	5	16	17	13	1	15	8	19	10	3	5	4	13	17
3	1	12	11	6	8	20	10	16	9	17	12	8	17	9	16	10	14	13	15	20
4	1	12	6	20	9	15	8	10	19	13	1	12	9	20	2	15	4	6	14	19
5	1	12	11	6	16	9	17	20	8	13	1	12	14	19	9	17	10	6	11	16
6	1	12	11	6	16	8	10	17	13	9	12	8	14	17	2	9	16	15	6	1
7	1	12	11	6	16	8	10	17	13	9	1	17	19	9	16	13	14	15	10	3
8	1	12	11	6	20	9	16	17	8	13	1	17	12	13	9	10	20	15	4	16
9	1	12	20	8	10	5	11	15	3	13	12	1	5	4	8	20	15	9	14	2
10	1	12	11	6	16	8	10	17	20	9	1	12	14	19	13	17	16	9	20	8
11	1	12	6	20	8	10	9	15	19	3	12	1	9	19	4	3	20	6	15	8
12	1	12	11	8	5	20	10	15	3	13	12	8	10	19	20	1	7	5	17	3
13	1	12	11	8	20	10	16	5	17	15	17	1	5	3	8	10	20	9	2	11
14	1	12	6	20	8	10	11	9	15	13	1	17	12	20	9	14	19	15	4	6
15	1	12	11	6	20	9	16	17	15	13	12	8	17	13	9	15	19	20	14	6
16	1	12	6	20	8	10	11	9	15	17	1	12	9	20	19	13	17	15	14	16
17	1	12	11	6	16	8	10	17	13	9	14	1	12	19	9	7	17	15	20	13
18	1	12	20	8	5	10	3	15	7	19	12	1	5	10	20	3	15	7	13	8
19	1	12	11	6	8	20	10	16	17	9	1	12	14	17	2	19	10	15	16	9
20	1	12	11	8	5	20	16	10	3	17	1	15	10	19	5	17	3	12	13	14

S/N	Item number selected in sequence by MCAT										Item number selected in sequence by IISNC
1	1	12	11	6	8	20	10	9	15	17	1	17	14	9	19	15	16	13	20	12
2	1	12	11	8	20	10	5	16	17	13	1	15	8	19	10	3	5	4	13	17
3	1	12	11	6	8	20	10	16	9	17	12	8	17	9	16	10	14	13	15	20
4	1	12	6	20	9	15	8	10	19	13	1	12	9	20	2	15	4	6	14	19
5	1	12	11	6	16	9	17	20	8	13	1	12	14	19	9	17	10	6	11	16
6	1	12	11	6	16	8	10	17	13	9	12	8	14	17	2	9	16	15	6	1
7	1	12	11	6	16	8	10	17	13	9	1	17	19	9	16	13	14	15	10	3
8	1	12	11	6	20	9	16	17	8	13	1	17	12	13	9	10	20	15	4	16
9	1	12	20	8	10	5	11	15	3	13	12	1	5	4	8	20	15	9	14	2
10	1	12	11	6	16	8	10	17	20	9	1	12	14	19	13	17	16	9	20	8
11	1	12	6	20	8	10	9	15	19	3	12	1	9	19	4	3	20	6	15	8
12	1	12	11	8	5	20	10	15	3	13	12	8	10	19	20	1	7	5	17	3
13	1	12	11	8	20	10	16	5	17	15	17	1	5	3	8	10	20	9	2	11
14	1	12	6	20	8	10	11	9	15	13	1	17	12	20	9	14	19	15	4	6
15	1	12	11	6	20	9	16	17	15	13	12	8	17	13	9	15	19	20	14	6
16	1	12	6	20	8	10	11	9	15	17	1	12	9	20	19	13	17	15	14	16
17	1	12	11	6	16	8	10	17	13	9	14	1	12	19	9	7	17	15	20	13
18	1	12	20	8	5	10	3	15	7	19	12	1	5	10	20	3	15	7	13	8
19	1	12	11	6	8	20	10	16	17	9	1	12	14	17	2	19	10	15	16	9
20	1	12	11	8	5	20	16	10	3	17	1	15	10	19	5	17	3	12	13	14

S/N	Item number selected in sequence by MCAT										Item number selected in sequence by IISNC
1	1	12	11	6	8	20	10	9	15	17	1	17	14	9	19	15	16	13	20	12
2	1	12	11	8	20	10	5	16	17	13	1	15	8	19	10	3	5	4	13	17
3	1	12	11	6	8	20	10	16	9	17	12	8	17	9	16	10	14	13	15	20
4	1	12	6	20	9	15	8	10	19	13	1	12	9	20	2	15	4	6	14	19
5	1	12	11	6	16	9	17	20	8	13	1	12	14	19	9	17	10	6	11	16
6	1	12	11	6	16	8	10	17	13	9	12	8	14	17	2	9	16	15	6	1
7	1	12	11	6	16	8	10	17	13	9	1	17	19	9	16	13	14	15	10	3
8	1	12	11	6	20	9	16	17	8	13	1	17	12	13	9	10	20	15	4	16
9	1	12	20	8	10	5	11	15	3	13	12	1	5	4	8	20	15	9	14	2
10	1	12	11	6	16	8	10	17	20	9	1	12	14	19	13	17	16	9	20	8
11	1	12	6	20	8	10	9	15	19	3	12	1	9	19	4	3	20	6	15	8
12	1	12	11	8	5	20	10	15	3	13	12	8	10	19	20	1	7	5	17	3
13	1	12	11	8	20	10	16	5	17	15	17	1	5	3	8	10	20	9	2	11
14	1	12	6	20	8	10	11	9	15	13	1	17	12	20	9	14	19	15	4	6
15	1	12	11	6	20	9	16	17	15	13	12	8	17	13	9	15	19	20	14	6
16	1	12	6	20	8	10	11	9	15	17	1	12	9	20	19	13	17	15	14	16
17	1	12	11	6	16	8	10	17	13	9	14	1	12	19	9	7	17	15	20	13
18	1	12	20	8	5	10	3	15	7	19	12	1	5	10	20	3	15	7	13	8
19	1	12	11	6	8	20	10	16	17	9	1	12	14	17	2	19	10	15	16	9
20	1	12	11	8	5	20	16	10	3	17	1	15	10	19	5	17	3	12	13	14