L G Bulusheva

V I Sysoev

E V Lobiak

Yu V Fedoseeva
email: fedoseeva@niic.nsc.ru

A A Makarova

M Dubois
email: marc.dubois@univ-bpclermont.fr

E Flahaut
email: flahaut@chimie.ups-tlse.fr

A V Okotrub

Nikolaev

Chlorinated holey double-walled carbon nanotubes for relative humidity sensor

Keywords:

A chemical procedure for modification of double walled carbon nanotubes (DWCNTs) to enhance their response to humidity was developed. The DWCNTs walls were etched by hot concentrated sulfuric acid, after what the edge carbon sites were saturated by chlorine via reaction with CCl 4 vapor. This treatment increases the dispersibility of DWCNTs in solvents, removes oxygen groups, and produces chlorine decorated holes in the outer walls. Networks of chlorinated holey DWCNTs showed a high repeatable response to humid environment and a good reversible behavior after the sensor purging by dry air. The density functional theory calculations predict enhanced polarization of the DWCNTs when they contain chlorine decorated holes in the outer walls and physisorption of H 2 O molecules near chlorine atoms. These two effects are the cause of an intense low noise signal to gaseous H 2 O and easy sensor recovery.

Introduction

In the family of carbon nanotubes (CNTs), double walled CNTs (DWCNTs) occupy a place between single walled CNTs (SWCNTs) and multi walled CNTs (MWCNTs) [START_REF] Kim | Double-walled carbon nanotubes: synthesis, structural characterization, and application[END_REF]. DWCNTs are composed of two coaxial cylindrical walls, and the inter wall interactions have an impact on their electronic structure and properties, like in MWCNTs [START_REF] Moore | Double-walled carbon nanotube processing[END_REF]. At the same time, the outer walls of DWCNTs have diameters close to SWCNTs and hence possess similar chemical reactivity. During a chemical reaction, the outer walls of DWCNTs protects the inner ones so functionalized DWCNTs maintain most of their electrical conductivity [START_REF] Piao | Optical and electrical properties of inner tubes in outer wallselectivity functionalized double-wall carbon nanotubes[END_REF][START_REF] Brozena | Outer wall selectively oxidized, water-soluble double-walled carbon nanotubes[END_REF] and mechanical resistance [START_REF] Kawasaki | Structural properties of pristine and fluorinated Fig. 6. Optimized position of H 2 O molecule at the hole in the (9,9) CNT, decorated by a) hydrogen (white balls) and b) two ketone groups, c) two hydroxyl groups, d) carboxyl group, e) hydroxyl and carboxyl groups, and f) two chlorine atoms (violet balls). The calculated values of the adsorption energy of H 2 O and the NBO charge of H 2 O. The dot lines show the shortest distances between H 2 O and functional groups. (A colour version of this figure can be viewed online.) double-walled carbon nanotubes under high pressure[END_REF]. This gives advantages for the use of DWCNTs in composites [START_REF] Jung | Robust, conducting and transparent polymer composites using surface-modified and individualized double-walled carbon nanotube[END_REF][START_REF] Leon | Spectroscopic study of double-walled carbon nanotube functionalization for preparation of carbon/epoxy composites[END_REF], electrochemical cells [START_REF] Jang | Capacitance response of double-walled carbon nanotubes depending on surface modification[END_REF][START_REF] Pumera | Electrochemical properties of double wall carbon nanotube electrodes[END_REF], biosensors [START_REF] Anik | Double-walled carbon nanotube based carbon paste electrode as xanthine biosensor[END_REF] and gas sensors [START_REF] Rumiche | Development of a fast-response/highsensitivity double wall carbon nanotube nanostructured hydrogen sensor[END_REF].

Humidity sensors are important in industry, medicine, research, and many everyday life applications. Theoretical calculations pre dict a weak interaction of water molecules with a perfect CNT surface [START_REF] Al-Hamdani | How strongly do hydrogen and water molecules stick to carbon nanomaterials?[END_REF]. The adsorbed H 2 O molecule polarizes a SWCNT without any noticeable transfer of electron density between the components [START_REF] Bell | Does water dope carbon nanotubes?[END_REF]. However, changes in the electrical conductivity of CNTs depending on environmental humidity were detected experimentally [START_REF] Lekawa-Raus | Influence of atmospheric water vapour on electrical performance of carbon nanotube fibres[END_REF]. The reason for this is mainly the functionali zation of the CNTs during purification procedures, and the adsorption of water between junctions in the networks of CNTs. Purification of CNTs using mineral acids produces oxygen containing groups, which interact with water via the hydrogen bonds [START_REF] Watts | The importance of oxygen-containing defects on carbon nanotubes for the detection of polar and non-polar vapours through hydrogen bond formation[END_REF]. This may significantly influence the electrical response of CNTs in case they contain a low amount of defects. Actually, the characterization of a network of purified arc produced SWCNTs revealed a crossover from decreasing to increasing conductance versus H 2 O concentration in the surrounding atmosphere [START_REF] Zahab | Water-vapor effect on the electrical conductivity of a single-walled carbon nanotube mat[END_REF]. Interestingly, the DWCNTs did not exhibit such a behavior [START_REF] Tang | Effect of H 2 O adsorption on the electrical transport properties of double-walled carbon nanotubes[END_REF]. A large electrical hysteresis measured for a single DWCNT in wet and dry air was assigned to the inter wall interactions. These in teractions cause p doping of the outer nanotube, thus increasing its ability to adsorb H 2 O molecules.

Functionalization of the CNTs surface is a way to tailor the sensitivity and selectivity of CNT based sensors to specific analytes [START_REF] Cont Es-De Jesús | Latest advances in modified/functionalized carbon nanotube-based gas sensors[END_REF]. A standard procedure to increase the interaction between a CNT and gaseous H 2 O molecules is the grafting of oxygen containing groups to the outer wall. Humidity sensors based on oxygen functionalized CNTs have a fast response followed by a long recovery (usually between 1 and 2 min) [START_REF] Arunachalam | Suspended carbon nanotubes for humidity sensing[END_REF][START_REF] Cao | Humidity sensor based on multi-walled carbon nanotube thin films[END_REF], unfortunately. This can be due in particular to a strong interaction of H 2 O with car boxylic groups [START_REF] Watts | The importance of oxygen-containing defects on carbon nanotubes for the detection of polar and non-polar vapours through hydrogen bond formation[END_REF]. Adsorption sites for weaker H 2 O bonding are defects in the CNT walls. Theoretical calculations have shown that the Stone Wales defect is attractive for H 2 O molecule [START_REF] Ellison | Interaction of water with single-walled carbon nanotubes: reaction and adsorption[END_REF]. Exper iments with SWCNTs treated by Ar plasma have evidenced a strong positive effect for sensing of ethanol gas [START_REF] Anoshkin | Single-walled carbon nanotube networks for ethanol vapor sensing applications[END_REF], which has a weak electron donation ability similar to water. The plasma treatment produces defects [START_REF] Yuv | A comparative study of argon ion irradiated pristine and fluorinated singlewall carbon nanotubes[END_REF] that enhance the sensitivity of the sensor as compared to the non treated sample.

In this paper, we propose a chemical procedure for covalent functionalization of DWCNTs by chlorine and demonstrate the prospect of the material as relative humidity (RH) sensor. Theory predicts a weak interaction of chlorine with large diameter CNTs [START_REF] Erbahar | Chlorination of carbon nanotubes[END_REF]. Experiments have shown in particular that the treatment of DWCNTs in a Cl 2 /O 2 atmosphere at 1000 C causes no chlorine attachment, but removes metal and disordered carbon contami nations [START_REF] Desforges | Dramatic enhancement of double-walled carbon nanotube quality through a one-pot tunable purification method[END_REF]. Covalent CeCl bonds are formed by using chlorine containing molecules, which can generate chlorine atoms under thermal [START_REF] Barkauskas | A novel purification method of carbon nanotubes by high-temperature treatment with tetrachloromethane[END_REF], plasma [START_REF] Abdelkader | Carbon tetrachloride cold plasma for extensive chlorination of carbon nanotubes[END_REF], or ultra violet photolysis [START_REF] Oliveira | UV photochlorination and bromination of single-walled carbon nanotubes[END_REF] activation. The carbon sites reacting with chlorine are defects in CNT walls or CNT edges [START_REF] Abdelkader | Carbon tetrachloride cold plasma for extensive chlorination of carbon nanotubes[END_REF]. Chlorination enhances overlapping of SWCNTs in an entangled network [START_REF] Dettlaff-Weglikowska | Effect of SOCl 2 treatment on electrical and mechanical properties of single-walled carbon nanotube networks[END_REF] and polarizes the CNT surface [START_REF] Kaur | Conjugation of chlorinated carbon nanotubes with quantum dots for electronic applications[END_REF]. As far as we know, the gas sensing properties of chlorinated CNTs and graphitic materials have not been investigated earlier.

Our strategy consists in the creation of holes in the DWCNTs walls by chemical etching and removal the contaminants from the DWCNTs surface by replacement of oxygen containing groups at the holes boundaries by chlorine atoms using a high temperature treatment by CCl 4 vapor. The first step reduces the contribution of the junction resistance between the DWCNTs in the network. As a result, the sensors response increases, and drift becomes negli gible. The second step further contributes to the relative response enhancement and significant decrease in the signal/noise ratio. Calculations performed by density functional theory (DFT) show that the interaction of H 2 O molecule with the surface of chlorinated holey SWCNT has a physisorption character. However, the binding energy substantially increases in case of the DWCNTs due to the inter wall interactions.

Experimental

Synthesis

DWCNTs were produced by a catalytic chemical vapor deposi tion (CCVD) method using a Mg 1-x Co x O solid solution with addition of Mo oxide and a CH 4 eH 2 mixture at 1000 C. The synthesis details are described elsewhere [START_REF] Flahaut | Gram-scale CCVD synthesis of double-walled carbon nanotubes[END_REF]. Accessible catalyst and MgO support were dissolved using a concentrated aqueous HCl solution.

