--- title: "kstMatrix" author: "Cord Hockemeyer" date: "Version 3.0-0" output: rmarkdown::html_vignette vignette: > %\VignetteIndexEntry{kstMatrix} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- ```{r setup, include = FALSE} knitr::opts_chunk$set( collapse = TRUE, comment = "#>" ) library(kstMatrix) library(grDevices) library(sets) library(pks) library(Rgraphviz) ``` # Content - [Introduction](#introduction) - [S3 classes in `kstMatrix`](#s3-classes-in-kstmatrix) - [Constructors](#constructors) - [Different representations for knowledge spaces](#different-representations-for-knowledge-spaces) - [Working with knowledge structures](#working-with-knowledge-structures) - [Creating trivial knowledge spaces](#creating-trivial-knowledge-spaces) - [Determining variants](#determining-variants) - [Closure operatorsa](#closure-operators) - [Dealing with equivalent items](#dealing-with-equivalent-items) - [Combining knowledge structures](#combining-knowledge-structures) - [Reducing and expanding structures](#reducing-and-expanding-structures) - [Working with data](#working-with-data) - [Simulating response patterns](#simulating-response-patterns) - [Generating knowledge structures from data](#generating-knowledge-structures-from-data) - [Validating knowledge structures](#validating-knowledge-structures) - [Assessment](#assessment) - [Fringes and learning paths](#fringes-and-learning-paths) - [Plotting and pretty-printing](#plotting-and-pretty-printing) - [Creating color vectors](#creating-color-vectors) - [Pretty-printing](#pretty-printing) - [Utilities](#utilities) - [Datasets provided by `kstMatrix`](#datasets-provided-by-kstmatrix) - [Empirical structures](#empirical-structures) - [Example structures](#example-structures) - [Removed and obsoleted functions and methods](#removed-and-obsoleted-functions-and-methods) - [References](#references) # Introduction Knowledge space theory applies prerequisite relationships between items of knowledge within a given domain for efficient adaptive assessment and training (Doignon & Falmagne, 1999). The `kstMatrix` package implements some basic functions for working with knowledge space. Furthermore, it provides several empirically obtained knowledge spaces in form of their bases. There is a certain overlap in functionality between the `kst`and `kstMatrix` packages, however the former uses a set representation and the latter a matrix representation. The packages are to be seen as complementary, not as a replacement for each other. This document gives a short overview on the `kstMatrix` package. For more details on the specific functions, please have a look at the manual. Subsequently, we start with a introduction into the S3 classes used in `kstMatrix`. Afterwards, the various functions are presented groupd by topic. # S3 classes in `kstMatrix` With version 2, S3 classes were introduced in `kstMatrix` most of which are in some hierarchy. A short explanation of the various classes: - `kmdata`: A matrix of response patterns. These may be either empirical or simulated. - `kmfamset`: A family of sets, i.e. of knowledge states. Due to the set character, any row may occur only once. - `kmbasis`: Basis of a knowledge space; sub-class of `kmfamset`. - `kmstructure`: Knowledge structure; a `kmfamset` which contains teh empty set and the full item set as states. - `kmspace`: Knowledge space; a `kmstructure` which is closed under union. - `kmqspace`: Quasi-ordinal knowledge space; a `kmspace` which is additionally closed under intersection. - `kmneidghbourhood`: The neighbourhood of an individual knowledge state; sub-class of `kmfamset`. - `kmattributionrelation`: Incidence matrix of an attribution relation; please note that here the rows contain the minimal states. - `kmsurmiserelation`: Closure of a `kmattributionrelation` under reflexivity and transitivity. - `kmattributionfunction`: Data frame describing an attribution function. - `kmsurmisefunction`: Closure of a `kmattributionfunction` under extended reflexivity, transitivity, and incomparability. The following classes are isolated from the general class hierarchy. - `kmlearningpath`: A list of printed knowledge states building a gradation. - `kmlearningpaths`: A list of `kmlearningpath` objects. - `kmlearningpathmatrix`: A matrix whose rows describe the states within a gradation. Technically also a family of sets. - `kmlearningpathmatrices`: A list of `kmlearningpathmatrix` objects. Figure 1 shows the dependencies between the former group of classes, e.g., `kmspace` being a sub-class of `kmstructure`. Besides the `kstMatrix` classes in blue, also the underlying standard `R` classes are shown in green. ```{r classes, fig.cap = 'Figure 1: kstMatrix object classes', echo = FALSE, fig.align = 'center', cache=FALSE, out.width='95%'} knitr::include_graphics("kstMatrix-Classes.png") ``` ## Constructors There exist several constructors - `kmfamset()` - `kmstructure()` - `kmbasis()` - `kmspace()` - `kmqspace()` which create the respective objects from various KST objects. # Different representations for knowledge spaces There exist various ways to represent knowledge spaces: the whole space itself, its basis, and the corresponding surmise function; in case of quasi--ordinal spaces also the surmise relation. The subsequent functions allow to map between these representations. ## `kmbasis()` The `kmbasis()` S3 method allows to map different representations to bases. There are implementations for the classes `kmsurmiserelation`, `kmsurmisefunction`, and `matrix`, the latter aiming at `kmfamset`s including `kmstructure`s and `kmspace`s. ## `kmspace()` Beyond being regarded as constructors, certain `kmspace()` S3 methods include mappings betwen different representations of knowledge structures. ## `kmsurmisefunction()` This function takes an arbitrary `kmfamset` (family of sets) and determines the surmise function of the smallest knowledge space containing this family of sets, i.e. its closure under union. ## `kmsurmiserelation()` This function determines the surmise relation for a quasi--ordinal knowledge space. If the parameter is an arbitrary `kmfamset`, the result is the surmise relation for the smallest quasi--ordinal knowledge space containing the family of sets, i.e. its closure under union *and* intersection. # Working with knowledge structures ## Creating trivial knowledge spaces For a given item number, there are two trivial knowledge spaces, the maximal knowledge space representing absolutely no prerequisite relationships (the knowledge space is the power set of the item set and the basis matrix is the diagonal matrix), and the minimal knowledge space representing equivalence of all items (the knowledge space contains just the empty set and the full item set, and the basis matrix contains one line full of '1's). These spaces can be generated with `kmmaximalspace()` and `kmminimalspace()`, respectively. Both functions generate the whole space, not the basis. ## Determining variants ### Closure Operators Several functions provide closures for respective data. - `kmclosure()` is the closure method providing closures - from an attribution relation (i.e. an arbitrary binary relation on the set of items) to a surmise relation, and - from an attribution function to a surmise function. - `kmunionclosure()` closes a family of sets under union, i.e. it determines the corresponding knowledge space. `kmspace()` does the same. - `kmqspace()` close an arbitrary family of sets to a quasi--ordinal knowledge space. `kmintersectionclosure()` does the same restricted to `kmspace` objects. ### Dealing with equivalent items `kmnotions()` determines classes of equivalent items, `kmeqreduction()` reduces a family of states to a notion-free subset of items. `kmrefinenotion()` dissolves notions by specifying a structure within the notion. Each basis element containing the notion is replaced by a family of states structured by a second basis on the equivalent items. ### Combining knowledge structures `kmunion()` computes the "union" of knowledge structures, surmise relations, or surmise functions. `kmintersection()` analogously computes their "intersection". Both functions return an object of the same type. Please keep in mind that a union of knowledge spaces corresponds to an intersection of the respective surmise relations or surmise functions and vice versa. `kmmesh()` determines the maximal mesh of two knowledge structures. ### Reducing and expanding structures `kmsubstructure()` reduces knowledge structure representations to a subset of items. It is an S3 method applicable for data, bases, structures, spaces, surmise relations, and surmise functions. The result is of the same object class as the original, i.e. the respective properties are checked/enforced. `kmexpand()`does the opposite: it expands an attribution function to a superset of items and closes it to a surmise function. The additional items are independent, i.e. they neither have nor are prerequisites. # Working with data ## Simulating response patterns Response patterns are simulated by `kmsimulate()` applying the BLIM (Basic Local Independence Model). It assumes identical $\beta$ and $\eta$ values for all items. More elaborated functions may follow. ## Generating knowledge structures from data `kmgenerate()` offers a trivial, straightforward approach to generating knowledge structures from data: any response pattern with an observed frequency beyond a given threshold is taken as a knowledge state. Furthermore, there exists the `kmiita2SR()` function linking to the `DAKS` package. It determines the surmise relation (in `kstMatrix` data representation form) from an `iita` object generated with the `DAKS` functions. ## Validating knowledge structures There exist two core functions for validation. `kmvalidate()` determines validity indices based on the states in the knowledge structure, and `kmSRvalidate()`determines indices based on the surmise relation of a quasi--ordinal knowledge space. Furthermore, there is a helper function `kmdist()` which returns a distance distribution. # Assessment There exist several functions in the assessment context. They are all based on a paper by Falmagne & Doignon (1988, see also Doignon & Falmagne, 1999, Chapter 10). The core functiuon is `kmassess()`. It does a complete assessmednt for a given response vector and a given knowledge structure. A simplified version is `kmsassess()` where the originally item-specific parameters are identical for all items. Both these functions rely on alternative question and update rules realised by `kmassesshalfsplit()` and `kmassessinfomrative()` and by `kmassessbayesian()` and `kmassessmultipöicatiuve()`, respectively. The separation of these functions allows also for a use in an interactive system, e.g., a Shiny app. Finally, there is `kmassessmentsimulation()` which does assessments for a whole dataset of response patterns and produces a table which can then be further evaluated statistically. # Fringes and Learning Paths Well-graded learning paths are an important concept in knowledge space theory. With `kmlearningpaths()`, we obtain a collection of all learning paths in a knowledge structure, with `kmgradations()` a collection of all gradations between two states in a structure. In this context also `kmiswellgraded()` should be mentioned which tests if a structure is well-graded. In this context, we may also need fringes and neighbourhoods. The former can be determined with `kmfringe()`, `kminnerfringe()`, and `kmouterfringe()`. For the latter, there are the functions `kmneighbourhood()` (determining the 1-neighbourhood of a state) and `kmnneighbourhood()` (determining an arbitrary n-neighbourhood). There exists also an alternative implementation with the functions `kmbasisfringe()`, `kmbasisinnerfringe()`, and `kmbasisouterfringe()`, as well as `kmbasisneighbourhood()`. These functions work on the basis of a knowledge space and may, thus, be faster, especially for large knowledge spaces (see Hockemeyer, 1997). Please note that, as a consequence of using the basis, these functions do not apply for general knowledge structures but only for knowledge spaces. Furthermore, due to complexity, there is no `kmbasisnneighbourhood()`(yet). # Plotting and pretty-printing With version 2.0 of `kstMatrix`, plotting functionality is provided through the S3 `plot` method. The method is available for the `kmfamset`, `kmsurmiserelation`, and `kmneighbourhood` classes. ```{r, eval=FALSE} plot(xpl$space) plot(xpl$sr) ``` ```{r, fig.cap = 'Figure 2: Example space', echo = FALSE, fig.align = 'center', cache=FALSE, out.width='450'} knitr::include_graphics("space.jpeg") ``` ```{r, fig.cap = 'Figure 3: Example surmise relation', echo = FALSE, fig.align = 'center', cache=FALSE, out.width='200'} knitr::include_graphics("SR.jpeg") ``` `plot` uses the `DiagrammeR` package which in turn uses the `Graphviz` software. The default parameters are slightly different for `kmfamset`s and `kmsurmiserelation`s. ```{r, eval=FALSE} plot(xpl$sr, colors="orange", vertexshape="circle") ``` For plotting neighbourhoods, by default three different colors are used. ```{r, eval=FALSE} plot(kmneighbourhood(c(1,1,0,0), xpl$space, include=TRUE), state=c(1,1,0,0), edgelabel=TRUE) ``` ```{r neighbourhood, fig.cap = 'Figure 4: Neighbourhood', echo = FALSE, fig.align = 'center', cache=FALSE, out.width='400'} knitr::include_graphics("neighbourhood.jpeg") ``` Alternatively, one can also plot the whole structure and highlight a certain state and its neighbourhood within the structure. Here, four colors are used. ```{r eval=FALSE} plot(xpl$space, state=c(1,1,0,0)) ``` ```{r neighbourhood_space, fig.cap = 'Figure 5: Neighbourhood within a knowledge space', echo = FALSE, fig.align = 'center', cache=FALSE, out.width='650'} knitr::include_graphics("neighbourhood2.png") ``` By default, Hasse diagrams are drawn vertically with just lines as edges. However, on finds also horizontal diagrams in which case the arrows are set as arrows from left to right. Please note that, for technical reasons, you should specify the `arrowhead` for horizontal but the `arrowtail` for vertical Hasse diagrams if you want arrows instead of plain lines. ```{r, eval=FALSE} plot(xpl$space, horizontal=TRUE, arrowtail="open") plot(xpl$space, arrowhead="empty") ``` ```{r horizontal, fig.cap = 'Figure 6: Horizontal Hasse diagram', echo = FALSE, fig.align = 'center', cache=FALSE, out.width='800'} knitr::include_graphics("horizontal.jpeg") ``` ```{r emptyhead, fig.cap = 'Figure 7: Using arrows instead of lines', echo = FALSE, fig.align = 'center', cache=FALSE, out.width='400'} knitr::include_graphics("emptyhead.jpeg") ``` ## Creating color vectors `kmcolors()` creates a colors vector for plot() based on an existing palette. ## Pretty-printing The `kmprettyprinting()` method prints various KST object types in set notation (or similar). ```{r prettyprinting} kmprettyprint(xpl$basis) kmprettyprint(xpl$basis, simplified=TRUE) kmprettyprint(xpl$sr,tuple=FALSE) cat(kmprettyprint(kmlearningpaths(xpl$space))) ``` # Utilities This group contains several smaller helper functions. - `binarymatrixproduct()` computes the Boolean multiplaction of two binary matrices. - `kmsymmsetdiff()`: Determine the symmetric set difference between two sets. - `kmsetdistance()`: Determine the cardinality of the symmetric set difference - `kmsetiselement()`: Test if an item is element of a state/set - `kmminimalfamset()`: Determine the minimal states within a `kmfamset` - `kmdoubleequal()`: Test if two doubles are (almost) equal thus avoiding rounding problems with the '==' operator - [`kmcolors()`](#sec:creating-color-vectors): Produce a color vector for `plot()` based on existing palettes - [`kmtrivial()`](#sec:creating-trivial-knowledge-spaces): Create a minimal or a maximal knowledge space for a given number of items - `kmheights()`: Determine a table of items and their _heights_ in the knowledge structure/space # Datasets provided by `kstMatrix` ## Empirical structures The provided empirical datasets were obtained by the research group around Cornelia Dowling through querying experts in the respective fields. ### cad Six experts were queried about prerequisite relationships between 28 AutoCAD knowledge items (Dowling, 1991; 1993a). A seventh basis represents those prerequisite relationships on which the majority (4 out of 6) of the experts agree (Dowling & Hockemeyer, 1998). ### fractions Three experts were queried about prerequisite relationships between 77 items on fractions (Baumunk & Dowling, 1997). A fourth basis represents those prerequisite relationships on which the majority of the experts agree (Dowling & Hockemeyer, 1998). ### readwrite Three experts were queried about prerequisite relationships between 48 items on reading and writing abilities (Dowling, 1991; 1993a). A fourth basis represents those prerequisite relationships on which the majority of the experts agree (Dowling & Hockemeyer, 1998). ## Example structures ### phsg A small knowledge space on a set of seven items on linear functions. This example is used in a manuscript by Steiner et al. ### xpl This is just a small fictitious 4-item-example used for the examples in the documentation. Please note that this knowledge space is not quasi--ordinal. # Removed and obsoleted functions and methods With the never-ending addition of new functions and methods, is sometimes becomes necessary to re-structure the interface. ## Removed/renamed functions with `kstMatrix` version 2.0-0 The functions `kmhasse()`, `kmbasisdiagram()`, and `kmSRdiagram()` were moved/renamed into S3 `plot()` methods for the respective object classes. ## Removed functions and methods with `kstMatrix` version 3.0-0 The following functions and methods were removed: - The `kmunionclosure()` methods has been merged into a new `kmclosure()` S3 method which also offers closure methods for attribution relations and attribution functions. - The `kmSF2basis()` and `kmSR2basis()` functions have been removed after their integration into the `kmbasis()` S3 method with the earlier version 2.0-0. # References - Baumunk, K. & Dowling, C. E. (1997). Validity of spaces for assessing knowledge about fractions. _Journal of Mathematical Psychology, 41,_ 99–105. - Doignon, J.-P. & Falmagne, J.-C. (1999). _Knowledge Spaces._ Springer–Verlag, Berlin. - Dowling, C. E. (1991). _Constructing Knowledge Structures from the Judgements of Experts._ Habilitationsschrift, Technische Universität Carolo-Wilhelmina, Braunschweig, Germany. - Dowling, C. E. (1993a). Applying the basis of a knowledge space for controlling the questioning of an expert. _Journal of Mathematical Psychology, 37,_ 21–48. - Dowling, C. E. (1993b). On the irredundant construction of knowledge spaces. Journal of Mathematical Psychology, 37, 49–62. their basis. In Cornelia E. Dowling, Fred S. Roberts, & Peter Theuns, editors, _Recent Progress in Mathematical Psychology,_ pp. 133–141. Lawrence Erlbaum Associates Ltd., Mahwah, NJ. - Falmagne J.-C. & Doignon J.-P. (1988). A class of stochastic procedures for the assessment of knowledge. _British Journal of Mathematical and Statistical Psychology, 41,_ 1–23. - Hockemeyer C (1997). Using the Basis of a Knowledge Space for Determining the Fringe of a Knowledge State. _Journal of Mathematical Psychology, 41,_ 275–279.