The obtained product is a mixture of disordered carbon (initially deposited on the MgO surface free of the catalyst [START_REF] Lobiak | One-step chemical vapor deposition synthesis and supercapacitor performance of nitrogen-doped porous carbon-carbon nanotube hybrids[END_REF]) and CNTs with a number of walls ranging from one to three and a large predominance of DWCNTs (ca. 80%). Disordered carbon was removed using two procedures. The first one was a heating in air at 550 C for 30 min. In situ Raman spectroscopy study of the oxida tion process has evidenced a very low I D /I G ratio at this temperature [START_REF] Osswald | Elimination of D-band in Raman spectra of double-wall carbon nanotubes by oxidation[END_REF]. Following the air oxidation, the sample was cleaned with HCl in order to dissolve Co residues. Hereinafter, the obtained sample is denoted air DWCNTs. The second procedure was etching of the disordered carbon by concentrated mineral acids. The sample was refluxed at 130 C in 3 M HNO 3 for 24 h followed by a treatment at 70 C in 1:3 vol. solution of 15 M HNO 3 and 18 M H 2 SO 4 for 5 h. It has been shown that this procedure allows removal of disordered carbon and additionally functionalizes the DWCNTs walls by oxygen containing groups [START_REF] Bortolamiol | Double-walled carbon nanotubes: quantitative purification assessment, balance between purification and degradation and solution filling as an evidence of opening[END_REF].

Holes in the DWCNTs walls were created by boiling the oxidized DWCNTs in concentrated H 2 SO 4 for 1 h. When we used this pro cedure for graphite oxide treatment, the formation of numerous holes with an average size of ~2 nm was observed [START_REF] Yudanov | Layered compounds based on perforated graphene[END_REF]. At high temperature the acid interacts with oxygen containing groups resulting in the defunctionalization of the basal plane and the development of holes with boundaries saturated by hydrogen and oxygen [START_REF] Stolyarova | Effect of the graphite oxide composition on the structure of products obtained by sulfuric acid treatment at elevated temperatures[END_REF]. The DWCNTs sample after this treatment is denoted h DWCNTs.

Chlorination of air DWCNTs and h DWCNTs was carried out by CCl 4 vapor at 650 C for 15 min. The details of the synthesis are presented elsewhere [START_REF] Bulusheva | Fabrication of free-standing aligned multiwalled carbon nanotube array for Li-ion batteries[END_REF]. The obtained samples are denoted Cl air DWCNTs and Cl h DWCNTs.

Characterization methods

Transmission electron microscopy (TEM) characterization of the samples was performed on a JEOL JEM ARM200F microscope equipped with a Cs aberration corrector. An acceleration voltage of 200 kV was used for recording TEM and high angle annular dark field (HAADF) scanning TEM (STEM) images.

X ray photoelectron spectra (XPS) were recorded using mono chromatic radiation of 830 eV at the Russian German beamline of the Berliner Elektronenspeicherring für Synchrotronstrahlung (BESSY II), Helmholtz Zentrum Berlin. The content of elements was evaluated from the ratio of the area under the corresponding core level peaks taking into consideration the photoionization cross sections at the given photon energy and transmission function of the analyzer. The energy scale was calibrated to the Au 4f 7/2 peak at 84 eV. The background signal was subtracted by Shirley's method.

Electron paramagnetic resonance (EPR) spectra were recorded using a X Band Bruker EMX spectrometer equipped with a standard variable temperature accessory and operating at 9.653 GHz. Diphenylpicrylhydrazyl (DPPH) (g 2.0036 ± 0.0002) was used to calibrate the resonance frequency. In order to avoid distortion of the spectrum, the modulation amplitude of the static field was maintained at less than or equal to one third of the smallest peak to peak linewidth (DHpp) each time. Non saturated microwave power levels were used when determining the g values and DHpp.

Data processing was performed using Brüker WIN EPR and Sim Fonia software, respectively.

Sensor preparation and testing

Pulsed ultrasound with a power of 100 W was used to disperse DWCNTs in an aqueous solution of sodium dodecyl sulphate (SDS, 1 wt %). A tip with a diameter of 5 mm has operated with amplitude 30% for 30 min in order to achieve splitting of bundles and to prevent further functionalization of the DWCNTs. The concentra tion of DWCNTs powder in the solvent was 0.02 mg mL À1 . The suspensions were vacuum filtered through cellulose nitrate (CN) membranes with a pore size of 0.45 mm. A rectangular piece of the CN membrane was then placed on a glass substrate (sample in contact with the glass) and pressed at 90 C for 30 min. This ensures good adhesion of the DWCNT film to the substrate. The CN membrane was dissolved using acetone, then the supported DWCNT film was washed with acetone and dried under ambient conditions. Finally, the samples were cut into 3 Â 5 mm sized pieces and glued with 1 mm thick contact pads using RS (UK) silver conducting paste.

The sensors tests were performed at room temperature using a flow chamber described in detail elsewhere [START_REF] Katkov | A backside fluorine-functionalized graphene layer for ammonia detection[END_REF]. Dry argon or dry air (C H2O < 300 ppm) passed through a flask with deionized water to produce a wet gas flow. Dry gas and wet gas were mixed at different ratios using mass flow controllers. The total gas flow rate in all experiments was 150 mL min À1 . The sensor's resistance was determined by means of a Keithley 6750 picoammeter at a constant voltage of 25 mV. A conventional test consisted of exposure to a dry gas flow in order to determine a baseline resistance, exposure to a wet flow (up to RH 100%), and finally regeneration of the sensor using a dry gas flow. The sensor's response was defined as:

Response R g R 0 R 0 ( 1
)
where R 0 is the starting resistance, R g is the resistance measured under gas/humidity atmosphere.

DFT calculations

The calculations were made using the gradient corrected func tional of PerdeweBurkeeErnzerhof (PBE) with local and nonlocal exchange and correlation [START_REF] Perdew | Generalized gradient approximation made simple[END_REF] as implemented in the program package Jaguar (Jaguar, version 7.9, Schrodinger, LLC, New York, NY, 2012). Atomic orbitals were presented by the 6 31G basis set.

We took a fragment of armchair [START_REF] Pumera | Electrochemical properties of double wall carbon nanotube electrodes[END_REF][START_REF] Pumera | Electrochemical properties of double wall carbon nanotube electrodes[END_REF] CNT to model an outer wall of a DWCNT. This nanotube has a diameter of ca. 12.3 Å, which is the minimum value established from the TEM study of the DWCNTs [START_REF] Flahaut | Gram-scale CCVD synthesis of double-walled carbon nanotubes[END_REF]. The [START_REF] Pumera | Electrochemical properties of double wall carbon nanotube electrodes[END_REF][START_REF] Pumera | Electrochemical properties of double wall carbon nanotube electrodes[END_REF] nanotube is able to nest the (4,4) carbon nanotube [START_REF] Zόlyomi | Intershell interaction in double walled carbon nanotubes: charge transfer and orbital mixing[END_REF]. The CNT models had a length of ca. 22.2 Å and hydrogen atoms saturated the dangling carbon bonds at the edges. Geometry optimizations were performed with default convergence criteria. The absence of imaginary frequencies indicated that the obtained structures correspond to the local minima on potential energy surfaces. At first, we have fully optimized the (4,4) nanotube fragment. Then, the obtained nanotube has been placed into the center of the (9,9) nanotube fragment and the latter nanotube was optimized at frozen inner nanotube. The relaxed structure was used to create holey CNT models. For these models (without and with adsorbed H 2 O), positions of the atoms located at a distance of more than 6 Å from the hole boundary were not optimized. The models based on (4,4)@(9,9) DWCNT were constructed by combining the optimized components.

The adsorption energy of a H 2 O molecule on ideal or holey CNT fragments was calculated as

E ad E tot (CNT) þ E tot (H 2 O) E tot (model), where E tot (CNT), E tot (H 2 O
) and E tot (model) are the total energy of the isolated CNT fragment, the isolated H 2 O molecule, and the model with adsorbed H 2 O, respectively. Atomic charges were calculated by the Natural Bond Orbital (NBO) analysis.

Results and discussion

Materials structure and composition

We have compared three materials: (1) air DWCNTs, obtained by the heat treatment of raw, as synthesized sample in air, (2) h DWCNTs with oxygen decorated holes in the walls, and (3) Cl h DWCNTs produced by the high temperature CCl 4 treatment of h DWCNTs.

XPS analysis showed that the conventional purification pro cedure of a DWCNT sample by heating in air results in attachment of ca. 5 at. % of oxygen (Fig. S1 in Supporting Information). Analysis of the C 1s and O 1s spectra (Fig. 1) shows that most of the oxygen is in the form of carboxyl groups [START_REF] Resenthal | Combined XPS and TPD study of oxygen-functionalized carbon nanofibers grown on sintered metal fibers[END_REF]. The component in the C 1s spectrum located around 285.3 eV corresponds to defects and CeH bonds [START_REF] Estrade-Szwarckopf | XPS photoemission in carbonaceous materials: a "defect" peak beside the graphitic asymmetric peak[END_REF]. The content of oxygen increases to ca. 12 at. % in the h DWCNTs (Fig. S1) and this oxygen forms different functional groups (Fig. 1), particularly, hydroxyls and carboxyls [START_REF] Fedorovskaya | Effect of oxidative treatment on the electrochemical properties of aligned multi-walled carbon nanotubes[END_REF]. The C 1s spec trum of this sample has an enhanced intensity of the component at ~285.3 eV, which could confirm the creation of defects (holes) in the DWCNTs walls as result of the boiling in concentrated H 2 SO 4 .

The treatment of the h DWCNTs by CCl 4 vapor removed almost all the oxygen and attached ca. 4 at. % of chlorine (Fig. S1). More over, EPR data showed a significant decrease in the content of re sidual metal after such treatment (Fig. S2). Because of a linewidth of about 1100 G and a g factor of 2.1, the EPR signal is assigned to residual metallic catalysts (Co) rather than carbon dangling bonds or conduction electrons. For those latter cases, narrow line, i.e. several Gauss, with g of 2.003 is expected. EPR has been often used to highlight the efficiency of catalyst removal [START_REF] Zaka | Electron paramagnetic resonance investigation of purified catalyst-free single-walled carbon nanotubes[END_REF][START_REF] Jang | Differences in the catalyst removal from single-and double-walled carbon nanotubes[END_REF]. Spectra recorded in air and under vacuum being similar, no interaction with paramagnetic O 2 occurs that must result in changes on linewidth and intensity.

The component related to defects in the C 1s spectrum of the Cl h DWCNTs has a very similar intensity compared to the starting h DWCNT sample (Fig. 1). Occurrence of the holes in the DWCNT walls can explain the large amount of chlorine in this sample. XPS Cl 2p spectrum consists of a single doublet, where the position of 2p 3/2 spin orbit component at 200.6 eV (Fig. 2(a)) corresponds to the bonding of chlorine with edge carbon atoms at a graphene frag ment [START_REF] Tan | Atomically precise edge chlorination of nanographenes and its application in graphene nanoribbons[END_REF][START_REF] Tur | Chlorination of perforated graphite via interaction with thionylchloride[END_REF]. The holes can serve as channels for the penetration of chlorine inside the DWCNT. Actually, the HAADF/STEM image of a Cl h DWCNT exhibits bright spots inside the nanotube (Fig. 2(b)), which are likely to be encapsulated chlorine species.

A control experiment with CCl 4 treatment of air DWCNTs resulted in the attachment of ca. 1 at.% of chlorine only (Fig. S1) and the Cl 2p spectrum found that only 60% of this chlorine was involved in covalent CeCl bonds (Fig. 2(a)). These bonds can develop at the ends of DWCNTs, which have been open during the heating in air. The importance of edged carbon atoms for chlori nation of DWCNT sample is demonstrated by the data showing no chlorine in the as produced DWCNT based sample treated by Cl 2 flow at temperatures of 900e1110 C [START_REF] Desforges | Dramatic enhancement of double-walled carbon nanotube quality through a one-pot tunable purification method[END_REF].

TEM images of the investigated samples show a splitting of the DWCNTs bundles resulting from the acidic treatment (Fig. 3). The size of the bundles decreases from 10 to 20 nm in air DWCNTs (Fig. 3(a)) to 3e10 nm in Cl h DWCNTs (Fig. 3(b)). This is impor tant for the nanotube network resistance, as we will discuss later.

Sensors study

Before the sensor's tests, we have measured the resistance of the DWCNT based networks. To remove the residual solvent, each sample was dried at 100 C for 30 min and then flushed with dry argon for an hour. The obtained resistance value was ~1 kU for air DWCNTs, ~0.06 kU for h DWCNTs, and ~0.4 kU for Cl h DWCNTs. Conducting channels in the networks are formed via connections of neighboring nanotubes [START_REF] Tang | Carbon nanotube-based chemiresistive sensors[END_REF]. The resistance of an entangled CNT network is determined by the electronic properties of individual CNTs and the resistance at CNT junctions. The latter contribution prevails when the CNTs have a low defect density, such as our air purified DWCNTs. The treatment by acids used in the preparation of h DWCNTs and Cl h DWCNTs creates defects in the walls of the DWCNTs. Since the Raman spectra reveals a similar density of de fects in h DWCNTs and Cl h DWCNTs (Fig. S3), the higher resis tance of the latter network is attributed to better splitting of bundles as observed from TEM images (Fig. 3). In fact, previous experiments have shown that CNT network conductivity decreases with the mean bundle diameter [START_REF] Lyons | The relationship between network morphology and conductivity in nanotube films[END_REF].

We first tested the sensors in wet argon in order to study the H 2 O sensing mechanism of DWCNT based networks in the absence of other active air molecules. The dynamic tests at a constant RH (100%) followed by exposure to Ar flow is presented in Fig. 4. All sensors have a good stability starting from the third cycle. The air DWCNTs showed the smallest relative response of about 4%, characteristic of the oxidized CNTs [START_REF] Watts | The importance of oxygen-containing defects on carbon nanotubes for the detection of polar and non-polar vapours through hydrogen bond formation[END_REF]. The response substantially increased for the h DWCNTs. This is because the resistance of this network is determined by the changes in the resistance of the defective nanotubes, while the contribution from the inter tube junctions is small [START_REF] Salehi-Khojin | On the sensing mechanism in carbon nanotube chemiresistors[END_REF]. However, the signal was very noisy. The reason could be a poor contact between surfaces of highly oxidized nano tubes. The air DWCNT and h DWCNT sensors exhibited a small drift due to trapping of H2O molecules between the nano tubes [START_REF] Zhang | Roles of inter-SWCNT junctions in resistive humidity response[END_REF]. A step like shape of the signals recorded for these sensors could reveal the existence of two kinds of adsorption sites, namely, the surface oxygen groups and the inter tube junctions. The latter kind of adsorption sites gives a significantly smaller contribution to the performance of the Cl h DWCNT sensor as follows from the rapid saturation of the signal and the absence of the drift starting from the second target exposure. The high temperature treatment used for the preparation of a h DWCNTs removes almost all oxygen from the nanotube surface and the cleaned defective nanotubes contact strongly, that hinders penetration of H 2 O molecules be tween them.

The characteristics of the sensors averaged over four cycles following the first adsorption/desorption are collected in Table 1. All sensors were characterized by the same recovery time, which is T.lble 1 dose to those observed for oxidized MWCNTs [START_REF] Jung | Humidity-sensing characteristics of multi-walled carbon nanotube sheet[END_REF] and graphene materials [START_REF] Bi | Ultrahigh humidity sensitivity of graphene oxide[END_REF]. Among the studied samples, the Cl h DWCNTs have the highest relative response and the lowest response time toward H2O vapor. Moreover, this sensor showed a repeatable stable response in air saturated with water vapor (Fig. S4). The sensor responds much faster to humid air than to wet argon, while the sensor's reco very time is almost independent of the environment (Table 1 ). This result indicates that Cl h DWCNTs have a prospect for monitoring of relative humidity.

Operation capabilities of the Cl h DWCNT sensor in practical conditions were further identified from measurements at various RH levels. The conductivity of the sensor drops gradually with an increa se in the air humidity (Fig. 5(a)). Since the initial Cl h DWCNTs are p doped, such a behavior indicates that the H2O molecules act as an electron donor for the Cl h DWCNTs. The subsequent decrease in humidity does not lead to the restoration of the initial state of the sensor. Such a behavior corresponds to the joint presence of low energy or reversible and high energy or irreversible sites for H 2 O adsorption. The high energy sites are likely pores always present in a CNT network. To extract H 2 O molecules from them, the sensor should be heated in dry argon flow at a temperature of"" 11 5 °C (Fig. S5 ). Note, that this temper ature is much lower than the value of 165 °C for MWCNT based sensor [START_REF] Cantalini | Sensitivity to NO 2 and cross-sensitivity analysis to NH 3 , ethanol, and humidity of carbon nanotubes thin films prepared by PECVD[END_REF] and 220 °C for SWCNTs [START_REF] Zahab | Water-vapor effect on the electrical conductivity of a single-walled carbon nanotube mat[END_REF]. It has been shown, that chlorinated SWCNTs are stable under oxidative atmosphere up to 1000 °C due to a protective effect from chlorine [START_REF] Desforges | Improvement of carbon nanotube stability by high temperature oxygen/ chlorine gas treatment[END_REF]. Therefore, a heating in dry air can be used to restore the Cl h DWCNT sensor. Alternatively, the practical application of the sensor can start after the filling of high energy sites by air molecules. We believe that tightly bound molecules should not interfere with further work of the sensor. Actually, the hysteresis decreases at the second expo sure of the sensor to humid air (Fig. 5(a)).

A dependence of the sensor response versus RH was determined from the measurements carried out at the same time (120 s) of exposure to air (Fig. 5(b)). The dependence has a monotonic char acter and is perfectly fitted by a straight line in log log scale (insert in Fig. 5 of charge transfer at high humidity levels [START_REF] Varghese | Gas sensing characteristics of multi-walled carbon nanotubes[END_REF][START_REF] Huang | Carboxylation malti-walled carbon nanotubes modified with LiClO4 for water vapour detection[END_REF]. Zhang and co authors have explained this difficulty by an in creased separation of crosslinking CNTs [START_REF] Zhang | Roles of inter-SWCNT junctions in resistive humidity response[END_REF], suppressing the mobility of the carriers via the networks [START_REF] Ling | Investigation of the humidity-dependent conductance of single-walled carbon nanotube networks[END_REF].

H 2 O adsorption on holey CNTs

To reveal the effect of the holes in the CNT walls on the adsorption of a H 2 O molecule, we have invoked the OFT calculations of different models. First, we checked the validity of the PBE/6 31 G approach on an example of the non modified (9,9) CNT fragment. The molecule is oriented by hydrogen atom to the nanotube surface (Fig. S6), giving an adsorption energy of 0.087 eV. This energy perfectly matches with the values of 0.080 ± 0.019 eV for a zig2ag (10,0) carbon tube and of 0.070±0.010eV for graphene, which have been obtained using diffusion Monte Carlo method [START_REF] Al-Hamdani | How strongly do hydrogen and water molecules stick to carbon nanomaterials?[END_REF]. This method is able to capture weak in teractions due to inclusion of electron correlation and exact exchange. The use of dispersion corrections and Van der Waals inclusive functionals overestimates the adsorption energy for H 2 O by about 30-40% [START_REF] Al-Hamdani | How strongly do hydrogen and water molecules stick to carbon nanomaterials?[END_REF]. The NBO analysis gives the charge of 0.0014e on the adsorbed H 2O, which agrees well with other calculations, predicting a very week in ter action between a CNT and water [START_REF] Bell | Does water dope carbon nanotubes?[END_REF][START_REF] Zhao | Gas molecule adsorption in carbon nanotubes and nanotube bundles[END_REF].

A hole in the (9,9) CNT wall was obtained by removal of a central hexagon. When a H 2 O molecule approaches close to the hole (Fig. S7(a)), it spontaneously dissociates with the formation of C 0 and C-H bonds (Fig. S7(b)). This process continues until all dangling bonds at the hole's boundary become saturated (Fig. S7(c,d)). Thus, an exposure of holey CNTs to water vapor should result in the decoration of the holes by hydrogen and oxygen containing functional groups. This is supported by EPR, which has obseived no dangling carbon bonds in the studied materials.

In the next step, we have investigated an interaction of a H2O molecule with hydrogenated, oxygenated, and chlorinated holes. The resulting configurations, obtained after the optimi2ation of the geometry of the models, are shown in Fig. 6. The H 2 O molecule is oriented in such a way as to form the largest number of contacts with hydrogen and oxygen containing functionalities. Thus, it stabilizes in the center of the fully hydrogenated hole (Fig. 6 small negative charge q ( 0.008e) on the chlorine atoms, which causes the orientation of the adsorbed molecule by a hydrogen atom to a chlorine one. The distance between the atoms is ca.

2.74A

Our calculations predict that the H 2 O molecule, when adsorbed on a holey CNT, should have a positive charge. Therefore, it donates an electron density to the nanotube. The determined NBO charge, however, is small and varies from +0.008e to +0.067e, depending on the functionalities at the hole boundaries (Fig. 6). For the chlo rinated holey CNT, the transferred charge of 0.015e is a reasonably large considering the small adsorption energy of the H 2O molecule.

The inner nanotubes may influence the interaction of H2O molecules with the DWCNTs. The walls of a DWCNT are polarized due to redistribution of charge density [START_REF] Abdali | A band structure study on inter-wall conductance of double-walled carbon nanotubes[END_REF]. Depending on the chirality of the constituting nano tubes, the charge transfer from the outer wall to the inner one ranges from 0.005 to 0.035 e A-1 [START_REF] Zόlyomi | Intershell interaction in double walled carbon nanotubes: charge transfer and orbital mixing[END_REF].

To evaluate the effect of the holes in the outer walls on the reactivity ofDWCNTs, we calculated the energies of H 2 O adsorption on the fragments of ideal (4,4)@(9,9) nanotube and that containing a functionalized hole. The inner (4,4) nanotube slightly affects the adsorption energy for the ideal DWCNTand the DWCNTs where the hole boundary is decorated by hydrogen and chlorine atoms (Table S1 ). However, for the oxygen containing DWCNTs the adsorption energy grows by 15-30% as compared to the SWCNT analogs. This can explain the observation of a higher sensitivity of the DWCNTs to H2O molecules as compared to SWCNTs [START_REF] Tang | Effect of H 2 O adsorption on the electrical transport properties of double-walled carbon nanotubes[END_REF]. Preparations of sensor elements usually include the steps of CNT purification and dispersion, which may introduce in the nanotube walls defects and oxygen groups active to H 2 O molecules.

Our calculations confirm negative charging of the inner nano tube in the ( 4,4 )@(9,9) DWCNT (Table S1 ). The value of the charge transfer of 0.014 e A-1 well agrees with the literature data (40].

Creation of a hole in the outer nanotube decreases polari2ation of the DWCNTs, especially for the oxygenated holes. The decoration of the hole's boundary with chlorine atoms has a little effect on the interaction of outer and inner nano tubes. The charge transfer in this DWCNT is 0.012 e Å À1 . Based on the calculation results, we specu late that the Cl h DWCNTs have the conductivity close to that for perfect DWCNTs, but unlike these nanotubes possess a higher reactivity to H 2 O molecules. This is the cause of an intense low noise signal to gaseous H 2 O. The oxygenation of the holes in the h DWCNTs reduces the nanotubes polarization, which likely leads to a small change in sensor conductivity upon the H 2 O adsorption/ desorption.

Conclusions

We have developed an effective humidity sensor using chemi cally treated DWCNTs. An oxidation of the DWCNTs by mineral acids splits the bundles that allows forming networks with many more contacts between the nanotubes. Thin films consisting of uniformly distributed DWCNTs possess a low electrical resistance. Boiling the oxidized DWCNTs in concentrated sulfuric acid creates holes in the walls, which serve as adsorption sites for H 2 O mole cules. Moreover, the contribution of the junctions between adja cent defective nanotubes has a little effect on the total resistance of the network. This considerably increases the response of the DWCNTs sensor. However, the nanotubes functionalized with oxygen containing groups should strongly interact with H 2 O mol ecules, as predicted by DFT calculations. Trapping of the molecules in the oxidized holey DWCNT network results in the drift and the noise of the sensor's signal. The high temperature treatment of these nanotubes by CCl 4 removes oxygen and decorates the holes' boundaries by chlorine. This last treatment significantly improves the relative response of the DWCNTs to H 2 O molecules and makes the sensor signal stable and reproducible after the heating at a relatively low temperature. Based on the calculations, we relate such behavior with a low adsorption energy of H 2 O at the chlori nated holes, which, however, is accompanied by a charging of the DWCNTs.

Fig. 1 .Fig. 3 .Fig. 4 .

 134 Fig. 1. XPS C 1s and O 1s spectra of air-purified DWCNTs (air-DWCNTs), holey DWCNTs (h-DWCNTs), and chlorinated holey DWCNTs (Cl-h-DWCNTs). (A colour version of this figure can be viewed online.)

Fig. 5 .

 5 Fig. 5. Tests of the 0-h-OWCITT sensor in air: (a) variation in electrical current at different relative humidity levels and (b) relative re sponse to target exposure (120 s). The inset shows dependence of sensor relative response on the relative humidity in lo�rithmic scale. (A colour version of this figure can be vie=d ontine.)

  (a)) at a distance of 2.43-2.63 A from the hydrogen atoms. The molecule forms two hydrogen bonds with the ketone groups (Fig. 6(b )), with the contacts HOH• • • 0 C of 1.95 A, and with the hydroxyl groups (Fig. 6(c)) via a hydrogen atom (HOH -• -O-H, 1.89A) and oxygen (H 2O• ••H-O, 1.60A). For the model with a carboxylic group, only one contact close to the hydrogen bond is found. It is formed by interaction via O QOH) species with a hydrogen atom of H 2 O. The stronger interaction between the H 2 O molecule and the hole is found in the case when hydroxyl and carboxyl groups are simul taneously present at the hole's boundary (Fig. 6( c)). This is due to the realization of very short contacts H 2 O-• • H-O, 1.46 A and HOH•• -0 C(OH), 1.64 A The adsorption energy of H2O at the chlorinated hole is substantially lower (Fig. 6(f)) than the values characteristics of the hydro gen bonds. The NBO analysis detects a

Acknowledgments

The work has been financially supported by the Russian Foun dation for Basic Research (Grant N 16 53 150003) and PRC CNRS/ RFBR(Grant No 1023). This research project has been supported by the Russian German Laboratory of BESSY II.

Appendix A. Supplementary data

Supplementary data to this article can be found online at https://doi.org/10.1016/j.carbon.2019.04.010.


Nyoman Juniarta

Miguel Couceiro

Amedeo Napoli

Order-preserving Biclustering Based on FCA and Pattern Structures

Biclustering is similar to formal concept analysis (FCA), whose objective is to retrieve all maximal rectangles in a binary matrix and arrange them in a concept lattice. FCA is generalized to more complex data using pattern structure. In this article, we explore the relation of biclustering and pattern structure. More precisely, we study the order-preserving biclusters, whose rows induce the same linear order across all columns.

Introduction

CrossCult (http://www.crosscult.eu) is a European project whose idea is to support the emergence of a European cultural heritage by allowing visitors in different cultural sites (e.g. museum, historic city, archaeological site) to improve the quality of their visit by using adapted computer-based devices and to consider the visit at a European level. Such improvement can be accomplished by studying, among others, the possibility to build a dynamic recommendation system. This system should be able to produce a relevant suggestion on which part of a cultural site may be interesting for a specific user/visitor. Given U as the set of previous users and I as the set of items, one approach for producing such suggestion is by retrieving a set of similar users in U. There are different techniques of calculating the similarity between any two users. From a dataset of item ratings, we can interpret u 1 ∈ U as similar to u 2 ∈ U if they have similar order of preference. For example, suppose that rating(u x , i y ) is the rating given by user u x ∈ U to item i y ∈ I. We can consider that u 1 is similar to u 2 if rating(u 1 , i 1 ) > rating(u 1 , i 2 ) and rating(u 2 , i 1 ) > rating(u 2 , i 2 ) (i.e. both of them prefer i 1 over i 2 ). Furthermore, their similarity is stronger if they give similar N. Juniarta, M. Couceiro, A. Napoli Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France, e-mail: {nyoman. juniarta,miguel.couceiro,amedeo.napoli}@loria.fr 1 rating order over a larger set of items, e.g. if rating(u 1 , i 1 ) > rating(u 1 , i 2 ) > • • • > rating(u 1 , i 10 ) and rating(u 2 , i 1 ) > rating(u 2 , i 2 ) > • • • > rating(u 2 , i 10 ). The task of finding a set of similar users based on this similarity can be regarded as the task of finding order-preserving (OP) biclusters in a numerical matrix.

In this article we explore two approaches of finding OP biclusters. The first is based on partition pattern structure, while the second is the application of sequence pattern structure. Both approaches originate from formal concept analysis (FCA), since it has a related objective with biclustering: finding submatrices whose cells have "similar" value. By using these approaches, we can theoretically enumerate all possible OP biclusters in a numerical matrix, and arrange them in a hierarchical structure.

OP bicluster is first defined in Ben et al. [START_REF] Ben-Dor | Discovering local structure in gene expression data: the order-preserving submatrix problem[END_REF] to find a highly statistically significant OPSM in a gene expression dataset. The dataset is represented as a numerical matrix with genes as rows, experiments as columns, and each cell represents the expression level of a given gene under a given experiment. In such a matrix, an OPSM corresponds to a subset of genes that induce the same linear ordering of a subset of experiments.

The OP bicluster discovery problem is also a special case of sequential pattern mining [START_REF] Henriques | BicSPAM: flexible biclustering using sequential patterns[END_REF]. A row in an m × n matrix can be regarded as a sequence of n items, and the whole matrix corresponds to a dataset of m sequences. This sequence dataset is extremely dense, since all possible items are present in each sequence (except missing value). Furthermore, many existing sequential pattern mining methods try to find patterns that satisfy a minimum support threshold [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF][START_REF] Wang | BIDE: Efficient mining of frequent closed sequences[END_REF][START_REF] Yan | CloSpan: Mining: Closed sequential patterns in large datasets[END_REF][START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF]. This means that longer sequences are difficult to be recovered, since shorter sequences (hence smaller OPSMs) dominate the results. This problem has been studied in [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] by proposing "rare" sequential pattern mining. We will also show that it can be used to obtain OP biclusters from a numerical matrix.

This article is organized as follows. First, we explains the background and examples of biclustering in Sect. 2. Sect. 3 describes the basic definitions of FCA and pattern structure. Our first approach is explained in Sect. 4, while the second approach is in Sect. 5. Some results of our experiments are described in Sect. 6. In the end, we discuss our conclusions and some future works in Sect. 7.

Order-preserving biclusters

In this section, we recall the basic background and discuss illustrative examples of biclustering, especially order-preserving biclusters, as described in [START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF].

We consider a dataset composed of a set of objects G, each of which has values over a set of attributes M. Therefore, in a numerical dataset (G, M), the value of m for object g is written as m(g).

One may be interested in finding which subset of objects possesses the same values w.r.t. a subset of attributes. Regarding the matrix representation, this is equivalent to the problem of finding a submatrix that has a constant value over all of its elements (example in Table 1a). This task is called biclustering with constant values, which is a simultaneous clustering of the rows and columns of a matrix.

Other than constant values, the bicluster approach also focused on finding other types of submatrices, as shown in Table 1. A bicluster with constant columns is a submatrix where each column has the same value, illustrated in Table 1b. In this article, we are dealing with OP biclusters. In this type, each row induces the same linear order across all columns as defined in Definition 1.

Definition 1 Given a dataset (G, M), a pair (A, B) (where A ⊆ G, B ⊆ M) is an order-preserving (OP) bicluster iff ∀g ∈ A, there exist a sequence of columns

(m 1 • • • m |B | ) in B such that m i (g) < m i+1 (g) for all 1 ≤ i ≤ |B| -1.
For example, in the bicluster in Table 1c, each row follows column1 < column2 < column4 < column3.

Biclustering shares many common elements with formal concept analysis (FCA). In FCA, from a binary matrix we try to find a maximal submatrix whose elements are 1. In other words, the objective of FCA is to identify maximal constant-value biclusters (but only for biclusters whose values are 1). Hence, a formal concept can be considered as a bicluster of objects and attributes. Furthermore, formal concepts are arranged in a concept lattice, that materializes the hierarchical relation among all biclusters. In the following section, we will recall some basic definitions of FCA and its generalization to pattern structures.

FCA and Pattern Structures

Formal concept analysis is a mathematical framework based on lattice theory and used for classification, data analysis, and knowledge discovery [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. From a formal context, FCA detects all formal concepts, and arranges them in a concept lattice.

A formal context is a triple (G, M, I), where G is a set of objects, M is a set of attributes, and I is a binary relation between G and M, i.e. I ⊆ G × M. If an object g has an attribute m, then (g, m) ∈ I. An example of a formal context is shown in Table 2, where × indicates the corresponding (g, m) ∈ I.

Between the sets G and M, there is a Galois connection that consists of two functions: 2 G → 2 M and 2 M → 2 G . For a subset of objects A ⊆ G, A is the set of

m 1 m 2 m 3 m 4 g 1 × g 2 × × g 3 × × × g 4 × × ×
attributes that are possessed by all objects in A, i.e.:

A = {m ∈ M |∀g ∈ A, (g, m) ∈ I}, A ⊆ G.
Dually, for a subset of attributes B ⊆ M, B is the set of objects that have all attributes in B, i.e.:

B = {g ∈ G|∀m ∈ B, (g, m) ∈ I}, B ⊆ M.
A formal concept is a pair (A, B), where A ⊆ G and B ⊆ M, and such that A = B and B = A. For example, {g 2 ,

g 3 } = {m 1 , m 3 }, and {m 1 , m 3 } = {g 2 , g 3 } in Table 2. They form a formal concept ({g 2 , g 3 }, {m 1 , m 3 }). A formal concept (A, B) is a subconcept of (C, D) -denoted by (A, B) ≤ (C, D) -if A ⊆ C (or equivalently D ⊆ B).
A concept lattice can be formed using the ≤ relation which defines the partial order among concepts. If (A, B) < (C, D) and there is no (E, F) such that (A, B) < (E, F) < (C, D), then (A, B) is a lower neighbor of (C, D). For the context in Table 2, the formal concepts and their corresponding lattice are shown in Fig. 1.

FCA is restricted to specific datasets where each attribute is binary (e.g. has only yes/no value). For more complex values (e.g. numbers, strings, trees, graphs. . . ), FCA is then generalized into pattern structures [START_REF] Ganter | Pattern structures and their projections[END_REF].

A pattern structure is a triple (G, (D, ), δ), where G is a set of objects, (D, ) is a complete meet-semilattice of descriptions, and δ : G → D maps an object to a description. The operator is a similarity operation that returns the common 2 elements between any two descriptions. It implies that c d = c ⇔ c d. A description can be a number, set, sequence, tree, graph, or other complex structure. In standard FCA (with set as description), corresponds to set intersection (∩), i.e. {a, b, c} {a, b, d} = {a, b}, and corresponds to subset inclusion (⊆). In the case of sequence as a description, can be a set of common closed subsequences (SCCS) [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. Similarly, corresponds to subsequence inclusion ( ).

The Galois connection for a pattern structure (G, (D, ), δ) is defined as:

A = g∈ A δ(g), A ⊆ G, d = {g ∈ G|d δ(g)}, d ∈ D.
A pattern concept -similar to a standard formal concept -is a pair (A, d), A ⊆ G and d ∈ D, where A = d and d = A. Table 2 can be regarded as a pattern structure with G = {g 1 • • • g 4 }, while the description of each object is a set of attributes. For example, δ(g

2 ) = {m 1 , m 3 } and δ(g 3 ) = {m 1 , m 2 , m 3 }. Their similarity is a set intersection, i.e. given A = {g 2 , g 3 }, A = δ(g 2 ) δ(g 3 ) = {m 1 , m 3 }. Furthermore, with d = {m 1 , m 3 }, we have d δ(g 2 ) and d δ(g 3 ). Therefore d = {g 2 , g 3 } and the pair ({g 2 , g 3 }, {m 1 , m 3 }) is a pattern concept.
The set of all pattern concepts also forms a lattice. When applying pattern structure to the task of finding biclusters, the lattice can be useful to obtain the hierarchical structure of a set of biclusters. In the following sections, we will describe two approaches of finding OP biclusters: based on partition pattern structure (Sect. 4) and based on sequence pattern structure (Sect. 5).

Finding Biclusters Using Partition Pattern Structure

In this section, first we recall the partition pattern structure (pps) detailed in [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF]. In pps, the pattern structures is (M, (D, ), δ), where attributes are considered as objects, explained in Sect. 4.1. The description of each attribute m ∈ M is a partition of objects according to the values on the given attribute. We will then propose an extension of this approach to perform OP biclustering in Sect. 4.2.

Partition Pattern Structure

As explained in [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF][START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF], a partition d of a set G is a collection of subsets of G (d = {p i }, p i ⊆ G), such that:

p i ∈d p i = G and p i ∩ p j = ∅ whenever i j. (1)
The set of all partitions is denoted as D, and it will become the description of attributes in the pattern structure (M, (D, ), δ). The function δ maps an attribute to a partition of objects, i.e. δ : M → D. The whole set of attributes can be partitioned (respecting Eq. 1) according to the values of an attribute. To do that, we need an equivalence relation -which is reflexive, symmetric, and transitive -among objects. The equivalence relation [g i ] m j of an object g i w.r.t. an attribute m j is:

[g i ] m j = {g k ∈ G|m j (g i ) = m j (g k )}. (2)
Given an attribute m j , the relation [g i ] m j splits G into equivalence classes. It satisfies Eq. 1, such that the classes cover the whole set of objects and there is no intersection between any two different classes. These classes can be regarded as partition elements. Therefore a partition mapping is defined as δ : M → D, such as:

δ(m j ) = {[g i ] m j |g i ∈ G}. (3)
For example, from Table 3:

[g 1 ] m 1 = [g 2 ] m 1 = {g 1 , g 2 } [g 3 ] m 1 = [g 4 ] m 1 = {g 3 , g 4 } δ(m 1 ) = {[g 1 ] m 1 , [g 2 ] m 1 , [g 3 ] m 1 , [g 4 ] m 1 } = {{g 1 , g 2 }, {g 3 , g 4 }}.
The meet and join of two partitions d 1 = {p i } and d 2 = {p j } are defined as:

d 1 d 2 = {{p i ∩ p j }|p i ∈ d 1 and p j ∈ d 2 } (4)
d 1 d 2 = ({{p i ∪ p j }|p i ∈ d 1 and p j ∈ d 2 and p i ∩ p j ∅}) + (5)
where (.) + is a closure that preserves only the maximal components in d. For example, given δ(m

1 ) = {{g 1 , g 2 }, {g 3 , g 4 }} and δ(m 4 ) = {{g 1 }, {g 2 }, {g 3 , g 4 }}, we have δ(m 1 ) δ(m 4 ) = {{g 1 }, {g 2 }, {g 3 , g 4 }}, and δ(m 1 ) δ(m 4 ) = {{g 1 , g 2 }, {g 3 , g 4 }}.
The order between any two partitions is given by the subsumption relation:

d 1 d 2 ⇐⇒ d 1 d 2 = d 1 . (6)
Therefore, δ(m 4 ) δ(m 1 ) since δ(m 1 ) δ(m 4 ) = δ(m 4 ).

Given a set of attributes M, a set of partitions D, and a mapping δ, a partition pattern structure is determined by the triple (M, (D, ), δ). Notice that in this triple, M is regarded as the set of objects, where the description of an object is a partition. A pair (A, d) is then called a partition pattern concept (pp-concept) iff A = d and d = A, where:

A = m∈ A δ(m) A ⊆ M (7)
d = {m ∈ M |d δ(m)} d ∈ D. (8)
For example, given 3 are hierarchically illustrated as a lattice in Figure 2.

A = {m 3 , m 5 } in Table 3, we get A = δ(m 3 ) δ(m 5 ) = {{g 1 }, {g 3 },
∅ {m 1 , m 2 } { {g 1 , g 2 }, {g 3 , g 4 } } {m 3 } { {g 1 }, {g 2 , g 3 , g 4 } } {m 5 } { {g 3 }, {g 1 , g 2 , g 4 } } {m 1 , m 2 , m 3 , m 4 } { {g 1 }, {g 2 }, {g 3 , g 4 } } {m 1 , m 2 , m 5 } { {g 1 , g 2 }, {g 3 }, {g 4 } } {m 3 , m 5 } { {g 1 }, {g 3 }, {g 2 , g 4 } } {m 1 , m 2 , m 3 , m 4 , m 5 } { {g 1 }, {g 2 }, {g 3 }, {g 4 } }
Fig. 2 Partition pattern lattice for Table 3.

OP Biclustering Using Partition

In this subsection, we will explain the possible application of partition pattern structure to discover OP biclusters as defined in Definition 1.

Consider the dataset given by Table 4, with the set of attributes G = {g 1 , g 2 , g 3 , g 4 , g 5 }. For the task of finding OP biclusters, we introduce the notation r x y as a pair of attributes m x and m y , x < y, and R is the set of all possible r x y . That is, from n attributes, there will be C n 2 pairs. 4 Pair Partition

r 1 2 { {g 1 , g 3 }, {g 2 , g 4 , g 5 } } r 1 3 { {g 1 , g 3 , g 5 }, {g 2 , g 4 } } r 1 4 { {g 1 , g 2 , g 5 }, {g 3 , g 4 } } r 2 3 { {g 1 , g 3 , g 5 }, {g 2 , g 4 } } r 2 5 { {g 1 , g 2 , g 3 , g 5 }, {g 4 } }
Using the same definition of partition as Equation 1, we define a new partition mapping δ : → D, such as:

δ(r x y ) = {[g i ] r x y |g i ∈ G}. (9)
The [g i ] r x y is the equivalence relation of an object w.r.t. a pair of attributes:

[g i ] r x y = {g k ∈ G| arg max j (m j (g i )) = arg max j (m j (g k )), j ∈ {x, y}}. (10)
For example, from Table 4:

[g 1 ] r 1 2 = [g 3 ] r 1 2 = {g 1 , g 3 } [g 2 ] r 1 2 = [g 4 ] r 1 2 = [g 5 ] r 1 2 = {g 2 , g 4 , g 5 }.
In other words, δ maps a pair of attributes to a partition according to the pair's comparison. For example, δ(r 1 2 ) = {{g 1 , g 3 }, {g 2 , g 4 , g 5 }} because m 2 > m 1 for g 1 and g 3 ; and m 1 > m 2 for g 2 , g 4 , and g 5 . Some pairs and their partitions are listed in Table 5.

Given a set of attribute pairs R, a set of partitions D, and the mapping function δ, a partition pattern structure for finding OP biclusters is determined by the triple (R, (D, ), δ). A concept is a pair (B, d) such that B = d and d = B, where:

B = r ∈B δ(h) B ⊆ R (11)
d = {r ∈ R|d δ(r)}. d ∈ D (12)
The meet and subsumption relation between two partitions follow Equation 4and Equation 6 respectively.

Here, the extent of a pp-concept is a set of attribute pairs. We can obtain a OP bicluster in a concept if there is a "clique" among the attributes in the pairs, as described in Definition 2.

Definition 2 Consider a concept (B, d).

There may exist a set of attributes C ⊆ M such that for all m, n ∈ C, there exists

r m n ∈ B or r n m ∈ B. The set C is called a clique in B.
For example, consider the concept pc 1 with extent {r 1 2 , r 1 3 , r 2 3 } and intent {{g 1 , g 3 }, {g 5 }, {g 2 , g 4 }}. Its extent forms a clique among m 1 , m 2 , and m 3 , since all pairs of any two of those attributes are included.

If a concept (B, d) contains a set of attributes C ⊆ M that forms a clique, then each pair in {(p, C)|p ∈ d} corresponds to a OP bicluster. For example, from pc 1 , we can obtain three OP biclusters:

• ({g 1 , g 3 }, {m 1 , m 2 , m 3 }), which follows m 1 < m 2 < m 3 ; • ({g 2 , g 4 }, {m 1 , m 2 , m 3 }), which follows m 3 < m 2 < m 1 ; and • ({g 5 }, {m 1 , m 2 , m 3 }), which follows m 2 < m 1 < m 3 .

Finding Biclusters Using Sequence Pattern Structure

In this section, we will recall the characterization of sequential pattern mining using sequence pattern structure as proposed in [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. Then, we show how the problem of finding OP biclusters can be solved using sequence pattern structure.

Sequence Pattern Structure

A sequence is an ordered list s 1 s 2 . . . s m , where s i is an itemset {i 1 , . . . , i n }. The list s 1 = {a, b}{a, c, d} is a sequence of 2 itemsets. For simplicity, we follow the bar notation in [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] such that two consecutive itemsets are separated by a bar. Therefore, the sequence from the previous example can be written as ab|acd.

A sequence s = s 1 |s 2 | . . . |s m is a subsequence of t = t 1 |t 2 | . . . |t n , denoted by s t, if there exist indices 1 ≤ i 1 < i 2 < . . . < i m ≤ n such that s j ⊆ t i j for all j = 1 . . . m and m ≤ n. For example, the sequence a|d is a subsequence of ab|acd, while sequence c|d is not.

Given a sequence database S (example in Table 6), the set of all subsequences of elements in S is denoted as Q, where q ∈ Q ⇐⇒ ∃s ∈ S s.t. q s (S ⊆ Q). The objective of frequent sequential pattern mining is to retrieve all q ∈ Q whose support is larger than a threshold. The support of a sequence -denoted as σ(q) -w.r.t. S is the number of sequences in S which have q as a subsequence, or σ(q) = |{s ∈ S|q s}|, q ∈ Q. In Table 6, given q 1 = a|c, the support of q 1 is 2, since q 1 s 1 and q 1 s 2 .

Sequential pattern mining in is defined with respect to a particular sequence pattern structure, and it can retrieve "rare" sequences (small support but having larger number of itemsets) [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF]. This pattern structure relies on the notion of closed sequences. From a set of sequences d, its set of closed sequences is: In other words, d + is all sequences in d who are not subsequence of other sequence in d. Then, the sequence pattern structure is defined as a triple (S, (D, ), δ), where δ : Q → D is a mapping from a sequence q to its description δ(q). Here, a description is a set of closed sequences. As example, δ(s 1 ) = {ab|acd} in Table 6.

d + = {q i ∈ d| q j ∈ d s.t. q i ≺ q j }. ( 13
)
The similarity operator between any two descriptions d 1 and d 2 is the similarity between each sequence in d 1 and each sequence in d 2 , or:

d 1 d 2 =        q i ∈d 1 ,q j ∈d 2 q i ∧ q j        + . (14)
The ∧ operator returns the set of closed sequences that are subsequences of both q i and q j , or: q i ∧ q j = {q ∈ Q|q q i and q q j } + . (

For example, suppose that we have d 1 = {a|c|d, a|b|c} and d 2 = {a|d|c, a|b|c|d}.

Each of these descriptions has two sequences. Their similarity is:

d 1 d 2 = {a|c|d ∧ a|d|c, a|c|d ∧ a|b|c|d, a|b|c ∧ a|d|c, a|b|c ∧ a|b|c|d} + = {a|c, a|d, a|c|d, a|c, a|b|c} + = {a|c|d, a|b|c}.
The space of descriptions is denoted by D, and is a partially ordered set of descriptions. A description d 1 ∈ D can be subsumed by ( ) d 2 ∈ D, iff:

d 1 d 2 ⇐⇒ ∀q i ∈ d 1 : ∃q j ∈ d 2 s.t. q i q j . (16)
This means that d 1 is subsumed by d 2 iff every sequence in d 1 is a subsequence of at least one sequence in d 2 .

With T ⊆ S and d ∈ D, a pair (T, d) is a sequence pattern concept iff T = d and d = T, where:

T = s ∈T δ(s) (17)
d = {s ∈ S|d δ(s)}. (18)
As example, ({s 1 , s 3 }, {a|d, b, ac}) is a sequence pattern concept from Table 6. All concepts from this table are shown in Figure 3.

OP Biclustering Using Sequence

The task of finding OP biclusters can be formulated as sequential pattern mining, and can be solved using sequence pattern structure. Consider again the dataset in Table 4.

It can be regarded as a sequence database. Each

g ∈ {g 1 , • • • g 5 } is a sequence of five items m ∈ {m 1 , • • • m 5 }.
The numbers in the matrix determine the order of each item in a given sequence. For example, the object A sequence pattern concept (T, d) has a set of objects (or sequences) as extent and a set of common subsequences as intent. Given a numerical table like Table 4, the intent is a set of sequence of attributes. A sequence m 1 | • • • |m n in the intent signifies that m 1 < • • • < m n for all objects in the extent. As a result, from any sequence pattern concept (T, d), any pair of T and each sequence in d forms a OP bicluster. For example, consider the concept ({g 2 , g 4 , g 5 }, {m 3 , m 2 |m 1 , m 5 |m 4 }) from Table 4. Its intent has three sequences, so we have three OP biclusters:

g 2 has m 3 < m 2 < m 5 < m 1 < m 4 ,
• ({g 2 , g 4 , g 5 }, {m 3 }),

• ({g 2 , g 4 , g 5 }, {m 1 , m 2 }), and

• ({g 2 , g 4 , g 5 }, {m 4 , m 5 }).
Therefore, we can obtain OP biclusters in a numerical matrix using sequence pattern structure.

Experiment

In this section, we first compare the runtime of the two methods for finding OP bicluster: partition pattern structure (pps) and sequence pattern structure (sps), both using AddIntent algorithm to generate all concepts and the corresponding lattice. Randomly generated matrices are used, where the value of each cell is between 1 and 100 following uniform distribution. We inspect the effect of the number of attributes on both methods, and we choose a small number of objects [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]. matrix is generated to compare every pair of columns. The partition is then performed in the new matrix. In this second approach, an m × n matrix is converted to a set of m sequences, each of them has n items. The first approach is more complex than the second, since the first creates a larger matrix before applying partition pattern structure.

We tested the pps-based approach to breast cancer dataset [START_REF] Hedenfalk | Gene-expression profiles in hereditary breast cancer[END_REF]. This dataset has 3226 rows (genes) and 21 columns (tissues). As shown in Table 7, these 21 tissues are composed by 7 brca1 mutations, 8 brca2 mutations, and 6 sporadic breast cancers.

Since it has 21 columns, the pps-based approach will convert the dataset into a 3226×C 21 2 = 3226×210 matrix. In order to reduce the computational complexity, we introduce a parameter θ. In calculation of the intent of any partition pattern concept, any partition component having the number of elements less than θ is discarded. For example, with θ = 3, the partition {{a, b, c}, {d, e}} becomes {{a, b, c}}. The number of concepts can be very large, so we provides the runtime until 10K concepts are obtained.

The result of experiment with varying θ is shown in Fig. 5. Here we see that in general, larger θ means more time to obtain 10K concepts. However, it does not necessarily mean that larger θ needs more time to finish the computation of the whole lattice. This is because lesser θ implies more concepts, hence faster to obtain 10K concepts. It can also be noted that for θ > 120 (not shown in the figure), there are less than 10K concepts in the whole lattice. We also tested the sps-based approach to the same dataset. Contrary to the previous experiment where we take only 10K concepts, here we calculate the runtime for the computation of the whole lattice. To reduce the computational time, we introduced the parameter , which is the minimal length of any sequence. Therefore, in calculating the intent of any sequence pattern concept, any sequence having length less than is discarded. For example, with = 3, an intent {a|b|c, a|d} becomes {a|b|c}.

The result of this experiment is shown in Fig. 6. With larger , the computational time is reduced, since we will have less concepts. This is useful compared to the majority of existing sequential pattern miners. To obtain sequential pattern with larger length, they usually need to lower the minimum support parameter. This results in more patterns, and consequently larger computational time.

Concerning the biclusters, we found that the bicluster of size 15 × 2 is the widest (having most columns) bicluster with more than 1 row. It follows the sequence of columns c 19 < c 20 < c 1 < c 17 < c 12 < c 21 < c 11 < c 9 < c 16 < c 14 < c 10 < c 7 < c 13 < c 5 < c 3 , which is present in gene #24638 and #291057. Regarding biclusters covering more than 2 rows, the widest biclusters are of size 10 × 3. They are statistically significant because at a random 3226 × 21 matrix, we can only expect a bicluster covering 1 row (as 3226/10! < 1) exhibiting a certain ordering of 10 columns.

Conclusion

In this article, we propose two approaches of finding OP biclusters. The first approach is based on partition pattern structure, going from the idea that given two attributes m i and m j , the set of all objects G can be separated to two groups: those with m i < m j and those with m i > m j . For this article, we do not consider yet the equality (the case with m i = m j ). Then given that the task of finding OP biclusters is similar to the sequential pattern mining, the second approach is based on sequence pattern structure. This allows us to define a threshold, such that we can mine OP biclusters whose number of columns is larger than the threshold.

In general, both approaches generate a set of overlapping OP biclusters, a characteristic similar to FCA, where a set of overlapping submatrices is obtained. Furthermore, both the set of partition pattern concepts and the set of sequence pattern concepts are partially ordered and forms a lattice. This ordering can be studied to obtain the hierarchical structure of the generated OP biclusters. The hierarchical and overlapping characteristics are notably similar to HOCCLUS2 method in [START_REF] Pio | A novel biclustering algorithm for the discovery of meaningful biological correlations between micrornas and their target genes[END_REF], although with different bicluster type. One of the differences between our method and HOCCLUS2 is that we obtain hierarchical and overlapping biclusters directly from a matrix, while HOCCLUS2 finds a set of non-overlapping biclusters from a matrix, and then identify overlapping and hierarchically organized biclusters.

The OP biclusters can be further studied to build a collaborative recommendation systems. One example is when we have a user-item matrix, where each cell shows the rating of an item given by a user. A OP bicluster from this matrix can be regarded as a set of users having similar order of preference over a set of items.

Fig. 1

 1 Fig. 1 Concept lattice for the formal context in Table 2

{g 2 ,

 2 g 4 }}. Dually, given d = {{g 1 }, {g 3 }, {g 2 , g 4 }}, we get d = {m 3 , m 5 } since d δ(m 3 ) and d δ(m 5 ). Therefore, ({m 3 , m 5 }, {{g 1 }, {g 3 }, {g 2 , g 4 }}) is a ppconcept. All pp-concepts from Table

so the sequence of g 2 is m 3

 3 |m 2 |m 5 |m 1 |m 4 , and consequently δ(g 2 ) = {m 3 |m 2 |m 5 |m 1 |m 4 }.

Fig. 4

 4 Fig.[START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF] Comparison of partition pattern structure (pps) and sequence pattern structure (sps) in the task of finding OP biclusters in matrices with 10 rows and varying number of columns.

  are shown in Figure 4. It is shown that the execution time of partition-based mining of OP biclusters grows faster than sequence-based. Using partition pattern structure, from an m × n numerical matrix, a new m × C n

2

 2

Fig. 6

 6 Fig.[START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] Runtime of sps-based approach with AddIntent and varying , applied to the breast cancer dataset. Any sequence having length less than is discarded.

Table 1

 1

	Examples of (a) constant-value, (b) constant-columns, and (c) order-preserving (OP)
	biclusters
	4 4 4 4	4 2 5 3	1 2 4 3
	4 4 4 4	4 2 5 3	3 5 7 6
	4 4 4 4	4 2 5 3	2 3 8 4
	4 4 4 4	4 2 5 3	4 5 9 8
	(a)	(b)	(c)

Table 2 A formal context

 2

Table 3

 3 A dataset with 4 objects and 5 attributes m 1 m 2 m 3 m 4 m 5

	g 1 1 2 3 1 7
	g 2 1 2 4 2 7
	g 3 2 5 4 5 3
	g 4 2 5 4 5 7

Table 4

 4 A dataset with 5 objects and 5 attributes m 1 m 2 m 3 m 4 m 5

	g 1 1 2 3 4 5
	g 2 4 2 1 5 3
	g 3 2 3 4 1 5
	g 4 5 4 2 3 1
	g 5 2 1 5 4 3

Table 5

 5 Some examples of partitions over Table

Table 6

 6 An example of sequence database

	s Sequence
	s 1 ab |acd
	s 2 a |d |c
	s 3 ac |d |b

Table 7

 7 The columns in the breast cancer dataset in[START_REF] Hedenfalk | Gene-expression profiles in hereditary breast cancer[END_REF].

	Column Type Column Type	Column Type
	c 1	brca1 c 8	brca2	c 15	sporadic
	c 2	brca1 c 9	brca2	c 16	sporadic
	c 3	brca1 c 10	brca2	c 17	brca1
	c 4	brca1 c 11	sporadic c 18	brca2
	c 5	brca1 c 12	sporadic c 19	brca2
	c 6	brca1 c 13	sporadic c 20	brca2
	c 7	brca2 c 14	sporadic c 21	brca2
	Fig. 5 Runtime of pps-based
	approach with AddIntent and
	varying θ in obtaining 10K
	concepts, applied to the breast
	cancer dataset. Any partition
	component having elements
	less than θ is discarded.


Nyoman Juniarta
email: nyoman.juniarta@loria.fr

Miguel Couceiro

Amedeo Napoli

Formal Concept Analysis for Identifying Biclusters with Coherent Sign Changes

In this paper we are studying the task of finding coherent-sign-changes biclusters in a binary matrix. This task can be applied to the interpretation of gene expression data, where such a bicluster represents a set of experiments that affect a set of genes in a consistent way. We start with a binary table and study biclustering methods based on FCA and partition pattern structures. Pattern concepts provide biclusters and their hierarchical relation, which can be used to analyze the profile of genes in the given expression data. Our approach is purely symbolic, so we can detect larger biclusters and work with rather complex data.

Introduction

Gene expression data can be represented as a matrix, where rows and columns represent genes and experiments respectively. Each cell contains the numeric expression level of a given gene under a given experiment. In such data, we can say that an experiment affect a gene by either lowering or raising its expression, according to the gene's normal level. One may be interested in finding a subset of genes and a subset of experiments, such that the experiments affect the genes in a consistent way. In other words, any two experiments in the subset have always either the same effect or the opposite effect on every gene in the subset. This task corresponds to the mining of coherent-sign-changes (CSC) biclusters.

Biclustering is an important technique aimed at discovering patterns in a matrix representing a dataset. It is related to standard clustering whose main objective is to group the rows based on their similarity. On the other hand, biclustering refers to the problem of discovering submatrices whose cells exhibit similar behavior. This problem is also called co-clustering [START_REF] Govaert | Co-clustering[END_REF], where rows and columns are clustered simultaneously.

In this paper, we present a method based on FCA and pattern structures for discovering a specific type of bicluster: coherent-sign-changes bicluster. An existing approach in [START_REF] Tanay | Discovering statistically significant biclusters in gene expression data[END_REF] can mine this bicluster type, but it is statistical, since its discovery of CSC biclusters is based on the magnitude of the expression changes. Our approach is more symbolic, by taking into account only the direction of the changes, with expectation of detecting larger biclusters. Our FCA-based method also gives us the hierarchical structure of all biclusters, allowing an easier interpretation of the results by experts. Furthermore, pattern structures and AddIntent algorithm allows us to define a threshold of bicluster size, so that we can limit the amount of retrieved biclusters. 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 (a)

+ + - + + - --+ --+ (b)
TAB. 1 -Examples of two bicluster types: (a) constant-values and (b) coherent-sign-changes (CSC).

Related Work

The row-column clustering was introduced in [START_REF] Hartigan | Direct clustering of a data matrix[END_REF], and Cheng and Church [START_REF] Cheng | Biclustering of expression data[END_REF] were the firsts to used the term biclustering while working on gene expression data. A bicluster in [START_REF] Cheng | Biclustering of expression data[END_REF] is a subset of genes and a subset of conditions with a high similarity score, statistically measured by calculating variances over all values in the submatrix.

Still in the domain of gene expression data, the algorithm called SAMBA was proposed in [START_REF] Tanay | Discovering statistically significant biclusters in gene expression data[END_REF] to discover a submatrix where the expressions of a subset of genes significantly changes across a subset of conditions. The first model of SAMBA searches a submatrix where there is a joint change across all genes, without looking whether it is an increase or a decrease. The second model takes into account the direction of the change, such that any two conditions in the submatrix have either always the same effect or always the opposite effect. We call this type of submatrix a coherent-sign-changes bicluster, as denoted in [START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF].

Regarding bicluster discovery based on FCA, several methods were proposed. In a binary matrix, dense approximate bicluster discovery was studied in [START_REF] Gnatyshak | Analysing online social network data with biclustering and triclustering[END_REF]; Ignatov et al. (2012a) based on standard FCA. This is similar to mining formal concept, but instead of "exact" concepts, the authors relax the problem such that the "approximate" concepts (having a certain amount of empty cells) can also be detected. For biclustering with similar values in a numerical matrix, [START_REF] Kaytoue | Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis[END_REF] proposed standard FCA with scaling and interval pattern structures. Triadic Concept Analysis was also studied in [START_REF] Kaytoue | Biclustering meets triadic concept analysis[END_REF] to extract this bicluster type. Furthermore, a partition pattern structure was presented in [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF]; [START_REF] Kaytoue | Traitement de données numériques pas analyse formelle de concepts et structures de patrons[END_REF] for mining bicluster with constant columns.

Biclustering

We consider that a dataset is composed of a set of objects G, each of which has values over a set of attributes M . This dataset can be represented as a numerical context (G, M, I) where G is a set of objects, M is a set of attributes, and I corresponds to m(g), which is the value of m ∈ M for object g ∈ G.

One may be interested in finding which subset of objects possesses the same values w.r.t. a subset of attributes. Regarding the matrix representation, this is equivalent to the problem of finding a submatrix that has a constant value over all of its elements (example in Table 1a). This task is called biclustering with constant values, which is a simultaneous clustering of the rows and columns of a matrix.

TAB. 2 -Example. M m 1 m 2 m 3 m 4 g 1 + + - - g 2 + + - - g 3 - - + - g 4 + + + + g 5 - - - -
In coherent-sign-changes (CSC) bicluster, the matrix is binary. In this bicluster, each row is correlated (either entirely identical or entirely opposite) to all other rows. In the example in Table 1c, the first row is identical to the second and opposite to the third and fourth. We can also see this bicluster by comparing the columns. In the example, the first column is identical to the second and opposite to the third.

In a binary dataset (G, M, I), given a set of objects A ⊆ G and an attribute m ∈ M , m(A) is the column submatrix formed by the attribute m over A. The submatrix m j (A) is equal to m k (A), denoted as m j (A) m k (A), if all rows in m j (A) are either entirely identical or entirely opposite to the corresponding rows in m k (A). With the previous notation, given a binary dataset (G, M, I), a pair (A, B) (where

A ⊆ G, B ⊆ M ) is a coherent-sign-changes bicluster if ∀m j , m k ∈ B : m j (A) m k (A).

The Pattern Structures of Signed Partition

In the task of CSC bicluster discovery in a formal context (G, M, I), we propose an approach based on partition pattern structures. Instead of partition of objects in G as described in [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF]; [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF], here we use partition of attributes in M . It is still similar to an object partition since an attribute partition covers every attribute in M and there is no overlapping between any two partition components.

In the original partition pattern structures, a partition is a set of components, where a component is a set of elements. For example, {{a, b, c}, {d, e}} is a partition with two components. The first component has three elements, while the second has two. For CSC biclustering, we define a component as a set of signed elements. This gives us {{a + , b -, c + }, {d -, e + }} as an example of our component. In this work, we define the similarity operator among our components. Based on this similarity, we can obtain a signed partition pattern concept, which eventually gives us CSC biclusters.

The number of concepts can be exponential. Our experiments show that these set of concepts and the computational time can be reduced by introducing parameters. For example, we can choose a threshold that defines a minimum number of columns or rows of the biclusters.


Xin Zhao
email: zhaoxin@hzu.edu.cn

Hongjian Yang

Yuqi Sheng

Yang Jiao

Haijiao Yu

Yao Qin

Guogang Zhao

Application of Principal Component Cluster Analysis in the Quality of Cordyceps Sinensis

Keywords: Cordyceps sinensis, amino acid, principal component analysis, cluster analysis

In this paper, the kinds and contents of amino acids in Cordyceps sinensis from different habitats of Tibet components using principal component analysis and cluster analysis, the principal component cluster analysis to evaluate thenutritional value of different localities, and provide scientific basis for the further research and development and utilization of Cordyceps resources in Tibet area. The principal component analysis method is a method of using the central idea ofdimensionality reduction, the analysis method of multi indicators into amultivariate data several comprehensive index of a few statistics. The principal component analysis method can guarantee the minimizing loss of original data information, with less comprehensive variables instead of multiple variables of the original. Cluster analysis can be used to classify samples of multiple variables by using comprehensive information, the classification results are intuitive, clusteringdendrogram clearly show the results of numerical classification, clustering analysis results than the traditional classification method is more detailed, comprehensive, reasonable.

Introduction

Cordyceps sinensis is Cordycepssinensis Sacc parasitic on the drying complex of stroma of the parasitic bat moth larvae on the insects and larval body [START_REF]Pharmacopoeia of Peoples Republic of China[END_REF] , it is a traditional rare tonic medicine in china, the earliest found in the "Materia Medica from the new", it is the nature of "gamping", have the effect of "protect lung and tonifying kidney, eliminating phlegm, relieving cough". Modern pharmacological research show that the Cordyceps sinensis has to adjust the body's immune [START_REF] Hu Min | The Chemical Constituents And Pharmacological Effects of Cordyceps Sinensis[J][END_REF] , fall hematic fat, fall blood sugar, anti-aging, anti-tumor and many kinds of pharmacological activities [START_REF] Bohua | Research progress of Pharmacological Actions of Cordyceps Sinensis[END_REF][START_REF] Wansheng | Chen peace. The Research Situation of Cordyceps Sinensis [J][END_REF] , the amino acid is material base of Cordyceps sinensis to strong effect and enhance immune function [START_REF] Yanyan | Determination of Amino Acid Content in Different Parts of Cordyceps Sinensis[END_REF] , and it is closely related to the function of the auxiliary treatment of nervous system [START_REF] Sha | The General Situation of The Study on the Chemical Constituents of Cordyceps Sinensis [J][END_REF] , digestive system disease and antibacteria. Zhang Shishan [START_REF] Zhang Shishan | Analysis of Amino Acid in Cordyceps Sinensis Pharmacology [J][END_REF] research showed that some amino acids inCordyceps sinensis has sedative effects. The amino acid of Cordyceps sinensisnot only has a wide range of pharmacological effects and important nutrients, so the amino acid research has positive significance. China's Tibet the main producing areas of Cordyceps sinensis, at present, for Tibet within the jurisdiction of different habitats component analysis of amino acid in Cordyceps sinensis has not been reported. Therefore, this paper intends to analysis and evaluation of nutritional value of amino acids in Cordyceps sinensis from different regions of Tibet, in order for further research and development by China's Tibet Cordyceps sinensis resources to provide a scientific basis.

Experiments and Methods

Experimental Samples

The origin of Tibet Cordyceps sinensis contains 17 kinds of amino acids, 7 kinds of essential amino acids, 4 kinds of delicious amino acids, 9 medicinal amino acids. The range of total amino acids between the 23.4%~24.52%, essential amino acids accounted for total amino acids between the 26.47%~27.52%, fresh flavor amino acids accounted for total amino acids between the 35.12%~37.44% and drug effective amino acids accounted for total amino acids in the range between the 55.03%~57.54% In this paper, we use the data of Yan Dong and Yang Xinyu [13] , The method is improved by using Principal component cluster analysis.

Principal component cluster analysis

In the principal component analysis method, when the variance contribution of the first principal component was higher (above), we can think the principal component can reflect the information with the original variables provide information almost, this is the time to sort and evaluation according to the scores of the first principal component.

(1) Erroneous zone of comprehensive score of principal component.

In many cases, the variance contribution rate of the first principalcomponent is not high enough, need to consider a number of main components , , … , , in order to sort the sample, commonly used method is based on the variance of each principal component contribution rate for the weight, the comprehensive score of the principal component is: H … , and according to the formula to calculate the main component of the sample and sort them.

The comprehensive score calculation looks very reasonable and it seems to increase the information content, that is, to increase the variance contribution rate, in fact, it is just an illusion, through to calculate the variance of H we can found that it is possible to completely opposite conclusions.

Var H Var   1
From this process we find that the variance of the composite score is smaller than the variance of the first principal component, which indicates that the information content of the comprehensive principal component score is less than that of the first principal component.

(2) principal component clustering The scheduling problem in multi index system evaluation, If the variance contribution rate of the first principal component is not large enough, that is, the first principal component expression of the original data is not large enough, only by the first principal component score on the evaluation of the sample will be one-sided, At this time, the principal component analysis and cluster analysis can be used to combine, and use the Principal component cluster analysis. Clustering analysis is a method of samples or variables are classified according to the intimacy of their nature, although the cluster analysis can be a good classification of multiple indicators of the data, but it can't get the evaluation result of each good or bad degree.

The idea of principal component clustering is take the principal component analysis firstly, then several principal components of the sample clustering analysis, combined with the first principal component score ranking to classify the samples. A new comprehensive evaluation method is obtained, specific practices are as follows:

, 1,2, … , . 2 Carry on the system clustering on the selected new datamatrix( , , … , ).Then calculate the mean score of all kinds of samples to determine the sort of class; Finally, according to the first principal component score of the sample, the order of all kinds of samples was determined, and the comprehensive evaluation was obtained. Through MATLAB to carry on the cluster analysis for 5 kinds of Cordyceps sinensis, Figure 1 Results that 1, 2, 4, 5 are clustered into a large class, 3 together for a class, The quality difference of amino acid of 1,2,4,5 was small, and the difference between the 3 and 1,2,4,5 amino acid was very large.

Results and Discussion

The data is processed by the method of cluster analysis

Carry on Principal Component Clustering:

Carry on principal component analysis about, We work out a linear combination of each of the principal components represented by each variable.

Fig. 1 .

 1 Fig. 1. Data processing results

Table 1 .

 1 The score of amino acid content of Cordyceps sinensis This shows that amino acids quality of Cordyceps sinensis in Linzhi have the large difference with Naqu Cordyceps, changdu Cordyceps, Shannan Cordyceps, Shigatse Cordyceps. Among the 17 kinds of amino acids, seven of them are essential amino acids, and ten of them are nonessential amino acids, from linear combination by principal component analysis we can draw five kinds of amino acid content of Cordyceps sinensis accounted for the proportion of all, essential amino acids of changdu Cordyceps is highest in five of the origin of Cordyceps sinensis, in umami amino acids, five of the origin of Cordyceps sinensis umami amino acid content was higher, Shannan Cordyceps umami amino acid content highest, which determines the delicious taste of Cordyceps sinensis, in drug effective amino acid, Cordyceps medicinal amino acids is very rich, containing 9 kinds of drug effective amino acids, in five of the origin of Cordyceps medicinal amino acids accounted for total 55.03%~57.54%, Shannan Cordyceps medicinal amino acids content of the highest, it is aweto nourishing and strengthening the immune by providing the material basis.

	0.193	0.352	0.315		0.0961	0.3485	⋯ 0.3438		0.1667	3
	0.0092	0.0575	0.0974	0.2436	0.0305	⋯ 0.0705		0.3337	4
	0.4808	0.0853	0.2361	0.4658	0.0543	⋯ 0.0562	0.0051	5
		Principal	component	Principal	component	Principal	component
		score one			score two		score three
	Naqu Cordyceps		-4.592403298	2.582416524		-1.953775208
	changdu Cordyceps		-4.326408906	2.528693027		-1.797035154
	Linzhi Cordyceps		-4.855238038	2.373217091		-1.584953726
	Shannan Cordyceps		-4.584720453	2.587483542		-2.066390962
	Shigatse Cordyceps		-4.470809315	2.374504833		-1.810989538
	4 Conclusions
	By the clustering analysis method of 5 kinds of Cordyceps amino acid quality
	clustering results and found Linzhi Cordyceps contained amino acid quality with
	respect to the Nagqu Cordyceps, Changdu Cordyceps, Shannan Cordyceps, Shigatse
	Cordyceps higher.